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

 

Изобретение относится к вычислительной технике, в частности к запоминающим устройствам. Целью изобретения является расширение области применения устройства за счет реализации поиска по критериям «ближайшее большее и «ближайшее меньшее за один такт ассоциативного опроса. Устройство содержит регистр аргумента поиска , регистры информации, блоки сравнения , элементы И, триггеры, регистр результата поиска, шифратор, коммутатор, мультиплексор и блок управления. Хранимые в регистрах информации слова состоят из информационной и поисковой частей и при записи упорядочиваются в порядке возрастания поисковых частей. В режиме ассоциативного поиска значения поисковых частей слов сравниваются со значением поисковой части слова , записанного в регистре аргумента поиска . Потенциалы с выходов блоков сравнения поступают на входы элементов И так, что на выходе любого из элементов И формируется единичный сигнал только в том случае, если значение аргумента поиска лежит между значениями поисковых частей слов, записанных в одноименном с элементом И и последующем регистрах информации . В результате этого устанавливается в единицу один из разрядов регистра результата поиска, указывающий номер регистра информации, в котором хранится слово, ближайшее большее к записанному в регистре аргумента поиска. 2 ил. § (Л IsD 00 со |

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

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

РЕСПУБЛИК

ÄÄSUÄÄ 1278977 (51) 4 G 11 С 15 00

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3925800/24-24 (22) 09.07.85 (46) 23.12.86. Бюл. № 47 (72) В. И. Корнейчук, В. П. Сидоренко, А. П. Марковский и А. В. Чернов (53) 681.327 (088.8) (56) Авторское свидетельство СССР № 1032483, кл. G 11 С 15/00, 1982.

Авторское свидетельство СССР

¹ 928414, кл. G 11 С 15/00, 1980. (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности к запоминающим устройствам. Целью изобретения является расширение области применения устройства за счет реализации поиска по критериям

«ближайшее большее» и «ближайшее меньшее» за один такт ассоциативного опроса.

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

l 278977

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

Целью изобретения является расширение области применения устройства за счет реализации поиска по критериям «ближайшее большее» и «ближайшее меньшее» за один такт ассоциативного опроса.

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

Предложенное устройство (фиг. l ) содержит регистр 1 аргумента поиска, регистры 2i — -2, информации, блоки 3i — З„сравнения (где n — целое число), элементы И 41—

4„л, регистр 5 результата поиска, триггеры 61 — 6„, шифратор 7, коммутатор 8, мультиплексор 9. На фиг.! обозначены также информационные выходы 10 устройства.

Устройство содержит также блок 11 управления с входами 12 — 14 и выходами 15—

18.

Ьлок 11 управления содержит (фиг.2) триггер 19 блока управления, счетчик 20, элемент НЕ 21, элементы И 22, 23, элемент 24 задержки и элементы ИЛИ 25 и 26.

На фиг.l и 2 обозначен тактовый вход 27 устройства, первый 28 и второй 29 выходы блоков 3 — З„сравнения.

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

Б регистрах 2 хранятся слова, состоящие из поисковой и информационной частей, упорядоченные в порядке возрастания их поисковой части, т. е. в регистре 21 хранится слово с минимальной поисковой частью, в регистре 2 — хранится слово с поисковой частьк>, следуюшей за минимальной и т. д.

Разряды поисковой части регистров 2 установлены в «!».

В режиме ассоциативного поиска по критериям «ближайшее большее» («меньшее») аргумент поиска помещается на регистр 1 и подается единичный импульс на вход 13 устройства. При поиске «ближайшего большего» на вход!4 подается потенциал единичного уровня, а при поиске «ближайшего меньшего» вЂ” нулевого.

Потенциалы значений разрядов поисковой части регистра 1 поступают на входы всех блоков 3, на другие входы каждого из которых поступают потенциалы значений разрядов поисковой части соответствующего регистра 2. Если поисковая часть слова из регистра 2 больше поисковой части аргумента поиска, то сигнал единичного уровня формируется на выходе 29 соответствуюшего блока 3, в противном случае, если между указанными числами имеет место отношение меньше или равно, сигнал единичного уровня формируется на выходе 28 блока 3. Оче5

55 видно, что единичный потенциал на выходе 28 будет иметь место для блоков 3, порядковый номер которых меньше номера регистра 2, в котором хранится слово, поисковая часть которого больше поисковой части аргумента, причем в предыдущем регистре 2 хранится слово, поисковая часть которого не больше поисковой части аргумента, а на выходе 29 — для последуюших блоков 3.

Потенциалы с выходов блоков 3 поступают на входы соответствуюших элементов И 4 так, что на выходе любого элемента И 4 единичный сигнал будет сформирован только в том случае, если поисковая часть аргумента поиска лежит в интервале между значениями поисковых частей слов, хранящихся в одноименном и последующем регистрах 2. Сигналы с выходов элементов И 4, выхода 29 блока 3i и выхода 28 блока З„записываются в соответствуюшие разряды регистра 5. Очевидно, что в единичном состоянии окажется только один разряд регистра 5, причем его позиция в совокупности разрядов с первого по и-й будет указывать номер слова, «ближайшего большего» к аргументу поиска, а в совокупности разрядов со второго по (и + 1) -й — позицию «ближайшего меньшего». Соответственно в первом случае (при поиске «ближайшего большего») сигналом с выхода 17 блока 11 содержимое регистра 5 будет сдвинуто на один разряд с тем, чтобы в разрядах регистра 5 с второго по (и+ 1)-й зафиксировалась позиция «ближайшего большего». При поиске «ближайшего меньшего» такой < двиг не производится.

Код из разрядов с второго по (и + 1)-й регистра 5 поступает через шифратор 7 на входы мультиплексора 9, и на выходах 10 устройства формируется код информационной части найденного слова. Работа мультиплексора 9 синхронизируется сигналом с выхода 18 блока 11.

В режиме записи записываемое слово заносится на регистр 1, а на вход 12, как и на вход 14, подается сигнал единичного уровня. Сигнал по входу 12, пройдя через элемент ИЛИ 26 (фиг.2), инициирует поиск слова, «ближайшего большего» по указанному способу. Этим же сигналом триггер !9 устанавливается в «1» и выдается сигнал с выхода 16 блока 11, по которому устанавливаются в «1» те триггеры 6 (фиг. l ), поисковая часть слова, хранящегося на соответствующем регистре 2 которых, больше поисковой части аргумента. Единичный потенциал на выходах указанных триггеров 6 с приходом очередного тактового импульса инициирует сдвиг содержимого регистров 2, поисковая часть слова которых больше поисковой части аргумента поиска. Сдвиг может быть реализован как поразрядно так и сразу группами разрядов. Количество сдвигов фиксируется счетчиком 20, сигнал переполнения которого устанавливает триггер 19 в «О», по выходу :5 блока 11 устанавли1278977 вает триггеры 6 в «0» и открывает коммутатор 8 для записи слова с регистра 1 на освободившийся в результате сдвигов регистр 2.

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

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

1278977

Сосгавигель T. Зайнена

Редактор В. Данко Текрсд H. Всрсс 1(орректор М. Самборская

Заказ 6847!54 Тираж 543 Подпис нос

BHHHIlH Государственного комитета СССР оо делам изобретений и открытий

113035, Москва, Ж вЂ” 35, Раушская наб., д. 4/5

Филиал ППП «Патент», г. Ужгород, ул. Проектная, 4