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

ОП ИКАНИЕ ИЗОБРЕТЕНИЯ Союз Советских Социалистических Республик(51)М К э С 11 С 15/00 Государственный комитет СССР но делам изобретений и открытий(23) Приоритет -Опубликовано 07,09,81. Бюллетень Ио ЗЗДата опублиноваиния описания 070981(71) Заяв итель 547 АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО На фиг. 1 приведена структурная схема устройства; на фиг, 2 - функциональная схема устройства, на которой более подробно раскрыты адресные блоки памяти; на фиг, 3 - функциональная схема устройства, имеющего повышенную производительность при выполнении операций умножения и деления. Изобретение относится к области запоминающих устройств.Известны ассоциативные запоминающие устройства 13 и 25В одном из известных ассоциативных запоминающих устройств арифметические операции над парой чисел выполняются в виде последовательностилогических операций . 1.ОНедостатком этого устройства является малая скорость работы.Из известных устройств наиболее близким техническим решением к данному изобретению является ассоциативное запоминающее устройство, еодер жащее матрицу адресных блоков памяти, элементы ИЛИ, входы которых подключены к выходам регистра опроса и ре. гистра маски, а выходы - к входам дещифраторов опроса, выходы которых сое О динены с адресными шинами адресных блоков памяти соответствующих строк .матрицы, дешифратор операций, выходы которого соединены с входа " управле .ния. выборкой и записью и информационными входами адресных блоков памяти каждого столбца матрицы, сумматоры по Модулю два, выходы которых подключены к разрядным шинам записи адресных блоков памяти, а первые входы к соответствующим выходам дешифратбра операций 2.Недостатком этого устройства является существенное снижение быстродействия при выполнении арифметических операций.Целью изобретения является повышение быстродействия устройства. Поставленная цель достигается тем, что устройство содержит двухканальные переключатели, выходы которых соединены с вторыми и третьими входами сумматоров по модулю два, входы с выходными разрядными шинами соответствующих адресных блоков памяти, управляющие входы двухканальных переключателей и сумматоров по модулю два подключены к соответствующим выходам дешифратора операций..3 0111 1 О 0 1111 010 11 111 Устройство содержит. (см. Фиг. 1)адресные блоки памяти 1, организованные в виде прямоугольной матрицы.Каждый блок 1 содержит, например,четыре адресных запоминающих блока1.1"1,4 или 1.5-1.8 (см. Фиг. 2),которые могут быть выполнены в видеполупроводниковых микросхем. Блоки1.1-1.8 имеют адресные шины 2, выходные разрядные шины 3, разрядные шины4 .записи, входы 5 управления выборкой, входы б управления записью, 1 О инФормационные входы 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. ЗОВходы 5 б и 7 блоков 1 каждого столбца матрицы присоединены к выходам дешиФратора 22 операций, Раз: рядные шины 4 записи блоков 1 подсоединены к выходам сумматоров 23 З 5 по модулю два, первые входы которых соединены с соответствующими выходами дешифратора 22 операций. Группы 13 триггеров 9 регистра 11 выполнены в виде кольцевых регистров сдвига. 4 ф Устройство содержит также двухканальные переключатели 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, проиллюстрируем напримере выполнения операции сложениядвух групп из четырх четырехразрядных чисел с помощью восьми блоков11-18. Каждый из этих блоков вданном примере имеет по четыре адресных шины 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 из й" (1 наФоне йнулей), Преобразование иэпозиционного кода в код 1 из й осуществляется дешиФраторами 20. Во всезапоминающие элементы блоков 1.7,1,3, 1.8 и 1.4 предварительно записывается код "1". Счет выходов дешиФраторов 20 начинается снизу, асчет чисел - слева направо:701349 1.7 1.80001 0110 0001 0111 1,3 1.4 0010 1101 1101 0010 кт 3 КТ 4 Такт 1.8 1000000010000 0000 0000001 1000100 0011010 00011000 1000110010 0 1 1111001111 111 В первом такте на регистры 10опроса первой и второй строки заносится код "11", а на регистры 11маски, соответствующие блокам1.1-1.3 и 1.5 - 1.7, код "10" ч нарегистры 11, соответствующие блокам1.4 и 1.8, в к "01", В результатеу блоков 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 сигнал логического "0",разрешающий считывание из этих блоков, а на входы 6 блоков 1.3, 1.4и 1.7 и 1.8 - сигнал логической "1", 1 Ъразрешающий запись в эти блоки. Блоки 1.7 и 1,3 используются для накопления поразрядной сумми, а блоки1,8 и 1.4 - для накопления переносов. Поразрядная сумма образуется 20путем суммирования пар исходных чисел по модулю два, а переносы - путемлогического умножения пар исходныхчисел со сдвигом на один разрядвлево (имеется ввиду сдвиг исходных р 5позиционных кодов чисел).При выполнении операции суммирования по модулю два на управляющие входы сумматоров 23, соответствующихблокам 1.7 и 1.3, поступают сигналыд = О, а при выполнении операции логического умножения на управляющиевходы сумматоров 23, соответствующихблокам 1.8 и 1.4, - сигналы д=1. Напервые входы этих сумматоров в первоми втором тактах; поступают сигналы- 1. Переключатели 24, соединенныес шинами 4 блоков 1.3 и 1.7, постоянно коммутируются сигналами на управляющих входахдля приема сигналовсоответственно из блоков 1.1, 1.2 и 401.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-ом тактах приведена ниже..3 1,4 1.3 1.4 1,3 1,4 О О 1 О ОООО О О 1 О О О О О О О 1 О ОООО1 О 1 1 1 1 0 1 1 О О 1 1 1 О 1 1 0 0 11 0 О 0 О 0 О О 1 0 0 0 О О О 0 О 0 О 0 1 1 1 1 1 1 1 1 1 1 О 1 О О 1 О 0 1 О 0 О О 1 О Непосредственное сравнение результатов выполнения четвертого такта с ,щ результатами сложения по модулю два и логического умножения позиционных кодов подтверждает правильность их вычисления. Так как содержимое блоков 1.4 и 1.8 отличается от позицион ного кода "0000" или слова "00010001 ф в коде 1 из й, то операция сложения процолжается аналогичным образом до тех пор,пока коды переносов не будут полностью совпадать с кодом "ОООО" для всех чисел, участвующих в данной операции сложения. Для этого во все запоминающие элементы блоков 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, в которых код опроса "111" может быть заменен кодом "000", например, за счет введения в состав каждой группы 21 независимого регистра 10 опроса. Перезапись в прямом коде выполняется как сложение по модулю два с кодом "ОООО", а операция инвертирования - как сложение по модулю два с кодом "1111".Операция вычитания выполняется как сложение с обратным или дополни О тельным кодом вычитаемого. Операции с плавающей запятой выполняются аналогично операциям в сумматорах с плавающей запятой, т,е. за счет вве-, дения ассоциативных разрядов, экви валентных сумматору порядка, которыеФункционируют аналогично устройству,приведенному в данном примере.Работа устройства, приведенногона Фиг. 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,предварительно записываются словас позиционным кодом "000". Далеепроизводится сложение содержимогоблоков 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умножения и деления над двумя про-. извольными массивами чисел, при этом эти операции могут выполняться в различных сочетаниях по одной независимой операции на каждый сточбец матрицы. Следовательно, быстродействие этого устройства по сравнению с известными устройствами при правильном выборе алгоритма записи исходных массивов возрастает на один-два порядка и может быть оценено в несколько десятков миллионов операций в секунду для Устройства емкостью 1024- 4096 слов по 18-72 разряда с единичным циклом опроса и записи порядка 200 нс.15Формула изобретенияАссоциативное запоминающее устройство, содержащее матрицу адресных Щ блоков памяти, элементы ИЛИ, входы которых подключены к выходам регистра опроса и регистра маски, а выходы - к входам дешифраторов опроса, выходы которых соединены с адресными шинами адресных блоков памяти соответствующих строк матрицы, дешифратор операций, выходы которого соединены с входами управления выборкойи записью и инФормационными входамиадресных блоков памяти каждого столбца матрицы, сумматоры по модулю два,выходы которых подключены к разрядным шинам записи адресных блоковпамяти, а первые входы - к соответствующим выходам дешиФратора операций, о т л и ч а ю щ е е с я тем,что, с целью повышения,быстродействия устройства, оно содержит двухканальные переключатели, выходы которых соединены с вторыми и третьимивходами сумматоров по модулю два,входы - с выходными разрядными шинами соответствующих адресных блоковпамяти, управляющие входы двухканальных переключателей и сумматоров помодудю два подключены к соответствующим выходам дешиФратора операций. Источники инФормации,принятые во внимание при экспертизе1. Авторское свидетельство СССРР 493162, кл. 6 11 С 15/00, 1974.2. Авторское свидетельство СССРР 588561, кл. 6 11 С 15/00,. 1975701349 оставитель В. Рудаковехред А Бабинец орректор М. Демч актор Е. Абрамов 20/62 Тираж б 45 Подпи ВНИИПИ Государственного комитета СССР по делам иэобретений и открытий 113035, Москва, Ж, Раушская наб., д 4/5акаэ илиал ППП "Патент", г. Ужгород, ул. Проектная