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

НИИ, шифратор 10, pci истр 16 ассоциативных признаков, элемент ИЛИ 28 и элемент задержки 29. Блок 7 поиска совпадений содержит элемент ИЛИ, два элемента задержки и п логических узлов (где п - число разрядов регистра 1 числа), каждый из которых содержит четыре элемента И, два элемента НЕ и три элемента ИЛИ. При записи числа в устройство в ячейку накопителя 4, определяемую старшим разрядом записываемого через регистр 5 числа, и в разряд, определяемый его младшими разрядами, записывается единица, а при исключении числа из памяти - нуль. Осу- шествляется поиск по совпадению с числом, задаваемым на входах регистра 5, а также поиск числа, ближайшего большего (или меньшего) к заданному числу. В режимах поиска по совпадению и ближайшего большего коммутатор 6 подает на информационные входы блока 7 считанный из на1

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

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

На фиг. 1 представлена функциональная схема предлагаемого устройства; на фиг. 2 - функциональная схема блока поиска совпадений.

Устройство содержит первый регистр 1 числа, реверсивный счетчик 2, первый дешифратор 3, матричный накопитель 4, второй регистр 5 числа, первый коммутатор 6, блок 7 поиска совпадений с информационными входами 8i-8п и выходами 9i-9п (где п - число разрядов регистра 1 числа) и шифратор 10. На фиг. 1 обозначены информационные выходы 11 устройства, вхор,ы 12i-12п ассоциативного признака и группа выходов 13i-13« блока 7 поиска совпадений.

Устройство содержит, кроме того, второй коммутатор 14, второй дешифратор 15 и регистр 16 ассоциативных признаков.

На фиг. 1 обозначены также вход 17 начала работы, вход 18 ассоциативного поиска слова, ближайшего к заданному, вход 19 задания вида ассоциативного поиска, выходы 20 и 21 ассоциативного ответа, вход 22 записи данных и вход 23 исключения данных устройства, выходы 24-24 с первого

копителя 4 код в порядке его возрастания, а при поиске ближайшего меньшего - в порядке убывания. На другие входы блока 7 в таком же порядке поступает ассоциативный признак, сформированный дешифратором 15 из младших разрядов заданного слова и содержаш.ий только одну единицу. В блоке 7 выполняется сравнение этих кодов и поиск ячейки накопителя 4, в соответствуюшем разряде которого записана единица. При этом поисковый сигнал распространяется по п логическим узлам до того узла, на информационый вход которого подана считанная единица. Счетчик 2 служит для перебора адресов накопителя 4 при поиске. Найденное число формируется из старших разрядов заданного числа, снимаемых с выходов счетчика 2, и младших разрядов числа, восстанавливаемых шифратором. 10 2 з.п.ф-лы. 2 ил.

по третий блока 7 поиска совпадений и информационные входы 27 устройства.

В состав устройства входят также элемент ИЛИ 28 и элемент 29 задержки.

Блок 7 поиска совпадений содержит (фиг. 2) логические узлы 30i-ЗОп, элемент ИЛИ 31, а также первый 32 и второй 33 элементы задержки.

Каждый логический узел 30 выполнен в виQ де первого элемента НЕ 34, элементов И 35-37 с первого по третий, первого элемента ИЛИ 38, четвертого элемента И 39, второго элемента НЕ 40, второго 41 и третьего 42 элементов ИЛИ. На фиг. 2 обозначена шина 43 нулевого потенциала.

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

-. ближайшего (большего или меньшего; к заданному.

В режиме записи записываемое слово через входы 27 (фиг. 1) заносится в регистр 5, на входы 18 и 22 подаются потенциалы единичного уровня, а на входы 19 и 23 - ну5 левого. По сигналу начала операции на входе 17 старшие разряды записываемого слова заносятся в счетчик 2 и далее, де- шифрируясь дешифратором 3, поступают на входы накопителя 4; младшие разряды записываемого слова дешифрируются дешифра0 тором- 15 и фиксируются на регистре 16. Сигналом с выхода элемента 29 задержки

инициируется считывание на информационные шины накопителя 4 слова, адрес которого соответствует старшим разрядам записываемого слова. Считанное таким образом п-разрядное слово фиксируется на регистре 1. Под управлением единичного потенциала на входе 18 коммутаторы 6 и 14 формируют на своих выходах коды, идентичные содержимому соответственно регистров 1и

16, а i-e выходы коммутаторов 6 и 14 (,п) коммутируются сигналы с первых из i-x пар входов коммутаторов 6 и 14, которые поступают через входы соответственно 8:-п и 13|-и на блок 7. По входам 13i - 13п на блок 7 подается код, содержащий только одну единицу, расположенную, например, в

10

деляемой старшими разрядами исключаемого слова, в разряде, определяемом его младшими разрядами, фиксируется «О, свиде- тельствуюш,ий об отсутствии указанного слова в памяти.

В режиме поиска по совпадению заданное число по входам 27 записывается в регистр 5. На входы 19, 22 и 23 подаются сигналы нулевого уровня, а на вход 18 - потенциал единичного уровня. На блок 7 аналогично описанному по входам 8i-8п и 13i - 13п подаются коды, хранящиеся соответственно на регистрах 1 и 16. Пусть например, I - номер входа 13, по которому подается единица. Тогда на выходах

F-M разряде (Еб(1, п)). Тогда на выходе 9к(к${1,п}, ) формируется нуль, так как 12j формируется единица (на входы элемента И 39 узла ЗОе подаются обе единицы, соответственно на выходах элементов И 39 и ИЛИ 42 узла 30f формируется «1, поступающая на выход 12г). На остальных выходах 12 формируется код, идентичный поступающему по входам 8i-8п) в каждом соответствующем узле 30 элемент И 39 закрыт нулевым потенциалом по входу 13, а элемент И 35 открыт единичным сигналом для прохождения сигнала с входа 8, следовательно, на выходе элементов И 35, ИЛИ 42 и соответствующем выходе 12 формируется сигнал, идентичный подаваемому на вход 8). С выхода 26 снимается по прошествии времени, необходимого для формирования сигналов на выходах 12 блока 7 определяемого элементом 32 задержки, сигнал, по которому код с входов 12 переписывается на регистр 1, а через время, определяемое элементом 33 задержки, на выходе 25 формируется сигнал, по которому содержимое регистра 1 переписывается в ячейку накопителя 4, определяемую старшим разрядом записываемого в устройство слова. Таким образом, в ячейке, определяемой старшими разрядами записываемого слова, в разряде, опрена выходах элементов И 37 всех узлов 30 формируются потенциалы нулевого уровня, поскольку нуль подается на вход 19, следовательно, на выходах всех элементов ИЛИ 38 узлов 30k формируются нулевые потенциа20 лы, которыми устанавливаются в «О выходы соответствующих элементов И 36. На выходе 9{ блока 7 формируется сигнал, идентичный поступающему на вход 8j (элемент,ИЛИ 38 узла 30{ формирует на своем

25 выходе единицу, поскольку единица пришла на его вход 13,, следовательно, он открыт для прохождения сигнала с входа 8f). Соответственно, единичный потенциал формируется и на выходе 21, есди на вход 8 поступает единица (т.е. слово, идентичное

30 записанному на регистре 5, хранится в устройстве). В противном случае на выходе 21 формируется нуль, свидетельствующий о том, что заданное слово не хранится в устройстве. В режиме ближайшего большего заданное слово заносится в регистр 5, на

35 входы 18 и 19 подается сигнал единичного уровня, а на входы 22 и 23 - нулевого. На блок 7 по входам 8i-8л и 13i-13п подаются коды, хранящиеся на регистрах соответственно 1 и 16. На выходах 9г ()

деляемом младшими разрядами записывае-формируются потенциалы нулевого уровня

МПГППППДЯ Жн Т РНПЛ/РТРС л-1 v fRLT ПРТР .- 4U „„,, ,,«,, ,,« r..r гт л-i, ттл.,,1тг.. ТЛ П1Л Qft I/

мого слова, фиксируется «1, свидетельствующая о наличии этого слова в памяти.

В режиме исключения слова из памяти на входы 22 и 19 подается потенциал нулевого уровня, а на входы 18 и 23 - единичного. Устройство функционирует в указанном режиме аналогично описанному для режима записи, с тем исключением, что на выходе 12 блока 7 всегда формируется нулевой сигнал (элемент И 39 узла 30 закрыт нулевым потенциалом по входу 22, элемент И 35 закрыт нулевым потенциалом с выхода элемента НЕ 40, следовательно, на выходах элементов И 39 и 35, ИЛИ 42 формируется нулевой сигнал, который передается на выход 12(). На остальных выходах 12 формируется код, идентичный подаваемому на входы Si-n, запись скорректированного таким o6pa3PN слова осуществляется аналогично описаинс-чу. Таким образом, в ячейке, опре45

50

55

так как на выходах элементов ИЛИ 38, И 37 соответствующих узлов ЗОг формируется потенциал нулевого уровня. На выходе 9i единичный сигнал формируется только в том случае, если на вход 8 по дан сигнал единичного потенциала, т.е. если в устройстве хранится число, совпадающее с заданным, которое и является ближай шим большим, код его формируется на вы ходе 11 устройства, а сигнал на вы.чоде 21 свидетельствует о том, что ближайщее слово найдено. Если на вход 8е подается нулевой потенциал (заданное слово не хра нится в устройстве), то на выходах эле мента и 37 и ИЛИ 38 узла ЗОе формируется единичный сигнал, который передается на вход элемента ИЛИ 38 последующего узла . Если на вход 8e подается сигнал нулевого уровня, то единичный сигнал формиру ется на выходе элемента И 37 узла 30p,i и

деляемой старшими разрядами исключаемого слова, в разряде, определяемом его младшими разрядами, фиксируется «О, свиде- тельствуюш,ий об отсутствии указанного слова в памяти.

В режиме поиска по совпадению заданное число по входам 27 записывается в регистр 5. На входы 19, 22 и 23 подаются сигналы нулевого уровня, а на вход 18 - потенциал единичного уровня. На блок 7 аналогично описанному по входам 8i-8п и 13i - 13п подаются коды, хранящиеся соответственно на регистрах 1 и 16. Пусть например, I - номер входа 13, по которому подается единица. Тогда на выходах

9к(к${1,п}, ) формируется нуль, так как

на выходах элементов И 37 всех узлов 30 формируются потенциалы нулевого уровня, поскольку нуль подается на вход 19, следовательно, на выходах всех элементов ИЛИ 38 узлов 30k формируются нулевые потенциа20 лы, которыми устанавливаются в «О выходы соответствующих элементов И 36. На выходе 9{ блока 7 формируется сигнал, идентичный поступающему на вход 8j (элемент,ИЛИ 38 узла 30{ формирует на своем

25 выходе единицу, поскольку единица пришла на его вход 13,, следовательно, он открыт для прохождения сигнала с входа 8f). Соответственно, единичный потенциал формируется и на выходе 21, есди на вход 8 поступает единица (т.е. слово, идентичное

30 записанному на регистре 5, хранится в устройстве). В противном случае на выходе 21 формируется нуль, свидетельствующий о том, что заданное слово не хранится в устройстве. В режиме ближайшего большего заданное слово заносится в регистр 5, на

35 входы 18 и 19 подается сигнал единичного уровня, а на входы 22 и 23 - нулевого. На блок 7 по входам 8i-8л и 13i-13п подаются коды, хранящиеся на регистрах соответственно 1 и 16. На выходах 9г ()

формируются потенциалы нулевого уровня

U „„,, ,,«,, ,,« r..r гт л-i, ттл.,,1тг.. ТЛ П1Л Qft I/

5

0

5

так как на выходах элементов ИЛИ 38, И 37 соответствующих узлов ЗОг формируется потенциал нулевого уровня. На выходе 9i единичный сигнал формируется только в том случае, если на вход 8 подан сигнал единичного потенциала, т.е. если в устройстве хранится число, совпадающее с заданным, которое и является ближайшим большим, код его формируется на выходе 11 устройства, а сигнал на вы.чоде 21 свидетельствует о том, что ближайщее слово найдено. Если на вход 8е подается нулевой потенциал (заданное слово не хранится в устройстве), то на выходах элемента и 37 и ИЛИ 38 узла ЗОе формируется единичный сигнал, который передается на вход элемента ИЛИ 38 последующего узла . Если на вход 8e подается сигнал нулевого уровня, то единичный сигнал формируется на выходе элемента И 37 узла 30p,i и

поступает на вход элемента ИЛИ 38 узла

.

Таким образом, сформированный на выходе элемента И 37 узла ЗОе сигнал передается через последующее логические узлы 30, если на их входы 8 будут подаваться сигналы нулевого потенциала. При поступлении сигнала на вход элемента ИЛИ 38 узла 30, на вход 8 которого поступает единица, формируется сигнал единичного уров23 и 18 - нулевого. Соответственно коммутаторы 6 и 14 коммутируют на свои i-e выходы сигналы, подаваемые на их соответствующие четные входы, т.е. на выходе коммутатора 6 формируется код, i-й разряд которого соответствует (п-1+1)-му разряду регистра 1, а на выходе коммутатора 14 формируется код, i-й разряд которого соответствует (п-1+1)-му разряду регистра 16. Таким образом, коммутаторы 6 и 14 преня на выходе элемента И 36 и на соответ-Ю образуют поступающие с регистров слова так,

етвующем выходе 9, а на выходе элементачто младщие и старщие разряды меняются

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

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

НОИ, за исключением того, что при проявлении сигнала на выходе 24 содержимое счетчика 2 уменьшается на единицу.

В режимах поиска сигналы с выходов

то сигнал на выходе элемента И 37 узла ЗОи 20 25 и 26 блока 7 не генерируются, а поэтому поступает на выход 24 блока 7, увеличи- запись в регистре 1 по входам 12 не произ- вает на единицу содержимое счетчика 2 и, водится, пройдя через элемент ИЛИ 28 и элемент 29 задержки, инициирует считывание из накопителя 4 числа, старщие разряды которого на единицу больше старших разрядов задан- кого числа. Одновременно сигнал с выхода 24 устанавливает все разряды регистра 16 в нуль. Коды с регистров 1 и 16 через коммутаторы 6 и 14 поступают на входы соответственно 8i-8п и 13i - 13п блока 7, причем единица подается по входу 13i. В этом случае процесс прохождения сигнала поиска через узлы 30 начинается с узла 30i и продолжается до тех пор, пока не будет найден узел 30, на вход 8 которого поступает единица. Если такой узел 30 не найден, то вновь формируется сигнал на выходе 24 и описанный процесс повторяется для следующего адреса. Если в устройстве нет чисел, больших заданного, то счет30

35

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

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

чик 2 формирует сигнал переполнения на

другие информационные выходы с первого

выходе 20, свидетельствующий об отсутствии 40 по п-й первого регистра числа подключены искомого числа в устройстве, т.е. об отри- к нечетным информационным входам перво- цательном результате поиска, при этом на го коммутатора, четные информационные выходе устанавливается сигнал нулевого входы которого соединены с другими инфор- уровня. Если на каком-либо из этапов опи-мационными выходами с п-го по первый персанного процесса поиска будет найден узел вого регистра числа, выходы первого комму- 30, на вход которого 8 подается единичный татора подключены к информационным вхо- потенциал, процесс поиска прекращается, дам блока поиска совпадений, информационные выходы которого соединены с входами шифратора, а входы ассоциативных признаков - с выходами второго коммутатора, нечетные информационные входы которого подключены к выходам с первого по п-й, а четные информационные входы - к выходам с п-го по первый регистра ассоциативных признаков, информационные входы которого соединены с выходами второго 55 дешифратора, входы которого подключены к выходам младших разрядов второго регистра числа, выходы старших разрядов которого соединены с информационными вхотак как блокируется выдача сигнала элементом И 37, и формируется единичный сигнал на соответствующем выходе 9 и на выходе 21. Код на выходах 9i-9п шифруется шифратором 10 и поступает на младшие разряды выходов 11, на старших разрядов которых присутствует код счетчика 2, т.е. код старших разрядов числа, ближайщего к заданному.

В режиме поиска чисЛа, ближайшего меньшего к заданному, на вход 19 подается сигнал елиничного уровня, а на входы 22,

50

23 и 18 - нулевого. Соответственно коммутаторы 6 и 14 коммутируют на свои i-e выходы сигналы, подаваемые на их соответствующие четные входы, т.е. на выходе коммутатора 6 формируется код, i-й разряд которого соответствует (п-1+1)-му разряду регистра 1, а на выходе коммутатора 14 формируется код, i-й разряд которого соответствует (п-1+1)-му разряду регистра 16. Таким образом, коммутаторы 6 и 14 преобразуют поступающие с регистров слова так,

20 25 и 26 блока 7 не генерируются, а поэтому запись в регистре 1 по входам 12 не произ- водится,

30

35

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

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

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

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

го, вход запуска реверсивного счетчика и 15 логических узлов объединены и являются

вход опроса регистра ассоциативных признаков объединены и являются входом начала работы устройства, управляющие входы коммутаторов и вход управления реверсом

входом опроса блока.

3. Устройство по пп. 1 и 2, отличающееся тем, что каждый логический узел содержит четыре элемента И, три элемента ИЛИ

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

мента НЕ и первые входы первого и второго элементов И объединены и являются первым входом логического узла, выход первого элемента НЕ соединен с первым входом третьего элемента И, выход первого

вход опроса и четвертый выход которого 25 элемента ИЛИ подключен к вторым входам

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

выходы разрядов которого, выходы шифра- 30 нен с первым входом третьего элемента

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

тора и входы второго регистра числа являются соответственно информационными выходами и входами устройства.

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

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

входами ассоциативнь1х признаков и груп-40 элемента ИЛИ, третьего элемента И и втопой выходов блока, причем третьи входырого элемента ИЛИ являются соответстлогических узлов и первый вход элементавенно выходами с второго по четвертый

ИЛИ объединены и являются первым вхо-логического узла.

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

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

логических узлов объединены и являются

входом опроса блока.

3. Устройство по пп. 1 и 2, отличающееся тем, что каждый логический узел содержит четыре элемента И, три элемента ИЛИ

Д элемента НЕ, причем вход первого эле Д элемента НЕ, причем вход первого элемента НЕ и первые входы первого и второго элементов И объединены и являются первым входом логического узла, выход первого элемента НЕ соединен с первым входом третьего элемента И, выход первого

элемента ИЛИ подключен к вторым входам

нен с первым входом третьего элемента

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

Ч) ID CMQ |

.0

Nj

cvi -i;

t

Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано в цифровых системах параллельной обработки информации. Целью изобретения является расширение функциональных возможностей устройства за счет реализации поиска числа, ближайшего к заданному. Устройство содержит два регистра 1,5 числа, реверсивный счетчик 2, матричный накопитель 4, два дешифратора 3, 15, два коммутатора 6, 14, блок 7 поиска совпаде(Л со ю 4 Фаг шг 2 79 2S 21