Запоминающий модуль для матричных блоков памяти

ОП ИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскикСоциалистическихРеспублик(22) Заявлено 16.02.7-м заяв исое ииыи комитет Го 3) Приорите бликовано 07.07.80. Бюллетень2ио делам изооретеиии и открытийДата опубликования описания Авторобретения И. Фе(71) Заявите нститут математики Сибирского отделения АН СССР) ЗАПОМИНАЮЩИЙ МБЛОКОВ ЛЬ ДЛЯ МАТРИЧНЫХМЯТИ 1Изобретение относится к запоминающим устройствам,Известен запоминающий модуль для матричных блоков памяти, содержащий двоичный запоминающий элемент с вентилями записи единицы и нуля, схему сравнения и шину опроса, причем входы схемы сравнения соединены с выходами запоминающего элемента и с шиной опроса.В ассоциативных матрицах, построенных их таких модулей, основной операцией является поиск числа, равного заданному. Все другие вычислительные и информационно-логические операции осуществляются по микропрограммам, состоящим из последовательностей операций поиска и записи. В соответствии с этими микропрограммами обработка ведется последовательно по разрядам и требует значительного времени,Наиболее близок к предлагаемому запоминающий модуль для матричных блоков памяти, содержащий элемент памяти, эле. менты И, ИЛИ и НЕ; схему сравнения, шины опроса, записи и запрета, причем первый и второй входы схемы сравнения соединены соответственно с единичным и нулевым выходами элемента памяти, а третий и четвертый - с шиной опроса и выходом первого элемента НЕ, вход которого соединен с шиной опроса, первые входы элемента памяти подключены к шине записи, шина запрета соединена с первым входом первого элемента И, второй вход которого подключен к первому входу запоминающего модуля, а выход - к первому входу первого элемента ИЛИ, выход которого соединен с первым выходом запоминающего модуля, первый вход второго элемента ИЛИ соединен со вторым входом запоминающего модуля, а выход - со вторым выходом запоминающего модуля, первые входы второго и третьего элементов И соединены с третьим входом запоминающего модуля, второй и третий входы третьего элемента И соединены соответственно с шиной опроса и нулевым выходом элемента памяти, а выход третьего элемента И - со вторыми входами первого и второго элементов ИЛИ.В ассоциативных матрицах, построенных из таких модулей, не только операция поиска по совпадению, но и ряд операций сложного поиска (поиск всех чисел, больших заданного или меньших заданного; поиск числа, ближайшего меньшего к заданномупоиск максимального числа) выполняются аппаратно, за одну микрокоманду. Однако и в этих ассоциативных матрицах более сложные операции (например, массовые арифметические вычисления) осуществляются с помощью микропрограмм, требующих для своего выполнения значительного времени.Целью настоящего изобретения является повышение быстродействия устройства.Поставленная цель достигается тем, что запоминающий модуль содержит четвертый и пятый элементы И, третий, четвертый и пятый элементы ИЛИ, второй элемент НЕ и шины маскирования и настройки, причем шина маскирования соединена с первым входом третьего элемента ИЛИ, второй вход которого подключен к выходу схемы сравнения, а выход - ко второму входу второго элемента И, выход которого соединен с первыми входами четвертого элемента И и четвертого элемента ИЛИ, вторые входы которых подключены к шине настройки, соединенной также через второй элемент НЕ с 20 первым входом пятого элемента И; выход четвертого элемента ИЛИ соединен с третьим выходом запоминающего модуля, второй вход пятого элемента И подключен к четвертому входу запоминающего модуля, а выход - к первому входу пятого элемента ИЛИ, второй вход которого соединен с выходом четвертого элемента И, а выход - с четвертым выходом запоминающего модуля и со вторыми входами элемента памяти, третьи входы которого соединены с ЭО шиной запрета, а четвертые соответственно с шиной опроса и с выходом первого элемента НЕ.На чертеже приведена функционально- логическая схема предложенного запоминающего модуля для матричных блоков памяти,Модуль содержит элемент памяти 1, состоящий из собственно запоминающего элемента 2 и вентилей записи единицы и нуля 3, схему сравнения 4, шину опроса 5, первый элемент НЕ 6, шину записи 7, шину запрета 8, шину маскирования 9, шину настройки 10, второй элемент НЕ 11, первый 12, второй 13, третий 14, четвертый 15и пятый 16 элементы И, первый 17, второй 18,третий 19, четвертый 20 и пятый 21 элементы ИЛИ.Кроме того, описываемый модуль имеет входы 22 - 25 логических переменных ч, у з, е соответственно и выходы 26 - 29 логических переменных ч , у, г, е соответственно. При соединении модулей в матрицу выходы 26 и 28 каждого модуля соеди- няются соответственно со входами 22 и 24соседнего справа модуля, выход 29 - со входом 25 соседнего слева модуля, а выход 2 - со входом 23 соседнего снизу модуля,Первый и второй входы схемы сравнения 4 соединены с соответствующими выходами элемента памяти 1, а третий и четвертый входы - с шиной опроса 5 и с выходом элемента НЕ 6, вход которого соединен с шиной опроса 5. Шина маскирования 9 и выход схемы сравнения 4 соединены со входами элемента ИЛИ 19. Первые входы элементов И 13 и 14 соединены со входом 24. Второй вход элемента И 13 подключен к выходу элемента ИЛИ 19, а второй вход элемента И 14 - к шине опроса 5. Третий вход элемента И 14 соединен с нулевым выходом элемента памяти 1, Выход элемента И 13 соединен с первыми входами элемента И 15 и элемента ИЛИ 20, вторые,входы которых подключены к шине настройки 10. Выход элемента ИЛИ 20 сое-динен с выходом 28, а выход элемента И 15 - со вторым входом элемента ИЛИ 21, выход которого подключен к выходу 29. Первый вход элемента ИЛИ 21 соединен с выходом элемента И 16, входы которого соединены соответственно со входом 25 и через элемент НЕ 11 - с шиной настройки 10. Выход элемента И 14 соединен со вторыми входами элементов ИЛИ 17 и 18. Первый вход элемента ИЛИ 17 соединен с выходом элемента И 12, входы которого подключены соответственно ко входу 22 и к шине запрета 8. Первый вход элемента ИЛИ 18 соединен с входом 23, а выход - с выходом 27. Выход элемента ИЛИ 17 подключен к выходу 26, Первые входы элемента памяти 1 подключены к шине записи 7, вторые - к выходу элемента ИЛИ 21, третьи - к шине запрета 8, а четвертые - соответственно к шине опроса 5 и выходу элемента НЕ 6.Как видно из чертежа, описанный модульреализует следующие логические функции:Ь = ахчах 1)г = г(уча)ч 1 (2)ч = ч 1 чгах (3)у = учгах (4)е = г 1(Ъча) че 1 (5)д = хеи 1 (6)д = хеи 1 (7)где х,1, 1,а, и соответственно - логическиепеременные на шинах опроса5; настройки 10, запрета 8,маскирования 9 и записи 7,а - состояние элемента памяти 1,Ъ - значение двоичной переменнойна выходе схемы сравнения(предполагается, что в= 1 прих=а).В ассоциативной матрице, состоящей измодулей предлагаемой конструкции, могутвыполняться следующие микрокоманды:- запись горизонтальная,- запись вертикальная,- чтение горизонтальное,- чтение дизъюнктивное,- поиск по совпадению,- поиск всех чисел, больших заданного,- поиск всех чисел, меньших заданного,5- чтение вертикальное,- поиск ближайшего меньшего,- поиск максимального числа,- совмещенные поиск-запись.Рассмотрим в качестве примера. выполнение поиска по совпадению и поиска чисел,больших (меньших) заданного.Для выполнения этих поисков на всевходы 24 левой границы матрицы подаютсяконстанты 1, на все входы 22 левой границы - константы 0. На все шины 8подаются константы 1. Состояния входов 23 и шин 10 несущественны.По шинам опроса 5 поступает поразрядно (старшими разрядами слева) код признака опроса, по шинам 9 - код маски (в маскируемых разрядах а = 1).Так как, согласно (2), в каждом модуле г = г(Ьча) ч 1, сигнал г = 1 проходитв каждой строке матрицы до тех пор, пока незамаскированные разряды соответствующих чисел эквивалентны разрядам признака, опроса. В частном случае, в той строке, где содержится число, равное признаку (илинескольких таких строках), на выходе 28 правой границы матрицы появится сигнал 1.Предположим, что какое-либо число совпадает с признаком опроса не по всем незамаскированным разрядам, а лишь по нескольким старшим, после чего имеется разряд, в котором а = О, х = 1. Ясно, что е 15такое число меньше признака опроса, независимо от соотношения дальнейших (млад/ших) разрядов. В том модуле, где впервые а = 0 и х = 1, схема сравнения вырабатывает Ь = О, что приводит к г= О. Однако согласно (3) в этом модуле появляется сигнал ч = 1, который проходит до правой границы матрицы и выдает там ч = 1. ззИтак, в любой строке матрицы, содержащей число, меньшее заданного признака, на правой границе будет г = О, ч = 1.Третий случай - число больше заданного признака. При этом нарушение эквивалентности при просмотре слева направо происходит впервые за счет разряда, в котором а = 1, х = О. В таком модуле также Ь = О, г= О, но ч = 1 не появляется.Следовательно, в любой строке, содержащей число, большее заданного признака, д на правой границе г = О, ч = О.Ассоциативная матрица, построенная из описанных модулей, приобретает новые положительные свойства: в ней может выполняться аппаратно, с большой эффективностью, ряд информационно-логических операций и, кроме того, возможна независимая обработка в различных полях матрицы. Этй свойства обеспечивают повышения быстродействия при решении многих задач.Формула изобретенияЗапоминающий модуль для матричных блоков памяти, содержащий элемент памяти, элементы И, ИЛИ и НЕ, схему сравнения, шины опроса, записи и запрета, причем первый и второй выходы схемы сравнения соединены соответственно с единичным и нулевым выходами элемента памяти, а третий и четвертый - с шиной опроса и выходом первого элемента НЕ, вход которого соединен с шиной опроса, первые входы элемента памяти подключены к шине записи, шина запрета соединена с первым входом первого элемента И, второй вход которого подключен к первому входу запоминающего модуля, а выход - к первому входу первого элемента ИЛИ, выход которого соединен с первым выходом запоминающего модуля, первый вход второго элемента ИЛИ соединен со вторым входом запоминающего модуля, а выход - со вторым выходом запоминающего модуля, первые входы второго и третьего элементов И соединены с третьим входом запоминающего модуля, второй и третий входы третьего элемента И соединены соответственно с шиной опроса и нулевым выходом элемента памяти, а выход третьего элемента И - со вторыми входами первого и второго элементов ИЛИ, отличающийся тем, что, с целью повышения быстродействия запоминающего модуля, он содержит четвертый и пятый элементы И, третий, четвертый и пятый элементы ИЛИ, второй элемент НЕ и шины маскирования и настройки, причем шина маскирования соединена с первым входом третьего элемента ИЛИ, второй вход которого подключен к выходу схемы сравнения, а выход - ко второму входу второго элемента И, выход которого соединен с первыми входами четвертого элемента И и четвертого элемента ИЛИ, вторые входы которых подключены к шине настройки, соединенной также через второй элемент НЕ с первым входом пятого элемента И, выход четвертого элемента ИЛИ соединен с третьим выходом запоминающего модуля, второй вход пятого элемента И подключен к четвертому входу запоминающего модуля, а выход - к первому входу пятого элемента ИЛИ, второй вход которого соединен с выходом четвертого элемента И, а выход - с четвертым выходом запоминающего модуля и со вторыми входами элемента памяти, третьи входы которого соединены с шиной запрета, а четвертые - соответственно с шиной опроса и с выходом первого элемента НЕ.. Шуф2 ного ений Рау жго Состав Редактор Б. федотов Техред К Заказ 3960/45 Тираж 6 ЦНИИПИ Государствен по делам изобрет 113035, Москва, Ж - 35,Филиал ППП Патент г. УВ. Рудаковрич Корректор В. СиниПодписноекомитета СССРи открытийшская наб., д. 4/5од, ул. Проектная, 4