Устройство для перемножения алгебраическихматриц

О П И С А Н И Е 264797

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТРУ

Союа Советсиих

Социалисти EBGKHx

Ресоублнн

Зависимое от авт, свидетельства №вЂ”

Заявлено 22,1Ч.1968 (№ 1234965, 18-24) с присоединением заявки №вЂ”

Приоритет

Опубликовано 03.Ill.1970. Бюллетень № 9

Дата опубликования описания 28Л 11,1970

Кл. 42m<, 7/16

МПК С 06g

УДК 621.385,831 (088.8) Комитет по делам изобретений и стнрытий ори Совете Министров

СССР

Авторы изобретения

H. И. Денисенко и А. А. Л

Заявитель

УСТРОЙСТВО ДЛЯ ПЕРЕМНОЖЕНИЯ АЛГЕБРАИЧЕСКИХ

МАТРИЦ

Изобретение относится к области вычислительной техники.

Известно устройство для перемножения алгебраических матриц, содержащее генератор опорных импульсов, генератор случайных импульсов, схемы сравнения, схему несовпадения, счетчики и триггер.

Предлагаемое устройство отличается от известного тем, что в нем одни входы группы схем сравнения, число которых равно порядку матрицы, соединены с выходом генератора случайных импульсов, а другое — с шинами ввода информации о значении элементов первой матрицы. Выходы группы схем сравнения соединены с одними входами группы реверсивных счетчиков, вторые входы которых соединены с выходом первой схемы сравнения и входом первого счетчика, не входящих в соответствующие группы,; третьи входы группы счетчиков соединены с шинами ввода информации о знаке элементов первой матрицы, а четвертые входы — с шиной ввода информации о знаке элементов второй матрицы. Выходы группы счетчиков подсоединены к шинам вывода информации о значении элементов матрицы-произведения и их знаке. Входы первой схемы сравнения, не входящей в группу, соединены соответственно с шиной ввода информации о порядке матрицы и выходом первого счетчика, не входящего в группу счетчиков.

Один вход второго счетчика соединен со входом генератора случайных импульсов и через схему несовпадения с выходом генератора опорных импульсов, второй вход схемы несовпадения соединен с выходом триггера, нулевой и единичный входы которого соединены соответственно с шиной ввода команды о начале работы устройства и с выходом второй схемы сравнения, который дополнительно сос10 динен со вторыми входами двух счетчиков, не входящих в группу счетчиков. Входы второй схемы сравнения соединены соответственно с выходом второго счетчика и с шиной ввода информации о значении элементов второй мат15 рицы, Используя один генератор случайных чисел, при перемножении матриц одновременно вычисляют произведения элемента к-го столбца левой матрицы на к-ую строку правой матри20 цы. Каждое из произведений входит слагаемым в разные элементы строки матрицы-произведения. А именно, если необходимо перемножить матрицы АВ = С, ;, где А(= а,, ()„; В= Ilaij.llzi то вычисляются одновременно и произведений: г(т )

С((— а,, в, (а) . д — а(,в а

264797 (Уг)

C;j — а„,в„. (й) и а! гв пь где С() — к-тое произведение, входящее слаtg гаемым в элемент матрицы-произведения С, то есть

С(1 = „ С(1) = 2 ацв 1, 1 = 1,2, ... и.

A=1 1=1

Таким образом, вычисляется одновременно

i-тая строка матрицы-произведения С. Граф, поясняющий работу устройства, представлен на фиг. 1, на котором ствол «дерева» моделирует а;; общее для всех сомножителей; ветви «дерева» моделируют ⻠—: вд„.

Ограничением на элементы матриц Л и В

И является а,, I (1;, в;, 1. Если моделиро1=1 вать число а,; регулярным потоком импульсов в количестве, равном Na;„, где N — количество импульсов, поданных для испытапия графа на проводимость, а числа ⻠—: в „ моделировать вероятностным образом, то отношение количества прошедших на выход импульсов 1-той ветви графа М кМ даст приближенное значение произведения а;„в„,.

Погрешность при этом оказывается меньше, чем если бы оба сомножителя моделировались вероятностным образом. Моделирование выполнено на базе известных и широко используемых в вычислительной технике узлов и блоков.

Блок-схема устройства представлена на фиг. 2. Она содержит генератор 1 опорных импульсов с частотой (1 — 5) 10 г(1; генератор 2 случайных чисел; и схем сравнения 8,— „„; счетчик 4; схему сравнения 5; триггер б; "veму несовпадения 7; и реверсивных счетчиков

8,— ()„; счетчик 9; схему сравнения 10. На схеме введены обозначения: al — а„— шины для ввода чисел ⻠— в,„; б — шина для ввода числа ад, в — шина для ввода знака элемента а;; г(— г„— шины для ввода знаков элементов ⻠—:в),„; д — шина для ввода команды начала испытаний; е — шина для ввода числа и (порядка матрицы); ж(— ж„— шины для вывода вычисленных элементов (-той строки матрицы-произведения; з) — з„— шины для

;, вывода знаков вычисленных элементов.

В момент стробирования импульсами генератора 1 опорных импульсов генератор 2 случайных равномерно распределенных чисел выдает m-разрядные случайные числа на схемы сравнения з) — з„. Пороги сравнения в схемах сравнения устанавливаются m-разрядными числами, вводимыми в них по шинам al — а„.

На выходах схем сравнения з — з„появляются одиночные импульсы при выполHåHêè неравенства: где — случайное число, поступившее на вход данной схемы сравнения; 1 — число, поданное на сравнение на тот же блок; в противном случае импульсы не появляются. Так как генерируемые случайные числа и числа, подаваемые на сравнение, заключены в интервале

5 (0,1), то вероятность появления импульса на выходе каждой схемы сравнения равна самому числу, поданному на сравнение.

Таким образом, блоки 1, 2 и 3> — 3„ в(оделируют элементы правой матрицы-сомножителя

10 ⻠—: ℄.

Элемент а(А, левой матрицы-сомножителя моделируется регулярным потоком импульсов в количестве Na;„. Они считываются счетчиком 4, со счетным входом которого соединен

)5 генератор 1 опорных импульсов. Счетчик 4 соединен со схемой сравнения 5, на котору(о по шине б подается число Na;),.

В момент фиксации счетчиком 4 числа

Na;, схема сравнения 5 выдает импульс, кото20 рый устанавливает счетчик 4 в нулевое состояние, а триггер б — в единичное. С единичного плеча триггера б снимается потенциал, который, запирая схему несовпадения 7, прекращает цикл вычисления. При этом реверсивные

25 счетчики 81 — 8„, счетные входы которых связаны с выходами схем сравнения 8,— 8„, зафиксируют числа М > — Л, где М( (>) (>) " (Ф)

= Naäâ„j; j = 1,2.....,n, с некоторой погрешностью Лк. Взяв отношение М (кЛ(полу33 (). ) А чаем С;, с погрешностью () =

Число N выбирается равным степени двух.

Знаки элементов а㻠⻠—:в „подаются до

35 начала испытаний на счетчики 8,— 8„в виде одиночных импульсов. По шине б подается знак а,, по шинам г(— г„— знаки элементов ⻠—: в„„. При этом знак минус обозначает наличие, а знак плюс — отсутствие импульса.

40 Команда начала испытаний подается по шине д в виде одиночного импульса, который фиксирует триггер б в нулевом положении. При этом триггер снимает запрет со схемы несовпадения, давая возможность импульсам про45 ходить от генератора 1 опорных импульсов.

Количество циклов испытаний фиксируется счетчиком 9, счетный вход которого соединен с выходом схемы сравнения 5. Счетчик 9 соединен со схемой сравнения 10, на которую по

50 шине е подается число и. В момент фиксации счетчиком 9 числа и схема сравнения 10 выдает одиночный импульс, который переводит счетчики 8,— 8„и 9 в нулевое состояние. При этом со счетчиков 8l — 8„по шинам ж,— ж„

55 считываются вычисленные элементы (-той строки матрицы С = AB и по шинам з(— з„их знаки.

60 Пр едв(ет изобретения

Устройство для перемножения алгебраических матриц, содержащее генератор опорных импульсов, генератор случайных импульсов, 65 схемы сравнения, счетчики, схему несовпадезия и триггер, отлича ощееся тем, что, с целью товышения быстродействия устройства, в нем дни входы группы схем сравнения, число коюрых равно порядку матрицы, соединены с выходом генератора случайных импульсов, а другие .— с шинами ввода информации о зна ении элементов первой матрицы, выходы руппы схем сравнения соединены с одними ходами группы реверсивных счетчиков, вторые входы которых соединень1 с выходом пер ой схемы сравнения и входом первого счет-1ика, не входящих в соответствующие группы, третьи входы группы счетчиков соединены с

:пинами ввода информации о знаке элеме IToB первой матрицы, а четверть..е входы — с шиной ввода информации о знаке элементов втоэой матрицы, выходы группы счетчиков под.оединены к шинам вывода информации о значении элементов матрицы-произведения и их знаке; входы первой схемы сравнения, не входящей в группу, соединены соответственно с шиной ввода информации о порядке матрицы и выходом первого счетчика, не входящего в группу счетчиков, один вход второго счетчика соединен со входом генератора случайных импульсов и через схему несовпадения с выходом генератора опорных импульсов, второй вход схемы несовпадения соединен с р выходом триггера, нулевой и единичный входы которого соединены соответственно с шиной ввода команды о начале работы устройства и с выходом второй схемы сравнения, который дополнительно соединен со вторыми

15 входами двух счетчиков, не входящих в группу счетчиков, а входы второй схемы сравнения соединены соответственно с выходом второго счетчика и с шиной ввода информации о значении элементов второй матрицы.

264797 ия г, cj г, г, Фиг. 2

Сосзавитель Л. Б. Дмитриева

Редактор Б. С. Нанкина Техред 3. Н. Тараненко Корректор Л. Фирсова

Заказ 2002!10 Тираж 480 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

Москва 7К-35, Раушская наб., д. 4/5

Типография, пр. Сапунова, 2