Метод синтезу пристроїв паралельно-потокового обчислення скалярного добутку у реальному часі

Abstract

Розроблено граф-схему узагальненого алгоритму паралельно-потокового обчислення скалярного добутку, особливістю якої є використання однотипних операцій формування часткових добутків, починаючи з молодших розрядів множників, обчислення макрочасткового добутку та його додавання до часткового результату, зсунутого вправо на кількість розрядів, використаних під час формування часткових добутків. Запропоновано розроблення ПКВМ-структур пристроїв паралельно-потокового обчислення скалярного добутку виконувати за такими принципами: використання однотипних сходинок конвеєра; виконання обчислень на основі операцій додавання, інверсії та зсуву; здійснення обчислення скалярного добутку як єдиної операції; регулярності та локалізації зв’язків між сходинками конвеєра; узгодження тривалості конвеєрного такту із часом введення даних і часом виведення результатів обчислень; просторово-часового розпаралелювання процесу обчислення скалярного добутку. Розроблено алгоритм і структуру паралельно-потокового пристрою обчислення скалярного добутку з прямим формуванням часткових добутків на основі аналізу одного розряду множників, яка забезпечує роботу із найменшим конвеєрним тактом. Розроблено алгоритм і структуру паралельно-потокового пристрою обчислення скалярного добутку із формуванням часткових добутків для суми двох пар добутків з аналізом одного розряду множників, яку доцільно використовувати для невеликої кількості операндів. Розроблено алгоритм і структуру паралельно-потокового пристрою обчислення скалярного добутку із формуванням часткових добутків за модифікованим алгоритмом Бута, яка забезпечує зменшення витрат обладнання під час опрацювання операндів розрядністю n≥24. Розроблено алгоритм і структуру пристрою обчислення скалярного добутку з формуванням групових часткових добутків, яка забезпечує найменші витрати обладнання, якщо n=8, для N>8. Розроблено метод синтезу ПКВМ- пристроїв паралельно-потокового обчислення скалярного добутку в реальному часі, який за рахунок вибору алгоритму формування часткових добутків, структури пристрою із переліку розроблених і узгодження такту роботи конвеєра вибраної структури із часом надходження вхідних даних забезпечує високу ефективність використання обладнання.

A graph scheme of a generalized algorithm for parallel stream calculation of the scalar product was developed. The proposed algorithm uses the same type of operations for forming a partial product that is calculated starting from the lowest digits of the multipliers. The developed algorithm of parallel stream calculation of the scalar product is performed with the use of operations for forming partial products, calculating the macro-partial product, and adding it to the partial result shifted to the right by the number of digits that were used in the formation of partial products. It is suggested that the development of FPGA structures of devices for parallel stream calculation of the scalar product be carried out according to the following principles: use of the same type of conveyor steps; performing calculations based on addition, inversion, and shift operations; performing the calculation of the scalar product as a single operation; regularity and localization of connections between conveyor steps; coordination of the duration of the conveyor time with the time of data input and the time of output of calculation results; space-time parallelization of the process of calculating the scalar product. The algorithm and structure of the parallel stream device for calculating the scalar product with direct formation of partial products based on the analysis of one order of multipliers, which ensures operation with the smallest conveyor cycle, has been developed. The algorithm and structure of the parallel stream device for calculating the scalar product with the formation of partial products for the sum of two pairs of products with the analysis of one order of multipliers, which is advisable to use for a small number of operands, have been developed. The algorithm and structure of a parallel stream device for calculating the scalar product with the formation of partial products according to the modified Booth algorithm have been developed, which ensures a reduction in equipment costs when processing operands with n≥24 bits. The algorithm and structure of the device for calculating the scalar product with the formation of group partial products have been developed, which provides the lowest equipment costs in the case of n=8 for N>8. A method for the synthesis of FPGA devices for parallel stream calculation of the scalar product in real-time has been developed. The proposed method ensures high efficiency of the use of the equipment due to the selection of the algorithm for the formation of partial products and the structure of the device from the list of developed ones and the coordination of the cycle of the conveyor of the selected structure with the time of arrival of input data.