Ассоциативное запоминающее устройство Советский патент 1981 года по МПК G11C15/00 

(,54) АССОЦИАТИВНОЕ BAnOMllHAIOtHEE УСТРОЙСТВО

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

Каждый блок 1 содержит, например, четыре адресных запоминающих блока 1.1-1.4 или 1.5-1.8 (см. фиг. 2), которые могут быть выполнены в виде полупроводниковых микросхем. Блоки 1.1-1,8 имеют адресные шины 2, выход .ные разрядные шины 3, разрядные шины 4 .записи, входы 5 управления выборкой, входы б управления записью, информационные входы 7. Кроме того, устройство содержит триггеры 8 и 9 регистра 10 опроса и регистра 11 маски соответственно, которые раздё.лены на группы 12 триггеров 8 и группы 13 триггеров 9 по числу строк матрицы, элементы ИЛИ 14. Первые вхо ды 15 и вторые входы 16 элементов ИЛИ 14 подключены соответственно к прямым выходам 17 и обратным выходам 18 триггеров 8 регистра 10 опроса и прямым выходам 19 триггеров .9 регистра 11 маски, а выходы - к входам дешифраторов опроса 20. выходы дешифра торов 20 соединены с адресными шина.ми 2 блоков 1 соответствующих строк матрицы .

Регистр 11 маски, элементы ИЛИ 14 и дешифраторы 20 разделень на управляющие группы 21 по числу блоков 1.1-1.8 в блоке 1.

Входы 5, б и 7 блоков 1 каяодого столбца матрицы присоединены к выходам дешифратора 22 операций. Разрядные шины 4 записи блоков 1 подсоединены к выходам сумматоров 23 по модулю два, первые входы которых соедине-ны с соответствующими выходами дешифратора 22 операций. Группы 13. триггеров 9 регистра 11 выполнены в виде кольцевых регистров сдвига. Устройство содержит также двухканаль ные переключатели 24.

Первые входы сумматоров 23 подключены к соответствующим выходам дешифратора 22.

Выходы переключателей 24 подключены соответственно к вторым и третьим входам сумматоров 23, а управляющие входы переключателей 24 и сумматоров 23 - к соответствуквдим выходам дешифратора 22.

Входы переключателей 24 соединены с выходными разрядными шинами 3 соответствующих блоков 1.1-1.8 (см. фиг. 2).

С целью увеличения производительности при выполнении операций умножения и деления устройство может содержать первые дополнительные двух- канальные переключатели 25 (см. фиг. 3), вторые дополнитегтные двухканальные. переключатели 26 и элементы И 27. При этом каждый блок 1 содержит дополнительные адресные блоки 1.9, 1.10. или 1.11, 1.12.

Работу устройства, изображенного на фиг. 1 и 2, проиллюстрируем на примере выполнения операции сложения двух групп из четырх четырехразрядных чисел с помощью восьми блоков 1,1-1.8, Каждый из этих блоков в данном примере имеет по четыре адресных шины 2 и по четыре разрядных шины 3 и 4. в блоках 1.5 и 1.1 записаны четыре числа 0001 , ООН, 1011,0111 а в блоках 1.6 и 1.2 - четыре числа

1011, 0111, 0100 и 0101. Два младших разряда каждого числа относятся к блокам 1.1 и 1.2, а два старших к блокам 1.5 и 1.6. Указанные числа записаны на соответствующих разрядны линиях этих блоков, т.е. в запоминающих элементах, соединенных с одной из шин 3 и 4, в коде 1 из N (1 на фоне N-1 нулей). Преобразование из позиционного кода в код 1 из N осуществляется дешифраторами 20. Во все запоминающие элементы блоков 1.7, 1.3, 1,8 и 1.4 предварительно записывается код 1, Счет выходов дешифраторов 20 начинается снизу, а .счет чисел - слева направо:

В первом такте на регистры 10 опроса первой и второй строки заносится код 11, а на регистры 11 маски, соответствующие блокам 1.1-1.3 и 1.5 - 1.7, код 10 ч на регистры 11, соответствующие блокам 1.4 и 1.8, . В результате у блоков 1.1. - 1.3и 1.5-1.7 возбуждаются адреса 01/11, а у блоков

1.4и 1.8 - адреса 10, 11. На входы 5 всех блоков подается сигнал логической 1, разрешающий обращение

к ним, ,на входы 6 блоков 1.1, 1,2, 1.5, 1.6 сигнал логического О, разрешающий считывание из этих блоков, а на входы 6 блоков 1.3, 1.4 и 1.7 и 1.8 - сигнсш логической 1, разрешающий запись в эти блоки. Блоки 1.7 и 1.3 используются для накопления поразрядной суммы, а блоки 1.8 и 1.4 - для накопления переносов. Поразрядная сумма образуется путем суммирования пар исходных чисел по модулю два, а переносы- путем логического умножения пар исходных чисел со сдвигом на одил разряд влево (имеется ввиду сдвиг исходных позиционных кодов чисел).

При выполнении операции суммирования по модулю два на управляющие входы сумматоров 23, соответствующих блокам 1.7 и 1.3, поступают сигналы d О, а при выполнении оперсщии логического умножения на управляющие входы сумматоров 23, соответствукхцих блокам 1.8 и 1.4, - сигналы . На первые входы этих сумматоров в перво и втором тактах: поступают сигналыС 1. Переключатели 24, соединенные с шинами 4 блоков 1.3 и 1.7, постоянно коммутируются сигналами на управляющих входах для приема сигналов соответственно из блоков 1.1, 1.2 и

1.5и 1.6 для того, чтобы поразрядная сумма записывалась в блоки 1.3, 1.7 без сдвига. В первом такте переключатели 24, соответствугадие блокам 1.4 и 1.8, также коммутируются на

прием информации соответственно из блоков 1.1,. 1.2 и 1,6, 1.5. .Сдвиг результата операции логического ум.ножения происходит за счет циклического сдвига на один разряд кода маски блоков 1.4 и 1.8 относительно кода маски блоков 1.1, 1.2 и 1.5, 1.6. После выполнения первого такта блоки 1.3, 1.7 и 1.4, 1.8 содержат следуюТцую информацию:

1.7

1.8 ОНО 0001

1111

0001

o

0111

1111

1111 1111

1.3

1.4

5

0010

1101

nil

1101

0010

1111

0

1111 1111

Во втором такте коды в регистрах 11 маски сдвигаются циклически 01

5 для блоков 1.1-1.3 и 1.5-1.7 и блоков 1.4 и 1.8, а переключатели 24, соответствующие блокам 1.4 и 1.8, коммутируются на прием информации со сдвигом на одну строку.

0

В третьем и четвертом тактах на первые входы сумматоров 23 поступают сигналы , на вторые входы переключателей, соответствующих блоку 1.4, сигналы логической 1, а на

5 регистра 10 опроса обеих строк - код 00, и коды маски циклически сдвигаются в каждом такте. Сигналы на вторых входах этих переключателей 24 являются обратными (инверсными) сигналу С.

0

При этом в третьем такте сдвиг результата переноса получается за счет сдвига кодов маски блоков 1.1-1.3 и 1.5-1.7, а в четвёртом такте - за счет сдвига кодов маски и

5 коммутсщии переключателей 24, соответствующих блокам 1.4 и 1.-8, которая аналогична второму такту. Диаг-рамма состояния модулей 1.3, 1.7, 1.4 1.8 во 2-ом, 3-ем и 4-ом тактах при0ведена ниже.

001000000010000000100000

101000011000000110000001

011001000110010001000100

111111111001 111000011010 Непосредственное сравнение резуль татов выполнения четвертого такта с результатами сложения по модулю два и логического умножения позиционных кодов подтверждает правигльность их вычисления. Так как содержимое блоков 1.4И 1.8 отличается от позицион ного кода 0000 или слова 00010001 в коде 1 из N, то операция сложения продолжается аналогичным образом до тех пор,пока коды переносов не будут полностью совпадать с кодом для всех чисел, участвующих в данной операции сложения. Для этого во все запоминающие элементы блоков 1.5, 1..1 и 1.6, 1.2 записываестя код 1 и производится попарное сложение содержимого блоков 1.7, 1.3и1.8, 1,4 и т.д. Проверка на равенство нулю всех переносов может выполняться путем опроса блоков 1.8, 1.4 или ,1.6, 1,2 по коду опроса 0000. Устройство, изображенное на фиг. 1 и 2,. может быть использовано для выполнения всех логических операций над двумя переменными. При выполнении операций равнозначности и логического сложения в первых двух тактах на первые входы сумматоров 23 Подаются сигналы , а в следующих двух тактах -,сигналы . Для вы.поЛнения операций с обратными кодами чисел используются управляющие групиы 21, в которых код опроса 11....1 может быть заменен кодом 00...О, .например, за счет введения в со тав каждой группы 21 независимого регистра 10 опроса. Перезапись в прямом коде выполняется как сложение по модулю два с кодом 0000, а -операция инвертирования - как сло жение по модулю два с кодом llllj. Операция вычитания выполняется, кик слолсение с обратным или дополни тельным {одом вычитаемого, Операции с плавающей запятой выполняются ана логично операциям в сумматорах с плавающей запятой, т.е. за счет вве ления ассоциативных разрядов, эквиПродолжение таблицы валентных сумматору порядка, которые функционируют аналогично устройству, приведенному в данном примере. Работа устройства, приведенного , на фиг, 3, отличается от работы устройства, изображенного на фиг, 2 тем, что блоки 1.9-1,12 используются для сдвига кодов множимого и множителя соответственно на один разряд вправо и влево. Умножение, реализуется путем накопления в модулях 1.3, 1.7 суммы последовательны;: сдвигов кодов, записанных в блоках 1.10, 1,12, в соответствии с кодами 1 на соответствующих шинах 3 блока 1.9каждого столбца матрицы. Блоки 1.1, 1,5, 1.2, 1.6 используются для хранения промежуточных результатов. Умножение начинается с занесения кодов сомножителей в блоки 1.9, 1.11 ... и 1.10, 1.12. Затем производится сдвиг кодов этих сомножителей на один разряд с записью окончательного результата в блоки 1.9,1.11 и 1.10,. 1,12 и перепись содержимого блоков 1.10, 1.12 в блоки 1.4, 1.8. В блоки 1.3, 1.7,... предварительно записываются слова с позиционным кодом 00.,,О. Далее производится сложение содержимого блоков 1.3, 1,7,,.. и 1.4, 1.8,... с записью окончательного результата в блоки 1.3, 1.7, Затем производится сдвиг кодов в блоках 1.9-1,12 еще на один разряд, содержимое блоков 1.10,1.12 переписывается в блоки 1.4 н 1,8 и суммируется с содержимым блоков 1.3 и 1.7. в остальном, выполнение операции умножения в данном устройстве аналогично выполнени;Ю умножения в обычном сумматоре. Деление можно заменить операцией вычитания содержимого блоков 1.10и 1,12 .из содержимого блоков 1.3 и 1.7. Применение описанного устройства позволяет параллельно производить логические операции, операции арифметического сложения, вычитания. умножения и деления над двумя произвольными массивами чисел, при этом эти операции могут выполняться в различных сочетаниях по одной независимой операции на каждый столбец матрицы. Следовательно, быстродейст вие этого устройства по сравнению с известными устройствами при прави ном выборе алгоритма записи исходны массивов возрастает на один-два порядка и может быть оценено в нескол ко десятков миллионов операций в се кунду для устройства емкостью 10244096 слов по 18-72 разряда с единич ным циклом опроса и записи порядка 200 НС. Формула изобретения Ассоциативное запоминающее устрой ство, содержащее матрицу адресных блоков памяти, элементы ИЛИ, входы которых подключены к выходам регистра опроса и регистра маски, а выходы - к входам дешифраторов опроса, выходы которых соединены с адресными шинами адресных блоков памяти соответствугацих строк матрицы, дешифра цг. 1 тор операций, выходы которого соединены с входами управления выборкой и записью и информационными входами адресных блоков памяти каждого столбца матрицы, сумматоры по модулю два выходы которых подключены к разрядным шинам записи адресных блоков памяти, а первые входы - к соответствующим выходам дешифратора операций, о т-л и ч а ю щ е е с я тем, что, с целью повышения .быстродействия устройства, оно содержит двухканальные переключатели, выходы которых соединены с вторыми и третьими входами сумматоров по модулю два, входы - с выходными разрядными шинами соответствующих адресных блоков памяти,управляющие входы двухканальных переключателей и сумматоров по МОДУЛЮ два подключены к соответствующим выходам дешифратора операций. Источники информации, принятые во внимание при экспертизе 1,Авторское свидетельство СССР № 493162, кл. G 11 С 15/00, 1974. 2.Авторское свидетельство СССР №588561, кл. G 11 С 15/00,.1975 (прототип).

OJ IM