Матричное вычислительное устройство
ОП ИСАНИЕ
ИЗОБРЕТЕН ИЯ
К АВТОРСКАЯ СВИДЕТЕЛЬСТВУ
Союз Советских
Социалистических
Республик
G 06 F 7/38 Государстеениый комитет Опубликовано 28.02.81. Бюллетень № 8 Дата опубликования описания 05.03.81 оо делам изобретений н открытий (53) УДК 681.325 (088.8) Л. А. Шумилов, А. И. Суейдан, Али Абдалла Абдалла Дауд и И. С. Зуев Ф (72) Авторы изобретения Ленинградский ордена Ленина электротехнический, институт им. В. И. Ульянова (Ленина) (71) Заявитель (54) МАТРИЧНОЕ ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО Изобретение относится к вычислительной технике и может быть использовано в быстродействующих процессорах и специализированных вычислительных устройствах. Известно матричное вычислительное устр0НсТВо для извлечения квадратного корня (1). Данное матричное вычислительное устройство требует для своей реализации больших аппаратурных затрат и имеет неидентичные связи, что затрудняет его реализацию на больших интегральных схемах. то Наиболее близким по технической сущности к предлагаемому устройству является матричное вычислительное устройство (МВУ) для извлечения квадратного корня. Каждая вычислительная ячейка включает сумматор по модулю два и сумматор и имеет четыре входа и четыре выхода (2). Недостатком устройства являются большие аппаратурные затраты при его реали- ар зации. Цель изобретения — сокращение аппаратурных затрат при реализации матричного вычислительного устройства. Поставленная цель достигается тем, что матричное вычислительное устройство, содержащее матрицу вычислительных ячеек, причем каждая вычислительная ячейка содержит сумматор, при этом первый вход вычислительной ячейки i-ой строки j-го столб-. ца соединен с первым выходом вычислительной ячейки i-ой строки (j — 1) -го столбца, первый вход предпоследней вычислительной ячейки каждой строки соединен с первым входом устройства, первый вход вычислительной ячейки i-ой строки первого столбца соединен со вторым выходом вычислительной ячейки (i — 1)- ой строки первого столбца, второй вход вычислительной ячейки i-ой строки j-го столбца соединен с третьим выходом вычислительной ячейки (i — 1) строки (j + 1) -ro столбца, вторые входы вычислительных ячеек второй строки первого и второго столбцов соединены с третьими выходами вычислительных ячеек первой строки первого и второго столбцов соответственно, вторые входы двух последних вычислительных ячеек каждой строки соединены со вторыми входами устройства, третий вход вычислительной ячейки i-ой строки j-го столбца соединен со вторым выходом 809174 вычислительной ячейки i-ой строки (j+1)-го столбца, третий вход последней вычислительной ячейки каждой строки соединен с первым выходом последней вычислительной ячейки, четвертый выход вычислительной ячейки i-ой строки j-го столбца соединен с четвертым входом вычислительной ячейки (i+ 1) -ой строки j-го столбца, четвертые выходы последних двух вычислительных ячеек 1-ой строки соединены с четвертыми входами последних двух вычислительных ячеек (i + 1)-ой строки соответственно, четвертые входы вычислительных ячеек первой строки соединены с третьими входами устройства, каждая вычислительная ячейка дополнительно содержит элемент И, причем в каждой вычислительной ячейке первый вход элемента И соединен с первым входом и с первым выходом вычислительной ячейки, второй вход элемента И соединен со вторым входом вычислительной ячейки, первый вход сумматора соединен с третьим входом вычислительной ячейки, четвертый вход вычислительной ячейки соединен со вторым входом сумматора, первый выход которого соединен со вторым, а второй выход с третьим выходами вычислительной ячейки соответственно, четвертый выход вычислительной ячейки соединен со вторым входом сумматора, третий вход которого соединен с выходом элемента И, третий вход которого соединен с пятым входом вычислительной ячейки, причем пятый вход вычислительной ячейки i-ой строки j-го столбца соединен со вторым входом вычислительной ячейки (i-1)-ой строки (j+1)-го столбца, пятые входы вычислительных ячеек второй строки первого и второго столбцов соединены со вторыми выходами вычислительных ячеек первой строки первого и второго столбцов соответственно, пятые входы последних двух вычислительных ячеек каждой строки соединены со вторыми входами устройства. На фиг. 1 изображена структурная схема матричного вычислительного устройства; на фиг. 2 — структурная схема вычислительной ячейки. Матричное вычислительное устройство содержит вычислительные ячейки 1, первые, вторые и третьи входы 2 — 4 устройства, выходы 5 устройства. Вычислительная ячейка (ВЯ) содержит сумматор 5, элемент И 6, входы 7 — 11, выходы 12 — 15. Рассмотрим алгоритм извлечения квадратного корня, который используется в предлагаемом МВУ. В отличии от известного предлагаемое МВУ работает по восстанавливающему алгоритму извлечения квадратного корня. Пусть подкоренное выражение Х представлено в данной системе счисления в прямом коде и нормализовано, т. е. 0(Х (1. 5 ! о 5О Пусть требуется найти квадратный корень из числа Х, где Х = 0,010011001100... 1-ый шаг: предположим, что первая цифра результата равна единице. Проверим это предположение. Это осуществляется вычитанием из первых двух цифр подкоренного выражения числа «01». Вычитание осуществляется сложением в дополнительном коде. Поэтому перенос в знаковый разряд означает положительность остатка. Отсутствие переноса означает отрицательность остатка. 0l+ В данном случае есть перенос в знако11 вый разряд, что означает положитель001 ность остатка. Следовательно, первая цифра результата равна «1». 2-ой шаг: в зависимости от знака остатка из первого шага берется либо уменьшаемое, либо остаток. Если остаток положительный, то берем сам остаток, иначе берется уменьшаемое. К этому числу добавляются еще цифры из подкоренного выражения. Это и есть уменьшаемое второго шага. Предположим, что вторая цифра результата равна единице. Проверка этого предположения осуществляется вычитанием из уменьшаемого числа ОС101, где CI — первая цифра результата. 0000 Переноса нет. Остаток отрицательный. Следовательно, вто01011 — рая цифра результата равна ну-. лю. 3-й шаг: отбрасываем первую цифру остатка и повторяем действия второго шага. Из вычитаемого вычитаем число ОС1С201, где С2 вторая цифра результата. 00011 Переноса нет. Остаток отрица1011! тельный. Третья цифра резуль011010 тата равна «О» и так далее. МВУ работает следующим образом. Разряды подкоренного выражения поступают на матрицу. Первые два разряда поступают на вторые и пятые входы ВЯ первой строки, следующие два разряда поступают на вторые и пятые входы последних двух ВЯ второй строки, третья пара разрядов поступает на вторые и пятые входы последних двух ВЯ третьей строки и т. д. Действия в первой строке соответствуют действиям на первом шаге, а действия во второй строке соответствуют действиям на втором шаге и так далее. В зависимости от результата из (i — 1)-ой строки, который поступает на первые выходы элементов И ВЯ i-ой строки, в качестве уменьшаемого i-ой строки выбирается остаток (i — 1) -ой строки, поступающий на вторые входы элементов И ВЯ -ой строки или уменьшаемое (i — 1)-ой строки, поступающее на третьи входы элементов ВЯ i-ой строки. При единогласном значении первого входа элемента И он пропускает значение второго входа, а при ну809174 Формула изобретения Матричное вычислительное устройство, содержащее матрицу вычислительных ячеек, причем каждая вычислительная ячейка содержит сумматор, при этом первый вход вычислительной ячейки i-ой строки -го столбца матрицы соединен с первым выходом вычислительной ячейки -ой строки (j — 1) -го столбца, первый вход предпоследней вычислительной ячейки каждой строки соединен с первым входом устройства, первый вход вычислительной ячейки i-ой строки первого столбца соединен со вторым выходом вычислительной ячейки (1 — 1)-ой строки первого столбца, второй вход вычислительной ячейки i-ой строки j-го столбца соединен с третьим выходом вычислительной ячейки (i — 1)-ой строки (j+1)-гостолбца, вторые входы вычислительных ячеек второй строки первого и второго столбцов соединены с третьими выходами вычислительных 50 левом значении первого входа — значение третьего входа. Вычитаемое подается на четвертые входы ВЯ в дополнительном коде. Определим аппаратурные затраты, необходимые при построении предлагаемого МВУ Предлагаемое МВУ и известное устройство требуют для своей реализации одинаковое количество ВЯ, а именно 1/2 (м. + 5п — 2) . Для конкретности оценим затраты оборудования, используя серию элементов 133. 10 Реализация сумматора по модулю два в известном устройстве и элемента И в предлагаемом МВУ требует по три логических элемента из этой серии. Реализация сумматора, имеющего только прямые выходы и пере- 5 носа, требует 10 логических элементов из этой серии и требует прямые и инверсные шины всех входов. Входы сумматора в известном устройстве являются переносами с соседней ячейки справа, выход сумматора по модулю два и выход суммы одной ячейки 20 верхнего ряда. Поэтому для сумматора по модулю два и выходов суммы и переноса двойных сумматоров требуется по инвертору, в то время как для предлагаемого МВУ требуется инвертировать только выход 5 элемента И и выход переноса двойного сумматора, так как выход сумматора не поступает ни на какой сумматор. Эффективность изобретения заключается в выигрыше, по оборудованию составляющего 1/2 (и +5п-2) инверторов, где 2п — разрядность подкоренного выражения, что составляет приблизительно 6 /о от общего числа оборудования. ячеек первой строки первого и второго столбцов соответственно, вторые входы двух последних вычислительных ячеек каждой строки соединены со вторыми входами устройства, третий вход вычислительной ячейки i-ой строки j ro столбца соединен со вторым выходом вычисЛительной ячейки 1-ой строки (j+1) -го столбца, третий вход последней вычислительной ячейки каждой строки соединен с первым выходом последней вычислительной ячейки, четвертый выход вычислительной ячейки i-ой строки 1-го столбца соединен с Четвертым входом вычислительной ячейки (i+1)-ой строки j-го столбца, четвертые выходы последних двух вычислительных ячеек i-ой строки соединены с четвертыми входами последних двух вычислительных ячеек (i + 1) -ой строки соответственно, четвертые входы вычислительных ячеек первой строки соединены с третьими входами устройства, отличающееся тем, что, с целью сокращения аппаратурных затрат, каждая вычислительная ячейка дополнительно содержит элемент И, причем в каждой вычислительной ячейке первый вход элемента И соединен с первым входом и с первым выходом вычислительной ячейки, второй вход элемента И соединен со вторым входом вычислительной ячейки, первый вход сумматора соединен с третьим входом вычислительной ячейки, четвертый вход вычислительной ячейки соединен со вторым входом сумматора, первый выход которого соединен со вторым, а второй выход — с третьим выходами вычислительной ячейки соответственно, четвертый выход вычислительной ячейки соединен со вторым входом сумматора, третий вход которого соединен с выходом элемента И, третий вход которого соединен с пятым входом вычислительной ячейки, причем пятый вход вычислительной ячейки i-ой строки j-ro столбца соединен со вторым входом вычислительной ячейки (i — 1)-ой строки (j+1)-го столбца, пятые входы вычислительных ячеек второй строки первого и второго столбцов соединены со вторыми входами вычислительных ячеек первой строки первого и второго столбцов соответственно, пятые входы последних двух вычислительных ячеек каждой строки соединены со вторыми входами устройства. Источники информации, принятые во внимание при экспертизе 1. Devries R. С., Chao М. Н. Fully Herative array for extracting square roots. «Electronics letters», 1970, vol. 6, № 8. 2. Шауман А. М. Матричное извлечение корня. Сб. «Вычислительная техника», ЛГУ, вып. 6, с. 105 — 111 (прототип). 809174 Риг. 7 рог. 2 Составитель В. Венцель Редактор H. Кузнецова Техред А. ЮЬойкас Корректор М. немчик Заказ 17/58 Тираж 756 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж вЂ” -35, Раушская наб., д. 4/5 Филиал ППП «Патент», г. Ужгород, ул. Проектная, 4
