Ассоциативное устройство для суммирования массива чисел

 

Изобретение относится к вычислительной технике и может быть использовано в системах обработки массивов чисел. Целью изобретения является повышение быстродействия устройства. Цель достигается за счет обработки разрядных срезов слагаемых параллельно по всем разрядам. Для этого в устройство, содержащее блок ассоциативной памяти и блок обработки разрядного среза, введены дополнительные блоки обработки разрядных срезов, каждый из которых содержит два регистра, две группы элементов И, преобразователь двоичного кода в код количества единиц, группу элементов И-ИЛИ, группу элементов ИЛИ, элементы ИЛИ и ИЛИ-НЕ. Устройство также содержит элемент задержки, элемент НЕ, распределитель синхроимпульсов и блок запоминания суммы и переносов. 9 ил. 1 табл.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (И) (51)5 С 06 F 7/50

ОПИСАНИЕ ИЗОБРЕТЕНИЯ н алов.

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ П.(НТ СССР (21) 4395482/24-24 (22) 21.03.88 (46) 15.05.90. Бюл. N - 18 (72) Г.И.Васильев, В.В.Храмов, С.В..Антонов и А.И.Клименко (53) 681.325.5(088.8) (56) Авторское свидетельство СССР

Ф 1273917, кл. G 06 F 7/50, 1985.

Авторское свидетельство СССР

)) 1424011, кл. G 06 F 7/50, 1986. (54) АССОЦИАТИВНОЕ УСТРОЙСТВО ДЛЯ

СУММИРОВАНИЯ МАССИВА ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано в системах обработки массивов чисел. Целью изобретения является поИзобретение относится к вычислительной технике и может быть использовано в системах обработки массивов чисел.

Цель изобретения — повьппение быстродействия устройства.

На фиг. 1 приведена структурная схема устройства; на фиг. 2 — структурная схема блока обработки разрядного среза; на фиг. 3 — функциональная схема преобразователя двоичного кода в код количества единиц, пример исполнения; на фиг. 4 — функциональная схема узла формирования признаков суммы и переносов, на фиг. 5— функциональная схема узла распределения значений перекосов для случая четырнадцати слагаемых; на фиг. 6— структурная схема блока запоминания

2 вышение быстродействия устройства

Цель достигается за счет обработки разрядных срезов слагаемых параллельно по всем разрядам. Для этого в устройство, содержащее блок ассоциативной памяти и блок обработки разрядного среза, введены дополнительные блоки обработки разрядных срезов, каждый из которых содержит два регистра, две группы элементов И, преобразователь двоичного кода в код количества еди— ниц, группу элементов И-ИЛИ, группу .элементов ИЛИ, элементы ИЛИ и ИЛИ-НЕ.

Устройство также содержит элемент задержки, элемент НЕ, распределитель синхроимпульсов и блок запоминания суммы и переносов. 9 ил., 1 табл. уммы и переносов; на фиг. 7 — схема соединения разрядов блоков обработки разрядных срезов и блока запоминания суммы и переносов; на фиг.8 функциональная схема узла хранения разрядного среза; на фиг. 9 — временные диаграммы выработки синхросигналов распределителем синхросигАссоциативное устройство для суммирования массива чисел содержит блок 1 ассоциативной памяти емкостью

)в слагаемых по и разрядов, группу из (n + log тп + 1) блоков 2 обработки разрядных срезов, имеющих информационные входы 3, управляющие входы

4, информационные выходы 5, управляющие выходы 6, блок 7 запоминания суммы и переносов, имеющий информа1564615 ц1 оные выходы 8 и 9, и распределитель

1() синхросигналов.

Каждый из блоков обработки разрядного среза (фиг. 2) включает узел 11 хранения разрядного среза, преобразователь.12 двоичного кода в код количЕства единиц, имеющий информационн1 е входы 13 и информационные выходы

14, узел 15 формирования признаков 10 суммы и переносов, имеющий информационный и:лход 16 суммы и информационн е выходы 17 переносов, а также узел

1 распределения значений переносов, имеющий информационные выходы 19.

Преобразователь 12 (фиг. 3) состоит из группы схем И/ИЛИ 20.

Узел 15 формирования признаков с уммы и переносов (фиг. 4) содержит р гистр 21, первую группу элементов yg

И;22, элемент ИЛИ 23, вторую группу элементов И 24 и элемент ИЛИ-НЕ 25.

Узел 18 распределения значений п реносов включает в себя группу элем нтов ИЛИ 26. Пример его реализации 25 д я случая четырнадцати слагаемых п едставлен на фиг. 5.

Блок 7 запоминания суммы и переносов содержит регистр 27 суммы, группу регистров 28 переносов, третью 3п группу элементов И 29, элемент И 30 и элемент 31 задержки.

Для управления записью .в регистры блоков 11 используются элемент НЕ 32 и группа элементов И-IgIH 33.

Первые и блоков 2 имеют разряд35 нЮсть обрабатываемых срезов, равную

m а остальные (log m+1) блоков име2. ют разрядность, равную ) lag

BJIoK 7 имеет (ll+ J logjam + и j x х1о8,тп (+ (glog

Устройство реализует алгоритм паРаллельного по всем разрядным срезам суммирования чисел. Процесс обработк и одного разрядного среза происходит следующим образом: сначала происходит . пВРегруппировка нулей и единиц Разрядного среза, в результате чего все

Единицы размещаются в младших разрядах, а все остальные разряды занимают йули; На основе анализа данной последовательности нулей и .единиц принимают решение о значении. суммы и признака единицы переноса. Если последняя единица находится в нечетном разряде, то значение суммы S в данном разрядном срезе равно "1",. если в четном, то ",0"., Признак переноса формируется в том разряде P, в котором проходит

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

Значение переносов формируют согласно таблице, где Р„ — переносы в

i-й разряд, формируемые на основании значений Р

Максимальное число переносов, ко-, торое может быть сформировано в раз-. рядном срезе, определяется формулой

N = Plog

Устройство работает следующим образом. !

Исходные данные для суммирования записываются в блок 1 ассиоциативной памяти, откуда слагаемые по вертикальным (разрядным) срезам направляются в блоки 2 обработки разрядных срезов. Из них и блоков имеет разрядность m. Остальные (logjam+1) блоки имеют разрядность, равную j logjam(, причем входы этих блоков задействованы в соответствии со схемой обработки .разрядных срезов. Обработка информа- ции в разрядных срезах происходит следующим образом. Разрядный срез записывается в регистр узла 11 хранения разрядного среза, откуда поступает на входы 13 преобразователя 12 на выходах 14 разрядный срез представляет последовательность всех единиц в младших разрядах и всех нулей в старших. Упорядоченная таким образом последовательность "0" и "1" разрядного среза записывается в регистр

21. Решение о наличии ассоциативных признаков суммы и переносов происходит на основе анализа границы между нулями и единицами в регистре 21.

Если йоследняя единица — в нечетном разряде, то она поступает на первый вход элемента И 22, на второй вход которого поступает единица с инверсного выхода следующего разряда. Если последняя единица — в четном разряде, то на вторые входы элементов И 22 поступает "0" и на выходах элементов

И 22 будет "0". Признак суммы с вы64615 6 как в устройство поступит очередной массив слагаемых из блока

15 в

Сформированные переносы по сигналу из распределителя 10 синхросигналов записываются в регистр 28 переносов блока 7 запоминания суммы и переносов. По сигналу из распределителя 10 информация из блока 7 запоминания сумм и переносов с выходов 8 поступает в регистры узлов 11 хранения разрядного среза и обработка повторяется аналогично описанному. Так .происходит до тех пор, пока будут формироваться признаки переносов. Как только признаки переносов будут равны нулю, с выходов элементов И 24 нули поступают на элемент ИЛИ-НЕ 25, с выхода 6 которого единица .поступает на вход элемента И 30 блока 7 хранения суммы и переноса. Сигнал с выхода И 30 открывает элемент И 29, и полученная сумма снимается с выхода 9 блока 7. Этот же сигнал с выхода элемента 31 задержки подается на входы управления записью в регистры узлов 11 блоков 2 очередного массива слагаемых из блока 1. Инверсное значение сигнала. с выхода элемента

И 30 используется для управления записью в регистры узлов 11 из регистров переносов на тех. тактах работы устройства, на которых еще не завершена обработка переносов. Задержка сигнала с выхода элемента И 30 необходима для завершения процесса передачи суммы из регистра 27 перед тем, 55

5 15 хода 16 элемента ИЛИ 23 поступает в регистр 27 суммы блока хранения сумм, и переносов и записывается в разряд, соответствующий данному разрядному срезу. Признак переноса Р; формируется при помощи элементов И 2. Если граница между нулями и единицами— в четном разряде, то эта единица поступает на первый вход элемента

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

И 24, которая соответствует паре разрядов, смещенной на один разряд в сторону соседнего младшего разряда.

Сформированные признаки переносов поступают с выходов 17 элементов И 24 на входы элементов ИЛИ 26 узла 18 распределения значений переносов, который формирует переносы согласно таблице.

Формула изобретения

Ассоциативное устройство для суммирования массива чисел, содержащее блок. ассоциативной памяти и первый блок обработки разрядного среза, содержащий первый и второй регистры, первую и вторую группу элементов И и преобразователь фвоичного кода в код количества единиц, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия, устройство содержит блоки обработки разрядных срезов с второго по (п + 1о@ в+1)-й, где

n — разрядность слагаемых, ш — число слагаемых, распределитель синхроимпульсов и блок запоминания суммы и переносов, каждый блок обработки разрядных срезов содержит группу элементов И-ИЛИ, группу элементов ИЛИ, элемент ИЛИ, элемент ИЛИ-НЕ, блок запоминания суммы и переносов содержит регистр суммы, группу регистров переноса, третью группу элементов И, устройство, кроме того, содержит элемент

И, элемент задержки и элемент НЕ, причем выходы блока ассоциативной памяти, соответствующие каждому разрядному срезу, соединены соответственно с первыми входами элементов И-ИЛИ в соответствующем блоке обработки разрядного среза, в каждом блоке обработки разрядного среза выходы элементов И-ИЛИ подключены к соответствующим входам первого регистра, выходы которого соединены с входами преобразователя двоичного кода в код количества единиц, выходы которого соединены с соответствующими входами второго регистра, прямые выходы нечетных разрядов которого соединены с первыми входами элементов И первой группы, вторые входы которых соединены с инверсными выходами соседних старших четных разрядов второго регистра, выходы элементов И первой группы соединены с входами элемента

ИЛИ, прямые выходы четных разрядов второго регистра соединены с первыми входами элементов И второй группы, вторые входы которых соединены с инверсными выходами соседних старших четных разрядов второго регистра, выходы элементов И второй группы соединены с входами элемента И-НЕ и с

1564615 входом (i+ 1) -го :элемента И-ИЛИ группы (i+j)-го блока обработки разрягного среза, выход элемента И соединен с вхоцами элемента HV-.и со входом элемента задержки, выход элемента HE соединен с третьими входами элементов

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

5 группы соединены с входами соответствующего регистра переноса, выход элемента ИЛИ каждого блока обработки разрядного среза соединен с соответс вующим входом регистра суммы, выко- 10 дЦ которого соединены с первыми входамй элементов И третьей группы и с вторь ми входами первых элементов И-ИЛИ группы всех блоков обработки разряд-нйх срезов, вторые входы элементов И третьей группы соединены с выходом э цемента И, входы которого соединены с выходами элементов ИЛИ-НЕ соответств ющих блоков обработки разрядных с", езов, i-й выход каждого j-го реги- 20 с ра переноса соединен с вторым

Количество

Распределение единиц относительного 1-го разрядного среза Р; единиц в

i-м разрядном срезе Р (+ 2 i+ 3 + 4

О

3

5

7

9

11

12

13

14

О

О

1

О

О

1

О

О

1

О

1.

О

О

О

Î

1

1

О

О

1

1

G

О

О

О

О

О

1 1

1

О

О

0

О

О

О

О

О

О

О

О

О

О

1564615

1564615

1564б15

- 1564615

4ьг.Ю

Составитель А.Степанов

Техред И.Дидык Корректор Н.Ренская

Редактор А.Orap

Заказ 1160

Тираж 561

Подписное

ВНИИПИ Государственного комитета ло изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101