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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву(22) Заявлено 100681 (21) 3299324/18-24 (51) М. Кл.

G 11 С 15/00 с присоединением заявки М (23) Приоритет—

Государственный комитет

СССР но делам изобретений и открытий

Опубликовано 3611.82. Бюллетень Но 4 4

Дата опубликования описания 30.1182 (53) УДК 681. 3Л7 (088. 8) (72) Автор изобретения

Я . И. Фет

У

Институт математики Сибирского отделений AH СССР и Новосибирский государственный универс1ттет им. Ленинского комсомола (71) Заявители (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО

Изобретение относится к запоминающим устройствам.

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

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

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

НЕРАВНОЗНАЧНОСТЬ, счетчики единиц, схему сравнения, а также регистр очередного слова и регистр результата, причем выходы элементов HEPAB—

НОЗНАЧНОСТЬ соединены со входами соответствующих счетчиков единиц, выходы которых подключены к соот" ветствующим входам схемы сравнения, а управляющие входы блока памяти и регистра опроса соединены с соответствующими выходами .блока управления Е23.

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

3О в нем используются аналоговые счет978196 чики единиц, основанные на принципе сумг, улронаулия токов, и аналоговая схема сравнения.

Цель изобретения -- повышение быстродействия и надежности устройства(Поставленная цель достигается тем, что н ассоциатинное запоминаю .»уее устройство содерх<ащее регистр опроса, накопитель,. элементы НЕРАБу31ОЗ13 EFOC I!I „0»1 Т ЧИ<КИ Еднпнц „pe1 1»стp p зуууь ;"% та и )и< ха блок уiipBH

ЛЕН1ЛУУ,, Ь»ЫХО111=1 1<ОТОРО.< О ПОДКЛЮ ГЕНЫ К

УпРавлнюУу»им HI<îïàì РегистРа РезУльтата пОиска „HBкОпителя и регистра

Опроса, выход которог0 подключен к

Одну,. 1 из —.-. <0,»401» элементов НЕРАВНО ЗгуАТ»ТНОС- 1 1.. 1»недеууа сортируу<»у»тая матри ца . н. <»,ууы кОтО»СОй подключег1ы к ны с . С . <» 1 < Н e,;Ë",iii! !i,р,а НЫЛОДЫ . К

»т лг 1»i.,"1»с"1 1»а. рс 1»ул ь татcl пОП 01< а р

-- = .Π—::-;;а:.<О-.п -е»ля соедуунепы с,пру,.-; »1 —,-", .-,;; ——.,1. с-.;.:„-:;;-- -iz» НЕРАБ11ОЗНА<1Ii 3Cc . ны-.-.„-оды которых сОРдинены с

-»х<-,, .1 ii; 0-1< тчиков единиц,.

Н.=. ф.уг. 3 приведена функциональная, .-;c.:а а ссоинатИННОГО ЗапомянаЮ111Его ,»ст»=0»01»ха; на. фиг „2 — структурная

:;-О.л=-. буio ..à управления; на фиг. 3

",-100 е;ууные дулу»г-раммь. работь1 устрой »>»

1» Г с 0lT, и а т и н н 0 е 3 а 10 MH I. а10 ще е;у с т— ройстно (фиг.1) содержит блок 1

1: .нулху,-;-1 акоп» iель 2 „coстоя11 <ий

;, - разрядных запоминающих уучеек „.

М р.i.»oяду»Н1:1 pc»ÃI<стр 3 ОпрОса М эл» ".=я=он 111ЕГА131" ОЗНА»-11-1ОСТЬ 4 М

l0 .-, ",-ра»pядных двоугчных счетчиков

5 едулул1114 „М-разрядный регистр 6 резулу тата »IOITcl N еек 8 н каждой строке. Инверсный выход, -го запоминающего элемента чет-чулка 5 (1.— 1, м; 3 =-1, log!3N) соединен с информационным входом i3-ой ячейки 8 матриць1 7, Перныуй логический выход (1, log>N) -ой ячейки 8 подключен к единичному входу ».-го разряда регистра 6, Нуле 1.Ie нходы всех разрядов регистра 6 объедигуены и подключены к ныходу 9 блока 1 управления, Управляющие входы накопителя 2 и регистра 3 соединены соответственно " выходами 10 и 11 блока 1 управления, 1

Блок 1 управления (фиг,2) сойеРжит регистр 12 кода операции, генератор 13 тактовых импульсов, деу»уифратор 14, микропрограммную матрицу

15, регистр 16 микрокоманд, Ассоциативное запоминающее устройство работает следующим образом.

Слова массива-аргумента хранятся в запоминающих ячейках накопителя 2, а признак опроса - в регистре 3 опроса. Запоминающие ячейки накопителя и регистр опроса могут иметь различную конструкцию (статические или динамические ЗУ, сдниговые регистры, Зу на ЦМД, дорожки нращающихся магнитных ЗУ и т.д.). Однако они должны обеспечивать последовательное поразрядное обращение, а именно: при поступлении очередного управляющего импульса на управляющий вход накопителя 2 с ныхода каждой запоминающей ячейки считывается очередной разряд содержимого данной ячейки. Аналогично при поступлении управляющего импульса на управляющий вход регистра 3 опроса с выхода этого регистра считывается очередной разряд его содержимого.

При поступлении на входы блока 1 управления команды поиска ближай113его по Хэммингу блок 3. управления нырабатывает следующую послe»IOT»ательность операций (фиг.3).

Б первой микрокоманде выдается сигнал на выходе 9 блока 1, который осуществляет установку н 0 всех разрядов регистра 6. Затем в ряде последовательных миу<рокоманд выдается серия из сигналон на выходах 10 и 11 блока 1, В результате происходит последонательная выборка из накопителя 2 всех разрядных срезов массива-аргумента с синхронной выборкой соответствующих разрядов регистра 3 опроса, Разряды с всех

Е4-слов-аргументов поступают из на— копителя 2 на Одни из входов соответствующих элемегутон НЕРАРНОЗНА<1НОСТЬ 4, Одновременно из регистра 3 на другие входы нсех элементов НЕРАБНОЗНА<1НОСТЬ 4 поступает сООтн Ртствующий разряд признака опроса.

Для тех слов, где значение какоголибо разряда не совпадает со значением соответствующего разряда признака опроса, на выходах соответстнующих элементов НЕРАВНОЗНАЧНОСТЬ 4 вырабатываются единицы, которые прибавляются в предыдущих тактах значениям соответствующих счетчиков 5.

По окончании этого цикла в каждом из счетчиков 5 содержится двоичное число, равное расстоянию Хэмминга. между соответствующим слоном массива-аргумента и признаком опроса.

Теперь выделение строки, содер жащей слово, ближайшее по Хэмминт у к признаку опроса, сводится к выделению счетчика 5, содержащего минимальное двоичное число. Последняя операция осуществляется матрицей 7, Необходимо отметить, что н общем случае массив-аргумент может содержать несколько слов, имеющих одинаковое минимальное кодовое расстояние по Отношению к признаку опроса, причем эти слона гтгут быть одинаковыми (тогда несовпадения имеют мес978196 то в одних и тех же разрядах) либо различными (несовпадения в разных разрядах). Всем этим словам соответствуют одинаковые (минимальные) содержимые счетчиков, и они за один цикл параллельно выделяются матрицей 7.

Кроме поиска ближайшего по Хэммингу,nðåäëàãàåMoå ассоциативное запоминающее устройство может использоваться для решения других задач, свя- 1О занных с определением некоторых свойств двоичных кодов, а именно: упорядоченной выборки слов из устройства; определения расстояния

Хэмминга (по отношению к признаку . опроса) для данного слова массивааргумента; выделения слова (слов), имеющего заданное расстояние

Хэмминга (по отношению к заданному признаку опроса), в частном случае совпадающего с признаком опроса.

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

В ассоциативном запоминающем устройстве операция поиска ближайшего по Хэммингу выполняется параллельно по всем словам массива-аргумента, и время, необходимое для ее выполнения, пропорционально разрядности слова и не зависит от объема масси- 35 ва, что обеспечивает существенное увеличение быстродействия, Кроме того, применение цифровых двоичных счетчиков единиц и сортирующей матрицы обеспечивают повышенную íà- 40 дежность.

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

При практической реализации счетчики 5 единиц могут быть совмещены с матрицей 7, образуя единую двумерную однородную структуру. Однородность всех блоков и регулярность связей между ними облегчает реализацию предлагаемого ассоциативного запоминающего устройства средствами интегральной технологии, что является его дополнительным преимуществом, Формула изобретения

Ассоциативное запоминающее устройство, содержащее регистр опроса, накопитель, элементы НЕРАВНОЗНАЧНОСТЬ, счетчики единиц, регистр результата поиска, блок управления, выходы которого подключены к управляющим входам регистра результата поиска, накопите я и регистра опроса, выход которого подключен к одним из входов элементов НЕРАВНОЗНАЧНОСТЬ, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия и надежности устройства, в него введена сортирующая матрица, входы которой подключены к выходам счетчиков единиц, а выходы — к входам регистра результата. поиска, выходы накопителя соединенЫ с другими входами элементов НЕРАВНОЗНАЧНОСТЬ, выходы которых соединены с входами счетчиков единиц.

Источники информации, принятые во внимание при экспертизе

1. Заявка ФРГ 9 2605344, кл. 42 t2 15/00, опублик. 1978.

2, Патент С21А 9 4084260,кл.364-900, опублик. 1978 (прототип).

978196

g f0 /1 юг. 2

2 3

Риа, 3

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

Редактор И. Ковальчук ТехредЛ.Пекарь Корректор М, Коста, Заказ.9227/67 Тираж 622 Подписное

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

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

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