Ассоциативное запоминающее устройство

 

!

ОПИСАНИЕ

ИЗОБРЕтЕНИя

Союз Советских

Социалистических

Реслублик

«»?01349

Х АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. сеид-ву(22) Заявлено 24 01.78 (21) 25 7 3116/18-24 с присоединением заявки ¹â€” (51) . кл з

G 11 С 15/00

Государственный комитет

СССР но делам изобретений и открытий (23) Приоритет—

Опубликовано 07.09.81. Бюллетень ИЯ ЗЗ

Дата опублиноваиния описания 070981 (53) У4К 681. 327..6(088.8) (72) Автор изобретения

Г.В. Виталиев (71) Заявитель (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО

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

Изобретение относится к области запоминающих устройств. .Известны ассоциативные запоминающие устройства (17 и (27 .

В одном из известных ассоциативных запоминающих устройств арифметические операции над парой чисел выполняются в виде последовательности логических операций . f1). !

О

Недостатком этого устройства является малая скорость работы.

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

Недостатком этого устройства является существенное снижение быстродействия при выполнении арифметических операций.

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

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

701349

1 1 1 1

11 11

О О О О 1.1 1 1

1 0 О О 1 1 1 1

0 О О О

0 О 1 0

0 0 О 1

1 1 О 0

0 1 1 1 1 1 1 1 1 1 1 1

О О О 0 1 1 1 1 1 1 1 1

00

О 1 1 1 1 1 О О 1 1 1 1

1 1 1 1

ОООО 1111 11

О О О О

1 0 О О

О О О 0

1 1 1.1

О О 0 1

00

001011111111

Устройство содержит (см. фиг. 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 и 15 группы 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. 30

Входы 5„ б и 7 блоков 1 каждого столбца матрицы присоединены к выходам дешифратора 22 операций, Раз: рядные шины 4 записи блоков 1 подсоединены к выходам сумматоров 23 по модулю два, первые входы которых соединены с соответствующими выходами дешифратора 22 операций. Группы

13 триггеров 9 регистра 11 выполнены в виде кольцевых регистров сдвига. @3

Устройство содержит также двухканальные переключатели 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, 0011, 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 начинается снизу, а счет чисел — слева направо:

701349

1.7

1.8

0001

0110

0001

0111

1. 3

1.4

0010

1101

1101

0010

Такт 3

Такт 2

Такт 4

1.7 1.8 1.7 1.8

1.7 1.8

0 0 1 0 0 0 0 0 0 0 1 0 О 0 0 0 0 0 1 0 0 0 0 0

1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1

0 1 1 0 0 1 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0

1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 1 0

В первом такте на регистры 10 опроса первой и второй строки заносится код "11", а на регистры 11 маски, соответствующие блокам

1.1-1.3 и 1.5 — 1.7, код "10" ч на регистры 11, соответствующие блокам

1.4 и 1.8, †к "0j. В результате у блоков 1.1 - 1.3 и 1.5 — 1.7 возбуждаются адреса 01, 11, а у блоков

1.4 и 1.8 — адреса 10, 11. На входы

5 всех блоков подается сигнал логической "1", разрешающий обращение к ним, .на входы б блоков 1.1, 1.2, 1.5, 1.6 сигнал логического "0", разрешающий считывание из этих блоков, а на входы б блоков 1.3, 1.4 и 1.7 и 1.8 — сигнал логической "1", разрешающий запись в эти блоки. Блоки 1.7 и 1.3 используются для накопления поразрядной сумми, а блоки

1.8 и 1.4 — для накопления переносов. Поразрядная сумма образуется 20 путем суммирования пар исходных чисел по модулю два, а переносы — путем логического умножения пар исходных чисел со сдвигом на один разряд влево (имеется ввиду сдвиг исходных 5 позиционных кодов чисел).

При выполнении операции суммирования по модулю два на управляющие входы сумматоров 23, соответствующих блокам 1.7 и 1.3, поступают сигналы

d = О, а при выполнении операции логического умножения на управляющие входы сумматоров 23, соответствующих блокам 1.8 и 1.4, — сигналы d 1. На первые входы этих сумматоров в первом и втором тактах; поступают сигналы

С = 1. Переключатели 24, соединенные с шинами 4 блоков 1.3 и 1.7, постоянно коммутируются сигналами на управляющих входах для приема сигналов соответственно из блоков 1.1, 1.2 и 40

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 содержат следую щую информацию:

Во втором такте коды в регистрах

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

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

1.4, сигналы логической "1", а на регистры 10 опроса обеих строк — код

"00", и коды маски циклически сдвигаются в каждом такте. Сигналы на вторых входах этих переключателей

24 являются обратными (инверсными) сигналу С.

При этом в третьем такте сдвиг результата переноса получается за счет сдвига кодов маски блоков

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

1.8 во 2-ом, 3-ем и 4-ом тактах приведена ниже.

701349

Продолжение таблицы.3 1.4 1.3

1.4

1.3

О О 1 О ÎÎÎÎ О О 1 О О О О О О О 1 О ОООО

1 0 1 1 1 1 0 1 1 O 0 1 1 1 0 1 1

10 0000 00 1000000000 00

111 1111 11О1ÎÎ1ОО1ОО ОО10

Непосредственное сравнение результатов выполнения четвертого такта с,щ результатами сложения по модулю два и логического умножения позиционных кодов подтверждает правильность их вычисления. Так как содержимое блоков 1.4 и 1.8 отличается от позициан- 25 ного кода "0000" или слова "00010001" в коде 1. из й, то операция сложения процолжается аналогичным образом до тех пар,пака коды переносов не будут полностью совпадать с кодом "0000" для всех чисел, участвующих в данной операции сложения. Для этого во все запоминающие элементы блоков 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 40 и 2,.может быть использовано для выполнения всех логических операций над двумя переменными. При выполнении операций равнозначности и логического сложения в первых двух тактах на первые входы сумматоров 23 подаются сигналы С=О, а в следующих двух тактах — сигналы С=1. Для вы. полнения операций с обратными кодами чисел используются управляющие групиы 21, в которых кад опроса "11...1" может быть заменен кодом "00...0", например, за счет введения в состав каждой группы 21 независимого регистра 10 опроса. Перезапись в прямом коде выполняется как сложение по модулю два с кодом "ОООО", а операция инвертирования. — как сложение па модулю два с кодом "1111".

Операция вычитания выполняется как сложение с обратным или дополни- 60 тельным кадом вычитаемога. Операции с плавающей запятой выполняются аналогична операциям в сумматорах с плавающей запятой, т,е. за счет вве-, дения ассоциативных разрядов, экви- 65 валентных сумматору порядка, которые

Функционируют аналогично устройству, приведенному в данном примере.

Работа устройства, приведенного на фиг. 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...0". Далее производится сложение содержимого блоков 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.

Применение описанного устройства позволяет параллельно производить логические операции, операции арифметического сложения, вычитания, 701349

10 умножения и деления над двумя про-. извольными массивами чисел, при этом эти операции могут выполняться в различных сочетаниях по одной независимой операции на каждый сточбец матрицы. Следовательно, быстродействие этого устройства по сравнению с известными устройствами при правильном выборе алгоритма записи исходных массивов возрастает на один-два порядка и может быть оценено в несколько десятков миллионов операций в секунду для устройства емкостью 10244096 слов по 18-72 разряда с единичным циклом опроса и записи порядка

200 нс.

)5

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

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

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

Р 493162, кл. G 11 С 15/00, 1974.

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

Р 588561, кл. G 11 С 15/00,. 1975 (прототип).

701349

Составитель В. Рудаков

Редактор Е. Абрамова Техред А, Бабинец . KoppBKTop М. Демчик, Закаэ 6720/62 Тираж 645. Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4