Ассоциативное запоминающее устройство
Изобретение относится к вычислительной технике и может быть использовано в специализированных системах хранения и цифровой обработки информации, в системах решения информационно-логических задач, задач поиска и сортировки данных, в устройствах цифровой обработки сигналов в реальном масштабе времени. Целью изобретения является решение области применения устройства за счет обеспечения возможности реконфигурации ассоциативного накопителя при проведении ассоциативного поиска. Устройство содержит ассоциативный накопитель, в состав которого входят элементы памяти, дешифратор адреса, блок регистров опроса и маскирования данных, регистр выходных данных, регистр фиксации реакций, анализатор многократного совпадения, шифратор, сдвиговый регистр, группа регистров реконфигурации . 4 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕ CKMX
РЕСПУБЛИК (я)5 G 11 С 15/00
ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ
ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4925821./24 (22) 04.04,91 (46) 15.08.93, Бюл. f4 30 (71) Смоленский филиал Московского энергетического института (72) В.В. Борисов (56) Белоус A.È., Вайнилоаич О.С., Кондратюк А,Л, и др. БИС ассоциативного ЗУ КР
583РА! емкостью 128 бит. "Электронная промышленность", 1986, t4 40 с. 82 — 83, Кохонен Т. Ассоциативные запоминающие устройства. - М,; Мир,.1982, с. 169. (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ
УСТРОЙСТВО (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных системах хранения и
Изобретение относится к вычислительной технике и может быть использовано в специализированных системах хранения и .цифровой обработки информации, в системах решения информационно-логических задач, задач поиска и сортировки данных, в устройствах цифровой обработки сигналов в реальном масштабе времени, Целью изобретения является расширение области применения устройства за счет обеспечения возможности реконфигурации ассоциативного накопителя при проведении ассоциативного поиска.
На фиг. 1 представлена схема предлагаемого устройства; на фиг, 2 — схема элемента памяти; на фиг; 3 — схема блока регистров опроса и маскирования данных; на фиг. 4— пример реконфигчрации ассоциативного накопителя.
„„ Ы„„1833917 А1 цифровой обработки информации, в системах решения информационно-логических задач, задач поиска и сортировки данных, в устройствах цифровой обработки сигналов в реальном масштабе времени. Целью изобретения является решение области приме нения устройства.за счет обеспечения возможности реконфигурации ассоциативного накопителя при проведении ассоциативного поиска, Устройство содержит ассоциативный накопитель, в состав которого входят элементы памяти, дешифратор адреса, блок регистров опроса и маскирования данных, регистр выходных данных, регистр фиксации реакций, анализатор многократного совпадения, шифратор, сдвиговый регистр, группа регистров реконфигурации. 4 ил.
Устройство (фиг. 1) содержит накопитель 1, в состав которого входят элементы памяти 2 со входами с первого 3 по пятый 7, со водами 8 задания конфигурации с перво- 0ф го по М, где M=logzN, с выходом 9 и с выхо- () дами 10 задания конфигурации с первого по
N, В состав устройства также входят дешифратор 11 адреса, блок 12 регистров опроса и маскирования данных, регистр 13 выходных данных, регистр 14 фиксации реакций, 4 анализатор 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 — сигнал опроса и считывания из устройства;
10
32, — сигнал записи в регистр опроса блока 12;
ЗЗ вЂ” сигнал записи в регистр маскирования блока 12;
34 †.сигнал установки в начальное со- 30 стояние устройства (подается на входы сигналов сброса в "0" регистров опроса и маскирования блока 12, регистра сдвига 17, а также всех регистров 18 реконфигурации);
35 — сигнал входа разрешения парал- 35 лельной загрузки данных в сдвиговый регистр 17 со входов 20;
36 — сигнал тактового входа параллельной загрузки данных в регистр сдвига 17 со входов 20 (параллельная запись осуществ- 40 . ляется по заднему фронту сигнала 36 при высоком уровне сигнала на входе 35);
37 — сигнал тактового входа сдвига
"вправо" содержимого регистра сдвига 17 (сдвиг осуществляется по заднему фронту 45 сигнала 37 при низком уровне сигнала на входе 35; при сдвиге в освободившийся раз.ряд регистра 17 заносится нуль);
38 - сигнал стробирования отработанной и выборки следующей активной линии 50 блоком 15, а также выдачи шифратором 16 на адресные выходы 28 устройства адреса следующей активности линии.
На фиг. 2 приведен пример реализации элемента 2 памяти, состоящего из R-S триг- 55 гера 39 с инверсными входами установки в
"1" и "0", элементов И-НЕ с первого 40 по пятый 44 и дешифратора 45 с Ы входами и
Nинверсными выходами,,где M=logzN. На фиг. 2 также представлены непоказанные на фиг. 1 ограничительные элементы 46 в виде резисторов.
Блок 12 регистров опроса и маскирования данных (фиг. 3) содержит регистр 47 опроса. регистр 48 маскирования, первую
49 и вторую 50 группы инверторов, первую
51 и вторую 52 группы элементов И.
Устройство может работать в следующих режимах: запись информации по эадайному адресу с маскированием произвольных разрядов; считывание информации по заданному адресу; параллельный ассоциативный маскируемый поиск с возможностью реконфигурации ассоциативного накопителя.
В режиме записи по заданному адресу с адресных входов 19 устройства на дешифратор 11 адреса поступает код адреса запи-. сываемого слова, который дешифрируется по сигналу 29, инициируя подачу уровня логической единицы на входы 3 элементов 2 памяти соответствующей строки ассоциативного накопителя 1.. Одновременно с этим на информационные входы блока 12 с информационных входов 20 устройства подается записываемое слово, которое фиксируется в регистре 47 блока 12 по сигналу 32, Затем в регистр 48 этого же блока записывается маска по сигналу 33 (единицы в разрядах регистра маскирование соответствующих разрядов слов накопителя). И при подаче сигнала 30 записи в ассоциативный накопитель 1 на входы 4 и 5 всех элементов
2 памяти с соответствующих выходов 23 и
24 всех, групп выходов блока 12 поступит одна из следующих комбинаций сигналов:
"0" — код записи единицы, "01 " — код записи нуля, "00" — код маскирования записи, И, таким образом, осуществляется запись по выбранному адресу.
При считывании информации по заданному адресу с адресных входов 19 устройства на дешифратор 11 подается код считываемого слова, который дешифрируется по сигналу 29, инициируя подачу уровня логической единицы на входы 3 элементов 2 соответствующей строки накопителя 1. И при подаче сигнала 31.опроса и считывания ассоциативного накопителя 1 считываемое слово в инверсном коде запишется в регистр 13 выходных данных и поступит на первую 25 группу информационных выходов устройства.
Перед началом проведения параллельного ассоциативного маскированного поиска нужно выполнить предварительную настройку устройства, заключающуюся в поразрядном задании необходимой конфигурации ассоциативного накопителя, Настройка заключается в следующем.
5 1833917 6
Сначала по сигналу 34 установки в начальное состояние устройства регистр сдвига 17 и все регистры 18 реконфигурации сбрасываются в "0".
Затем в регистр сдвига 17 со входов 20 данных устройства по заднему фронту тактового сигнала 36 (при единичном значении сигнала 35) записывается унитарный код с единицей в крайнем левом разряде.
Одновременно с этим на входы данных регистров 18 реконфигурации с адресных входов 20 устройства подается M-разрядный двоичный код смещения (где М=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 записывают аргумент поиска. После этого в
35 памяти, что укажет на наличие несовпадания. Результат ассоциативного поиска фик40
50
5
15 .20
30 регистре 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 сируется в регистре 14 фиксаций по заднему фронту сигнала 31.
Анализатор 15 многократного совпадения служит для приоритетной выборки одной из активных линий регистра 14. При этом наивысшим приоритетом обладает аргумент с нулевым адресом.
Адрес активной линии, выбранной анализатором выдается на адресные выходы 28 устройства по сигналу 38. Повторной подачей этого сигнала осуществляется стробирование отработанной и инициализация следующей активной линии анализатором
15 многократного совпадения.
Формула изобретения
Ассоциативное запоминающее устройство, содержащее ассоциативный накопитель, блок регистров опроса и маскирования данных, выходной регистр, регистр фиксации реакций, анализатор многократного совпадения, шифратор, дешифратор адре.са, управляющий вход которого является входом выборки устройства, адресными входами которого являются информационные входы дешифратора адреса, первые входы элементов памяти строк ассоциатив1833917 ного накопителя объединены и подключены к соответствующим выходам дешифратора адреса, первый и второй управляющие вхо ды блока регистров опроса и маскирования данных являются соответственно первым входом записи и входом опроса устройства, третий и четвертый управляющие входы блока регистров опроса и маскирования данных являются соответственно вторым и третьим входами, записи устройства, пятый управляющий вход блока регистров опроса и маскирования данных является входом начальной установки устройства, информационными входами которого являются информационные входы блока регистров опроса и маскирования данных, выходы с первого по четвертый каждой группы выходов которого подключены к объединенным соответственно пятым, четвертым, вторым и третьим входам элементов памяти соответствующего столбца ассоциативного накопителя, выходы элементов памяти которого объединены и подключены к соответствующему информационному входу выходного регистра, вход записи которого и вход записи регистра фиксации реакций объединены и подключены к входу опроса устройства, выходы выходного регистра являются информационными выходами первой группы устройства, информационными выходами второй группы которого являются выходы первой группы регистра фиксации реакций, выходы второй группы которого соединены с соответствующими информационными входами анализатора многократного совпадения, управляющий вход которого и управляющий вход шифратора объединены и являются входом стробирования и выборки активной линии устройства, выходом состояния которого является. выход состояния анализатора многократного совпадения, информационные выходы которого соединены с соответствующими информационными входами шифратора, выходы которого
5 являются адресными выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения устройства за счет обеспечения возможности реконфигурации ассоциативного накопителя при
10 проведении ассоциативного поиска, в него введены регистр сдвига и регистры реконфигурации с первого по и (где и — количество столбцов ассоциативного накопителя), информационные входы регистров реконфигу15 рации подключены к адресным входам устройства, входы сброса регистров реконфигурации и вход сброса регистра сдвига объединены и подключены к входу начальной установки устройства, тактовый вход
20 регистров реконфигурации соединен с соответствующим выходом регистра сдвига, информационные входы которого соединены с информационными входами устройства, управляющие входы регистра сдвига являются
25 соответственно входом разрешения параллельной загрузки и тактовыми входами устройства, причем К-выход регистра реконфигурации (где К=1...M) подключен к соответствующему входу группы входов
30 элементов памяти соответствующего столбца ассоциативного накопителя, I-выход группы выходов элемента памяти ассоциативного накопителя (где i-1...N, а И=2") подключен к(1+))-входу регистра фиксации
35 реакций (где/ — номер строки ассоциативного накопителя), если (i+j) N, либо i-выход группы выходов элемента памяти ассоциативного накопителя подключен к(Й (I+j)-входу регистра фиксации реакций, если (i+j)PN. 0
1833917
183391 7
1833917
/Ф c seCгам Р
Составитель Н. Полякова
Техред М.Моргентал Корректор А. Мотыль
Редактор
Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101
Заказ 2689 Тираж Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж 35, Раушская наб., 4/5
