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

,ЯО,324071 А 50411 С ПИСАНИЕ ИЗОБРЕТЕН ий институт ой социалиста Зеебау А. Иван ССС 982,СУДАРСТВЕННЫЙ НОМИТЕТ ССС О ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫ 8 ТОРСКОМУ СВИДЕТЕЛЬСТВ(71) Киевский политехничесим. 50-летия Великой Октябрьстической революции(56) Авторское свидетельство928414, кл. б 11 С 15/00,Авторское свидетельство С978197, кл. б 11 С 15/00,(54) АССОЦИАТИВНОЕ ОПЕРАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано в цифровых системах параллельной обработки информации. Целью изобретения является расширение функциональных возможностей устройства за счет реализации поиска числа, ближайшего к заданному. Устройство содержит два регистра 1,5 числа, реверсивный счетчик 2, матричный накопитель 4, два дешифратора 3,5, два коммутатора 6, 14, блок 7 поиска совпаде1324071 ний, шифратор 10, ре. истр 16 ассоциативных признаков, элемент ИЛИ 28 и элемент задержки 29. Блок 7 поиска совпадений содержит элемент ИЛИ, два элемента задержки и и логических узлов (где и - число разрядов регистра 1 числа), каждый из которых содержит четыре элемента И, два элемента НЕ и три элемента ИЛИ. Г 1 ри записи числа в устройство в ячейку накопителя 4, определяемую старшим разрядом записываемого через регистр 5 числа, и в разряд, определяемый его младшими разрядами, записывается единица, а при исключении числа из памяти - нуль. Осуществляется поиск по совпадению с числом, задаваемым на входах регистра 5, а также поиск числа, ближайшего большего (или меньшего) к заданному числу. В режимах поиска по совпадению и ближайшего большего коммутатор 6 подает на информационные входы блока 7 считанный из наИзобретение отйосится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано в цифровых системах параллельной обработки информации.Цель изобретения - расширение функциональных возможностей устройства за счет реализации поиска числа, ближайшего к заданному.На фиг. 1 представлена функциональная схема предлагаемого устройства; на фиг. 2 - функциональная схема блока поиска совпадений.Устройство содержит первый регистр 1 числа, реверсивный счетчик 2, первый дешифратор 3, матричный накопитель 4, второй регистр 5 числа, первый коммутатор 6, блокпоиска совпадений с информационными входами 8 - 8 п и выходами 9 - 9 п (где п - число разрядов регистра 1 числа) и шифратор 10. На фиг. 1 обозначены информационные выходы 11 устройства, входы 12 - 12 п ассоциативного признака и группа выходов 13 - 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 задержки.5 Блок 7 поиска совпадений содержит(фиг. 2) логические узлы 30 в 3, элемент ИЛИ 31, а также первый 32 и второй 33 элементы задержки.Каждый логический узел 30 выполнен в ви де первого элемента 11 Е 34, элементов И35 - 37 с первого по третий, первого элемента ИЛИ 38, четвертого элемента И 39, второго элемента НЕ 40, второго 41 и третьего 42 элементов ИЛИ. На фиг. 2 обозначена шина 43 нулевого потенциала.15 Устройство работает следующим образом.Устройство может работать в одном изчетырех режимв: записи числа в память, исключения числа из памяти, поиска числа, совпадающего с заданным, и поиска числа, ближайшего (большего или меньшего 1 к заданному.В режиме записи записываемое словочерез входы 2 (фиг. 1) заносится в регистр 5, на входы 18 и 22 подаются потенциалы единичного уровня, а на входы 19 и 23 - ну левого. По сигналу начала операции навходе 17 старшие разряды записываемого слова заносятся в счетчик 2 и далее, дешифрируясь дешифратором 3, поступают на входы накопителя 4; младшие разряды записываемого слова дешифрируются дешифра тороми фиксируются на регистре 16.Сигналом с выхода элемента 29 задержки3инициируется считывание на информационные шины накопителя 4 слова, адрес которого соответствует старшим разрядам записываемого слова. Считанное таким образом и-разрядное слово фиксируется на регистре 1, Под управлением единичного потенциала на входе 18 коммутаторы 6 и 14 формируют на своих выходах коды, идентичные содержимому соответственно регистров 1 и 16, а 1-е выходы коммутаторов 6 и 14 (1=1 и) коммутируются сигналы с первых из 1-х пар входов коммутаторов 6 и 14, которые поступают через входы соответственно 8- и 13на блок 7. По входам 13 - 13 на блок 7 подается код, содержащий только одну единицу, расположенную, например, в 1-м разряде (161, п . Тогда на выходе 12, формируется единица (на входы элемента И 39 узла 30, подаются обе единицы, соответственно на выходах элементов И 39 и ИЛИ 42 узла 30, формируется 1, поступающая на выход 12,). На остальных выходах 12 формируется код, идентичный поступающему по входам 8 - 8 П) в каждом соответствующем узле 30 элемент И 39 закрыт нулевым потенциалом по входу 13, а элемент И 35 открыт единичным сигналом для прохождения сигнала с входа 8, следовательно, на выходе элементов И 35, ИЛИ 42 и соответствующем выходе 12 формируется сигнал, идентичный подаваемому на вход 8). С выхода 26 снимается по прошествии времени, необходимого для формирования сигналов на выходах 12 блока 7 определяемого элементом 32 задержки, сигнал, по которому код с входов 12 переписывается на регистр 1, а через время, определяемое элементом 33 задержки, на выходе 25 формируется сигнал, по которому содержимое регистра 1 переписывается в ячейку накопителя 4, определяемую старшим разрядом записываемого в устройство слова. Таким образом, в ячейке, определяемой старшими разрядами записываемого слова, в разряде, определяемом младшими разрядами записываемого слова, фиксируется 1, свидетельствующая о наличии этого слова в памяти.В режиме исключения слова из памяти на входы 22 и 19 подается потенциал нулевого уровня, а на входы 18 и 23 - единичного. Устройство функционирует в указанном режиме аналогично описанному для режима записи, с тем исключением, что на выходе 12 блока 7 всегда формируется нулевой сигнал (элемент И 39 узла 30 закрыт нулевым потенциалом по входу 22, элемент И 35 закрыт нулевым потенциалом с выхода элемента НЕ 40, следовательно, на выходах элементов И 39 и 35, ИЛИ 42 формируется нулевой сигнал, который передается на выход 12,). На остальных выходах 12 формируется код, идентичный подаваемому на входы 8-, запись скорректированного таким образо ч слова осуществляется аналогично описаннс ",. Таким образом, в ячейке, опре деляемой старшими разрядами исключаемого слова, в разряде, определяемом его младшими разрядами, фиксируется О, свидетельствующий об отсутствии указанного слова в памяти.5В режиме поиска по совпадению заданное число по входам 27 записывается в регистр 5. На входы 19, 22 и 23 подаются сигналы нулевого уровня, а на вход 18 - потенциал единичного уровня. На блок 7 ана логично описанному по входам 8 - 8 п и13, - 13 П подаются коды, хранящиеся соответственно на регистрах 1 и 16. Пусть например, 1 - номер входа 13, по которому подается единица. Тогда на выходах 15 9(кб(1 п) кФ 3) формируется нуль так какна выходах элементов И 37 всех узлов 30 формируются потенциалы нулевого уровня, поскольку нуль подается на вход 19, спедовательно, на выходах всех элементов ИЛИ 38 узлов 30 к формируются нулевые потенциа лы, которыми устанавливаются в О выходы соответствующих элементов И 36. На выходе 9 блока 7 формируется сигнал, идентичный поступающему на вход 8 (элемент,ИЛИ 38 узла 30, формирует на своем 25 выходе единицу, поскольку единица пришлана его вход 13, следовательно, он открыт для прохождения сигнала с входа 8). Соответственно, единичный потенциал формируется и на выходе 21, есди на вход 8 поступает единица (т.е. слово, идентичное 30 записанному на регистре 5, хранится в устройстве). В противном случае на выходе 21 формируется нуль, свидетельствующий о том, что заданное слово не хранится в устройстве.В режиме ближайшего большего за 35 40 45 50 55 данное слово заносится в регистр 5, на входы 18 и 19 подается сигнал единичного уровня, а на входы 22 и 23 - нулевого. На блок 7 по входам 8, - 8 п и 13 в 1 подаются коды, хранящиеся на регистрах соответственно 1 и 16, На выходах 9. (1(г формируются потенциалы нулевого уровня, так как на выходах элементов ИЛИ 38, И 37 соответствующих узлов 30 г формируется потенциал нулевого уровня. На выходе 9 единичный сигнал формируется только в том случае, если на вход 8 подан сигнал единичного потенциала, т.е, если в устройстве хранится число, совпадающее с заданным, которое и является ближайшим большим, код его формируется на выходе 11 устройства, а сигнал на выходе 21 свидетельствует о том, что ближайшее слово найдено. Если на вход 8 подается нулевой потенциал (заданное слово не хранится в устройстве), то на выходах элемента и 37 и ИЛИ 38 узла 30, формируется единичный сигнал, который передается на. вход элемента ИЛИ 38 последующего узла 30 р+. Если на вход 8, подается сигнал нулевого уровня, то единичный сигнал формируется на выходе элемента И 37 узла 30 и5поступает на вход элемента ИЛИ 38 узла ЗОм.Таким образом, сформированный на выходе элемента И 37 узла 30 е сигнал передается через последующее логические узлы 30, если на их входы 8 будут подаваться сигналы нулевого потенциала, При поступлении сигнала на вход элемента ИЛИ 38 узла ЗО, на вход 8 которого поступает единица, формируется сигнал единичного уровня на выходе элемента И 36 и на соответствующем выходе 9, а на выходе элемента И 37 остается нулевой потенциал, т.е. передача сигнала поиска через узлы 30 прекращается. Единица, поступающая в рассматриваемом случае на вход 8, соответствует числу, ближайшему большему заданного. Если на все входы 8,поступают сигналы нулевого уровня, что соответствует отсутствию чисел больших заданного и отличающихся от заданного только младшими разрядами, то сигнал на выходе элемента И 37 узла ЗО поступает на выход 24 блока 7, увеличивает на единицу содержимое счетчика 2 и, пройдя через элемент ИЛИ 28 и элемент 29 задержки, инициирует считывание из накопителя 4 числа, старшие разряды которого на единицу больше старших разрядов заданного числа. Одновременно сигнал с выхода 24 устанавливает все разряды регистра 16 в нуль, Коды с регистров 1 и 16 через коммутаторы 6 и 14 поступают на входы соответственно 8 - 8 п и 13, - 13. блока 7, причем единица подается по входу 13. В этом случае процесс прохождения сигнала поиска через узлы 30 начинается с узла 30 и продолжается до тех пор, пока не будет найден узел 30, на вход 8 которого поступает единица. Если такой узел 30 не найден, то вновь формируется сигнал на выходе 24 и описанный процесс повторяется для следующего адреса, Если в устройстве нет чисел, больших заданного, то счетчик 2 формирует сигнал переполнения на выходе 20, свидетельствующий об отсутствии искомого числа в устройстве, т.е. об отрицательном результате поиска, при этом на выходе устанавливается сигнал нулевого уровня. Если на каком-либо из этапов описанного процесса поиска будет найден узел 30, на вход которого 8 подается единичный потенциал, процесс поиска прекращается, так как блокируется выдача сигнала элементом И 37, и формируется единичный сигнал на соответствующем выходе 9 и на выходе 21. Код на выходах 9 - 9, шифруется шифратором 10 и поступает на младшие разряды выходов 11, на старших разрядов которых присутствует код счетчика 2, т.е. код старших разрядов числа, ближайшего к заданному.В режиме поиска чистка, ближайшегоменьшего к заданному, на вход 19 подается сигнал елиничного уровня, а на входы 22, 23 и 18 - нулевого. Соответственно коммутаторы 6 и 14 коммутируют на свои 1-е выходы сигналы, подаваемые на их соответствующие четные входы, т.е. на выходе коммутатора 6 формируется код, 1-й разряд которого соответствует (и - 1+1) -му разряду регистра 1, а на выходе коммутатора 14 формируется код, 1-й разряд которого соответствует (и - 1+1) -му разряду регистра 16. Таким образом, коммутаторы 6 и 14 преобразуют поступающие с регистров слова так, что младшие и старшие разряды меняются местами. Соответственно, при поиске ближайшего меньшего числа перенос с выхода элемента И 37 узла 30 распространяется в сторону, соответствующую младшим раврядом. Процедура поиска аналогична описанной, за исключением того, что при проявлении сигнала на выходе 24 содержимое счетчика 2 уменьшается на единицу.В режимах поиска сигналы с выходов 25 и 26 блока 7 не генерируются, а поэтому запись в регистре 1 по входам 12 не производится. 5 10 15 20 Формула изобретения 25 1. Ассоциативное оперативное запоминающее устройство, содержащее матричный накопитель, два дешифратора, два регистра числа и элемент ИЛИ, причем выходы первого дешифратора подключены к адресным входам матричного накопителя, информационные входы и выходы которого соединены с одними из информационных выходов и входов первого регистра числа, отличающееся тем, что, с целью расширения функциональных возможностей устройства за счет реализации поиска числа, ближайшего к заданному, в него введены реверсивный счетчик, регистр ассоциативных признаков, коммутаторы, шифратор, блок поиска совпадений и элемент задержки, причем другие информационные выходы с первого 40 по и-й первого регистра числа подключенык нечетным информационным входам первого коммутатора, четные информационные входы которого соединены с другими информационными выходами с и-го по первый первого регистра числа, выходы первого комму татора подключены к информационным входам блока поиска совпадений, информационные выходы которого соединены с входами шифратора, а входы ассоциативных признаков - с выходами второго коммутатора, нечетные информационные входы которого подключены к выходам с первого по и-й, а четные информационные входы - к выходам с и-го по первый регистра ассоциативных признаков, информационные входы которого соединены с выходами второго 55 дешифратора, вод котороо подклюеык выходам младших разрядов второго регистра числа, выходы старших разрядов которого соединены с информационными вхо 1324071дами реверсивного счетчика, выходы разрядов которого подключены к входам первого дешифратора, группа выходов блока поиска совпадений соединена с другими информационными входами первого регистра числа, первый выход блока поиска совпадений соединен со счетным входом реверсивного счетчика, первым входом элемента ИЛИ и входом установки в О регистра ассоциативных признаков, а второй и третий выходы блока поиска совпадений - соответственно с входами записи матричного накопителя и первого регистра числа, входы чтения которых подключены к выходу элемента задержки, вход которого соединен с выходом элемента ИЛИ, второй вход которого, вход запуска реверсивного счетчика и вход опроса регистра ассоциативных признаков объединены и являются входом начала работы устройства, управляющие входы коммутаторов и вход управления реверсом реверсивного счетчика объединены и являются входом ассоциативного поиска слова, ближайшего к заданному, устройства, входами записи и исключения данных которого являются первый и второй входы разрешения записи блока поиска совпадений, вход опроса и четвертый выход которого являются входом задания вида ассоциативного поиска и одним из выходов ассоциативного ответа устройства, другим выходом ассоциативного ответа которого является выход переполнения реверсивного счетчика, выходы разрядов которого, выходы шифратора и входы второго регистра числа являются соответственно информационными выходами и входами устройства.2. Устройство по п. 1, отличающееся тем, что блок поиска совпадений содержит элемент ИЛИ, два элемента задержки и и логических узлов, первые входы и выходы которых являются соответственно информационными входами и выходами блока, а вторые входы и выходы - соответственно входами ассоциативных признаков и группой выходов блока, причем третьи входы логических узлов и первый вход элемента ИЛИ объединены и являются первым входом разрешения записи блока, вторым входом разрешения записи которого является второй вход элемента ИЛИ, выход которого соединен с входом первого элемента задержки, выход которого подключен к входу вто рого элемента задержки, третий и четвертыйвыходы каждого предыдушего логического узла подключены соответственно к четвертому и пятому входам последующего логического узла, четвертый и пятый входы 1 О первого логического узла соединены с шиной нулевого потенциала, третий выход и-го логического узла, выходы второго и первого элементов задержки и четвертый выход и-го логического узла являются выходами с первого по четвертый блока, шестые входы 15 логических узлов объединены и являютсявходом опроса блока.3. Устройство по пп. 1 и 2, отличающеесятем, что каждый логический узел содержит четыре элемента И, три элемента ИЛИ 20 и два элемента НЕ, причем вход первого элемента НЕ и первые входы первого и второго элементов И объединены и являются первым входом логического узла, выход первого элемента НЕ соединен с первым входом третьего элемента И, выход первого 25 элемента ИЛИ подключен к вторым входам, второго и третьего элементов И, выходвторого элемента И соединен с первым входом второго элемента ИЛИ, выход второго элемента НЕ подключен к второму входу первого элемента И, выход которого соедиЗ 0 нен с первым входом третьего элементаИЛИ, второй вход которого подключен к выходу четвертого элемента И, первый вход которого, вход второго элемента НЕ и первый вход первого элемента ИЛИ объединены и являются вторым входом логичесЗ 5 кого узла, второй вход четвертого элементаИ, вторые входы первого и второго элементов ИЛИ и третий вход второго элемента И являются соответственно входами с третьего по шестой логического узла, выходы третьего 40 элемента ИЛИ, третьего элемента И и второго элемента ИЛИ являются соответственно выходами с второго по четвертый логического узла.тель Г Верес Состав ехред И ираж 5 едактор Л. Огааказ 297054 Г 1 илипенк СР по Раушс рпяти крытий ктная, 4 НИИГ 1 И Государственного комитета СС.3035, Москва, Ж -35,Производственно-полиграфическое пред ЗайцеваКорректор ГГ 1 одписноеделам изобретений иая наб., д. 45