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

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

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

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

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

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

Блок 11 управления содержит {фиг.2) триггер 19 блока управления, счетчик 20, элемент НЕ 21, элементы И 22, 23, элемент 24 задержки и элементы ИЛИ 25 и 26. На фиг.1 и 2 обозначен тактовый вход 27 устройства, первый 28 и второй 29 выходы блоков 3|-Зп сравнения.

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

В регистрах 2 хранятся слова, состоящие из поисковой и информационной частей, упорядоченные в порядке возрастания их поисковой части, т. е. в регистре 2i хранится слово с минимальной поисковой частью, в регистре 2-2 - хранится слово с поисковой частью, следующей за минимальной и т. д. Разряды поисковой части регистров 2 установлены в «1.

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

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

поисковых частей слов, хранящихся в одноименном и последующем регистрах 2. Сигналы с выходов элементов И 4, выхода 29 блока 3i и выхода 28 блока 3л записываются в соответствующие разряды регистра 5. Очевидно, что в единичном состоянии окажется

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

, (п-|- 1)-й - позицию «ближайшего меньшего. Соответственно в первом случае (при поиске «ближайшего большего) сигналом с выхода 17 блока 11 содержимое регистра 5 будет сдвинуто на один разряд с тем, чтобы в разрядах регист)а 5 с второго по

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

устройства формируется код информационной части найденного слова. Работа мультиплексора 9 синхронизируется сигналом с выхода 18 блока 11.

В режиме записи записываемое слово заносится на регистр 1, а на вход 12, как и

0 на вход 14, подается сигнал единичного уровня. Сигнал по входу 12, пройдя через элемент ИЛИ 26 (фиг.2), инициирует поиск слова, «ближайшего большего по указанному способу. Этим же сигналом триггер 19

, устанавливается в «1 и выдается сигнал с выхода 16 блока 11, по которому устанавливаются в «1 те триггеры 6 (фиг.1), поисковая часть слова, хранящегося на соответствующем регистре 2 которых, больше поисковой части аргумента. Единичный потен0 циал на выходах указанных триггеров 6 с приходом очередного тактового импульса инициирует сдвиг содержимого регистров 2, поисковая часть слова которых больше поисковой части аргумента поиска. Сдвиг может быть реализован как поразрядно так и

5 сразу группами разрядов. Количество сдвигов фиксируется счетчиком 20, сигнал переполнения которого устанавливает триггер 19 в «О, по выходу 15 блока 11 устанавливает триггеры 6 в «О и открывает коммутатор 8 для записи слова с регистра 1 на освободившийся в результате сдвигов регистр 2.

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

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

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

Ю

ЦТ

J2 13 № Фиг.1

Сосгавитель Т. Зайцева

Редактор В. ДаикоТехред И. ВересКорректор Л. Самборская

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий

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

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

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