Модель и аппаратно-ориентированный алгоритм вычислительного устройства для обработки бинарных матриц

Во введении обоснована актуальность работы, сформулированы цель и
задачи исследований, научная новизна и положения, выносимые на защиту,
практическая ценность результатов диссертационного исследования.
В первом разделе проведен анализ задач, методов, алгоритмов и их
практических реализаций устройств обработки бинарных матриц, позволяющих
выполнять определение состава бинарных отношений.
В связи с тем, что задача разбиения алгоритмов управления относится к
классу NP–сложных и не допускает получение оптимального решения за
приемлемое время для управляющих алгоритмов реальной сложности, на
практике для ее решения применяются эвристические методы (методы
ограниченного перебора, жадные методы, методы случайного перебора, метод
взвешенного случайного перебора, метод муравьиной колонии, генетические
алгоритмы, метод пчелиной колонии, метод капель воды, роевые методы, метод
параллельно-последовательной декомпозиции). Они требуют в процессе работы
информации о бинарных отношениях вершин параллельной граф-схемы
алгоритма управления, для которых производится поиск разбиений, с целью
организации проверки на отсутствие параллельных вершин в составе
формируемых блоков разбиения. При разработке программных реализаций
алгоритмов поиска разбиений существенную часть вычислительного времени
при определении состава отношений занимают матричные операции, что делает
актуальной задачу снижения затрат вычислительного времени путем
разработки специализированных устройств обработки бинарных матриц.
В настоящее время существует большое количество важных
практических задач, включающих в своем составе выполнение операции
умножения матриц. Задача умножения бинарных матриц имеет ряд
особенностей, к которым относятся однородность расположения исходных
данных и идентичность алгоритмов их обработки, позволяющие разработку
большого количества параллельных программных или аппаратных реализаций.
При программной реализации одним из главных недостатков классических
методов умножения является низкая эффективность использования подсистемы
памяти используемой вычислительной системы (например, связки CPU – RAM
или GPU – графическая память), что приводит к увеличению времени
обработки и снижению реальной производительности вычислительной
системы. С целью снижения влияния указанного недостатка возможен ряд
оптимизаций, выполняющихся программно на алгоритмическом уровне и
позволяющих повысить эффективность использования кэш-памяти CPU
(снизить число промахов кэша) или разделяемой памяти GPU и, как следствие,
реальную производительность используемой вычислительной системы. Другим
направлением для снижения времени выполнения матричного умножения
является использование специализированных вычислительных структур в виде
устройств в заказном исполнении или на базе ПЛИС. Большинство известных
устройств основаны на систолических вычислительных структурах, могут
выполнять умножение за линейное время, однако они характеризуются
большой аппаратной сложностью, что не позволяет их практическую
реализацию на современном уровне развития полупроводниковых цифровых
схем для матриц большой размерности.
Существующие способы реализации матричных операций на аппаратном
уровне, способные снизить время обработки, могут быть разделены на три
основных направления.
1.Схемы на оптических элементах, которые по ряду причин не
получили широкого распространения и в настоящее время практически не
применяются.
2.Устройства умножения матриц, имеющие вероятностные свойства и
присущую им статистическую погрешность, в настоящее время на практике не
используются.
3.Устройства, в основу работы которых положен принцип
параллельной, иногда в сочетании с конвейерной, матричной и/или
систолической обработкой данных (в том числе на базе систолических
структур). Они характеризуется существенным выигрышем во времени
выполнения операции, в некоторых случаях позволяя выполнение умножения
матриц за линейное время, однако данным устройствам необходима
специализированная многопортовая память, которая должна обеспечить
достаточный темп поступления исходных данных, иначе быстродействие
устройства будет лимитировано именно им, а не скоростью работы
операционной части.
Кроме рассмотренных выше аппаратных реализаций известны алгоритмы
умножения матриц Штрассена, Штрассена-Винограда, Копперсмита-
Винограда, отличительной особенность которых является более низкая
временная асимптотика. Однако практический выигрыш от их использования
наблюдается на матрицах значительно большего размера (миллионы
элементов).
На основании вышеизложенного сделан вывод о необходимости
разработки устройств обработки бинарных матриц, в основу работы которых
положен принцип параллельной, в некоторых случаях в сочетании с
конвейерной, матричной и/или систолической обработкой данных, что
позволяет снизить их аппаратную сложность и расширить сферу практического
применения.
Во втором разделе приведена модифицированная математическая
модель бинарных отношений и аппаратно-ориентированный алгоритм
умножения бинарных матриц. Для этой цели введены основные понятия и
свойства бинарных отношений вершин граф-схем параллельных алгоритмов.
Бинарные отношения обладают такими свойствами как
транзитивность ( “x, y, z Î S : xRy, yRz  xRz );
рефлексивность ( “x Î S : xRx );
симметричность ( “x, y Î S : xRy  yRx ).
С учетом рассмотренных выше свойств бинарных отношений на
множестве вершин граф-схемы алгоритма используются следующие бинарные
отношения:
 следования (n ) – обладает свойствами антирефлексивности,
несимметричности и транзитивности;
 связи (j ) – обладает свойствами рефлексивности, симметричности и
не обладает свойством транзитивности;
 параллельности (w) – обладает свойствами рефлексивности,
симметричности и нетранзитивности;
 альтернативы (y ) – обладает свойствами антирефлексивности,
симметричности и нетранзитивности.
Аналогичными отношениям следования и связи, которые определены для
граф-схем параллельных алгоритмов, являются бинарные отношения
контрдостижимости, достижимости и связности вершин графов общего вида.
В первую очередь выполняется определение отношения следования. Для
этого производится его транзитивное замыкание, отталкиваясь от начальных
значений, получаемых исходя из рассмотрения всех дуг передачи управления
между вершинами в составе граф-схемы:
( ai n a j )  (a j na k )  ( ai n a k ) , (1)
где ai , aj , ak – вершины граф-схемы параллельных алгоритмов.
Для хранения бинарного отношения следования применяется матрица
отношений M Rn = (mijn ) , i, j =1, N , N – число вершин в граф-схеме алгоритма. В
исходной матрице необходимо найти такие i, j и k, что истинно выражение
( ai n a j )  ( a j n a k )   ( a i n a k ) ,(2)
или, что то же самое:
(mijn = 1)  (m njk = 1)  (mikn = 0)(3)
n
и положить mikn := 1 , где mik – значение бинарного отношения в составе
n
соответствующей матрицы отношений M R , повторяя указанное действие до
тех пор, пока возможно нахождение элементов, удовлетворяющих (2).
При практической реализации указанного действия существует два
подхода. Первый базируется на алгоритме Флойда-Уоршала, позволяющим
выполнить транзитивное замыкание отношения за один проход ввиду
использования особого порядка рассмотрения элементов матриц, что
ограничивает возможность его распараллеливания. Второй основан на
возведении матрицы в степень.
Данная операция реализуется двумя способами. Первый из них
выполняется путем умножения исходной матрицы бинарного отношения самой
на себя:
M Rn ¢ = M Rn ´ M Rn ´…´ M Rn .(4)
Число матричных умножений в формуле (4) определяется исходными
данными и ограничено сверху значением N, т.е. в худшем случае искомое
транзитивное замыкание будет найдено путем возведения матрицы в N-ю
степень. На практике, умножения прерывается начиная с момента, когда после
выполнения очередного умножения матрица не изменится.
Второй способ основан на возведении матрицы в квадрат по следующей
схеме:
M 2n = M Rn ´ M Rn ,
M 4n = M 2n ´ M 2n ,
(5)
M 8n = M 4n ´ M 4n ,
…
Результирующеезначениематрицы,обладающейсвойством
транзитивного замыкания, будет получено в худшем случае за éêlog2 Nùú шагов.
При практической реализации действия, как и в рассмотренной выше ситуации,
изменение матрицы может прекратиться значительно раньше, однако в худшем
случае потребуется число шагов, пропорциональное логарифму от N.
В процессе нахождения произведения бинарных матриц базовой
операцией является операция нахождения бинарного скалярного произведения
i-го столбца и j-й строки матриц. Оно выполняется по формуле:
æö
mijn ¢ = mijn  çç  mikn mkjn ÷÷÷.(6)
çè k =1, N÷ø
В результате выполнения данной операции N 2 раз для всех i, j = 1, N
получается результирующая матрица. Новизной алгоритма является
сокращение числа итераций внутреннего цикла (по переменной k) при
получении единичного значения на одной из итераций нахождения скалярного
произведения двоичных векторов.
При умножении матриц с большим числом единиц число выполняемых
итераций по k будет малым, что уменьшает как число выполняемых операций
(конъюнкций и дизъюнкций), так и число обращений к памяти. Программная
реализация с использованием универсальных конвейерных суперскалярных
вычислителей данного способа экономии числа выполняемых операций имеет
ряд недостатков, основным из которых является нерегулярно срабатывающее
условие прерывания внутреннего цикла, приводящее к сбросам конвейера при
спекулятивном выполнении соответствующего программного кода. Они
снижают реальную производительность вычислительной системы при
выполнении умножения неплотных бинарных матриц, выполняемого для
реализации транзитивного замыкания.
После выяснения отношения следования производится определение
отношения связи путем выполнения покомпонентной конъюнкции:
T
( )
M Rj = M Rn  M Rn .
(7)
Выяснение отношения альтернативы производится путем анализа путей
между условными вершинами и вершинами объединения альтернативных дуг, в
y
результате чего оказывается сформирована матрица MR . Указанная операция
не зависит по данным от рассмотренных выше операций выяснения отношения
следования и связи и может быть выполнена параллельно с ними. На
завершающем этапе определения состава бинарных отношений выполняется
выяснение отношения параллельности:
M Rw = M Rj  M Ry .(8)
Граф-схема параллельного алгоритма определения состава бинарных
отношений представлена на рис. 1.

Рис. 1. Параллельный алгоритм определения состава бинарных
отношений
Формулы (1) – (3) определяют свойства используемых бинарных
отношений и в совокупности с (6) – (8) образуют модифицированную
математическую модель работы устройства обработки бинарных матриц.
Новизной математической модели является введение бинарных отношений
связи, альтернативы и параллельности вершин граф-схем параллельных
алгоритмов в дополнение к отношению следования, известному в теории
графов.
Таким образом, эффективным способом практической реализации
являетсяразработкаспециализированнойаппаратно-ориентированной
структурно-функциональной организации устройства обработки бинарных
матриц. Разработанная математическая модель и алгоритм позволяют
осуществить практическую реализацию устройства для умножения бинарных
матриц с прерыванием внутреннего цикла.
В третьем разделе разработана структурно-функциональная организация
устройства обработки бинарных матриц, приведены соответствующие
структурные схемы и описание их работы.
На рисунке 2 приведена структурная схема подключения устройства
обработки бинарных матриц (УОБМ) к современным вычислительным
системам с использованием шины PCI Express. Она включает в своем составе
запоминающее устройство (ЗУ) 1, устройство обработки бинарных матриц,
матрицы логических элементов ИЛИ 3 (М ИЛИ) и И 4 (М И), использующиеся
при выяснении бинарных отношений связи и параллельности. Запоминающее
устройство подключено к шине PCI Express с целью загрузки исходных данных
для построения матрицы отношений и выгрузки результата. УОБМ 2 включает
в своем составе одно из предложенных в диссертации устройств.

Рис. 2. Структурная схема устройства обработки бинарных матриц
При программной обработке матрица хранится в оперативной памяти в
виде двумерного массива бинарных значений, элементы матрицы
располагаются в памяти подряд, а для обращения к элементу требуется
вычисление адреса. При схемотехнической реализации это приводит к
появлению в схеме дополнительных сумматоров и блоков умножения,
увеличивая аппаратную сложность, тепловыделение и время задержки
распространения сигнала. Выходом из данной ситуации является разработка
специализированного запоминающего устройства с двухкоординатной
адресацией (блока коэффициентов матрицы), ориентированного на хранение
именно матричной информации. На рисунке 3 приведена схема блока
коэффициентов матрицы, на рисунке 4 – функциональная схема ячейки блока
хранения битовых признаков бинарного отношения.

Рис. 3. Схема блока коэффициентов матрицы
(пример запоминающего устройства со структурой 3´3´1 )
Рис. 4. Функциональная схема ячейки блоков хранения битовых
признаков бинарного отношения
Существуют два основных направления разработки устройств обработки
бинарных матриц: на базе систолических структур и на базе аппаратной
реализации алгоритмов классического умножения матриц с возможностью
параллельной обработки информации.
Устройствапервогонаправленияхарактеризуетсявысоким
быстродействием, однако они обладают чрезмерно большой аппаратной
сложностью, являющейся препятствием для их практической реализации при
умножении матриц большого размера. Устройства обработки бинарных матриц,
ориентированные на аппаратную реализацию алгоритмов классического
умножения, характеризуются умеренным быстродействием и низкой
аппаратнойсложностьюипозволяютосуществитьпрерывание
вычислительного процесса при умножении битовых векторов в соответствии с
алгоритмом, приведенным на рис. 1. В данном диссертационном исследовании
выполнена разработка двух способов реализации устройства обработки
бинарных матриц (по одному для каждого направления), с целью сравнения их
аппаратной сложности и быстродействия.
Устройство обработки бинарных матриц на базе систолических структур,
его функциональная схема и схема операционного блока приведены на рисунке
5.
Значения элементов умножаемых матриц загружаются в блоки
коэффициентов матриц 2 и 3, загрузка элементов первой и второй матриц
может быть совмещена во времени.
а)б)
Рис. 5. Функциональная схема устройства обработки бинарных матриц на
базе систолических структур (а); схема операционного блока устройства
обработки бинарных матриц на базе систолических структур (б)
Значения с выходов блоков коэффициентов матрицы 2 и 3 поступают на
вход триггеров 6 и 7, соответственно, матрицы операционных блоков. С
выходов триггеров 6 и 7 значения подаются на входы элемента И 9, на выходе
которого формируется их конъюнкция. Данные с выхода элемента И 9
поступают на второй вход элемента ИЛИ 10, а на первый вход подается
значение из триггера 8, с выхода которого сформированное значение поступает
на второй вход элемента И 11. Значение со второго входа элемента И 11
проходит на его выход. Значение с выхода элемента И 11 проходит через
элемент ИЛИ 13 на вход первой ступени триггера 8, где фиксируется по
пришествии соответствующего синхросигнала, что обеспечивает формирование
в триггерах 8 операционных блоков 1 искомых значений.
Функциональная схема устройства обработки бинарных матриц на базе
аппаратной реализации алгоритмов классического умножения матриц
приведена на рисунке 7.

Рис. 7. Схема устройства обработки бинарных матриц на базе аппаратной
реализации алгоритмов классического умножения матриц
Перед началом работы устройства на информационных входах сдвиговых
регистров 2 и 3 формируются значения «00…01». На входы адреса записи
строки и адреса записи столбца устройства внешним устройством поочередно
подаются адреса строк и столбцов элементов загружаемой матрицы, имеющих
единичное значение. При умножении матрицы значение с выхода rd1 блока
коэффициентов матрицы 10 проходит через коммутатор 11 и попадает на
информационный вход двухступенчатого триггера 12. Сигнал со входа 2
проходит через инвертор 8 и формирует на информационном входе сдвигового
регистра 9 значение «00…01». На выходе элемента ИЛИ 14 формируется
значение t  mik mkj = mij  mi1m1 j  mi 2m2 j …  mik mkj , которое подается на
второй вход коммутатора 11.
Синхросигнал со входа C3 устанавливается в единичное значение,
которое производит сдвиг влево содержимого сдвигового регистра 9. Если на
данной итерации в двухступенчатом триггере 12 хранится единичное значение,
оно открывает элемент И 15 для прохождения синхросигнала со входа C3 через
элемент ИЛИ 16 на синхровход записи cw блока коэффициентов матрицы 10,
что приводит к записи единичного значения в элемент mij матрицы взамен
предыдущего нулевого. В противном случае новое значение k обеспечивает
чтение новых значений m ik и mkj матрицы из блока коэффициентов матрицы
10 – производится переход к новой итерации.
После завершения умножения i-й строки на j-ый столбец единичное
значение с выхода элемента ИЛИ 18 открывает элемент И 5 для прохождения
синхросигнала со входа C2 на синхровход регистра 2, обеспечивая сдвиг его
содержимого в сторону старших разрядов. Далее процесс умножения
повторяется для (i+1)-й строки и j-го столбца аналогично рассмотренному
выше. После выполнения n итераций умножения единичное значение в составе
сдвигового регистра 2 попадает в (n+1)-й разряд. С выхода сдвигового регистра
2 указанное значение открывает элемент И 6 для прохождения синхросигнала
со входа C2 через элементы И 5 и элемент задержки 7 на синхровход сдвигового
регистра 3. Поступление n2 синхроимпульсов на вход C2 обеспечивает
получение n2 результатов умножения mij .
Таким образом, предложена структурно-функциональная организация
устройства обработки бинарных матриц: на базе систолических структур,
отличающаяся от прототипа узкой ориентацией на умножение бинарных
матриц, и на базе аппаратной реализации алгоритмов классического умножения
матриц, позволяющего аппаратную реализацию прерывания внутреннего цикла
в соответствии с алгоритмом, приведенным на рисунке 1, позволяющие
сокращение аппаратной сложности по сравнению с известными устройствами,
что подтверждается расчетами, приведенными в разделе 4.
В четвертом разделе приведены оценки аппаратной сложности и
быстродействия разработанного устройства обработки бинарных матриц: на
базе систолических структур и на базе аппаратной реализации алгоритмов
классического умножения матриц и их сравнение с устройством для умножения
матриц.
При умножении бинарных матриц по формуле (6) работу
соответствующего алгоритма и его практической реализации (программной или
аппаратной) досрочно прерывается в случае, если текущее значение частичной
конъюнкции при умножении бинарных векторов равно 1 (дальнейшие действия
не выполняются ввиду того, что 1  x = 1 ). Это позволяет экономить время на
умножение матриц за счет сокращения числа итераций внутреннего цикла.
С целью оценки соответствующей экономии используется понятие
плотности d умножаемых матриц размера N ´ N :
M
d= 2,(7)
N
где M – число единиц в умножаемых матрицах, 0 £ d £ 1 , и вероятности a
досрочного прекращения операции умножения бинарных векторов, 0 £ a £ 1 .
Зависимость вероятности a = 1-b ( b – вероятность выполнения
операций умножения ) досрочного прекращения умножения бинарных векторов
от размера N умножаемых матриц и их плотности d является нетривиальной, не
выражается аналитическими формулами и была установлена эмпирически в
ходе вычислительного эксперимента. Для этого формируется случайная
бинарная матрица размера N ´ N , включающая в своем составе M = éê dN 2 ùú
единиц, для нее производится возведение в квадрат, в ходе выполнения
которого подсчитывается необходимое для этого число конъюнкций
(логических умножений) K, по которому вычисляется вероятность досрочного
K
прекращения умножения a = 1-b = 1-3
( N 3 – число умножений элементов
N
матриц без досрочного прерывания). Соответствующая зависимость b (d ) для
N=64 представлена на рисунке 8.

Рис. 8 – Зависимость вероятности выполнения умножения (b) от
плотности умножаемых матриц (d ) (пример для N = 64 )
Анализ полученных результатов позволяет сделать вывод о том, что с
ростом размера N умножаемых матриц число выполняемых умножений
K  N 3 , значение величины b< 0,1 для N = 10 , d > 0,5 ; b < 0,01 для N = 100 , d > 0,1 , и раннее прекращение операции умножения битовых
векторов (в приведенном примере – на 2–3 порядка) сокращает необходимое
число умножений элементов матриц при вычислении произведения бинарных
матриц.
Оценка аппаратной сложности произведена в эквивалентных вентилях
(ЭВ) (одно- или двухвходовых логических элементах, выполняющих
элементарную логическую операцию).
Аппаратная сложность устройства для умножения матриц (R3)
(прототип, патент РФ на полезную модель № 157948) в целом складывается из
сложности блоков блока хранения (R1), набора регистров и матрицы nn
операционных блоков (R2) и вычисляется по формулам:
R1  4mn 2  3mn3  3n2  n,
R2  35mn2  3m2n2 ,
R3  43mn 2  3m 2 n 2  6mn 3  14n 2  2n, (8)
где n – размер обрабатываемых матриц, m – разрядность обрабатываемых
данных.
Аппаратная сложность устройства обработки бинарных матриц на базе
систолических структур (R6) (патент на полезную модель № 193927) в целом
складывается из сложности блоков блока хранения (R4), набора регистров и
матрицы nn операционных блоков (R5) и вычисляется по формулам:
R4  7n2  3n3  n,
R5  30n2 ,
R6  6 n 3  52 n 2  2 n.(9)
Аппаратная сложность устройства обработки бинарных матриц на базе
аппаратной реализации алгоритмов классического умножения матриц (R8)
(патент на изобретение № 2744239) складывается из аппаратной сложности
блока коэффициентов матрицы (R7) и аппаратной сложности элементов
устройства, образующих его операционную часть и вычисляется по формулам:
R7  15n 2  3n  3.
R8  15n2  45n  59.(10)
Значения величины аппаратной сложности устройства для умножения
матриц (R3) и устройства обработки бинарных матриц: на базе систолических
структур (R6) и на базе аппаратной реализации алгоритмов классического
умножения матриц (R8) приведены в таблице 1.
Таблица 1.
Результаты оценки аппаратной сложности разработанных устройств
mnУстройство дляУстройство обработки бинарных матриц
умноженияна базена базе аппаратной реализации
матриц (прототип,систолическихалгоритмов классического
патент РФ наструктурумножения матриц (патент на
полезную модель(патент наизобретение № 2744239), ЭВ
№ 157948), ЭВполезную модель(R8)
(R3)№ 193927), ЭВ
(R6)
8101,0×1051,1×1042,0×103
81005,4×1076,5×1061,5×105
810004,9×10106,1×1091,5×107
16102,4×1051,1×1042,0×103
161001,1×1086,5×1061,5×105
1610009,7×10106,1×1091,5×107
32106,4×1051,1×1042,0×103
321002,4×1086,5×1061,5×105
3210002,0×10116,1×1091,5×107
64101,9×1061,1×1042,0×103
641005,3×1086,5×1061,5×105
6410004,0×10116,1×1091,5×107
128106,2×1061,1×1042,0×103
1281001,3×1096,5×1061,5×105
12810008,2×10116,1×1091,5×107
Снижение аппаратной сложности устройства обработки бинарных матриц
на базе систолических структур достигается за счет хранения и обработки 1
бита информации для каждого коэффициента обрабатываемых бинарных
матриц вместо m бит в составе устройства для умножения матриц, что
позволяет снизить аппаратную сложность как схем хранения (блоков
коэффициентов матриц), так и схем обработки информации (матрица
операционных блоков) не менее чем в 8 раз в зависимости от размера матрицы
n и разрядности обрабатываемых данных m.
Из результатов расчета видно, что устройство обработки бинарных
матриц на базе аппаратной реализации алгоритмов классического умножения
матриц обладает не менее чем в 5 раз меньшей аппаратной сложностью по
сравнению с устройством обработки бинарных матриц на базе систолических
структур в зависимости от размера матрицы n.
Устройство обработки бинарных матриц на базе аппаратной реализации
алгоритмов классического умножения матриц обладает не менее чем в 5 раз
меньшей аппаратной сложностью по сравнению с устройством обработки
бинарных матриц на базе систолических структур, и не менее чем в 50 раз
меньшей аппаратной сложностью по сравнению с устройством для умножения
матриц в зависимости от размера матрицы n и разрядности обрабатываемых
данных m за счет более простой операционной части.
Выполнена сравнительная оценка быстродействия устройства для
умножения матриц и устройства обработки бинарных матриц: на базе
систолических структур и на базе аппаратной реализации алгоритмов
классического умножения матриц.
Оценка быстродействия устройств обработкибинарныхматриц
производится по формулам, приведенным в таблице 2:
Таблица 2.
Формулы для оценки быстродействия разработанных устройств,
t0 – время работы одного эквивалентного вентиля
НазваниеФормула для оценки быстродействия
Устройство для умножения матриц
(прототип, патент РФ на полезную модельtобщ1  8t0n2  t0  6t0n  9t0m(2n 1),
№ 157948)
Устройство обработки бинарных матриц
на базе систолических структур (патент на
полезную модель №193927)
( п)
tобщ2 
 14n2  2  log2 n  n t0 ,
набазеаппаратнойреализацииtобщ3  3t0  4t0  d  n 
алгоритмов классического умножения
матриц (патент на изобретение №
2744239)

 3t0n2  t0n  12  log2 n    n2
2t0n2  3t0n3  log2 n t0n2 .
В таблице 3 приведены результаты оценки быстродействия устройств
обработки бинарных матриц (для сравнения взяты усредненные значения
m  16,   0,5, t 0  1 нс ).
Таблица 3.
Результаты оценки быстродействия разработанных устройств
nУстройство дляУстройство обработки бинарных матриц
умножения матрицна базе аппаратной реализации
(прототип, патент РФна базе систолическихалгоритмов классического
на полезную модель №структур (патент наумножения матриц (патент на
157948), мсполезную модель №изобретение № 2744239), мс
193927), мс

40,1450,0140,0008
80,1450,0270,0039
160,1450,0520,0243
320,1450,1010,1759
640,1980,1981,3148
1280,3910,39110,0733
Полученные оценки быстродействия позволяют сделать вывод о том, что
быстродействие предложенных устройств сопоставимо с быстродействием
прототипа, в то время как их аппаратная сложность на 1 – 2 порядка ниже.
Таким образом, поставленная в диссертационном исследовании цель,
заключающаяся в снижении аппаратной сложности разработанных устройств,
достигнута.
Взаключениисформулированыосновныерезультаты
диссертационного исследования.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
В диссертационной работе в рамках решения поставленной научно-
технической задачи, заключающейся в сокращении аппаратной сложности
устройства обработки бинарных матриц, используемого для определения
состава бинарных отношений при построении разбиений граф-схем
параллельных алгоритмов логического управления получены следующие
результаты:
1.Проведен анализ существующих алгоритмов, программных и
аппаратных реализаций устройств для обработки матриц, в ходе которого
выявлены три способа реализации матричных операций на аппаратном уровне,
способных снизить время обработки. По итогу обзора сделан вывод о
необходимости разработки устройств обработки бинарных матриц, в основу
работы которых положен принцип параллельной, в некоторых случаях в
сочетании с конвейерной, матричной и/или систолической обработкой данных,
что позволяет снизить их аппаратную сложность и расширить сферу
практического применения
2.Разработана модифицированная математическая модель бинарных
отношений граф-схем параллельных алгоритмов, позволяющая свести задачу
определения состава указанной пары отношений к задаче транзитивного
замыкания бинарного отношения, решаемую путем нахождения произведения
бинарной матрицы самой на себя.
3.На базе модифицированной математической модели бинарных
отношений разработан аппаратно-ориентированный алгоритм для умножения
бинарных матриц, ориентированный на параллельную аппаратную реализацию,
позволяющий перенести вычислительно сложные процедуры умножения
бинарных матриц на аппаратный уровень. Особенностью данного алгоритма
является сокращение числа итераций внутреннего цикла за счет возможности
досрочного прерывания умножения матриц, что реализовано в рамках
разработанного устройства обработки бинарных матриц на базе аппаратной
реализации алгоритмов классического умножения матриц.
4.Разработана структурно-функциональная организация устройства
обработки бинарных матриц: на базе систолических структур и
ориентированное на аппаратную реализацию алгоритмов классического
умножения матриц, отличающихся низкой аппаратной сложностью по
сравнению с известными устройствами за счет их узкой ориентации на
обработку бинарных матриц.
5.В ходе проведенных вычислительных экспериментов были
получены зависимости вероятности досрочного прекращения умножения
бинарных векторов от размера умножаемых матриц и их плотности, анализ
которых позволил сделать вывод о том, что досрочное прерывание процесса
умножения сокращает временные затраты на 2 – 3 порядка по сравнению с
умножением матриц общего вида. На основе полученных зависимостей была
произведена оценка быстродействия разработанного устройства, которая
показала сопоставимые значения в сравнении с устройством прототипом. При
этом аппаратную сложность разработанного устройства удалось снизить не
менее чем в 50 раз для устройства обработки бинарных матриц на базе
аппаратной реализации алгоритмов классического умножения матриц по
сравнению с прототипом в зависимости от размера матрицы и разрядности
обрабатываемых данных, и в не менее чем в 5 раз для устройства обработки
бинарных матриц на базе систолических структур по сравнению с прототипом.
Перспективы дальнейшей разработки темы. Созданные алгоритм и
устройства могут найти применение в составе аппаратно-программных
комплексов по разработке СЛУ в базисе ЛМК, позволяя снизить время,
затрачиваемое на проектирование. Дальнейшее повышение быстродействия
предложенных устройств возможно за счет введения параллельной и
конвейерной обработки матриц.