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

 

Изобретение относится к вычислительной технике, в частности к запоминающим устройствам. Целью изобретения является повышение быстродействия устройства. Устройство содержит детекторный блок 1, матрицу m X п (где m - число строк и п - число столбцов матрицы) запоминающ1тх элементов 2, например, В-т 5иггеров, (Л со О5 О 4 00

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

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

РЕСПУБЛИК

Al (19) (11) (51)4 G 11 С 15/00

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

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

° ° °

° ° е

2р

° ° е

° ° °

° ° е е ф ° ° е ° °

r..

° °

° °

° °

° °

° °

12р

° ее е ° °

Ос

° ° Ô

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4015258/24-24 (22) 22, 01. 86 (46) 07,06, 87. Бюл. №- 21 (71) Казанский авиационный институт им.A.Н.Туполева (72) В.Г,11отягин (53) 681.327 (088,8) (56) Авторское свидетельство СССР № 277857, кл. G ll С 15/00, 1968, Авторское свидетельство СССР

¹ 674802, кл. G 11 С 15/00, 1978, (54) АССОЦИАТИВНОЕ ЗАПОМИН JOLIFÅ УСТРОЙСТВО (57) Изобретение относится K вычислительной технике, в частности к запоминающим устройствам. Целью изобретения является повыпение быстродействия устройства, Устройство содержит детекторный блок 1, матрицу

m х и (где m — число строк и и число столбцов матрицы) запоминающих элементов 2, например, D-триггеров, е ° °

° ° °

1316048 блоки 3 -3 сравнения, регистр признаков опроса, блоки 5„-5 „ адержки, сумматоры 7, -7„с информв ионными входами 13„-13 и выходами 12„ -12 и блок 8 поиска максимума совпадений, который содержит матрицу ячеек ассоциативной памяти. Каждая ячейка ассоциативной памяти содержит два элемента НЕ, элемент ИЛИ-НЕ и четыре элемента И. В запоминающих элементах 2 находятся ассоциативпLl(lIpH паки,которые сравниваются B блоках 3„-3 „с йризнаками опроса, сод«ржаг имися в регистре 4, При их совпадении на выходе блока 3 появляется сигнал "1", который обеспечивает прохо;ление сигнала "1" с входа блока 5 задержки данной строки на ег< выход и на вход следующего в столбце б ока задержки ° Во всех сумматора>.. 7, -7 одного столбца подсчитывается сумма по модулю 2 (где е — число информа—

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

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

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

Устройство содержит (фиг.l) детекторный блок 1, матрицу m x п, где ш — число строк и n — число столбцов матрицы запоминающих элементов

2, блоки 3, -3„ сравнения, регистр 4 признаков опроса, блоки 5, -5„ задержки с первыми входами 6, сумматоры

7„ -7„ и блок 8 поиска максимума совпадений.

На фиг.l обозначены вторые входы

9,-9„, выходы 10,-10„, третьи входы

1l 11„ блоков 5„-5„ задержки, выходы 12,-12 и входы 13„ -13 сумматоров 7„-7 „, четвертые входы 14 блоков

5„-5 „задержки.

Блок 8 поиска максимума совпадений содержит (фиг.2) матрицу ячеек

l5 ассоциативной памяти с первыми ционных входов каждого сумматора 7) единичных сигналов несовпадения.

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

"0" на выходе блока 5п какого-либо столбца исключает из поиска соответствующий столбец ячеек в блоке 8.

Так как с выходов каждого сумматора

7п поступает в блок 8 остаток от деления К/2 в инверсном виде (где К ( число несовпадающих разрядов признаков опроса и ассоциативных признаков), то в блоке 8 осуществляется поиск минимального остатка от деления, Устройство обеспечивает поиск ближайшего по образу слова зе меньшее, чем К,, число тактов, за счет чего повышается его быстродействие, 2 з.п.ф-лы, 5 ил., 1 табл. выходами 16, управляющими входами

17 и вторыми выходами 18, Каждая ячейка 15 ассоциативной памяти содержит (фиг,3) первый элемент НЕ 19, первый 20 и второй 21 элементы И, элемент ИЛИ-НЕ 22, третий 23 и четвертый 24 элементы И> второй элемент

fiE 25, На фиг.2 и 3 обозначены разрядные шины 26 блока 8 поиска макси10 мума совпадений, Каждый блок 5 задержки фиг.4 может содержать, например, двухступенчатый синхронный

D-триггер 27, элемент 28 ИЛИ и элементы И 29 и 30. Каждый сумматор 7 содержит (фиг.5) элемент.л 31, -31 равнозначности (где 1 log< m/2) и элементы ИЛИ 32 -32 . Запоминающие

e элементы 2 могут быть выполнены иэ синхронных одноступенчатых В-тригге20 ров.

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

В исходном состоянии в регистре

4 (фиг. 1) находится приэнак опроса, в вертикальных линейках их синхронных одноступенчатых D-триггеров 2 находятся ассоциативные признаки, триггеры 27 находятся в нулевом стабильном состоянии. На вход 6 эле30 группы количество нулей, поступающих с входов 6 блоков 3, равно 2 (в крайней верхней группе — 4 2 ).Единица, поступившая по входу 9, распространяется внутри группы по элементам И 29 блоков 5,-5„ до границы.

3 13!60 мента ИЛИ 28 (фиг.4) и сумматора 7 и входы 13„ действует уровень логии и ческого О, если состояние соответствующих запоминающего элемента 2 и разряда регистра 4 не совпадают, или — "l, если совпадают. На входы

9„ всех блоков 5„ и входы 13 сумматоров 7 подается константа "1".Ес1 ли с выхода какого-либо блока 3 по выходу 6 поступает сигнал "1" (раз- 10 ряды совпадают), то этот сигнал проходит через элемент ИЛИ 28 иа вход элемента И 29 и разрешает прохождение сигнала с входа 9 на выход 10 блока 5. Этот же сигнал ("!") поступает на вход элемента ИЛИ 32, соот.ветствующего сумматора 7 (фиг.5), пройдя через него поступает на входы элементов равнозначности 31„ и с элементов ИЛИ 322 и так далее, т.е, 20 если на вход 6 элементов равнозначности 31, -31р поступает сигнал "!", в этом случае на выходы 12 сумматора 7 проходит информация с его входов 13, — 13 ° Если по входу 6 поступает сигнал 0 (разряды не совпада. ют), то в сумматоре 7 происходит прибавление единицы к коду, представленному в инверсном виде, постулающему по входам 13 -13 с выдачей

Г результата (в инверсном виде) иа выходы 12„-12

В столбцах иэ сумматоров 7, -7 и происходит подсчет по модулю . сигналов несовпадения, поступающих с 35 соответствующих блоков 3, Если код, поступающий по входам 13 в сумматор

7, не равен "О" (имеется хотя бы одна единица), то на выходе последнего элемента ИЛИ 32 этого сумматора 4О

7 появляется "l", которая, пройдя через вход 11 на элемент ИЛИ 28 блока 5, поступает на вход элемента

И 29 (фиг.4) и соответственно на выход 10 этого блока 5 проходит сиг- 45 нал с входа 9. Столбец иэ сумматора

7„ -7 делится на группы, внутри группы значение выходов 11 (элементов

ИЛИ 32) равно "l" а на границах групп равно 0, так как код на входах 13, сумматора 7 равен "О" и по входу 6 проходит "О". Внутри

48

Первый сигнал, постуиииг;и1. иа вгс элементы И 30 блокс и 5, -5, установит в "l" триггеры 27 блоков 5 перВОЙ Гp l1hl як 1юч ая и Гpаи11чиый блок 5, тем самым разрешает прохождение единицы с входа 9 блока 5 иа выход 10 этого же блока 5 H следующую группу. !lусть, например, имеется два столбца с наименьшим количеством групп (например, S=3). Если ! = 3, К вЂ” количество несовпавших разрядов (К„=25, К =26), то после трех тактов сигнал единицы появится на выходах 10 крайних верхних блоков

5 этих столбцов, С выходов !2, „ сумматоров 7 этих столбцов в блок

8 поступят соответственно коды чисел ʄ— 2 S и К., — 2 S (т ° е. единицы и двойки) в инверсном виде. Единицы, поступающие с выходов 0 блоков 5„этих столбцов, поступают на входы 17 блока 8, разрешая его рабо— ту в соответ ствующих столбцах °

Если на вход 7 ячейки 15 (фиг.2) поступает сигнал "0" то через элемент НЕ 19 он отпирает элемент И 21 и на выход 16 с шины нулевого потенциала поступает "О", тем самым соответствующий столбец в блоке 8 исключается иэ поиска и на выходе 16 крайней верхней ячейки 15 блока 8 появится сигнал "О". Если на вход 17 поступает "1", то она через элемент

НГ 19 запирает элемент И 21. Единичный сигнал с одного из входов 12 отпирает элемент И 23, через который единица входа 17 поступает на выход

16. Если оказалось, что в строке ячеек 15 блока 8 на входы 12,-12 всех ячеек, у которых на входе 17 действует сигнал 1", поданы сигналы

"О", то сигнал "1" с входов 17 проходит через элемент И 24 на выход

16, Элементы И 24 этой строки ячеек

15 открываются единицей на шине 26, так как сигнал "0" поступающий с информационных входов 12,-121 через элемент НЕ 25 и элемент ИЛИ-ЙЕ 22, запирает элемент И 20, а элементы

И 20 тех ячеек 15, у которых сигнал

"О" подан на вход 17, так же заперты. Таким образом, если на совокупность входов 17 крайней нижней строки ячеек 15 блока 8 подать "1", то на выходе 16 крайней верхней ячейки 15 блока 8 появится си -нал "1", если в соответствующем ..толбце на входы 12,-12 ячеек 15 подано макси1316048

1 I т

16 32 64

Номер

2,8 3,3

4,7 6,0

6,9 9,9 25

8,9 14,6

2,2

3,2

4,1

19,0 мальное число. Так как с сумматоров 7 по входам 12 -12 поступает

t остаток от деления К/2! в инверсном виде, ro осуществляется поиск минимального остатка от деления. Коэффициент увеличения быстродействия зависит от m К,l, и н таблице дано значение его величины в зависимости от m и 1, при этом величина К беm рется равной ----,значение 1 целе2 сообразно выбирать log К, Как видг но из таблицы, предложенное устройство позволяет ускорить процесс поиска ближайшего ло образцу" слова, Ф о р м у л а и з о б р е т е н и я

1 . Ассоциативное запоминающее уст35 ройстно, сочержащее регистр признаков опроса, блоки сравнения, детекторный блок, блоки задержки и матрицу запоминающих элементов, причем выход каждого запоминающего элемента строки матрицы подключен к первому нходу соответствующего блока сравнения, второй вход которого соединен с соответствующим выходом регистра признаков опроса, инверсный выход каждого бло- 45 ка сравнения подключен к первому входу блока задержки, второй вход которого соединен с выходом предыдущего блока задержки данного столбца матрицы, о т л и ч а ю ш е е с я тем, что, с целью повышения быстродействия устройства, в Hего введены блок поиска максимума совладений и сумматоры, причем один из входов каждого сумматора подключен к инверсному выходу соответствующего блока сравнения, а выход переноса — к третьему входу соответствующего блока задержки, вторые входы первых блоков задержки и другие входы лервьгх сумматоров каждого столбца матрицы подключены к шине единичного потенциала, выходы каждого сумматора соединены с другими входами последующего сумматора данного столбца матрицы, выходы последнего сумматора каждого столбца матрицы соединены с группой информационных нходов блока поиска максимума совпадений, управляющие входы и выходы которого подключены соответственно к выходам последних блоков задержки каждого столбца матрицы и к входам детекторного блока, четвертые входы блоков задержки объединены и являются входом синхронизации устройства.

2. Устройство по п.1, о т л и ч а ю щ е е с я тем, что блок поиска максимума совпадений содержит матрицу ячеек ассоциативной памяти,причем первый выход каждой ячейки ассоциативной памяти соединен с первым входом последующей н столбце ячейки ассоциативной памяти, первые входы первых и первые выходы последних в столбцах ячеек ассоциативной памяти являются соответственно управляющими входами и выходами блока, информационными входами которого являются вторые входы ячеек ассоциативной памяти, вторые выходы ячеек ассоциативной памяти строки объединены.

3. Устройство по пп. 1 и 2, о т л и ч а ю щ е е с я тем, что каждая ячейка ассоциативной памяти содержит элементы НЕ, элемент ИЛИ-НЕ и элементы И, причем первый вход перного элемента И соединен с выходом элемента ИЛИ-НЕ, первый вход которого подключен к выходу первого элемента HE и к первому входу второго элемента И, вторые входы первого и второго элементов И соединены с шиной нулевого потенциала, второй вход элемента ИЛИ-НЕ подключен к выходу второго элемента НЕ, вход первого элемента НЕ и первые входы третьего и четвертого элементов И объединены и являются первым входом ячейки, второй вход третьего элемента И и вход второго элемента НЕ объединены и являются вторым входом ячейки, второй вход четвертого элемента И подключен к выходу первого элемента И, выходы элементов И с второго по четвертый объединены и являются первым выходом ячейки, вторым выходом которой является выход первого элемента И.

1316048

1316048

Фиг. Ч

f2<

Рие 5

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

Техред Л. Олийнык Корректор Г.Решетник

Редактор Г.Гербер

Тираж 589 Подписное

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

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

Заказ 2369/54

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