Високопродуктивні матричні та потокові перемножувачі цифрових даних

Запропоновані алгоритми та структури високопродуктивних матрично-потокових перемножувачів багаторозрядних двійкових чисел, в яких застосовні компоненти з мінімаксними характеристиками часової, апаратної та структурної складності. Розроблений алгоритм матричного виконання операцій множення згідно стр...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2019
Hauptverfasser:	Николайчук, Я.М., Возна, Н.Я., Грига, В.М., Круліковський, Б.Б., Давлетова, А.Я.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2019
Schriftenreihe:	Математичне та комп'ютерне моделювання. Серія: Технічні науки
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/168578
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Високопродуктивні матричні та потокові перемножувачі цифрових даних / Я.М. Николайчук, Н.Я. Возна, В.М. Грига, Б.Б. Круліковський, А.Я. Давлетова // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 19. — С. 101-107. — Бібліогр.: 5 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-168578
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1685782025-02-09T20:31:04Z Високопродуктивні матричні та потокові перемножувачі цифрових даних High-performance matrix and stream multipliers of digital data Николайчук, Я.М. Возна, Н.Я. Грига, В.М. Круліковський, Б.Б. Давлетова, А.Я. Запропоновані алгоритми та структури високопродуктивних матрично-потокових перемножувачів багаторозрядних двійкових чисел, в яких застосовні компоненти з мінімаксними характеристиками часової, апаратної та структурної складності. Розроблений алгоритм матричного виконання операцій множення згідно структури перемножувача Брауна, який реалізує виконання операції додавання в однорозрядному повному двійковому суматорі та формування переносів за мінімально досяжний інтервал часу — один мікротакт. Розроблений алгоритм та структура потокового матричного перемножувача з високим рівнем розпаралелення обчислювальних операцій, в якому процеси завантаження кодів перемножуваних двійкових чисел відбуваються паралельно з процесами матричного перемноження та зчитування результатів множення у попередньому циклі. The algorithms and structures of high-performance matrix-stream multipliers of multi-bit binary numbers are proposed, in which components are used with minimal characteristics of time, hardware and structural complexity. The algorithm of matrix execution of multiplication operations according to the structure of the Brown multiplier is developed, which implements the addition operation in a one-bit full binary adder and the formation of transfers at a min-imum reachable time interval — one micro-cycle. The algorithm and structure of the current matrix switch with a high level of deployment of computational operations are developed, in the process of loading codes of transitive binary numbers occurs in parallel with procedural matrix recount and coincidence of results. Compared to known structures, stream multipliers can significantly reduce the number of in/out of microelectronic crystals that implement operations for multiplying multi-bit binary numbers. 2019 Article Високопродуктивні матричні та потокові перемножувачі цифрових даних / Я.М. Николайчук, Н.Я. Возна, В.М. Грига, Б.Б. Круліковський, А.Я. Давлетова // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 19. — С. 101-107. — Бібліогр.: 5 назв. — укр. 2308-5916 DOI: 10.32626/2308-5916.2019-19.101-107 https://nasplib.isofts.kiev.ua/handle/123456789/168578 681.32 uk Математичне та комп'ютерне моделювання. Серія: Технічні науки application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
description	Запропоновані алгоритми та структури високопродуктивних матрично-потокових перемножувачів багаторозрядних двійкових чисел, в яких застосовні компоненти з мінімаксними характеристиками часової, апаратної та структурної складності. Розроблений алгоритм матричного виконання операцій множення згідно структури перемножувача Брауна, який реалізує виконання операції додавання в однорозрядному повному двійковому суматорі та формування переносів за мінімально досяжний інтервал часу — один мікротакт. Розроблений алгоритм та структура потокового матричного перемножувача з високим рівнем розпаралелення обчислювальних операцій, в якому процеси завантаження кодів перемножуваних двійкових чисел відбуваються паралельно з процесами матричного перемноження та зчитування результатів множення у попередньому циклі.
format	Article
author	Николайчук, Я.М. Возна, Н.Я. Грига, В.М. Круліковський, Б.Б. Давлетова, А.Я.
spellingShingle	Николайчук, Я.М. Возна, Н.Я. Грига, В.М. Круліковський, Б.Б. Давлетова, А.Я. Високопродуктивні матричні та потокові перемножувачі цифрових даних Математичне та комп'ютерне моделювання. Серія: Технічні науки
author_facet	Николайчук, Я.М. Возна, Н.Я. Грига, В.М. Круліковський, Б.Б. Давлетова, А.Я.
author_sort	Николайчук, Я.М.
title	Високопродуктивні матричні та потокові перемножувачі цифрових даних
title_short	Високопродуктивні матричні та потокові перемножувачі цифрових даних
title_full	Високопродуктивні матричні та потокові перемножувачі цифрових даних
title_fullStr	Високопродуктивні матричні та потокові перемножувачі цифрових даних
title_full_unstemmed	Високопродуктивні матричні та потокові перемножувачі цифрових даних
title_sort	високопродуктивні матричні та потокові перемножувачі цифрових даних
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2019
url	https://nasplib.isofts.kiev.ua/handle/123456789/168578
citation_txt	Високопродуктивні матричні та потокові перемножувачі цифрових даних / Я.М. Николайчук, Н.Я. Возна, В.М. Грига, Б.Б. Круліковський, А.Я. Давлетова // Математичне та комп'ютерне моделювання. Серія: Технічні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2019. — Вип. 19. — С. 101-107. — Бібліогр.: 5 назв. — укр.
series	Математичне та комп'ютерне моделювання. Серія: Технічні науки
work_keys_str_mv	AT nikolaičukâm visokoproduktivnímatričnítapotokovíperemnožuvačícifrovihdanih AT voznanâ visokoproduktivnímatričnítapotokovíperemnožuvačícifrovihdanih AT grigavm visokoproduktivnímatričnítapotokovíperemnožuvačícifrovihdanih AT krulíkovsʹkiibb visokoproduktivnímatričnítapotokovíperemnožuvačícifrovihdanih AT davletovaaâ visokoproduktivnímatričnítapotokovíperemnožuvačícifrovihdanih AT nikolaičukâm highperformancematrixandstreammultipliersofdigitaldata AT voznanâ highperformancematrixandstreammultipliersofdigitaldata AT grigavm highperformancematrixandstreammultipliersofdigitaldata AT krulíkovsʹkiibb highperformancematrixandstreammultipliersofdigitaldata AT davletovaaâ highperformancematrixandstreammultipliersofdigitaldata
first_indexed	2025-11-30T13:04:41Z
last_indexed	2025-11-30T13:04:41Z
_version_	1850220622794194944
fulltext	Серія: Технічні науки. Випуск 19 101 УДК 681.32 DOI: 10.32626/2308-5916.2019-19.101-107 Я. М. Николайчук, д-р техн. наук, Н. Я. Возна, канд. техн. наук, В. М. Грига, канд. техн. наук, Б. Б. Круліковський, канд. техн. наук, А. Я. Давлетова, асистент Тернопільський національний економічний університет м. Тернопіль, Прикарпатський національний університет імені В. Стефаника м. Івано-Франківськ, **Національний університет водного господарства та природокористування м. Рівне ВИСОКОПРОДУКТИВНІ МАТРИЧНІ ТА ПОТОКОВІ ПЕРЕМНОЖУВАЧІ ЦИФРОВИХ ДАНИХ Запропоновані алгоритми та структури високопродуктив- них матрично-потокових перемножувачів багаторозрядних двійкових чисел, в яких застосовні компоненти з мінімаксни- ми характеристиками часової, апаратної та структурної склад- ності. Розроблений алгоритм матричного виконання операцій множення згідно структури перемножувача Брауна, який реа- лізує виконання операції додавання в однорозрядному повно- му двійковому суматорі та формування переносів за мінімаль- но досяжний інтервал часу — один мікротакт. Розроблений алгоритм та структура потокового матричного перемножувача з високим рівнем розпаралелення обчислювальних операцій, в якому процеси завантаження кодів перемножуваних двійкових чисел відбуваються паралельно з процесами матричного пере- множення та зчитування результатів множення у попередньо- му циклі. У порівнянні з відомими структурами потокові пе- ремножувачі дозволяють суттєво зменшити число вхо- дів/виходів мікроелектронних кристалів, які реалізують опе- рації перемноження багаторозрядних двійкових чисел. Ключові слова: матрично-потокові перемножувачі, пара- фазна структура Брауна, максимальна швидкодія, розпарале- лення обчислювальних операцій. Вступ. Перемножувачі двійкових чисел є важливими компонента- ми арифметико-логічних пристроїв універсальних та спеціалізованих процесорів. При значній розрядності множників 32-512 біт такі пере- множувачі застосовуються в універсальних комп’ютерах як швидкодію- чі співпроцесори [1–4]. У сучасній обчислювальній техніці найширше © Я. М. Николайчук, Н. Я. Возна, В. М. Грига, Б. Б. Круліковський, А. Я. Давлетова, 2019 Математичне та комп’ютерне моделювання 102 застосування отримали матричні перемножувачі з паралельним вводом та виводом даних, що суттєво знижує ефективність їх використання як потокові перемножувачі, які є базовими компонентами мультиядерних та систолічних процесорів [2]. Особливо негативно цей недолік проявля- ється при опрацюванні багаторозрядних двійкових кодів (1024÷4096 біт) процесорами шифрування даних [4]. Крім того є практично недоцільним реалізація чіпів перемножувачів з вказаним числом виводів. Перспекти- вним напрямком вирішення цієї проблеми є створення потокових пере- множувачів з високим рівнем розпаралелення обчислювальних операцій та біт-орієнтованою організацією вводу та виводу даних. Дослідження структури та системних характеристик матри- чних перемножувачів. В матричних перемножувачах сумування здійснюється матрицею суматорів, які складаються із послідовних рядків однорозрядних суматорів із збереженням переносу. Найбільш відомими матричними перемножувачами є перемножувач Брауна з горизонтальним та вертикальним розповсюдженням переносу [1–3]. Перемножувачі, які побудовані за алгоритмами Бо-Вулі та Пезариса [1] для множення двійкових чисел в доповнюючих кодах та інші. На рис. 1 показано матричний перемножувач для 4-ох розрядних двійкових чисел, в якому кожному стовпцю у матриці множення від- повідає діагональ перемножувача. Схема відома, як перемножувач Брауна [1] або перемножувач з горизонтальним розповсюдженням переносу. Біти часткових добутків виду ( i ja b ) формуються за допо- могою елементів «І». Для сумування часткових добутків застосову- ються два види однорозрядних суматорів із збереженням переносу: напівсуматори (НС) і повні суматори (СМ). Рис. 1. Структура матричного перемножувача Брауна 4х4 з горизонтальним розповсюдженням переносу Матричний перемножувач Брауна ( n n ) складається з 2 n опе- рацій логічного добутку та ( 2 n n ) — операцій однорозрядного Серія: Технічні науки. Випуск 19 103 двійкового сумування. Для повного двійкового сумування потрібно ( 2 2n n ) операцій, а для не повного сумування n операцій, де n — розрядність вхідних даних. Для реалізації напівсуматора, який виконує операцію не повного двійкового сумування потрібно 5 логічних елементів (рис. 2, а) а для повного суматора, який виконує операцію повного двійкового суму- вання потрібно 11 логічних елементів (рис. 2, б). Час розповсюдження вихідного переносу неповного суматора складає 1 мікротакт а повного 5 мікротактів, а час формування суми складає 3 мікротакти для неповного суматора і 6 мікротактів для пов- ного суматора. Рис. 2. Внутрішня структура однорозрядного суматора: а — неповного; б — повного на елементах виключне АБО Матричний перемножувач Брауна характеризується наступними системними характеристиками:  швидкодія структури перемножувача визначається найбільш дов- гим маршрутом розповсюдження сигналу, що складає (3 4)n  од- норозрядних суматора, і розраховується згідно виразу 2МП НС   (3 6) ПСn   , де НС , ПС — відповідно часова складність (затримка сигналів) у структурі однофазного неповно- го та повного однорозрядного двійкового суматора;  апаратна складність перемножувача визначається сумарною кіль- кістю логічних елементів та вентилів у його структурі і розрахову- ється згідно виразу: 2 ( 2 )МП НС ПСA n A n n A     , де НСA , ПС A — відповідно апаратна складність повного та неповного одорозрядного двійкового суматора;  структурна складність перемножувача визначається зваженою сумою структурної складності його компонентів згідно виразу: Математичне та комп’ютерне моделювання 104 1 m МП i i i S S   , де i — онтологічна оцінка структурної складнос- ті iS -го компонента, m — кількість структурно-класифікованих компонентів [5]. Оцінка часової складності матричного перемножувача (рис. 1) роз- раховується з урахуванням горизонтальних затримок сигналів наскріз- них переносів та вертикальних затримок сигналів при формуванні бітів суми. Тобто системні характеристики часової складності відомих одно- розрядних двійкових суматорів (рис. 2) з горизонтальними (+) і вертика- льними ( S ) інформаційними зв’язками відповідно складають: 2 (3 6) 2 3 (3 4 6) 6 6 (12 6) 6 42 . МП НС ПСn                    Оцінка апаратної складності матричного перемножувача (рис. 1) розраховується з урахуванням кількості логічних елементів, які міс- тять однорозрядні двійкові суматори (рис. 2) і становить: 2 2 ( 2 ) 4 5 (4 2 4) 11 20 (16 8) 11 108( ). МП НС ПСA n A n n A вентилів                  Оцінка структурної складності матричного перемножувача (рис. 1) становить 1026МПS  одиниць. Недоліком матричного перемножувача Брауна є обмежені фун- кціональні можливості та низька швидкодія, яка обумовлена тим, що базовий компонент матриці однорозрядних суматорів не містить парафазних входів та виходів, що потребує не менше 2 3 мікрота- кти часової затримки сигналів переносів і не дозволяє, у принципі, реалізувати відповідні вертикальні та горизонтальні переноси між виходами та входами однорозрядних суматорів з часовою затрим- кою 1 мікротакт. Запропонована структура потокового матричного перемножува- ча багаторозрядних двійкових чисел на основі парафазних однороз- рядних суматорів, яка показана на рис. 3. В даній структурі потокового матричного перемножувача додат- ково введено матрицю однорозрядних повних суматорів з парафаз- ними входами та виходами, що дозволило реалізувати інформаційні переноси між суматорами з гранично мінімальною затримкою сигна- лів на 1 мікротакт, а крім того підвищити регулярність структури матриці суматорів, що спрощує проектування та нарощення розряд- ності утилітів таких багаторозрядних пристроїв на реконфігурованих програмних кристалах ПЛІС. Серія: Технічні науки. Випуск 19 105 Рис. 3. Структура потокового матричного перемножувача на основі однорозрядних суматорів з парафазними входами і виходами Розробка структури та компонентів потокового перемножу- вача багаторозрядних двійкових чисел. На рис. 4 подано структуру потокового перемножувача двійкових чисел. Перемножувач містить: вхідний регістр зсуву (R1), регістри пам’яті (R2, R3), матрицю одно розрядних двійкових суматорів (МС), вихідний регістр пам’яті та зсуву (R4), та логічний елемент “Виключаюче АБО” (ЛЕ). Рис. 4. Структура потокового перемножувача двійкових чисел На даному рисунку: вхід 2 — біт-орієнтований ввід кодів множни- ків x, y; вхід 3 — тактова синхронізація зсувів R1 та R4; вхід 4 — запис даних у регістри R2-R4; вхід 5 — біт-орієнтований вхід тестового коду; вихід 6 — вихід біт-орієнтованого двійкового коду добутку x на y. В потоковому перемножувачі регістр R1 виконує операцію перет- ворення n-розрядних біт-орієнтованих кодів множників x та y у пара- лельний пара фазний 2n-розрядний двійковий код. Часова складність Ттгр = 2 мікротакти, тобто занесення кодів (x, y) в регістр R1 здійсню- Математичне та комп’ютерне моделювання 106 ється за 4n мікротактів. Регістр R2 призначений для зберігання кодів множників на часовий інтервал занесення вхідних кодів (x, y) у регістр зсуву R1. Матриця однорозрядних повних парафазних суматорів МС виконує операцію перемноження кодів (x, y) на виході якої формується 2n-розрядний вихідний код добутку на інтервалі часу k x 2n, де k — затримка сигналів формування наскрізних переносів та суми на вихо- дах суматорів. Регістр R3 зберігає код добутку до кінця інтервалу зчи- тування прямих кодів добутків до завершення біт-орієнтованого зчиту- вання добутків на виході перемножувача. Логічний елемент виключа- юче АБО призначений для реалізації операції тестування безпомилко- вості роботи перемножувача. З метою контролю надійності роботи перемножувача на початку певного числа циклів здійснюється тесту- вання правильності його роботи шляхом порівняння добутку заданих перемножувачів (x, y) з тестовим кодом добутку, який поступає на вхід 5 перемножувача. При цьому на виході 6 логічного елемента виклю- чаюче АБО формується 2n — розрядний потік нулів, яка свідчить про безпомилковість виконання операції множення. На початку кожного циклу перемноження сигналом входу 4 здійснюється запис пара фаз- них кодів регістра R1 у регістр R2 та прямих кодів добутків регістра R3 у регістр R4. У наступному циклі роботи перемножувача сигналами синхронізації Sx входу 3 тактується занесення біт-орієнтованих кодів множників x та y в регістр R1. Одночасно цими сигналами тактується зчитування біт-орієнтованих кодів добутків на виході 6 пристрою. Од- ночасно з виконанням операцій вводу та виводу даних у матричній структурі суматорів МС здійснюється перемноження двійкових кодів x та y за 1 мікротакт. Регістри зсуву побудовані на основі D-тригерів. Висновки. Виконано аналіз структурних схем матричних пере- множувачів Брауна, потоково матричних та потокових перемножува- чів, досліджені системні характеристики часової, апаратної та струк- турної складності матричного перемножувача Брауна з горизонталь- ним розповсюдженням переносів на основі однорозрядних неповних та повних суматорів з однофазними входами та виходами. Відмічена принципова неможливість підвищення граничної швидкодії такого класу перемножувачів при застосуванні в матриці перемножувача однофазних суматорів. Відомі перемножувачі характеризуються та- кож низькою потоковою швидкодією оскільки введення поточних ко- дів перемножувачів здійснюється тільки після завершення попередньо- го циклу перемноження. Запропонована нова структура потокового перемножувача з високим рівнем розпаралелення операцій шляхом паралельного вводу, зчитування та перемноження цифрових даних. При цьому суттєво зростає інформаційна активність компонентів пе- ремножувача на 1–2 порядки у порівнянні з відомими структурами. Серія: Технічні науки. Випуск 19 107 Список використаних джерел: 1. Цилькер Б. Я., Орлов С. А. Организация ЭВМ и систем : учебник для вузов. Питер, 2006. 668 с. 2. Мельник А. О. Архітектура комп’ютера. Луцьк : Волинська обласна дру- карня, 2008. 470 с. 3. Самофалов К. Г., Романкевич А. М., Валуйский В. Н., Каневский Ю. С., Пиневич М. М. Прикладная теория цифровых автоматов. Киев : Вища шк. Головное изд-во, 1987. 375 с. 4. Valeriy Zadiraka, Yaroslav Nykolaichuk. Methods of effective protection of information flows. Ternopil : Terno-graf, 2014. 308 p. 5. Николайчук Я. М., Возна Н. Я., Пітух І. Р. Проектування спеціалізованих комп’ютерних систем : навчальний посібник. Тернопіль : ТзОВ «Терно- граф», 2010. 302 c. HIGH-PERFORMANCE MATRIX AND STREAM MULTIPLIERS OF DIGITAL DATA The algorithms and structures of high-performance matrix-stream multipli- ers of multi-bit binary numbers are proposed, in which components are used with minimal characteristics of time, hardware and structural complexity. The algorithm of matrix execution of multiplication operations according to the structure of the Brown multiplier is developed, which implements the addition operation in a one-bit full binary adder and the formation of transfers at a min- imum reachable time interval — one micro-cycle. The algorithm and structure of the current matrix switch with a high level of deployment of computational operations are developed, in the process of loading codes of transitive binary numbers occurs in parallel with procedural matrix recount and coincidence of results. Compared to known structures, stream multipliers can significantly re- duce the number of in/out of microelectronic crystals that implement operations for multiplying multi-bit binary numbers. Key words: matrix-flow multipliers, paraphase structure of Brown, maximum performance, parallelization of computational operations. Одержано 31.01.2019

Високопродуктивні матричні та потокові перемножувачі цифрових даних

Institution

Ähnliche Einträge