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

 

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

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

СОЦИАЛИСТИНЕСНИХ

РЕСПУБЛИН (19I (111 (51> 611 С 15/OQ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ -Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (2 1) 3443699/18-24 (22) 25.05.82 (46) 23.08.83. Бюл. Ж 31 (72) В. И. Корнейчук, B..È. Павловский и А. П. Марковский (71) Киеиский орцена Ленина политехнический институт нм. 50 летия Великой

Октябрьской социалистической революции (53) 681,327(088.8)

{56) 1. Патент США Ж 4254477, кл. 340 172.5, опублик. 1981.

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

М 877617, кл. 6-11 С 15 00, 1980 (прототип). (54) (57) АССОЦИАТИВНОЕ ЗАПОМИНАЮШЕЕ УСТРОЙСТВО, соцержашее накопитель, первый регистр опроса, регистр маски, регистры результата поиска, первую и вторую группы элементов И и элементы ИЛИ, выходы которых н выкоцы регистра маски поцключены к входам опроса и к вхоцам маскирования накопителя соответственно, причем вхоцы

ПЕРВОГО Pel HCTPR liPKSHBXR OllPOC& H SXO ды регистра маски являются соответственно вхоцами опроса и вхоцами маскиръ вания устройства, о т л и ч а ю ш е е с s тем, что, с целью расширения области применения устройства путем выполнения поиска по отношениям межцу частями записанных слов, в него ввецены второй регистр признака опроса, третья, чет» вертая -и пятая группы элементов И, регистр сцвига, выход которого является выхоцом устройства, и элемент НЕ, вход которого является тактовым вхоцом ус1,« г . ° ройства и соецинен с управляющими вхо» дами второго регистра признака опроса и регистра маски, входом регистра сдвига и первыми вхоцами элементов И первой и четвертой групп, причем выход элемента НЕ поцключен к первым входам элементов И второй группы и первым вхоцам элементов И третьей группы, вторые Bxotlbl которых соецинены с пря мыми выхоцами второго регистра призна» ка опроса, инверсные выходы. которого поцключены к вторым вхоцам элементовИ четвертой группы, а вхоцы - к выходам элементов И пятой группы, первые вхо» цы которых соединены с выхоцами пер вого регистра признака опроса, а вторые вхоцы - с вхоцами регистра маски, выхо цы элементов И третьей н четвертой групп поцключены соответственно к первым и к вторым входам элементов ИЛИ, выхоцы накопителя соединены с вторыми входами элементов И первой и второй групп, выхоцв1 которых поцключены соответственно к входам первого н вто рого регистров результата поиска, выхоцы. первого регистра результата поиска соединены .с третьими вхоцами элементов И второй группы, выхоцы второго .

t .регистра результата поиска поцключены к третьим входам элементов И первой группы. 3э

1037345

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

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

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

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

30 выполнения поиска по отношениям между частями записанных слов.

Поставленная цель достигается тем, что в ассоциативное запоминающее устройство, содержащее накопитель, первый регистр признака опроса> регистр маски, регистры реэульrara поиска, первую и вторую группы элементов И и элементы ИЛИ, выходы которых и выходы perm стра маски подключены к входам опро са и к входам маскирования накопителя соответственно, причем входы первого регистра признака опроса и входы регист ра маски являются соответственно вхо дами опроса и входами маскирования устройства, введены второй регистр приз кака опроса, третья, четвертая и пятая группы элементов И, регистр сдвига, выход которого является выходом устрой ства, и элемент НЕ, вход которого является тактовым входом устройства и соеР динен с управляющими входами второго регистра признака опроса и регистра маски, входом регистра сдвига и перв ми входами элементов И первой и четвертой групп, причем выход элемента НЕ > подключен к первым входам элементов И второй группы и первым входам элемен тов И третьей группы, вторые входы которых соединены с прямыми выходами второго регистра признака опроса, инверсные выходы которого подключены к вторым входам элементов И четвертой группы, а входы - к выходам элементов И пятой группы, первые входы кото рых соединены с выходами первого регистра признака опроса, а вторые входы с входами регистра маски, выходы элементов И третьей и четвертой групп включены соответственно к первым и к вторым входам элементов ИЛИ, выходы накопителя соединены с вторыми входами элементов И первой и второй групп, выходы которых подключены соответствен но к входам первого и второго регистров результата поиска, выходы первого регистра результата поиска соединены с третьими входами элементов И второй группы, выходы второго регистра резуль тата поиска подключены к третьим входам элементов И первой группы.

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

Ассоциативное запоминающее устройство содержит первый регистр 1 признака опроса с входами 2, первую группу элементов И 3. - (,p- целое число, равное числу строк накопителя), второй регистр 4 признака опроса, регистр 5 маски с входами 6, вторую группу элементов И 7 - 7p, элементы ИЛИ 8, -8>, (И - целое число, равное числу входов опроса накопителя), накопитель 9, третью группу элементов И 10 10>, пер вый ll и второй 12 регистры реэульта ,та поиска, четвертую группу элементов И 13» »13и, элемент НЕ 14, ре.гистр 15 сдвига с выходом 16 и пятую группу элементов И 17 - 17» тактовый вход 18 устройства.

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

Перед началом работы все регистры устройства сбрасываются в нуль. В ячейках накопителя 9 хранятся информационные слова> причем в состав каждого такого слова входит ряд подолов, представляющих собой текстовые и числовые данные одинаковой длины, так что струк ра информадионного GJIQBa EMGBT вид 4q,о(, .",с К, где К- количество числовых или текстовых подслов. Например, информационное слово может представлять собой последовательно paaMemaемое имя некоторого обьекта, числовые и текстовые данные, его характеризующие, з 1037

Операция поиска начинается подачей е на входы 2 и 6 устройства набора сигналов, зацаюшим виц поиска. Причем на входах 2 задаются операционные отношения типа (id), где . gg - данные иэ набора )e(), а на вхоцах 6 - логические отношении типа цизъюнкции (ИЛИ) и конъюнкции (И) межцу операционными отношениями. Зацание операционных отношений типас >afar реализуется выдачей !О единого сигнала по Р-тому из . вхс дов 2, гце (= — (9-1), и соответствуИ

1( ет номеру разряда, начиная с которого хранится а(. Задание логического отношения конъюнкции нескольких операци- 15 онных отношений реализуется одновременной выдачей единичного сигнала на те из вхоцов 6, которые соответствуют номерам ячеек накопителя 9, с которых начинается поле записи всех цанных, 20 которые участвуют в указанных операционных отношениях. Задание логического отношения дизъюнкции произвоцится послецовательной во времени выдачей единичных сигналов- на те из входов 6, 25 которые соответствуют номерам разрядов начала полей записи данных, входя ших в операционные отношения.

Сигналы с вхоцов 2 записываются на

30 .регистр 1, откуца через открытые сигналами с вхоцов 6 элементы 17 -17> записываются на регистр 4. Одновременно сигналами с входов 6 устанавливаются в единицу разряды регистра 5, со„ответствующие началам . полей записи цанных, которые участвуют в операционных отношениях.

При поцаче тактового импульса на вход 18 производится одновременное сравнение инверсных, значений содержимо- 40 го разрядов регистра 4, определяемых содержимым регистра 5, с соответствуюшими разрядами ячеек накопителя 9, причем сигналы с инверсных выхоцов регистра 4 через открытые элементы И 10А - 10> и 13 - 13 и элементы ИЛИ 8 поступают на вхоцы опро са накопителя 9. При поиске по отношению8r1о(.ф Г-тые разряды всех ячеек накопителя 9 сравниваются с нулевым сигналом с выхода 6-того разряда регистра 4, à $-тые разряды всех ячеек накопителя 9, где q +(<-1) - номер разряда, с которого начинается поле записи данного сЕ, сравниваются с еди» 55 ничным сигналом с выхоца ф -го разряца регистра 4. Таким образом, на выхоцах накопителя 9 будут оформи рованы единичные сигналы, соответствуюшие тем ячейкам, цля которых старший разряд сЬ.- меньше старшего разряда dg.

Укаэан ые ецинич:ые сигналы через открытые тактовым сигналом элементы И 3 - 3о устанавливают в ециничное состояние соответствующие раэряцы регистра 11.

При нулевом потенциале на входе 18 единичный сигнал с выхоца элемента НЕ 14, открывая элементы И 10, 10и, 13 - 13, разрешает сравнение содержимого g -го и с -го разрядов регистра 4, в которых записаны соот» ветственно "1 и "О», соцержимым этих же разрядов ячеек накопителя 9.

На выходах накопителя 9 будут сформированы единичные сигналы, соответствуюшие тем ячейкам, цля которых стар г ший разряд 4> больше старшего раэря .ца с(g..ÓKàçaííûå ециничные сигналы через открытые элементы И 7„- 7р устанавливают в единичное состояние соответствуюшие разряды регистра 12.

При подаче слецуюшего тактового сиг» нала содержимое регистров 4, 5 и 15 сцвигается на оцин разряц и аналогично анализируются слецуюшие разряды в по,лях записи данных 4g ис(. При этом, если слецуюший эа старшим разряц о гменьше такого же разряцас/, на соотвеэ ствуюших выходах накопителя 9 формируются единичные сигналы, которые за-. писываются в те из разрядов регистра 11, запись в которые не блокируется единичными состояниями таких же разря» дов регистра 12. При опросе, выявляюшем ячейки, цля которых слецяший за .старшим разряцс больше такого же разряда сЦ, на соответствуюших выходах накопителя 9 формируются единичные car калы, которые (если не блокируются единичными состояниями соответствуюших разрядов регистра 11) записываются в соответствуюшие .разряды регистра 12.

Таким образом, когда на выходе 16 сформирован единичный сигнал, в регион ре 11 зафиксированы единичными состояниями разряды, соответствуюшие ячей кам накопителя 9, для которых с(с, единицы в разряцах регистра 12 соответствуют ячейкам накопителя 9, для кото рых dq ) оЦ,а разряды регистров 11 и 12 в которых записаны нули, соответствуют с =оЦ. При большем числе операци» онных отношений, соединенных отноше нием конъюнкции, результат в вице отме

1037345 ченных ециничными состояниями разряцов регистра 11, которые соответствуют ячейкам, для которых выполняются указанные отношения, фиксируется при ециничном сигнале на выхоце 16. При операционных отношениях, связанных дизъюнкцией, совокупность операций производится послецовательно во времени цля каждого операционного отношения.

Таким образом, ассоциативное запоминаюшее устройство позволяет осущес1вить параллельный сложный поиск по отношениям -между частями слов, храни5 мых в накопителе 9.

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

ВНИИПИ Заказ 6020/55 .Тираж 594 По1писное

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