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

 

Изобретение относится к области вычислительной технике, в частности к ассоциативным запоминающим устройствам, и может быть использовано при ассоциативной обработке информации в электронных устройствах для исследования параметров интегральных изделий памяти. Цель изобретения - расщирение функциональных возможностей устройства за счет обеспечения поиска по экстремальным значениям признака поиска. Устройство содержит регистр 1 слова , первый 2 и второй 21 блоки сравнения, регистр 3 признака, блок 4 управления записью признака, в состав которого входят триггеры 5, 6, 10 и 13, элементы И 7, 8, 1 и 2 и элемент ИЛИ 9, блок 14 счетчиков 15-17, блок 18 памяти данных, состоящий из ключей 26 и регистров 27 сдвига, дещифратор 19, блок 20 управления, блок 2:2 памяти признаков, состоящий из ключей 23 ч регистров 24 сдвига, коммутатор 28, регистр 29 фразы и регистр 30 данных. 5 ил. (С

союз советских социАлистических

РЕСПУБЛИК ао 4 11 С 15/00

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

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

ГОсудАРственный НОмитет по изОБРетениям и откРытиям пРи гкнт сссР (21) 4185922/24-24 (22) 26.01.87 (46) 07.03.89. Бюл. № 9 (71) Одесский политехнический институт и

Одесский электротехнический институт связи им. А. С. Попова (72) С. А. Березовский, Л. Б. Березовская и Ю. К. Филипский (53) 681.327 (088.8) (56) Крайзмер Л. П. Ассоциативные запоминающие устройства. — Л.: Энергия, 1967, с. 71 — 85.

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

„,Я0„„1464214 А 1 может быть использовано при ассоциативной обработке информации в электронных устройствах для исследования параметров интегральных изделий памяти. Цель изобретения — расширение функциональных возможностей устройства за счет обеспечения поиска по экстремальным значениям признака поиска. Устройство содержит регистр 1 слова, первый 2 и второй 21 блоки сравнения, регистр 3 признака, блок 4 управления записью признака, в состав которого входят триггеры 5, 6, 10 и 13, элементы И 7, 8, 11 и 12 и элемент ИЛИ 9, блок 14 счетчиков 15 — 17, блок 18 памяти данных, состоящий из ключей 26 и регистров 27 сдвига, дешифратор 19, блок 20 управления, блок 22 памяти признаков, состоящий из ключей 23 ч регистров 24 сдвига, коммутатор 28, регистр 29 фразы и регистр 30 данных. 5 ил.

1464214

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

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

На фиг. 1 дана структурная схема динамического ассоциативного запоминающего устройства (ДАЗУ); на фиг. 2 — графсхема состояний ДАЗУ (указаны функции возбуждения); на фиг. 3 л 4 -- коды состояний граф-схемы ДАЗУ; на фиг. 5 — — структурная схема второго блока сравнения (для четырех фраз) .

Устройство (фиг. 1) содержит регистр 1 слова, первый блок 2 сравнения, регистр 3 признака, блок 4 управления записью призна-20 ка, н состав которого входят триггеры 5 и 6, элементы И 7 н 8, элемент ИЛИ .), триггер 10, элемент И 11, элемент И 12 и триггер 13, блок 14, включающий в себя счетчик 15 длины слона, счетчик !6 длины фразы и счетчик 17 номера фразы, кроме того, устройство имеет блок 8 памяти данных, дешифратор 19, блок 22 памяти признаков, состоящий из ключей 23 ---23«и регистров

24 — 24«сдвига (К 2, целое), информационный вход 25, блок 18, содержащий ключи

26 --26с и регистры 27 — — ?7:, коммутатор 28, регистр 29 фразы и регистр 30 данных, Граф-схема состояний ДАЗУ (см. фиг. 2) содержит 14 вершин. Кеды вершин графа (фиг. 3 и 4) доопределены с учетом противогоночного кода. 35

Двоичные цифры (коды) вершин соответствуют (слена направо) состояниям триггеров блока 20 управления.

Второй блок 21 сравнения содержит (фиг. 5) элементы И-НЕ 31-33, элемент И 34,,лементы И-HL 35, .рн- гры 36 и му.bTH. 40 плексор 37.

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

Перед началом работы динамического ассоциативного запоминающего устройства (ДАЗУ) осуществляется начальная установка -- сброс всех счетчиков, регистров и триггеров (сигнал Уь фиг. 2).

Цепи начальной установки и синхронизации этих элементов на фчг. 1 не показаны.

Информация в ДАЗУ вводится в последо- «р нательном коде с частотой f, í-чиная со старших разрядон, в ниде фразы, состоящей из

m байтоных слов Ь„.

Устройство функционирует в трех режимах: запись информации, отбор информации, по заданному признаку, ассоциативный ана- 55 лиз и отбор информации.

Режим работы ДАЗУ задается блоком 20 управления.

В режиме записи информации блоком 20 блокируется работа дешифратора 19 (сигнал Х ), íà его вход поступает код, состоящий -из нулей.

В этом случае ключи 26 блока 18 замыкают регистры 27 сдвига в линейку. При этом логическая часть ДАЗУ не работает.

Информация последовательно вводится в блок 18 через регистры 1, 29 и 30.

В режиме отбора информации по заданному признаку или ассоциативного анализа и отбора информации возможна работа

ДАЗУ с входной информацией или работа

«на себя».

Hpи работе «на себя> осуществляется отбор информации по заданному признаку из информации, записа.иной в блоке 18. В этом случае по команде с блока 20 управления информация с выхода последнего регистра 27 сдвига через коммутатор 28 поступает на вход ДАЗУ, номера записанных фраз информации в регистре 30 блокируются управлякпцей командой с блока 20.

Прн работе ДАЗУ н режиме отбора информации по заданному признаку Р он н параллельном коде из блока 20 вносится в регистр 3, в котором он сохраняется во время всего процесса обработки. Процесс поиска в этом случае сводится к поиску во фразе входной информации слова Ь, совпадающего с признаком P.

Блок 2 сравнения н этом случае ocvществляет операцию по управляющей команде (У5, фиг. 5) с блока 20.

Взаимодействие всех блоков ДАЗУ рассматривают подробно в режиме ассоциативного анализа и отбора информации из входной на примере проведения сложного поиска по экстремальным (наибольшее и К-1 ближайших больших) значениям в соответствии с граф-схемой алгоритма работы ДАЗУ (фнг. 2).

Первое байтовое слово Ь, фразы информации через коммутатор 28 вводится в регистр и одновременно с первого разряда регистра 1 подается на первый вход блока 2 (сигнал Х, фиг. 1), на второй вход которого поступает информация н виде байтового слова -- признака Р с первого разряда регистра 3 признака (Хг).

На другие входы блока 2 подаются управляющий сигнал У5 и строб-импульс с блока 20, по приходу которого осуществляется сравнение разрядов слов bi и р.

Блок 2 вырабатывает сигнал неравнозначности двух слов и Р (при поразрядном сравнении), который записывается в триггер 13 по входу установки в состояние логическая «1» и хранится в течение времени записи слова в регистр 1, после чего на триггер 13 из блока 20 подается импульс

3 сброса (У7), задержанный на время t= —4-f

146!>21 л

Относительно вос1. мог() синхроимпульса записи ба ЙтовОго слова (сигнал Х;!) .

}3 триггер !3 записывается «1», если

Ь! р, и «О»., -,.:Ост()(нее триггера не из

МСНЯЕТСЯ, СС.I,! l)l.- Р.

Сarlla.,i с (j,"èpÿìoão выхода триггера 13 подается Hа первый вход элемента Ь, на второй Bxo) ко (орого пс)стуiraaI импульс с Bbr)(0да элемента II 12, сформированный из импульса счетчика 15 и импульсов частоты f„ который задер)кап относительно момента появления синхроимпульса на время 1= — -.

1 !() Ii!)!!) (; >. n>f)авл)1юп>eг!) HI пульса блока 20 (>! 3) и п(»! Ийли >НН «1» 1 а выходе эдеме)гга 6 про)!СхОд>г! пе()езапись информа" ции из пери()го Ir)arrepa 13 в триггер 6„информация с выхода е,)! которого поступает на первыи вход элемента И 7, второй вход которого подключен к входу регистра 29.

Если в триггере 6 записана «1», то она является сигналом раэре(пения перезаписи (У;!) слова Ь! Из регистра 1 через элемент

И 7 и элемент ИЛИ 9 в регистр 3, как удовлетворяющего заданному критерию ассоциатие)ИОГО О1 бора.

Одновременно с перезаписью ЬЕ из регистра 1 в регистр 29 через элемент И 7 и элемент ИЛИ 9 ь регистр 3 вводится новое слово bJ в регистр 1 (У4)! а значит,выполняется сравнение Ь, и bi в блоке 2.

Гслн Ьр Ь1, fo по приходу импульса с элемента И 12 в триггер 13 записывается

«0» и он переэаписываегся в триггер 6. Это означает, что перезаписи слова Ь2 из регистра 1 в регистр 3 нет (X). Слово, ранее записанное в регистр 3 (слово bi), сохраняется и участвует в сравнении с новым словом Ьз входной информации, Регистр 3 в данном случае является динамическим регистром сдвига с управляемой цепепо обратной связи, Управление цепью обратной связи осуществляется в соответствии с состоянием тригrE .p a 6.

При записи «1» в триггер 6, когда выполняется условие записи слова из регистра 1 в регисгр 3, работа элемента И 8 блокируется и слово b„, из регистра 1 через элемент

И 7 и элемент ИЛИ 9 поступает на вход регистра 3. Цепь обратной связи разорвана.

Если сигнал ©=-0 на выходе триггера 6, то блокируется элемент И 7 и цель обратной связи регистра 3 замкнута. Импульсы с выхода регистра 3 через элементы И 8 и ИЛИ 9 поступают на его вход информации. Происходит перезапись признака в регистр 3.

Процесс сравнения слов продолжается до М (число слов во фразе информации), В течение длительности (М+1) -байтового слова блок 20 блокирует работу отдельных схем ЛАЗУ: не подаются стробимпульсы с блока 20 на блок 2 и процесс сравнения содержимого регистра 1 и регистра 3 не осуществляется, блокируется работа счетчика 15 { У)) ) .

Ассоцна1 ивнь!й признак На pc rистра,3 че. рс:, элем«)нт И 11 и блок 20 г)оступает в блок .. 1 (У,,, . J за длит,льность биЙТОП(:Г() с. !Оэ» 1 „, с! (1BHHB>a"..тся . Ic f):; ) (!. !1!;. (« .! "(Оц)! i! I)!! м и 11 ())! э 1;:: <;.1. и 1 >, (л (:; а ;, {,> . ) . ! i!)()е чего начинается процесс записи H в1!!1лила сле)еую(цеЙ фразы информации, Г:сли вновь выделенный признак, и» р(г и с т p a,(!) р= 11

1О

)J!a П!» -- минимальное значение j-го признака, хранящегося в блоке 22 (.Х() ), то вновь выдел(.нный признак Р и соответстн):ю;цая ему фраза информ((ееим с присвоенHh!! ."> и )()ндковым НОм(poM, запи(ь!Ваеч„«) Н» c>1етчика !7 и pcrHcTp 30> Но команд,. И» бло! а 20 (У!!)) вносятся в блоки 22 и 18

{,;.. 1 в место фразы, ассоциативный приз)lак которого i i/I»».

Перез--пись фразы из регистра 29 через регистр 30 в заданный регистр 27 блока 18 происходит одновременно с вводом новой ф1).!»ы B регистр 29 через регистр i (У ).

1..;ели вновь выделенный признак Р -П!.-, при !"! К, где N — число поступивших фраз

2«информации, то сам признак и соответствующая ему фраза не вносятся в накопители 22 и 18 — стираются, так как с блока 20 в дешифратор 19 поступает нулевой код, по которому все регистры блоков 22 н 18 соедиЕ1> )>!>! С ПОМОЩЬЮ КЛЮЧЕЙ В КОЛЬЦО И ЭаПИСаН30 ння в них информация циркулирует по кольцу (У!).

Если BHoab выделенный признак 1))П)1»!»

{фиг, 5), на выходе элемента И 34 формируется сигнал неравноэначности Н при поразрядном сравнении признаков П! ()=Г,4)

35 и Р, который подается на элементы И НЕ 35 для формирования коньюнкции П;- Н-У!!.

По приходу сигнала У! в триггер 36 записывается «1», если указанная конъюнкция истинна н сигнал с инверсного выхода триггера блокирует участие признака П, в дальнейшем поразрядном сравнении, По окончании процесса сравнения в йс«Одном состоянии «О» останется один из триггеров 36. Это является информацией, что соотв(:гствующий признак П подлежит замене на Р из регистра 3.

Код с инверсных выходов триггеров 36 через мультиплексор 37 выдается в блок 20, с которого поступает в дешифратор 19, С выхода дешифратора коды Al, A2, А3, А4 подаются на управляющие входы ключей

50 18 и 22, обеспечивая желаемый разрыв колец блоков памяти и места записи новой фразы информации (из регистра 29) и ассоциативного признака (из регистра 3) по адр - СУ j+1

Перезапись признака иэ регистра 3 в блок 22 признаков по адресу j+1 осуществляется эа время записи первого слова h! Следук)щей входной фразы информации, при этом все регистры 24 блока 22 соединяются на это время в линейку с входом по адресу j+1, 1464214 после чего признаки циркулируют в регистрах 24 в течение записи следук>щих М байтовых слов информации.

В результате обработки N фраз информации в блоке 18 оказываются записанными К фраз со своими порядковыми номерами, ассоциативные признаки которых сформированы по сложному поиску по экстремальным («наибольшее» и К-1 ближайшие

«большие») условиям.

ДАЗУ в соответствии с граф-схемой алгоритма работы (фиг. 2) обеспечивает выборку

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

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

Динамическое ассоциативное запоминающее устройство, содержащее последовательно соединенные регистр слова и регистр фразы, блок памяти данных, выход которого является информационным выходом устрой- 25 ства, блок управления, регистр даннь|х, регистр признака и первый блок сравнения, первый и второй информационные входы которого подключены соответственно к выходам первых разрядов регистра слова и оегистра признака, входы приема и разреше- К ния сравнения первого блока сравнения соединены соответственно с первым и вторым выходами блока управления, вход запуска которого является входом обращения устройства, отличающееся тем, что, с целью расширения функциональныХ возможностей уст- $5 ройства за счет обеспечения поиска по экстремальным значениям признака поиска, в него введены блок памяти признаков, второй блок сравнения, дешифратор, блок счетчиков, коммутатор и блок управления записью признака, причем первый информационный вход коммутатора является информационным входом устройства, второй информационный и управляющий входы коммутатора подключены соответственно к выходу блока памяти данных и третьему выходу блока управления, выход регистра фразы подключен к первому информационному входу регистра данных, второй информационный вход которого соединен с информационным выходом блока счетчиков, первый и второй выходы переполнения которого подключены соответственно к первому и второму установочным входам блока управления записью признака, вход запуска которого и счетный вход блока счетчиков соединены с четвертым выходом блока управления, пятый выход которого соединен с входом приема регистра данных, выход которого соединен с информационным входом блока памяти данных, шестой выход блока управления подключен к информационному входу блока памяти признаков и первому информационному входу второго блока сравнения, второй информационный вход которого соединен с выходом блока памяти признаков, седьмой выход блока управления соединен с управляющим входом второго блока сравнения, выход которого подключен к входу окончания цикла блока управления, восьмой выход которого подключен к третьему установочному входу блока управления записью признака, девятый выход блока управления соединен с входом приема регистра признака, информационный вход которого соединен с первым выходом блока управления записью признака, второй выход которого подключен к входу окончания подцикла блока управления, информационные входы группы регистра признака подключены к выходам первой группы блока управления, вь1ходы второй гр ппы которого соединены с входами дешифратора, выходы которого подключены к соответствующим управляющим входам блоков памяти данных и признаков, первый и второй информационные входы блока управления записью признаков подключены соответственно к выходам регистра слова и регистра признака, выход первого блока сравнения подключен к четвертому установочному входу блока управления записью признака, выход первого разряда регистра признака соединен со стробирующим входом блока управления записью признака, выход коммутатора подключен к информационному входу регистра слова, вход признака блока управления является входом задания признака поиска устройства.

1464214

1464214

)g», гт»

6) 7», Сгг4 7г

Фиг.г/

Л2

R5

ЛУ

У1 л bn zg

Рсг.5

Составитель В. Рудаков

Редактор Н. Гунько Техред И. Верес Корректор И. Муска

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

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

П 3035, Москва, гК вЂ” 35, Раушская наб., д. 4/5

Производственно-издательский комбинат «Патент», г. Ужгород, ул. Гагарина, 10i