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

 

СОЮЗ СОВЕтСНИХ сОциАлистичесних

РЕСПУБЛИН (59 4 G 11 С 15/00 фР „.

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

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4031755/24-24 (22) 03.03.86 (46) 23.04.88. Бюл. № 15 (71) Институт кибернетики им. В.М,Глушкова (72) В.А.Яшенко (53) 681.327(088.8) (56) Авторское свидетельство СССР

¹ 1056269, кл. Г 11 С 15/00, 1980.

Авторское свидетельство СССР № 1127008, кл. Г 11 С 15/00, 1983.

I (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике и может быть использовано в системах, построенных на

ÄÄSUÄÄ 1390637 д1 принципах искусственного интеллекта, а также в экспертных системах. Цель изобретения — расширение функциональных возможностей устройства за счет обеспечения запоминания и динамической перестройки ассоциативных .связей по совокупности свойств объектов. Устройство содержит блок 1 счетчиков, первый 2, второй 13 и третий

16 блоки элементов И, первый 3 и второй 11 блоки регистров, первый и второй 8 блоки памяти, первый 5 и второй 14 блоки сравнения, счетчик 6, сумматор 7, регистр 9 сдвига, дешифратор 10, блок 12 триггеров, элемент ,5И-ИЛИ 15, блок 17 управления и пороговый элемент 18. 15 ил.

1390637

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

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

На фиг. 1 изображена структурная схема ассоциативного запоминающего устройства; на фиг. 2 — таблица значений признаков объектов, на фиг. 3 алгоритм формирования Ы вЂ” растущей пирамидальной сети; на фиг. 4 — матрица элементов сети и связи между ними; на фиг. 5 — структурная схема блока управления, на фиг, 6 — микропрограмма работы устройства; на фиг.

7 — структурная схема блока счетчиков; на фиг. 8 — структурная схема первого блока сравнения; на фиг. 9 — 25 структурная схема первого блока элементов И; на фиг. 10 — структурная схема первого блока регистров на фиг. 11 — структурная схема второго блока сравнения; на фиг. 12 — струк- 30 турная схема второго блока регистров; на фиг. 13 — структурная схема блока триггеров; на фиг, 14 и 15 — структурные схемы второго и третьего блоков элементов И соответственно.

Ассоциативное запоминающее устройство содержит (фиг. 1) блок 1 счетчиков, первый блок 2 элементов И, первый блок 3 регистров, первый блок 40

4 памяти, первый блок 5 сравнения, счетчик 6, сумматор 7, второй блок 8 памяти, регистр 9 сдвига, дешифратор

10, второй блок 11 регистров, блок

12 триггеров, второй блок 13 элемен- 45 тов И, второй блок 14 сравнения, элемент 5И-ИЛИ 15, третий блок 16 элементов И, блок 17 управления и пороговый элемент 18. Блок 17 управления содержит (фиг. 5) блоки 19-27 элементов И, регистры 28-34, счетчи— ки 35 и 36 импульсов, элемент НЕ 37, счетчик 38 адреса микрокоманд и блок

39 перепрограммируемой памяти, Блок

17 имеет входы 40-47. На фиг. 1 обоз- 55 начены информационные входы 48 и 49 устройства, Блок 17 имеет также входы

50-66, Устройство (фиг. 1) имеет вход

67 и выходы 68 и 69, Блок 1 (фиг. 7) содержит счетчики

1, и 1 адресов. Блок 5 (фиг ° 8) содержит блоки 5, и 5 сравнения. Блок

2 (фиг. 9) содержит элементы И ?.@-2<.

Блок 3 (фиг. 10) содержит регистры

3,-3 . Блок 14 (фиг. 11) содержит блоки 141 и 14 сравнения и элемент HE

14 . Блок 11 (фиг. 12) содержит регистры 11, и 11, элемент ИЛИ 11 и регистр 11 . Блок 12 (фиг. 13) содержит триггеры 12, -1? . Блок 13 (фиг.

14) содержит элементы И 13,-13«и элемент НЕ 13,д . Блок 16 (фиг. 15) содержит элементы И 16 -16 .

На фиг, 1-15 даны следующие обозначения: g — информационный выход;

Р— информационный вход; А — адресный вход; f — вход разрешения, +1 суммирующий вход; ЗП вЂ” вход разрешения записи; ЧТ вЂ” вход разрешения чтения; 1У вЂ” нулевой вход; 1 — единичный вход; — 1 — вычитающий вход.

Работа устройства поясняется алгоритмом (фиг. 3) формирования растущей пирамидальной сети (РПС), обеспечивающей запоминание и динамическую перестройку ассоциативных связей между элементами сети по совокупности свойств объектов, представленных набором значений признаков (фиг. 2). Связи между элементами

РПС представлены в блоке памяти матрицей элементов сети и связей между ними (фиг. 4), где N разрядов представляют набор значений признаков элементов, а остальные m разрядов указывают. на наличие или отсутствие связи между элементами сети, представленными в строках матрицы. Если разряд установлен, тс это указывает на наличие признака в объекте (фиг.

2 и 4) или наличие связи между элементами (фиг, 4).

Обозначения„ используемые на фиг.

3, следующие:

В . — набор объектов (3=1,2,3,..., п);

А;, А,, — набор элементов сети (i

1,2,3,...,1с); — результат конъюнкции элементов матрицы;

R< R„ — регистры 11, и 11 второго блока 11 регистров;

PR,,PR — признаки, устанавливаемые в блоке l2 триггеров.

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

При включении устройства на входы

54,56,58,60,62,64 и 66 блока 17 управления последовательно подают сигналы, разрешающие запись адресов микрокоманд циклов, а на входы 53, 55, 57, 59, 61, 63, 65 блока 17 в той же последовательности подают адреса (уменьшенные на единицу) микрокоманд циклов В, Е, 1, 2, С, 3 и 4. 10

В блок 4 памяти по входу 48 последовательно производится запись объектов В, при этом подаются сигналы на вход +1 первого счетчика 1„ адреса (фиг. 7), разрешающий сигнал на вход элемента И 2» (фиг. 9) и сигнал записи (ЗП) на вход блока 8 памяти, По сигналу на входе 67 на входе блока 3 (фиг. 10) запоминается адрес последнего объекта В (З=п). На вход 49 устройства подается значение N.

На вход 40 блока 17 подается сигнал, резрешающий запись начального адреса микропрограммы минус (уменьшенного на единицу) по входу 52. За- 25 тем на вход 5f блока 17 подается сигнал,разрешающий прохождение тактовых сигналов по входу 50 на вход +1 счетчика 38 адреса микрокоманд и через счетчик 36 на вход чтения (ЧТ) блока

39 перепрограммируемой памяти микрокоманд, с выхода счетчика 38 на вход адреса (A) блока 39 подается адрес микрокоманды, которая считывается на вход блока 39 при наличии сигнала на входе ЧТ. Микрокоманда имеет верти; кальное кодирование микроопераций, число которых равно 41. Циклы в микропрограмме организованы изменением адреса микрокоманды в счетчике 38. 40

Значение адресов микрокоманд, соответствующих началу соответствующего цикла, хранятся в регистрах 28-34 блока 17 управления.

По первой микрокоманде (фиг. 6) 45 осуществляется сброс счетчикон в блоке 1 счетчиков адреса, триггеров

12„-12 < блока f2, счетчика 6. .Вторая микрокоманда выполняет перезапись объекта В,,где j = 1 (для первого шага), из блока 8 памяти в блок 4 памяти

° В и запоминание адреса А элемента в

55 регистре 3 блока 3 регистров.

Третьей микрокомандой начинается цикл Е, осуществляется перезапись объекта В ., где 1 = 2 (для первого шага), из блока 8 памяти и блок 4 памяти запоминается адрес элемента А в регистре З блока 3 и анализ конца таблицы объектов.

По-четвертой микрокоманде элемент

А < переписывается в регистр 11q блока 11 регистров (фиг. 12).

По пятой микрокоманде адрес элемента А 1„ записывается в регистр

З блока 3 регистров.

По шестой микрокоманде (цикл С) осуществляется промежуточный сброс устройства, установка указателя выборки элементов в начало матрицы и запись Af, н регистр ff блока 11 регистров.

Седьмой микрокомандой начинается выполнение цикла В. Микрокоманда выполняет запись элемента А; н регистр

11,, анализ конца матрицы элементов, конъюнкцию k = К23 п R24, инверсию.

k nAi. uk nА

По восьмои микрокоманде осуществляется сдвиг содержимого регистра

9 сдвига. Эта микрокоманда повторяется п раз по числу разрядов в k.

В счетчике 6 (фиг. 1) осуществляется подсчет количества установленных разрядов. С ныхода счетчика 6 результат поступает на вход порогового элемента 18, Если число установленных разрядов k >i 2, то на выходе порогового элемента 18 вырабатывается сигнал и поступает на вход триггера 12 блока 12.

IIo n + 1 микрокоманде осуществляется анализ: число установленных разрядов k (2; если нет, то PR2=0 и выход на цикл В; если k 1 2, то анализ k = Rf f, (k = A;); если нет, то PR 1 = 1, если k = R11„., то анализ k = R11 (В. = А Д; если k = Rife, то айализ РК1 = О; если PR1 О, то выход на цикл 1; если PRf = О, то выход на цикл 2; если k = Р11,, то .анализ PR1 = О; если PR1 Ф О, то выход на цикл 3, если PR1 = О, то выход на цикл 4, В цикле i по микрокоманде п+2 осуществляется запись в элемент А; значения k n А, 1390637

По микрокоманде и + 3 осуществляется запись в элемент А 1, значения

k nЛ„

По микрокоманде п + 4 осуществляется запись k в строку k + 1.

По микрокомандам n+5, n+6, n+7 осуществляются запись единицы в строке элемента А; в столбец N + адрес элемента А ь,, ycTaHoBKR PR2 = 1, 10 сброс PRI и выход на цикл В.

В цикле 2 по микрокомандам n+8, n+9,n+10, n+i1, n+i2 осуществляются

А : = k Л А, запись единицы в стро-. ке элемента А» в столбец N + адрес элемента А: PR2 = 1, PR1 = 0 и переход на цикл В.

В цикле 3 по микрокомандам и+13.

n+14, n+15 осуществляется выполнение третьего цикла; А1, . = О, указатель просмотра матрицы элементов уменьшить на единицу i = i-1 и сбросить PR1.

В цикле 4 по микрокомандам а+16, n+17, n+18, n+19 и и+20 выполняют

A .,: = k n А1„ установку разряда N + 25 адрес А1„ сброс PR1, установку PR2 и выход на цикл В. г1алее происходит выполнение описанного цикла В. Если PR2 установлен, осуществляются переход на цикл С вЂ” 3< установка указателя просмотра матрицы в нуль i = О, и новый просмотр матрицы с целью выявления элементов, совпадающих по установленным признакам.

Ъ

Если PR2 не установлен, то переход на цикл Е, в котором из второго блока

4 памяти выбирается следующий объект

В. (j = 2 выполняется второй шаг) и

1 т.д. до исчерпания всех объектов во втором блоке 4 памяти.

Таким образом осуществляется запись объектов в первый блок памяти с формированием и динамической перестройкой (в процессе записи) ассоциативных связей по совокупности свойств записываемых объектов.

Считывание информации из ассоциативного запоминающего устройства осуществляется по сигналу разрешения чтения на входе первого блока 8 памяти.

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

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

Ассоциативное запоминающее устройство, сопержащее первый блок памяти, первый блок регистров, пороговый элемент, блок счетчиков, блоки сравнения и блок управления, причем первый выход блока управления соединен с первым суммирующим входом блока счетчиков, второй выход блока управления соединен с первым установочным входом блока счетчиков, третий выход блока управления соединен с вычитающим входом блока счетчиков, четвертый выход блока управления соединен с вторым суммирующим входом блока счетчиков, пятый выход блока управления соединен с вторым установочным входом блока счетчиков, шестой и седьмой выходы блока управления соединены соответственно с входами разрешения записи и чтения первого блока памяти, восьмой, девятый, десятый и одиннадцатый выходы блока управления соединены соответственно с первым, вторым, третьим и четвертым входами разрешения записи первого блока регистров, о т л и ч а ю щ е ес я тем, что, с целью расширения функциональных возможностей устройства за счет обеспечения запоминания и динамической перестройки ассоциативных связей по совокупности свойств объектов, в него введены первый, второй и третий блоки элементов И, второй блок регистров, сумматор, второи блок памяти, регистр сдвига, счетчик, дешифратор, блок триггеров и элемент 5И-ИЛИ, информационный выход которого соединен синформационным входом первого блока памяти, вы- ход которого соединен с первым информационным входом второго блока регистров, первый и второй выходы которого соединены с первым и вторым информационными входами второго блока элементов И, третий выход второго блока регистров соединен с первым информационным входом элемента 5И-HJ7rf, второй информационный вход которого соединен с первым выходом второго блока элементов И, второй выход которого соединен с третьим информационным входом элемента 5И-ИЛИ, третий выход второго блока элементов И соединен с первым входом второго блока сравнения, первый выход которого соединен с первым установочным вхо1390637 дом блока триггеров, первый, второй гистров соединены соответственно с и третии прямые выходы которого сое- четвеРтым и пятым информационными динены соответственно с первым, входамп первого блока элементов И, вторым и третьим разрешаюгртми входа- втоРой выход котоРого соединен с аЛми второго блока элементов И, чет- ресным входом первого блока памяти и вертый выход которого соединен с первым входом сумматора, выход кото— вторым входом второго блока сравнения, Рого соединен с вхоЛом Дешифратора, второй выход которого соединен с выход которого соеди е оеди не н с в торым инпервым входом третьего блока элемен- 10 фоРмационным вхоЛом второго блока Ретов И, третий выход второго блока. гистров, пятый выход пеРвого блока ом третьего блока элементов И, пятый вы- сумматора, восьмой, девятый и Лесяход второго блока элементов И сое- тый выходы второго блока элементов динен с четвертым информационным вхо- И, первый, второй, третий и четвердом элемента 5И-ИЛИ и информационным тый выходы третьего блока элементов входом регистра сдвига, выход кото- И соединены соответственно с входарого соединен со счетным входом ми первой группы разрешения записи счетчика, выход которого соединен с блока управления, двенадцатый, тривходом порогового элемента, выход 20 надцатый, четырнадцатый, пятнадцатый которого соединен с вторым установоч- н шестнадцатый выходы блока управным входом блока триггеров, второй и ления соединены соответственно с третин инверсные выходы которого сое- первым вторым третьим

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

1 У Лвадцатыи и Лвадпрямой выход блока триггеров соединен - цать первый выходы б

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

ый вход третьего динен с пятым инверсным выходом бло- блока элементов И подключены соответка триггеров, первый выход блока счет- còâåíío к шине нулевого потенциала и чиков соединен с первыми информацион- к двадцать первому выходу блока управными входами первого блока элементов ления, двадцать второй, двадцать треИ и первого блока регистров, второй тий, двадцать четвертый, двадцать выход блока счетчиков соединен с вто- пятыи двадцать шестой и два а

40 вадцать рыми информационными входами первого седьмой выходы блока управления соеблока элементов И и первого блока динены соответственно с первым, вторегистров и первым информационным вхо- Рым, тРетьим, четвеРтым, пЯтым нУ дом первого блока сравнений, первый левыми и шестым информационным входавыход которого соепинен с третьим

45 ми блока триггеров а двадца

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

Э с орои, тридцат ь торого соединен с четвертым входом третий, тридцать четвертый и тридпервого блока сравнения и адресным цать пятый выходы блока управления входом второго блока памяти, выход 55 соединены соответственно с первым, которого соединен с информационным вторым, третьим, четвертым и пятым входом первого блока памяти, третий Разрешающими входами элемента 5И-ИПИ, и четвертый выходы первого блока ре- информационный вход второго блока паI 3906 мяти и третий информационный вход первого блока регистров являются информационными входами устройства, выход первого блока памяти является информационным выходом устройства, входы разрешения записи первого блока регистров являются входами первой группы признака записи устройства, входы второй группы разрешения запиСи блока управления являются входа37 1О ми второй группы признака записи устройства, входы адресов микрокоманд ,блока управления являются адресными входами устройства, второй выход первого блока сравнения является выходом останова устройства, вход тактовых импульсов блока управления и вход строба блока управления являются входами синхронизации уст— ройства.

1390637

1390б37

1 15 Ф 5 b..

Значения при

1390637

1gggg Мают

4i

Ак луч т

С

Щ

Ю

6 лу Af

4i Ag я

Л, 4я 4

4„4f

Аки лс! 390637

1390637

1390637 ф»»е

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

Редактор Л. Гратилло Техред А. Кравчук

Корректор Л,Пилипенко

Заказ 1771/48 Тираж 590 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул, Проектная, 4