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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (Я) 4 G 11 С 15 00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А 8ТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4029666/24-24 (22) 26.02.86

1 (46) 15.07.87. Бюл. № 26 (71) Киевский поли гехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) В. И. Корнейчук (SU), Марта Зеебауэр (HU), А. П. Марковский, Л. А. Иванец и И. А. Дичка (SU) (53) 681.327 (088.8) (56) Авторское свидетельство СССР № 928414, кл. G ll С 15/00, 1982.

Авторское свидетельство СССР № 978197, кл. G ll С 15/00, 1982.

„„Я0„„1324071 А1 (54) АССОЦИАТИВНОЕ ОПЕРАТИВНОЕ

ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано в цифровых системах параллельной обработки информации. Целью изобретения является расширение функциональных возможностей устройства за счет реализации поиска числа, ближайшего к заданному.

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

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

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

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

12i — 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) логические узлы 301 †3, элемент

ИЛИ 31, а также первый 32 и второй 33 элементы задержки.

Каждый логический узел 30 выполнен в ви10 де первого элемента HE 34, элементов И

35 — 37 с первого по третий, первого элемента ИЛИ 38, четвертого элемента И 39, второго элемента НЕ 40, второго 41 и третьего

42 элементов ИЛИ. На фиг. 2 обозначена шина 43 нулевого потенциала.

15 Устройство работает следующим образом.

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

В режиме записи записываемое слово через входы 27 (фиг. 1) заносится в регистр

5, на входы 18 и 22 подаются потенциалы единичного уровня, а на входы 19 и 23 — ну25 левого. По сигналу начала операции на входе 17 старшие разряды записываемого слова заносятся в счетчик 2 и далее, дешифрируясь дешифратором 3, поступают на входы накопителя 4; младшие разряды записываемого слова дешифрируются дешифра30 тором- 15 и фиксируются на регистре 16.

Сигналом с выхода элемента 29 задержки

1324071

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

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

f-м разряде (f<(1, и}). Тогда на выходе

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, запись скорректированного таким образо.ч слова осуществляется аналогично описанн"". :. Таким образом, в ячейке, определяемой старшими разрядами исключаемого слова, в разряде, определяемом его младшими разрядами, фиксируется «О», свидетельствующий об отсутствии указанного слова в памяти.

В режиме поиска по совпадению заданное число по входам 27 записывается в регистр 5. На входы 19, 22 и 23 подаются сигналы нулевого уровня, а на вход 18— потенциал единичного уровня. На блок 7 ана10 логично описанному по входам 8 — 8п и

13 — 13. подаются коды, хранящиеся соответственно на регистрах 1 и 16. Пусть например, f — номер входа 13, по которому подается единица. Тогда на выходах

15 9.(к =(1,") к 3) формируется нуль, так как на выходах элементов И 37 всех узлов 30( формируются потенциалы нулевого уровня, поскольку нуль подается на вход 19, следовательно, на выходах всех элементов ИЛИ

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

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

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

B режиме ближайшего большего за35

S0

55 данное слово заносится в регистр 5, на входы 18 и 19 подается сигнал единичного уровня, а на входы 22 и 23 — нулевого.

На блок 7 по входам 8 — 8п и 13 — 13 подаются коды, хранящиеся на регистрах соответственно 1 и 16. На выходах 9. (1(r(E) формируются потенциалы нулевого уровня, так как на выходах элементов ИЛИ 38, И

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

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

30e+>- Если на вход 8c,i подается сигнал нулевого уровня, то единичный сигнал формируется на выходе элемента И 37 узла 30 i и

1324071

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

30sz.

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

30, если на их входы 8 будут подаваться сигналы нулевого потенциала. При поступлении сигнала на вход элемента ИЛИ 38 узла 30, на вход 8 которого поступает единицa, формируется сигнал единичного уровня на выходе элемента И 36 и на соответствующем выходе 9, а на выходе элемента

И 37 остается нулевой потенциал, т.е. передача сигнала поиска через узлы 30 прекращается. Единица, поступающая в рассматриваемом случае на вход 8, соответствует числу, ближайшему большему заданного. Если на все входы 8 > поступают сигналы нулевого уровня, что соответствует отсутствию чисел больших заданного и отличающихся от заданного только младшими разрядами, то сигнал на выходе элемента И 37 узла 30„ поступает на выход 24 блока 7, увеличивает на единицу содержимое счетчика 2 и, пройдя через элемент ИЛИ 28 и элемент 29 задержки, инициирует считывание из накопителя 4 числа, старшие разряды которого на единицу больше старших разрядов заданного числа. Одновременно сигнал с выхода

24 устанавливает все разряды регистра 16 в нуль. Коды с регистров 1 и 16 через коммутаторы 6 и 14 поступают на входы соответственно 8i — 8. и 13 — 13. блока 7, причем единица подается по входу 13 .

В этом случае процесс прохождения сигнала поиска через узлы 30 начинается с узла 30 и продолжается до тех пор, пока не будет найден узел 30, на вход 8 которого поступает единица. Если такой узел 30 не найден, то вновь формируется сигнал на выходе 24 и описанный процесс повторяется для следующего адреса. Если в устройстве нет чисел, больших заданного, то счетчик 2 формирует сигнал переполнения на выходе 20, свидетельствующий об отсутствии искомого числа в устройстве, т.е. об отрицательном результате поиска, при этом на выходе устанавливается сигнал нулевого уровня. Если на каком-либо из этапов описанного процесса поиска будет найден узел

30, на вход которого 8 подается единичный потенциал, процесс поиска прекращается, так как блокируется выдача сигнала элементом И 37, и формируется единичный сигнал на соответствующем выходе 9 и на выходе

21. Код на выходах 9i — 9„шифруется шифратором 10 и поступает на младшие разряды выходов 11, на старших разрядов которых присутствует код счетчика 2, т.е. код старших разрядов числа, ближайшего к заданному.

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

Таким образом, коммутаторы 6 и 14 преобразуют поступающие с регистров слова так, что младшие и старшие разряды меняются местами. Соответственно, при поиске ближайшего меньшего числа перенос с выхода элемента И 37 узла 30 распространяется в сторону, соответствующую младшим раврядом. Процедура поиска аналогична описанной, за исключением того, что при проявлении сигнала на выходе 24 содержимое счетчика 2 уменьшается на единицу.

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

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

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

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

40 по п-й первого регистра числа подключены к нечетным информационным входам первого коммутатора, четные информационные входы которого соединены с другими информационными выходами с и-го по первый первого регистра числа, выходы первого комму45 татора подключены к информационным входам блока поиска совпадений, информационные выходы которого соединены с входами шифратора, а входы ассоциативных признаков — с выходами второго коммутатора, нечетные информационные входы которого подключены к выходам с первого по п-й, а четные информационные входы — к выходам с и-го по первый регистра ассоциативных признаков, информационные входы которого соединены с выходами второго

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

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

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

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

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

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

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

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

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

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

1324071 (оставит<гав Г. Заицева

Редактор A. Огар Техред И. Верес Корректор Л. Пилипенко

Заказ 2970/54 Тираж 589 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий ! .3035, Москва, ж — 35, Раушская наб., д. 4, 5

Произво Гственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4