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

 

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

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

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

РЕСПУБЛИК

3(5П G 11 С 15/00

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

H ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3433941/18-24 (- 22) 05 . 05. 82 (46) 23.09. 83: ., Бюл. 9 35 (72) В.И. Корнейчук, В.И. Павловский, Марта Зеебауэр, И.П. Дробязко. и A.Ï. Марковский (71) Киевский ордена Ленина политех. нический институт им. 50-летия

Великой Октябрьской социалистической. революции (53) 681.327 (088.8) (56) 1. Авторское свидетельство СССР В 410462, "кл. G 11 С 15/00, 1974.

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

В 773729, кл. G 11, С 15/00, 1979 (прототип). (54) (57) АССОЦИАТИВНОЕ ЗАПОМИНАЮ- .

ЩЕЕ УСТРОЙСТВО, содержащее оперативный накопитель, первый регистр числа, первый выход которого подключен к входу второго регистра числа, регистр маски, первый регистр опроса, первый вход которого соединен с выходом второго регистра опроса, элементы И, шифрато». ры, причем второй вход первого регистра опроса является одним из управляющих входов устройства, первый и второй входы и первый выход" оперативного накопителя подключе-. ны соответственно к первому выходупервого регистра. опроса, выходу ре™ гистра маски и первому входу пер-. вого регистра числа, о т л и .ч а -. ю щ е. е .с я тем, что, с целью pac: ширения области применения устройства путем обеспечения возможности храхранения в нем чисел переменной;„ длины, в него введены постоянный накопитель, регистр адреса, третий. регистр числа, триггер, элементы

ИЛИ и элементы задержки, причем второй и третий выходы первого регистра числа подключены соответст„„SU„„1043750 А венно к входам регистра адреса и первого шифратора, выход ксторого соединен с одним нз входов первого элемента И и входом триггера; инверсный выход которого подключен к первому входу второго элемента И, а прямой — к другому входу первого элемента И и первому входу третьего элемента И, выходы второго и третьего элементов И соединены непосредственно с первым и вторым входами постоянного накопителя и вторым и третьим входами первого регистра числа и через первый элемент ИЛИ с первым входом третьего регистра числа, второй вход и вы— ход которого соответственно подключены к второму выходу и третьему входу оперативного накопителя, второй выход. первого регистра onроса соединен с входом второго шифратора, выходы которого подключенЫ к первым входам четвертого и пятого. элементов И, выходы которых . непосредственио соединены с третьим и четвертым входами постоянного накопителя и через второй, элемент ИЛИ с третьим входом третьего регистра числа, выход постоянного накопителя подключен к входу ре- гистра маски, выход четвертого элемента И подключен к первому элементу задержки, выходы четвертого и пятого элементов И через второй и третий элементы задержки соединены соответственно с четвертым и пятым входами регистра числа, вторые входы второго и третьего элементов И и вторые входы четвертого и пятого элементов И объединены соответственно и являются другими управлякхцими входами устройства, выходами которого являются выходы первых элемента И и элемента задержки.

1043750

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

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

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

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

Однако это устройство также не повволяет хранить в нем слова (висла переменной длины.

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

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

И соединены непосредственно с первым и вторым входами ..постоянного накопителя и вторым и третьим входами первого регистра числа и.через .первый элемент ИЛИ с первым входом третьего регистра числа, второй вход и выход которого соответственно подключены к второму выходу.и третьему входу оперативного нако.пителя, второй выход первого регист19 ра опроса соединен с входом второго шифратора, выходы которого подключены к первым входам четверто го и пятого элементов И, выходы которых непосредственно соединены с третьим и четвертым входами постоянн ого накопителя и через второй элемент ИЛИ с третьим входом третьего регистра числа, выход посто.янного накопителя подключен к входу регистра маски, выход четвер2О того элемента И подключен к первому элементу задержки, выходы четвертого и пятого элементов И через второй и третий элементы задержки соединены соответственно с четвер- тым и пятым входами регистра числа, вторые входы второго и третьего элементов И и вторые входы четвертого и пятого элементов И объединены соответственно и являются

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

На чертеже изображена структурная

g5 Схема ассоциативного запоминающе:го устройства.

Устройство содержит оперативный накопитель 1, выполненный из ассоциативных ячеек памяти (не показаны)

4О пеРвый РегистР 2 опрос, РегистР 3 маски, второй регистр 4 опроса, первый 5, второй 6 и третий 7 регистры числа, регистр 8 адреса, первый шифратор 9, триггер 10, первый элемент И 11, выход которого является, первым выходом 12 устройст.ва, второй 13 и третий 14 элементы И, одни из входов которых объединены и являются первым управляющим входом 15 устройства, постоян50 ный накопитель 16, второй шифратор 17, четвертый 18 и пятый 19 элементы И, одни из входов которых объединены и являются вторым управляющим входом 20 устройства, 55 первый элемент 21 задержки, выход которого является вторым выходом 22 устройства, первый 23 и- второй 24 элементы ИЛИ. Регистр 2 имеет вход, являющийся третьим управляющим входом 25 устройства. Устройство также содержит второй 26 и третий

27 элементы задержки. Регистр 7 служит для хранения управляющей информации.

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

65 образом.

;1043750

В исходном состоянии в ячейках памяти накопителя 1 записаны информационные слова производной длйны и соответствующие им коды, причем структура записи информации в накопителе 1 следующая: код символов информационного слова записываются в ячейку, начиная с первого ее разряда, если длина слова.m .больше, чем i символов (где i=n -f., причем

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

8 исходном состоянии триггер 10 установлен в нулевое состояние, age разряды регистра 7 установлены в единичное состояние.

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

16, формирует на выходах последнего нулевой код, который, поступая" на регистр 3, разрешает сравнение всех разрядов ячейки .накопителя 1 с, соответствующими разрядами регист ра 2, сигнал единичного уровня формируется на шинах поиска тех ячеек. накопителя 1, содержимое которых поразрядно совпадает с содержимым регистра 2, указанными сигналами перезаписываются единицы в соответ-. ствующие разряды регистра 6. Одновременно слово, адекватное записанному на регистре 2, считывает- ся на регистр 5, Сигналом с выхода элемента И 19 через элемент ИЛИ 24 содержимое регистра 6 сдвигается . на один разряд, при этом единичные сигналы на адресные входы опроса выдаются лишь для ячеек накопителя 1,.следующйх за ячейками, выделенными единичными сигналами в такте опроса. Сигналом с выхода элемента .И 19 через элемент 26 задержки регистр 5 сбрасывается в нуль.

В следующем такте вновь на регистр 2 заносятся следующие и символов из регистра 4, и вновь i-й символ анализируется шифратором 17, и если символ-метка отсутствует, то вновь содержимое регистра 2 сравнивается с содержимым ячеек накопителя 1, следующих за выделенными на предыдущем такте, и устройство функционирует аналогично описанно1О My

В случае, если в i-й группе разрядов. регистра 2 окажется записанным символ-метка, то единичный сигнал последовательно будет сформирован на выходе шифратора 17 и элемента И 18, с выхода последнего единичный сигнал поступает на вход постоянного накопителя 16, с выхода которого на регистр маски 3

Считывается код, маскирующий срав20 кение последних +1 групп разрядов . ячеек накопителя 1 и, таким образом, опрос производится лишь по первым и- 2-1 символам регистра 2, на п-8-1 групп разрядов регистра 5, при

25 этом считывается содержимое и-2- 1 групп разрядов регистра 2, а в последние 2 группы разрядов заносится искомый код адреса. Сигналом с выхода элемента И 18 через элемент .27 задержки содержимое регистра 5 сдвигается вправо на Ю разрядов так, что на регистре 8 оказывается записанным искомый код адреса. Этим же сигналом через элемент 21 эадержки с выхода 22 формируется сигнал конца операции поиска.

В случае поиска информационного слова по его коду последний заносится на регистр 4, на вход 15 выдается сигнал единичного уровня.

40 По сигналу начала операции, подаваемого на вход 25, код при сдвиге на п групп разрядов заносится в последние Х группы разрядов регистра

2, в i-ю группу разрядов этого ре45 гистра записывается код метки.

Маскирование разрядов при этом не производится и сравнение содержимого всех ячеек накопителя 1 и регистра 2 происходит по всем разря50 -дам. В РезУльтате цикла опроса на регистр 5 записывается содержимое ячейки накопителя 1, в которой записан конец искомого информационного слова, метка конца и код. При этом записывается единица в соответствующий. разряд регистра 7, все остальные разряды которого при этом устанавливаются в нуль. Наличие кода метки в i-й группе разрядов регистра 5 формирует на выхо60 де шифратора 9 сигнал единичного уровня, который поступает на вход триггера 10, который, будучи установлен в нулевое соСтояние, формирует через открытый элемент И 13 единичный сигнал на входе постоян1043750

ВНИИПИ Заказ 7348/57 Тираж 594 Подписное

Филйал ППП "Патент", г.ужгород,ул.Проектная,4 ю ного накопителя 1б.и на входе регистра 5. Указанным сигналом содержимое-первых п-Х-1 разрядов регист. ра 5 сдвигается в регистр 6. Триг-. гер 10 устанавливается в единичное состояние и в этом же такте производится цикл опроса накопителя 1.

На регистре маски З.при этом записан код, маскирующий сравнение всех разрядов ячеек накопителя 1, так что выборка ячейки для считывания на регистр 5 определяется толь ко состоянием разрядов регистра 7, содержимое которого предварительно сигналом с элемента И 13 через элемент ИЛИ .23 сдвигается на один . разряд, так что на регистр 5 считывается содержимое ячейки, предшествующей выбранной на предыдущем такте опроса, в которой записана либо часть информационного слова,,уже считанного в предыдущем такте, либо конец другого информационного слова. В первом случае шифратором 9 код метки не регист — рируется, и единичный сигнал с выхода триггера 16 через элемент И

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

5 такте опроса.

Работа в последующем такте аналогична описанной, так что когда в регистре 5 наличием метки в i-й группе разрядов регистра 5 зафикси О рован конец другого информационно.— го слова, то в регистре 6 хранится код искомого слова„ Сигнал, поступающий с выхода шифратора 9, в этом случае формирует, пройдя через открытый элемент И. 11, сигнал единичного уровня на выходе 12.

Таким образом, предлагаемое ассоциативное запоминающее устройство позволяет хранить и осуществлять поиск информационных слов перемен20 ной длины по их коду и наоборот .

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

25 с адресными устройствами, в которых используется списковая структура. записей