Ассоциативное устройство для суммирования массива чисел Советский патент 1990 года по МПК G06F7/50 

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

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

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

.уммы и переносов; на фиг. 7 - схема соединения разрядов блоков обработки разрядных срезов и блока запоминания суммы и переносов; на фиг.8 - функциональная схема узла хранения разрядного среза; на фиг. 9 - временные диаграммы выработки синхросигналов распределителем синхросигналов.

Ассоциативное устройство для суммирования массива чисел содержит блок 1 ассоциативной памяти емкостью т слагаемых по п разрядов, группу из (n + + 1) блоков 2 обработки разрядных срезов, имеющих информационные входы 3, управляющие входы 4, информационные выходы 5, управляющие выходы 6, блок 7 запоминания суммы и переносов,, имеющий информяСП

& 4ъ Од

СД

ipjtoiibie выходы 8 и 9, и распределитель 10 синхросигналов.

Каждый из блоков обработки разряд- нфго среза (фиг. 2) включает узел 11 хранения разрядного среза, преобразователь 12 двоичного кода в код количества единиц, имеющий информацион- шйе входы 13 фи информационные выходы 14, узел 15 формирования признаков суммы и переносов, имеющий информационный тзиход 16 суммы и информационные выходы 17 переносов, а также узел 18 распределения значений переносов, имеющий информационные выходы 19.

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

Узел 15 формирования признаков суммы и переносов (фиг. 4) содержит регистр 21, первую группу элементов И 22, элемент ИЛИ 23, вторую группу элементов И 24 и элемент ИЛИ-НЕ 25.

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

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

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

Первые п блоков 2 имеют разряд- н|эсть обрабатываемых срезов, равную IHL а остальные (lo.) блоков имеют разрядность, равную . Соответственно, в этих блоках число входив 13 (как и число выходов 14) блоков 12 составляет m и J-og TБлок 7 имеет (.m L+ xlog1m + i) + 1, где i (1, ... logam+1), выходов 8, (ti+ + 1) выходов 9. В узле 15 имеется К/2 выходов 17, а в узле 18 Имеется 3 logjK выходов 19, где К - число входов этих узлов.

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

5

0

5

g

,

5

0

5

0

довательности нулей и единиц принимают решение о значении суммы и признака единицы переноса. Если последняя диницэ находится в нечетном разряде, то значение суммы S в данном разрядном срезе равно 1, если в четном, то О. Признак переноса формируется в том разряде Р, , в котором проходит граница между нулями и единицами, причем если граница проходит через нечетный разряд, то признак переноса смещается на один разряд в сторону единиц.

Значение переносов формируют согласно таблице, где Р1 - переносы в i-й разряд, формируемые на основании

значений Р. . а

Максимальное число переносов, которое может быть сформировано в разрядном срезе, определяется формулой N 1оёгт . (1)

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

Исходные данные для суммирования записываются в блок 1 ассиоциативной памяти, откуда слагаемые по вертикальным (разрядным) срезам направляются в блоки 2 обработки разрядных срезов. Из них п блоков имеет разрядность т. Остальные () блоки имеют разрядность, равную J log,mL, причем входы этих блоков задействованы в соответствии со схемой обработки разрядных срезов. Обработка информации в разрядных срезах происходит следующим образом. Разрядный срез записывается в регистр узла 11 хранения разрядного среза, откуда поступает на входы 13 преобразователя 12 на выходах 14 разрядный срез представляет последовательность всех единиц в младших разрядах и всех нулей в старших. Упорядоченная таким образом последовательность О и 1 разрядного среза записывается в регистр 21. Решение о наличии ассоциативных признаков суммы и переносов происходит на основе анализа границы между нулями и единицами в регистре 21. Если последняя единица - в нечетном разряде, то она поступает на первый вход элемента И 22, на второй вход которого поступает единица с инверсного выхода следующего разряда. Если последняя единица - в четном разряде, то на вторые входы элементов И 22 поступает О и на выходах элементов И 22 будет О. Признак суммы с вы51564615«

хода 16 элемента ИЛИ 23 поступает в как в устройство поступит очередной регистр 27 суммы блока хранения сумм массив слагаемых из блока 1. и переносов и записывается в разряд,

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

соответствующий данному разрядному срезу. Признак переноса PJ формируется при помощи элементов И 2. Если граница между нулями и единицами - в четном разряде, то эта единица поступает на первый вход элемента И 2, на второй вход которого поступает единица с инверсного выхода соседнего старшего четного разряда регистра 21. Если последняя единица - в нечетном разряде, то признак, переноса формируется группой элементов И 24, которая соответствует паре разрядов, смещенной на один разряд в сторону соседнего младшего разряда. Сформированные признаки переносов поступают с выходов 17 элементов И 24 на входы элементов ИЛИ 26 узла 18 распределения значений переносовs который формирует переносы согласно таблице.

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

10

15

20

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

30 И, элемент задержки и элемент НЕ,

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

35

40

45

50

55

0

5

0

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

0 И, элемент задержки и элемент НЕ,

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

5

0

5

0

5

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

в}

CI

сг

ющих блоков обработки разрядных езов, i-й выход каждого j-ro реги- ра переноса соединен с вторым

5

0

входом (1+1)-го элемента И-ИЛИ группы (i+j)-ro блока обработки разрядного среза, выход элемента И соединен с входами элемента НЕ и со входом элемента задержки, выход элемента НЕ соединен с третьими входами элементов И-ИЛИ группы во всех блоках обработки разрядных срезов, выход элемента задержки подключен к четвертым входам элементов И-ИЛИ групп во всех блоках обработки разрядных срезов, выходы элементов И третьей группы соединены с выходами суммы устройства, выходы распределителя синхроимпульсов соединены соответственно с тактовыми входами первых регистров, вторых ре- гиг тров блоков обработки разрядных срезов и с тактовыми вхбрами регистра суммы и регистров переноса.

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

Количество единиц в 1-м разрядном срезе Р/

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

среза Р

i + 1 ji + 2 ji + 3 I i + 4 |

Фиг 2

EL...

к10

Фиг

51

в

ФиП

t/jfaf

W

11

g

33

-2Ji

Я

33

от 28

К23

30 n+tagiffi

31

Фиг. В

я.г§

#fO

о

I

/3

)

Jj

и

21

iMM1

r LLL

hp hp

I

A

Й