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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ Союз СоветскихСоциалистическихРеспублик К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(23) Приоритет -Государственный комитет СССР но дедам изобретений и открытий(72) Авторизобретения Я.И. Фет Институт математики Сибирского отделений АН СССРи Новосибирский государственный универсйтетим. Ленинского комсомолаа.е,(71) Заявители(54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО Изобретение относится к запоминающим устройствам,Известно ассоциативное запоминающее устройство, состоящее из расположенных в форме матрицы накопительных блоков, каждый из -которыхсодержит адресуемый запоминающий модуль с адресными и разрядными шина"ми и имеет декодер опроса для возбуждения адресных шин адресуемогозапоминающего блока, выходы которогоподключены к соответствующим им адресным шинам запоминающего модуля,иэ регистра опроса для записи и хранения кода опроса, представляющегособой определенную комбинацию бинарных поисковых признаков, иэ детек-торов, постоянно связанных входамис определенными разрядными шинаминакопительных блоков отдельных столбцов матрицы, из дополнительного декодера опроса для возбуждения отдельных детекторов и дополнительногорегистра огроса 1 3.Недостаток этого устройства. -ограниченный набор операций, Так,в нем не осуществляется важная дляпрактических приложений операцияпоиска слов, имеющих минимальноекодовое расстояние по отношению к признаку опроса .(поиск ближайшегопо Хэммингу) .Наиболее близким техническим ре" 5 шением к предлагаемому является ассоциативное запоминающее устройство,содержащее блок управления, блокпамяти, регистр опроса, элементыНЕРАВНОЗНАЧНОСТЬ, счетчики единиц,схему сравнения, а также регистрочередного слова и регистр результата, причем выходы элементов НЕРАВ -НОЗНАЧНОСТЬ соединены со входамисоответствующих счетчиков единиц,выходы которых подключены к соот"ветствующим входам схемы сравнения,а управляющие входы блока памяти ирегистра опроса соединены с соответствующими выходами блока управления Е 22.В известном устройстве операцияпоиска ближайшего по Хэммингувыполняется последовательно по словам массива-аргумента, и время,необходимое для ее выполнения,ропорционально объему массива, чемобусловлен основной недостаток устройства - малое быстродействие. Кроме тога, это устройство обладаетнедостаточной надежностью, так как 30 в нем используются аналоговые счет 978196чики единиц, основанные на принципесумгрулронания токов, и аналоговаясхема сравнения,Цель изобретения - повышениебыстродействия и надежности устройтва(Поставленная цель достигаетсятем, что н ассоциатинное запоминающее устройство содержащее регистрОпроса, накопительр элементы НЕРАВНОЗ 1 л 7 ЯКОС 1 Ьсчетрикуг единицу регистр везультата поиска, блок управЛЕНИЯр НЫХОПЬУ КОТОРОГО УЛОЦЕЛУО"РЕНЫ Куправляющим нхопам регистра результата поискар накОпителЯ и РегистРаОпроса, выход которого подключен кОпии;", из нхоцон элеглентов НЕРАВНОзнА".ТПОс 1 ь. ннедеууа р.;Ортирующая матрица входы котоуоой подуруяусученьу к выхДа, сУУт Улхг,н е, ", .ив р ". выхоцыУН Уи, РН ."ИсГРН РСЗУЛЬТата ПОЦС 1(а р-,рг О - ,; руа конту геля соедциеууы с друг;р ( н; лгу-.",г.;л злеуеуутон НЕРАВуОЗНАЧ 1:;ОС Ь р вь ходы которых соединены снхочат;,ул счотчууков единиц,Н;-. ф.уг.1 приведена функциональная;.разрялулуух запоминающих учеек р111-ра,урядный регул стр 3 опросаэту ".=ул Он 1 П",ГАу 3 у".ОЗНАул 110 СТЬ 4 МТо.-.,х-разрядньух двоичных счетчиков5 единицу у 11-разрядныйу регистр 6 резулутата поиска и сортирующую матри;ту 7, Одержащую К строк по 1 О 9 2 Кячеек 8 н каждой строке. Ннверсньуйьгуход 1-го запоминающего элементат-ГО рсчратчулка 5 (3.=1 р Г 4 р=-1 р.у.о 92 И)соединен с информационным входом 1.)-ой ячейки 8 матрицры 7, Первый логический выход (1 р ТорИ) -ойячейки 8 подключен к единичномувходу 1.-го разряда регистра б, Нулевые нходы всех разрядов регистра бОбъединены и подключены к ныходу 9блока 1 управления, Управляющиевходы накопителя 2 и регистра 3 соединены соответственно с выходами 10и 11 блока 1 управления,Блок 1 управления (фиг,2) содержит регистр 12 кода операции, генератор 13 тактовых импульсов, деуууифратор 14, микропрограммную матрицу15, регистр 16 микрокоманд,Ассоциативное запоминающее устройство работает следующим образом.Слова массива-аргумента хранятсяв запоминающих ячейках накопителя 2,а признак опроса - в регистре 3опроса. Запоминающие ячейки накопителя и регистр опроса могут иметь различную конструкцию (статические или динамические Зур сдвиговые регистры, ЗУ на ЦМДр дорожки нращающихся магнитных ЗУ и т.д.). Однако они должны обеспечивать последовательное поразрядное обращение, а именно: при поступлении очередногоуправляющего импульса на управляющийвход накопителя 2 с ныхода каждойзапоминающей ячейки считываетсяочередной разряд содержимого даннойячейки, Аналогично при поступленииуправляющего импульса на управляюуций вход регистра 3 опроса с выхода этого регистра считывается очередной разряд его содержимого.При поступлении на входы блока 1управления команды поиска ближайуу 1 его по Хэммингу блок 1 управления нырабатывает следующую последовательность операций (фиг.3).В первой микрокоманде выдаетсясигнал на выходе 9 блока 1, которыйосуществляет установку н О всехразрядов регистра 6. Затем в рядепоследовательных микрокоманд вь 1 дается серия из сигналон на выходах 10 и 11 блока 1, В результате происходит последонательная выборка из накопителя 2 всех разрядных срезов массива-аргумента с синхронной выборкой соответствующих разрядов регистра 3 опроса, Разряды с всех М-слов-аргум нтов поступают из накопителя 2 на одни из входов соответствующих элеглентон НЕРАВНОЗНАр 1- НОСТЬ 4, Одновременно из регистра 3 на другие входы нсех элементов НЕРАВНОЗНАЧНОСТЬ 4 поступает соответствующий разряд признака опроса. Для тех слов, где значение какого- либо разряда не совпадает со значением соответствующего разряда признака опроса, на выходах соответстнующих элементов НЕРАВНОЗНАЧНОСТЬ 4вырабатываются единицы, которые прибавляются в предыдущих тактах значениям соответствующих счетчиков 5,По окончании этого цикла в каждом из счетчиков 5 содержится двоичное число, равное расстоянию Хэмминга. между соответствующим слономмассива-аргумента и признаком опроса,Теперь выделение строки, содержащей слово, ближайшее по Хэмминт У к признаку опроса, сводится к выделению счетчика 5, содержащего минимальное двоичное число. Последняя операция осуществляется матрицей 7,Необходимо отметить, что н общемслучае массив-аргумент может содержать несколько слов, имеющих одинаковое минимальное кодовое расстояние по отношению к признаку опроса,причем эти слона могут быть одинако 65 ными (тогданесовпадения имеют место в одних и тех же разрядах) либо различными (несовпадения в разных разрядах). Всем этим словам соответствуют одинаковые (минимальные) содержимые счетчиков, и они за один цикл параллельно выделяются матри цей 7.Кроме поиска ближайшего по Хэммингу,предлагаемое ассоциативное запоми" нающее устройство может использоваться для решения других задач, свя О занных с определением некоторых свойств двоичных кодов, а именно; упорядоченной выборки слов из устройства; определения расстояния Хэмминга (по отношению к признаку 5 опроса) для данного слова массива- аргумента; выделения слова (слов), имеющего заданное расстояние Хэмминга (по отношению к заданному признаку опроса), в частном случае совпадающего с признаком опроса.В случае необходимости в предлагаемое устройство известными средствами может быть введено маскирование произвольных разрядов накопителя, при этом обеспечивается возможность выполнения всех описанных операций только над незамаскированными разрядными срезами.В ассоциативном запоминающем устройстве операция поиска ближайшего по Хэммингу выполняется параллельно по всем словам массива-аргумента, и время, необходимое для ее выполнения, пропорционально разрядности слова и не зависит от объема масси ва, что обеспечивает существенное увеличение быстродействия, Кроме того, применение цифровых двоичных счетчиков единиц и сортирующей матрицы обеспечивают повышенную на дежность.Существенное увелйчение быстродействия за счет параллельного выполнения, инФормационно-логических операций (при умеренных дополнитель ных затратах оборудования по сравнению с прототипом) определяет технико-зкономическую эффективностьассоциативного запоминающего устройства,При практической реализациисчетчики 5 единиц могут быть совмещены с матрицей 7, образуя единуюдвумерную однородную структуру, Однородность всех блоков и регулярность связей между ними облегчаетреализацию предлагаемого ассоциативного запоминающего устройства средствами интегральной технологии,что является его дополнительным преимуществом,Формула изобретенияАссоциативное запоминающее устройство, содержащее регистр опроса,накопитель, элементы НЕРАВНОЗНАЧНОСТЬ, счетчики единиц, регистр результата поиска, блок управления,выходы которого подключены к управляющим входам регистра результатапоиска, накопитея и регистра опроса, выход которого подключен к одним из входов элементов НЕРАВНОЗНАЧНОСТЬ, о т л и ч а ю щ е е с ятем, что, с целью повышения быстродействия и надежности устройства,в него введена сортирующая матрица,входы которой подключены к выходамсчетчиков единиц, а выходы - к входам регистра результата поиска, выходы накопителя соединенЫ с другимивходами элементов НЕРАВНОЗНАЧНОСТЬ,выходы которых соединены с входамисчетчиков единиц,Источники информации,принятые во внимание при экспертизе1. Заявка ФРГ Р 2605344,кл. 42 2 15/00, опублик, 1978,2, Патент США Р 4084260,кл.364"900,опублик, 1978 (прототип).978196 Составитель В. Рудаковор И. Ковальчук ТехредЛ.Пекарь Корректор з,9227/67ВНИ 11303 ПП Патентф, г, Ужгород, ул, Проектная,Тираж 622 осударственного ком лам изобретений и о ква, Ж, Раушская Подписноеета СССРрытийаб д. 4/5