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

)5 6 11 С 15/О ГОСУДАРСТВЕННОЕ ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) НТН ТЕН ИС КО ИДЕТЕЛЬС АВ ИЕ ИЗОБР(71) Смоленский филиал Московского энергетического института(56) Белоус А.И., Вайнилоаич О.С., Кондратюк А,Л, и др. БИС ассоциативного ЗУ КР 583 РА емкостью 128 бит. "Электронная промышленность", 1986, Я 40 с, 82 - 83,Кохонен Т. Ассоциативные запоминающие устройства. - М,: Мир, 1982, с. 169.(54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО 57) Изобретение относится к вычислительой технике и может быть использовано в пвциализированных системах хранения и Изобретение относится к вычислительной технике и может быть использовано в специализированных системах хранения и .цифровой обработки информации, в системах решения информационно-логических задач, задач поиска и сортировки данных, в устройствах цифровой обработки сигналов в реальном масштабе времени,Целью изобретения является расширение области применения устройства за счет обеспечения возможности реконфигурации ассоциативного накопителя при проведении ассоциативного поиска.На фиг. 1 представлена схема предлагаемого устройства; на фиг, 2 - схема элемента памяти; на фиг; 3 - схема блока регистров опроса и маскирования данных; на фиг. 4 -ример реконфигчрации ассоциативного акопителя. цифровой обработки информации, в системах решения информационно-логических задач, задач поиска и сортировки данных, в устройствах цифровой обработки сигналов в реальном масштабе времени, Целью изобретения является решение области применения устройства.за счет обеспечения возможности реконфигурации ассоциативного накопителя при проведении ассоциативного поиска, Устройство содержит ассоциативный накопитель, в состав которого входят элементы памяти, дешифратор адреса, блок регистров опроса и маскирования данных, регистр выходных данных, регистр фиксации реакций, анализатор многократного совпадения, шифратор, сдвиговый регистр, группа регистров реконфигурации. 4 ил. Устройство (фиг. 1) содержит накопитель 1, в состав которого входят элементы памяти 2 со входами с первого 3 по пятый 7, со водами 8 задания конфигурации с первого по М, где М=о 92 Й, с выходом 9 и с выходами 10 задания конфигурации с первого по М, В состав устройства также входят дешифратор 11 адреса, блок 12 регистров опроса и маскирования данных, регистр 13 выходных данных, регистр 14 фиксации реакций, анализатор 15 многократного совпадения, шифратор 16, сдвиговый регистр 17, регистры 18 реконфигурации с первого по и,Адресные входы 19 устройства подключены к адресным входамдешифратора 11 адреса и к информационным входам регистров 18 реконфигурации, Информационные входы 20 устройства подключены к входам данных регистра сдвига 17 и ко входам,дан 1833917ных блока 12 регистров опроса и маскирования, выходы с первого 21 по четвертый 24 каждой груп пы выходов которого подключе ны соответственно к пятым 7, четвертым 6, вторым 4 и третьим 5 входам элементов 2 памяти соответствующего столбца ассоциативного накопителя 1, Выходы 25 выходного регистра 13 являются информационными выходами первой. группы устройства, а первая группа информационными выходами второй группы устройства, Выход 27 состояния анализатора 15 многократного совпадения является выходом состояния устройства, указывающим на наличие "некоторого числа" совпадений в результатепроведения ассоциативного поиска. Выходы 28 шифратора являются адресными выходами устройства.На устройство подаются следующие управляющие сигналы29 - сигнал выборки дешифратора 11 адреса;.30 - сигнал записи в устройство;31 - сигнал опроса и считывания из устройства;5 10 20 32, - сигнал записи в регистр опросаблока 12;ЗЗ - сигнал записи в регистр маскирования блока 12;34 в .сигнал установки в начальное со- ЗОстояние устройства (подается на входы сигналов сброса в "0" регистров опроса имаскирования блока 12, регистра сдвига 17,а также всех регистров 18 реконфигурации);35 - сигнал входа разрешения парал- З 5лельной загрузки данных в сдвиговый регистр 17 со входов 20;36 - сигнал тактового входа параллельной загрузки данных в регистр сдвига 17 совходов 20 параллельная запись осуществ. ляется по заднему фронту сигнала 36 привысоком уровне сигнала на входе 35);37 - сигнал тактового входа сдвига"вправо" содержимого регистра сдвига 17(сдвиг осуществляется по заднему фронту 45сигнала 37 при низком уровне сигнала навходе 35; при сдвиге в освободившийся раз.ряд регистра 17 заносится нуль);38 - сигнал стробирования отработанной и выборки следующей активной линии 50блоком 15, а также выдачи шифратором 16на адресные выходы 28 устройства адресаследующей активности линии,На фиг, 2 приведен пример реализацииэлемента 2 памяти, состоящего из В-Я триггера 39 с инверсными входами установки в"1" и "О", элементов И-НЕ с первого 40 попятый 44 и дешифратора 45 с М входами ий инверсными выходами, где М=оцгй. Нафиг. 2 также представлены непоказанные на фиг, 1 ограничительные элементы 46 в виде резисторов.Блок 12 регистров опроса и маскирования данных (фиг, 3) содержит регистр 47 опроса, регистр 48 маскирования,первую 49 и вторую 50 группы инверторов, первую 51 и вторую 52 группы элементов И,Устройство может работать в следующих режимах: запись информации по эадайному адресу с маскированием произвольных разрядов; считывание информации по заданному. адресу; параллельный ассоциативный маскируемый поиск с возможностью реконфигурации ассоциативного накопителя,В режиме записи по заданному адресу с адресных входов 19 устройства на дешифратор 11 адреса поступает код адреса запи-. сываемого слова, который дешифрируется по сигналу 29, инициируя подачу уровня логической единицы на входы 3 элементов 2 памяти соответствующей строки ассоциативного накопителя 1 Одновременно с этим на информационные входы блока 12 с информационных входов 20 устройства подается записываемое слово, которое фиксируется в регистре 47 блока 12 по сигналу 32, Затем в регистр 48 этого же блока записывается маска по сигналу ЗЗ (единицы в разрядах регистра маскирование соответствующих разрядов слов накопителя), И при подаче сигнала 30 записи в ассоциативный накопитель 1 на входы 4 и 5 всех элементов 2 памяти с соответствующих выходов 23 и 24 всех, групп выходов блока 12 поступит одна из следующих комбинаций сигналов: "О" - код записи единицы, "01" - код записи нуля, "00" - код маскирования записи, И, таким образом, осуществляется запись по выбранному адресу,При считывании информации по заданному адресу с адресных входов 19 устройства на дешифратор 11 подается код считываемого слова, который дешифрируется по сигналу 29, инициируя подачу уровня логической единицы на входы 3 элементов 2 соответствующей строки накопителя 1. И при подаче сигнала 31.опроса и считывания ассоциативного накопителя 1 считываемое слово в инверсном коде запишется в регистр 13 выходных данных и поступит на первую 25 группу информационных выходов устройства.Перед началом проведения параллельного ассоциативного маскированного поиска нужно выполнить предварительную настройку устройства, заключающуюся в поразрядном задании необходимой конфигурации ассоциативного накопителя, Настройка заключается в следующем, 5 1833917 65 10 15 .20 25 30 40 45 50 55 Сначала по сигналу 34 установки в начальное состояние устройства регистр сдвига 17 и все регистры 18 реконфигурации сбрасываются в "0".Затем в регистр сдвига 17 со входов 20 данных устройства по заднему фронту тактового сигнала 36(при единичном значении сигнала 35) записывается унитарный код с единицей в крайнем левом разряде.Одновременно с этим на входы данных регистров 18 реконфигурации с адресных входов 20 устройства подается М-разрядный двоичный код смещения где М=1 оц 2 И), определяющий подключение элементов памяти для каждого столбца ассоциативного накопителя к соответствующим информационным входам регистра 14 фиксации реакций при последующем ассоциативном поиске,Затем сигнал 35 устанавливается в "0" и по заднему фронту сигнала 37 единица в регистре 17 сдвигается на один разряд вправо, При этом в крайний левый разряд регистра 17 запишется "0". И по перепаду крайнего левого разряда "1" в "0" код смещения занесется в первый регистр 20 реконфигурации, определяя подключение элементов 2 памяти первого столбца ассоциативного накопителя к соответствующим информационным входам регистра 14 фиксации реакций при последующем ассоциативнОм поиске путем подачи кода смещения на входы 8 задания конфигурации элементов 2 памяти первого столбца ассоциативного накопителя 1.Подавая совходов 19 код смещения для элементов 2 памяти следующего столбца ассоциативного накопителя и сдвигая единицу из второго разряда вправо, мы запишем этот код смещения во второй регистр 18 реконфигурации.Выполнив указанную процедуру записи кодов смещения и раз, мы осуществим предварительную настройку устройства, заключающуюся в поразрядном задании необходимой конфигурации ассоциативного накопителя.На фиг. 4 приведен пример реконфигурации ассоциативного накопителя, При заданных кодах смещения (О - . для первого разряда; 1 - для второго; 2 - для третьего) к информационному входу А регистра 14 фиксации реакций будут подключены элементы 2 памяти: А 1,А 2.АЗ; ко входу В - элементы 2 памяти В 1, В 2, ВЗ; ко входу С - элементы 2 памяти С 1, С 2. СЗ,Затем выполняют параллельный ассоциативный поиск. Для этого в регистр 47 опроса блока 12 со входов 20 по сигналу 32 записывают аргумент поиска. После этого в регистре 48 маскирования блока 12 фиксируется маска по сигналу 33. И при подаче сигнала 31 на входы 6 и 7 с выходов 22 и 21 каждой группы выходов блока 12 поступит одна из следующих комбинаций сигналов "01" - сравнение с единицей, "1 О" - сравнение с нулем, "00" - маскирование поиска. Если содержимое бита маскируемого аргумента поиска совпало с содержимым элемента 2 памятито соединенные между собой выходы четвертого 43 и пятого 44 элементов И-НЕ сохраняет уровень логической единицы, и не произойдет выборки дешифратора 45 этого элемента 2 памяти, Т,е, все выходы 10 задания конфигурации рассматриваемого элемента 2 памяти сохранят единичный потенциал.Если же не произошло совпадения содержимого бита маскируемого аргумента поиска с содержимым рассматриваемого элемента 2 памяти, то осуществится обнуление соединенных между собой выходов четвертого 43 и пятого 44 элементов И-НЕ, и на вход выборки дешифратора 45 этого элемента 2 памяти будет подан нулевой уровень, инициирующий дешифрацию кода смещения со входов 8. И, таким образом, обнулится соответствующий выход из группы выходов 10, Следовательно, обнулится и вход регистра 14 фиксации реакций, к которому подключен этот выход из группы выходов 10 рассматриваемого элемента 2 35 памяти, что укажет на наличие несовпадания, Результат ассоциативного поиска фиксируется в регистре 14 фиксаций по заднемуфронту сигнала 31.Анализатор 15 многократного совпадения служит для приоритетной выборки одной из активных линий регистра 14. При этом наивысшим приоритетом обладает аргумент с нулевым адресом.Адрес активной линии, выбранной анализатором выдается на адресные выходы 28 устройства по сигналу 38, Повторной подачей этого сигнала осуществляется стробирование отработанной и инициализация следующей активной линии анализатором 15 многократного совпадения,Формула изобретения Ассоциативное запоминающее устройство, содержащее ассоциативный накопитель, блок регистров опроса и маскирования данных, выходной регистр, регистр фиксации реакций, анализатор многократного совпадения, шифратор, дешифратор адре.са, управляющий вход которого является входом выборки устройства, адресными входами которого являются информационные входы дешифратора адреса, первые входы элементов памяти строк ассоциатив 1833917ного накопителя объединены и подключены к соответствующим выходам дешифратора адреса, первый и второй управляющие вхо ды блока регистров опроса и маскирования данных являются соответственно первым входом записи и входом опроса устройства, третий и четвертый управляющие входы блока регистров опроса и маскирования данных являются соответственно вторым и третьим входами, записи устройства, пятый управляющий вход блока регистров опроса и маскирования данных является входом начальной установки устройства, информационными входами которого являются информационные входы блока регистров опроса и маскирования данных, выходы с первого по четвертый каждой группы выходов которого подключены к объединенным соответственно пятым, четвертым, вторым и третьим входам элементов памяти соответствующего столбца ассоциативного накопителя, выходы элементов памяти которого объединены и подключены к соответствующему информационному входу выходного регистра, вход записи которого и вход записи регистра фиксации реакций объединены и подключены к входу опроса устройства, выходы выходного регистра являются информационными выходами первой группы устройства, информационными выходами второй группы которого являются выходы первой группы регистра фиксации реакций, выходы второй группы которого соединены с соответствующими информационными входами анализатора многократного совпадения, управляющий вход которого и управляющий вход шифратора объединены и являются входом стробирования и выборки активной линии устройства, выходом состояния которого является выход состояния анализатора многократного совпадения, информационные выходы которого соединены с соответствующими информационными входами шифратора, выходы которого 5 являются адресными выходами устройства,о т л и ч а ю щ е е с я тем, что, с целью расширения области применения устройства за счет обеспечения возможности реконфигурации ассоциативного накопителя при 10 проведении ассоциативного поиска, в неговведены регистр сдвига и регистры реконфигурации с первого по и где и - количество столбцов ассоциативного накопителя), информационные входы регистров реконфигу рации подключены к адресным входамустройства, входы сброса регистров реконфигурации и вход сброса регистра сдвига объединены и подключены к входу начальной установки устройства, тактовый вход 20 регистров реконфигурации соединен с соответствующим выходом регистра сдвига, информационные входы которого соединены с информационными входами устройства, управляющие входы регистра сдвига являются 25 соответственно входом разрешения параллельной загрузки и тактовыми входами устройства, причем К-выход регистра реконфигурации (где К=1 М) подключен к соответствующему входу группы входов 30 элементов памяти соответствующего столбца ассоциативного накопителя, 1-выход группы выходов элемента памяти ассоциативного накопителя (где 1=1 М, а И=2") подкл юче н к(1+-входу регистра фиксации 35 реакций (где/ - номер строки ассоциативного накопителя), если (+ М, либо 1-выход группы выходов элемента памяти ассоциативного накопителя подключен к(Й-(1+-входу регистра фиксации реакций, если (г+1)М, 0.Гагарина, 101 роизводственно-издательский комбинат "Патент", г. Ужго Заказ 2689 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-ЗБ, Раушская наб., 4/5