Матричное вычислительное устройство
Изобретение относится к вычислительной технике и может быть использовано при построении вычислителей матричного типа для выполнения операции умножения и деления двоичных чисел. Целью изобретения является расширение функциональных возможностей за счет умножения и деления двоичных чисел в дополнительных кодах. Матричное вычислительное устройство содержит матрицу ячеек из N строк и N столбцов, первую и вторую группы из N элементов И, группу из N одноразрядных сумматоров, а каждая ячейка матрицы включает элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент И и одноразрядный сумматор. Устройство дополнительно содержит элемент НЕ, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, группу из N коммутаторов, элемент ИЛИ и N узлов, каждый из которых включает два коммутатора, три элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент И-НЕ и элемент ИЛИ. 5 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (51)5 0 06 F 7/52
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К ABTOPCHOMV СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
1 (21) 4439630/24-24 (22) 03.05.88 (46) 07.02,90. Вюл. ¹ 5 (72) С.А.Волощенко (53) 681 ° 325 (088. 8) (56) Авторское свидетельство СССР
Р 1164697, кл. (* 06 F 7/52, 1985.
Авторское свидетельство СССР
Р 1024910, кл. С 06 F 7/52, 1982, (54) МАТРИЧНОЕ ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙ"
СТВО (57) Изобретение относится к вычисли тельной технике и может быть использовано при построении вычислителей матричного типа для выполнения операции умножения и деления двоичных чи
Изобретение относится к вычислительной технике и может быть использо вано при построении однотактовых вычислителей матричного типа для выполнения операции умножения и деления двоичных целых и дробных чисел, представленных в дополнительном коде.
Цель изобретения — расширение функциональных возможностей за счет умножения и деления двоичных чисел в дополнительных кодах, На фиг. 1 приведена структурная схема предлагаемого устройства при
N=4; на фиг. 2 — функциональная схема узла; на фиг. 3 — функциональная схема ячейки, используемой в устройстве; на фиг. 4 и 5 — схемы вычислительных процессов„ происходящих при
„.,SU„„ 415ßß А1
2 сел. Целью изобретения является расширение функциональных возможностей за счет умножения и деления двоичных чисел в дополнительных кодах, Матричное вычислительное устройство содержит матрицу ячеек из 11 строк и М столбцов, первую и вторую группы из N элементов И, группы из N одноразрядных сумматоров, а каждая ячейка матрицы включает элемент ИСК1ПЗЧАЮЦЕЕ ИЛИ, элемент И и одноразрядный сумматор, Устройство дополнительно содержит элемент НЕ, элемент ИСКЛЮЧАЮЩЕЕ И1В1, группу из N коммутаторов,,элемент ИЛИ и N узлов, каждый из которых включает два коммутатора, три элемента ИСКЛИЧА10ЩЕЕ ИЗП1, элемент И-1!Е и элемент
ИЗП1. 5 ил. умножении и делении (N — разрядность операндов).
Иатричное вычислительное устройство (фиг. 1) содержит группу из N узлов I матрицу NxN ячеек 2, элемент
НЕ 3, первую группу из N элементов И
4, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 5, группу из N коммутаторов 6, элемент 1П1И 7, вторую группу из 1 элементов И 8, группу из Ы одноразрядных сумматоров 9. Кроме этого, устройство имеет первый 10 и второй 11 входы управления устройством, первую группу входов
12 (входы множителя В или старших разрядов делимого Х)-, вторую группу входов 13 (входы множимого А или делителя Y), третью группу входов 14 (вхо- ды младших разрядов делимого Х ), пер<
1541599 вую группу выходов 15 (выходы старних разрядов произведения С или facTHoro
Х), вторую группу выходов 16 (выходы младших разрядов произведения С ), а
5 также вход 17 логического нуля.
Каждый узел 1 (Аиг. 2), выполняющий в устройстве функции локального (поразрядного) управления, содержит первый коммутатор 18, первый 19 и втброй 20 элементы ИС1(1ПОЧА1ЩЕ1 . ШП1, элемент И-НЕ.21, третий элемент ИС=
К1ПОЧА1О1 1ЕЕ ШIИ 22, второй коммутатор
23 и элемент ШПI 24. Кроме этого, узел 1 имеет вход 25, подключенный к первому входу коммутатора 18, первым входам элементов ИСКЗПОЧАЮЦЕЕ ИЛИ
19 и 22, а также второму входу коммутатора 23, выход 26 первого коммутатора, вход 27, подключенный к второму и первому входу элементов ИСКЗПОЧАЮЩЕЕ
ИЛИ 19 и 20 соответственно, второй вход 28 второго элемента ИСКЛЮЧА1ОП1ЕК
KIIH, выход 29 второго коммутатора, выход 30 элемента ШП1, второй вход 31 25 элемента ШIИ, выход 32 второго элемента ИСКЛЮЧА1 )ЦЕК ИЛ11,, второй вход 33 третьего элемен га ИСКЗПОЧАЮЦЕЕ ШП1, Каждая ячейка 2 (Аиг. 3), выполняющая функции поразрядной арифметической обработки, содержит элемент
ИСКЗПОЧАЮЦЕЕ ШПI 34, элемент И 35 и одноразрядный сумматор 36. Кроме этого, ячейка 2 имеет выход 37 переноса одноразрядного сумматора, второй вход
38 элемента И, первый 39 и второй 40
35 входы элемента ИСКЛЮЧАМЦЕЕ ШП1, втор«й вход 41, вход переноса 42 и выход
43 одноразрядного сумматора соответственно.
Входы управления коммутаторов не изображены. При делении коммутаторы передают инАормацию через первые входы, расположенные на условных граАических отображениях (УГО) сверху и слева, а при умножении — с вторых входов, расположенных соответственно снизу и справа.
Номера строк в устройстве возрастают сверху вниз, я столбцов — слева направо. Аналогична нумерация элемен- тов в группах. Входы знаковых разрядов операндов и выход знака результата расположены в разрядных группах слева и сверху.
Умножение в устройстве выполняется следующим образом (фиг.1). На вход 10 управления должен поступать нулевой уровень, а на вход 11 — единичный. При этом происходит настройка на операцию =A В, что обеспечивается передачей информационных сигналов через вторые входы коммутаторов (расположенных на УГО справа и снизу), настройкой элементов И 8 и ШП1
?4 на режим логического повторения, а также закреплением за элементом
ИЛИ 7 функций генератора логической единицы. Дополнительный код N-разрядного множимого А поступает на входы 13 устройства и передается во все строки ячеек матрицы. Дополнительный код множителя В в М разрядов поступает на входы 12 устройства и передается в узлы 1. В узлах 1 происходит преобразование кода из двоичной системы счисления (0,1) в двоичную систему счисления (-1, О, +1), используемую только для внутреннего представления множителя. В этом случае произведение С будет представлено обычным двоичным кодом (0,1), так как оно получено в результате суммирования либо вычитания кодов множимого А, не подвергавшихся нреобразованию. Код (2N-1)-разрядного произведения С формируется на выходах 15 и 16 устройства (соответственно N старших и N-1 младних разрядов).
Алгоритм умножения основан на следующей формуле (для дробных чисел):
М-< N-1
С= Kb„A ? + (а,ЩЬ; ) (Ь; 9Ъ;+, )
1 =O 4 (1)
2 +22 где Амножимое, равное а0,а,,а ак- разряд множителя Б (где В
=Ью,Ь,,Ь Ьй- ) причем < (0,1) и считается, что Ь„=О; разряд множителя В, выражен- ного в двоичной системе счисления (-1, О, +1), причем b ;e (-1, Q, +1); константный поправочный член; операция ИСКЭПОЧАЮЦЕЕ ШП1.
Ь
2 2
Формулу (1) при N=4 можно представить в виде следующего информационного поля частичных произведений, кода поправки и константного члена, дающих при суммировании код произведения С. Причем каждый бит инАормационного поля представлен здесь в виде прямоугольника, в прямоугольнике ст«бражен и способ вычисления этого бита.
1541599
b, ), ), (a((a( л (1 л!
Ь а, а< а а1
b> д а1 аа а мируется на выходах сумматоров ячеек
2N-й строки и группы 6, и далее поступает на выходы 15 и 16. При этом на.входах 14 должен быть нулевой код при вычислении С=А ° В. В противном случае устройство реализует формулу (C=AB+, : (где К вЂ” код на входах 14), что позволяет дополнительно вводить поправки в виде смецений либо осуцествлять округление при усечеliHH разрядности произведения.
Примеры (фиг. 4) иллюстрируют вычислительные процессы в устройстве при реализации умножения В=А Б. Разряды промежуточного представления обведены овалом, а стрелки указывают на формируемые по их значению частичные произведения.
Деление в предлагаемом устройстве выполняется по алгоритму без восстановления остатка. Перед выполнением операции X=X/Y на вход 10 управления необходимо подать логическую единицу, а на вход 11 — логический ноль (фиг. 1). Это обеспечивает передачу информационных сигналов через первые входы коммутаторов !.входы, расположенные сверху и слева на УГО коммутаторов). Одновременно с этим блокируется прохождение сигналов через элементы И группы 8, а элемент И(Ш 7 и элементы И 35 ячеек 2 начинают работать как логические повторители. с с с с с с5
Код поправки формируется на выходах коммутаторов 18 узлов 1 и поступает для суммирования на вторые входы сум-, маторов ячеек 2 первой строки матрицы.
Вычисление каждого информационного 30 разряда кода поправки происходит на элементах ИСКЛЮЧАЮ!!ЕЕ ИЛИ 19 (операция ад9Ь;), элементе ИСКЛЮЧАЮЦЕЕ
KIH 22 (операция Ь;9Ь;,) и элементе
И-НЕ 21.
Вычисление частичных произведений выполняется на элементах ИСКЛЮЧАЮЦЕЕ
ИЛИ 34 и И 35 каждой,!1з строк ячееек
2 матрицы, управляемых сигналами с выходов коммутатора 23 и элемента ИЛИ 40
24 соответствуюцего этой строке уз( ла 1. При b;=+1 на выходе коммутатора 23 и элемента ШП! 24 формируется ( код 01, при Ъ;=-1 формируется код 11, а при Ь =0 этот код равен 10 или 00, 45
1 (Сами же b; определяются по значению двух разрядов Ь; и Ь . Причем Ъ; =О, если Ь; и Ь; „ одинаковы; в противном ! I случае b;=-1, если b;=1, иначе Ь =+1, { если Ь„=О. 50
„,, N-1
Константный член 2. 2 задается единичным уровнем на выходе -элемента
ИЛИ 7 (так как на входе 11 единица), и уровнем единицы, формируемым при этом на выходе N-ro коммутатора 6.
Сформированные таким образом слагаемые формулы (1} суммируются сумматорами ячеек 1 и сумматорами 6 группы. !!олнораэрядное произведение фор
N-<
О(ад ЯЬ „) (Ь,®!э(„) ° 2
Частичные произведения
H-1 (,КЬ;, 2
1 =Д
М-1
Константный член 2.2
1541599
Код 2N-разрядного делимого Х поступает на входы 12 (стяршие разряды) и входы 14 (младшие разряды). Код делителя Y í N разрядов — на входы 13
5 устройства. Между величинами делимого и делителя должно выполняться соотношение IX! lY!. Код частного Z формируется ня выходах 15. . Знак частного lо формируется на 10 выходе элемента ИСКЛЮЧАЩЕЕ ИЛИ 20 первого узла 1 и передается на знаковый разряд выходов 15, проходя последовательно первый коммутатор 6 и первый сумматор 9. !!роцесс вычисления остальных цифр частного Z состоит в итерационном вычислении очередных остатков Il,, формируемых последовательно в каждой из строк ячеек 2 матрицы. При этом каждая очеред- 20 ная цифра частного Х вычисляется
1 в (i+1) ì узле 1 ня основе следующих выражений (; =2(2;,+Sign() Y, йри (P,=Х, (2) <1
+1, если знаки Ц„, и Y противоположны; где БЦп(у )=
-1, если знаки < ; 1 и Y равны;
О, если знаки ()„ и Y противо- 30 положны
1, если знаки Ц: и Y равны.
Причем вычитание:. н выражении (2) заменено суммированием с дополнительным кодом путем инвертирования кода Y 35 на элементах ИСИ1ЮЧАЮЦЕЕ ИЛИ 34 яче- ек 2 и суммирования единицы в младший разряд через элемент И 4.
Определение выполняемого действия. 40 (суммирование либо вычитание), d также очередной цифры ".; осуществляется на элементах ИСК3!1ОЧА1011ЕЕ ИЛИ 20 (i+
+1)-го узла 1. Вычисленные таким образом Е, поступают через коммутато- 45 ры 6 ня первые входы сумматоров 9 группы, ня которых осуществляется коррекция чястноГо.
Необходимость коррекции частного следует из особенности деления н доIIoJIHHTåëüHûõ кодах и выполняется после определения N-разрядного кода
la,Å,,Е .../NI. )(пя этого вычисляется дополнительная цифра частного
Еп (это осуществляется в !1-Й строке ячеек 2 матрицы с использованием элементя ИСКЛ1ОЧА1ОЦЕЕ ШП! 5), после чего ". суммируется н младший разht ряд этого кода.
Таким образом, окончательный реэультят равен .<-н
"a > I, К . Н-1 Н 2
Примеры деления (фиг. 5) иллюстрируют последовательность ны11олняемых действий при И=4. Х связи с тем, что
1 значение переноса иэ знакового разряда и значение знакового разряда кода (; всегда противоположны, цифры равны логической операции ИСК!!ЮЧАЮЦЕЕ ШЫ знакового разряда делителя с переносом из знаковых разрядов кодов очередных остатков (ныделено нижней полускобкой).
Формула изобретения
Иатричное вычислительное устройство, содержащее матрицу ячеек иэ Й строк и N столбцов, первую и вторую группы из N элементов И, группу из N одноразрядных сумматоров, причем каждая ячейка матрицы содержит элемент
ИСК.1ПОЧА10ЦЕЕ ШП1, элемент И и одноразрядный сумматор, первый вход одноразрядного сумматора m-й ячейки (m+1)-й строки матрицы (m=1,2...N-1) подключен к выходу одноразрядного сумматора (m+1)-й ячейки m-й строки матрицы, вход переноса одноразрядного сумматора, первый вход элемента ИСКЗПОЧА10ЦЕЕ
ИЛИ и второй вход элемента И т-й ячейки и-й строки матрицы (п=1,2 ;..., N) соответственно подключены к выходу переноса одноразрядного сумматора, первому входу элемента ИСКЛ1ОЧАЮЦЕЕ
HJIH и второму входу элемента И (m+1)-й ячейки этой же строки матрицы, второй вход элемента ИСЙПОЧАЮЩЕЕ ИЛИ и-й ячейки m-й строки матрицы подключен к второму входу элемента ИСКЛ10ЧАЮЦЕЕ ШП1 и-й ячейки (m+1)-й строки и к и-му разрядному входу второй группы входов устройства, выход одноразрядного сумматора первой ячейки и-й строки матрицы подключен к первому входу и-го элемента И второй группы, а вторые входы элементов И второй группы соединены с вторым входом управления устройства, вход переноса
m ãо одноразрядного сумматора группы соединен с выходом переноса (тп+1)-ro одноразрядного сумматора группы, выход и-го одноразрядного суммятора группы соединен с и-м разрядным выходом первой группы ныхо11ов устройства, а выход однораэрядвого сум11;IToðà (m+
+1)-й ячейки N-й строки мя1рицы соеди154 l 599
l0 нен с ш-м разрядным выходам второй группы выходов устройства, о т л ич а ю щ e e с я тем, что, с цепью расширения»»»ункцио»»а»»нных возможнос5 тей за счет умножения и деления в дополнительных кодах, введены элемент
НЕ, элемент ИСКЛОЧАЮ!(ЕЕ ИЛИ, группа из N коммутаторов,,элемент HJIH u N управляющих узлов, каждый из которых содержит дна коммутатора, три элемента ИСКЛЮЧАМ(ЕЕ ШП1, элемент И-НЕ и элемент HJIH, n-й разрядный вход первой группы входов соединен с первым входом первого и третьего элементов ИСКЛЮЧА(ОП(ЕЕ ШIИ, первым входом первого коммутатора и вторым входом второго коммутатора п-го управляющего узла, а также с вторым входом третьего элемента ИСКЛЮЧАЫ(ЕЕ ШШ . gp (и-1)-го управляющего узла, первый разрядный вход второй группы входов устройства соединен с вторым входом первого и первым входом второго элемента ИСИПОЧАЮ!(ЕЕ ШП1 каждого п-го управляющего узла и первым входом элемента ИСКЛЮЧА(ОЩЕЕ ШП1, выходы первого и второго элементов ИСК.!ПОЧА10П(ЕЕ
ИЛИ и-го управляющего узла соединены соответственно с первым входом эле-: — 30 мента И-НЕ и первым входом второго коммутатора этого же и-го управляющего узла, а выход и второй вход элемента И-HL n-го управляющего уЛла соединены соответственно с вторым 35 входом первого коммутатора и выходом третьего элемента HCKJIYWAY34EE HJIH п-го управляющего узла, причем к выходу третьего элемента ИСКЛЮЧАЮП(ЕЕ
HJIH n-ro управляющего узла подключен 4р первый вход элемента ШП1 этого же узла, выход переноса одноразрядного сумматора первой ячейки m-й строки матрицы соединен с вторым входом второго элемента ИСК1ПОЧА(ОП(ЕЕ ШП1 45 (m+1) — ro управляюще го узла, а выход переноса одноразрядного сумматора первой ячейки N-. и строки матрицы соединен с вторым входом элемента ИСКЛ(0ЧАЮЦЕЕ ИЛИ, выход которого соединен с первым входом элемента ИЛИ, а второй вход и выход этого эЛемента
ШIИ соединены соответственно с вторым входом управления устройства и входом переноса N-ro о»»»»оразрядного суммато55 ра » руппы, первый и нторой входы m-ro
1 коммутатора гру»п»ы соединены соответственно с выходом второго э »емента ИСКЗПОЧА1ЩЕЕ И31И m-го управляющего узла и выходом переноса одноразрядного сумматора первой ячейки (m+1)-й строки матрицы, первый и второй входы N-го коммутатора группы соединены соответственно с выходом второго элемента ИСК1ПОЧА!ОП(ЕЕ ШПI N-ro управляющего узла и выходом элемента ШПI, первый и второй входы п-re одноразрядного сумматора группы соединены соответственно с выходами п-го коммутатора и и-го элемента И второй группы, вход переноса одноразрядного сумматора N-й ячейки п-й строки матрицы соединен с выходом п-го элемента И первой группы, а первый и второй входы этого же элемента И соединены соответственно с первым входом элемента ИСКЗПОЧАЮ((ЕЕ ИЛИ и вторым входом элем»нта И этой же N-й ячейки и-й строки матрицы, первый вход элемента
ИСКЛЮЧ".!ОП(ЕЕ ШП1 и второй вход элемента И первой ячейки (m+1)-й строки матрицы соединены соответственно с выходом второго коммутатора и выходом элемента ИЗП! (m+1)-ãî управляющего узла, выход второго коммутатора и выход элемента ШIИ первого управляющего узла соединены соответственно с входом элемента НЕ и вторым входом элемента И первой ячейки первой строки матрицы, а выход элемента НЕ соединен с первым входом элемента ИСК ПОЧА1ЩЕЕ
ШПI этой же ячейки, второй вход второго элемента ИСКЛЮЧА!ОП(ЕЕ Ш1И первого управляющего узла соединен с выходом первого коммутатора первого управляющего узла, второй вход одноразрядного сумматора m-й ячейки первой строки матрицы соединен с выходомпервого коммутатора (m+1)-го узла, нторой вход одноразрядного сумматора N-й ячейки и-й строки матрицы соединен с и-м разрядным входом третьей группы входов устройства, вторые входы элементов HJIH каждого управляющего узла, а также входы управления коммутаторов группы и коммутаторов всех управляющих узлов подключены к первому входу управления устройства, второй вход третьего элемента !!СКЛ!0ЧАЮ((ЕЕ ИЛИ
N-го управляющего узла подключен к входу. логического нуля устройстна.
154 1599
A,Ó
fZ
Qluz. фут. 4.
Операми оппо ото
ысиио по
Фо рниро ва
HNo она%а частиоГО о ппо
I.OIO о.сспо
1-я итерация с.опо
I.OIO
I.IOIO
2-я итерация
I.ÎIÎ о.по о.осо
3-я итерация о.осо
r.OIO
I.ÛÎ
4-я итерация
Корреяция яастнОГо
Реауяътат йримары Ладаинм
ХХ - IOCOIO (-ф) и - с.по- (ф
I.СаНО о. по
I.ПО О т.IGIO с.по с.опо о.по
I.ÎIÎ о.ссо о.ооо
I,я О .OIO
I OII
ZI- I.oö <ф
Хг - O.OIIIIO - (Д)
Xa - I.О О » »(-ф,..,У
I.ou
Ю- ?.оп - (-ф
