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

 

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

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

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

РЕСПУБЛИК

Ю)5 6,11 С 15/00

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (I OCflATEHT СССР) ОПИСАНИЕ ИЗОБРЕТЕНИ е

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4877134/24 (22) 22.10.90 (46) 30.03.93. Б юл. ¹ 12 (71) Московский энергетический институт (72) И.В,Огнев и В.В.Борисов (56) . Кохонен Т. Ассоциативные запоминающие устройства. М.: Мир, 1982, с,176, Авторское свидетельство СССР № 760187, кл. G 11 С 15/00, 1978, с (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ

УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности, к запоминающим устройствам, и может быть использовано в. специализированных системах хранения и цифровой обработки изображений, в ассоциативных параллельных процессорах при решении информационно-логических задач, задач поиска и сортировки данных, в устИзобретение отйосится к вычислительной технике, в частности к запоминающим .устройствам, и может быть использовано в специализированных системах цифровой обработки изображений, в ассоциативных параллельных процессорах, при решении информационно-логических задач, задач .поиска и сортировки данных, в устройствах цифровой обработки сигналов в реальном масштабе времени.

Целью изобретения является расшире:. ние области применения устройств за счет осуществления как простого, так и конъюнктивного.параллельного маскируемого ассоциативного поиска по строкам, по столбцам и одновременно по строкам и столбцам ассоциативного накопителя по любым аргументам из матрицы аргументов поиска.

ЫЛ 18Q5499 А1 ройствах цифровой обработки сигналов в реальном масштабе времени, Целью изобретения является расширение области применения устройства за счет обеспечения возможности осуществления как простого, так и коньюнктивного параллельного маскирующего ассоциативного поиска по строкам. по столбцам и одйовременно по строкам и столбцам ассоциативного накопителя по любым аргументам из матрицы аргументов поиска. Ассоциативное запоминающее устройство содержит матричный накопитель 1, в состав которого входят элементы памяти с восемью входами и двумя выходами, Устройство также содержит матрицу аргументов поиска, в состав которой. входят элементы памяти с шестью входами и восемью выходами каждый. В состав устройства входят два регистра маскирования данных и два регистра фиксации реакции. 3 ил.

На фиг. 1 представлена схема ассоциативного запоминающего устройства; на фиг.

2 — схема элемента. памяти ассоциативного ( накопителя; на фиг. 3 — схема элемента памяти матрицы аргументов поиска. (л

Устройство (фиг. 1) содержит ассоциативный накопитель 1, в состав которого входят элементы памяти накопителя 2 со входами с первого 3 по восьмой 10 и с пер- 0 вым 11 и вторым 12 выходами 10. Устройство также содержит матрицу аргументов поиска 13, в состав которой входят элементы памяти матрицы 14 со входами с первого

15 по шестой 20 и с выходами с первого 21 по восьмой 28, В состав устройства входят первый 29 и второй 30 регистры маскирования данных и первый 31 и второй 32 регистры фиксации реакций.

1805499

Информационные входы 33 первого 29 регистра маскирования данных служат первой группой информационных входов устройства, а выходы подключены к первым 3 входам элементов памяти 2 накопителя 1 и к первым 15 входам соответствующих им элементов памяти 14 матрицы 13 аргументов поиска соответствующих строк, Информационные вхады 34 второго 30 регистра маскирования данных служат второй группой информациойных входов устройства, а первый (прямой выход регистра) и второй (инверсный выход регистра) выходы каждой группы выходов подключенйсо- ответственно ко вторым 4 и третьим 5 входам элементов памяти 2 накопителя 1 и ко вторым 16 и третьим 17 входам, соответствующих этим элементам памяти 2, нако, пителя 1, элементов памяти 14 матрицы 13 аргументов поиска соответствующих строк.

Выходы с первого 21 по четвертый 24 каждого элемента 14 матрицы 13 аргументов поиска подключены ко входам с пятого

7 по восьмой 10 соответствующего ему элемента памяти 2 накопителя 1.

Как пятые 25, так и шестые 26 выходы элементов памяти 14 соответствующих столбцов матрицы 13 аргументов поиска соединены между собой.

Как седьмые 27, так и восьмые 28 выходы элементов памяти 14 соответствующих строк матрицы 13 аргументов поиска соединены между собой.

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

Вторые выходы 12 элементов памяти 2 соответствующих столбцов накопителя 1 соединены между собой и подключены к сроТветствующим входам второго регистра 32 фиксации реакций, выходы которого служат второй 36 группой информационных выходов устройства, На устройство подаются следующие управляющие сигналы:

37 — сигнал записи в ассоциативный накопитель 1 (подается на четвертые 6 входы всех элементов память 2 накопителя 1);

38 — сигнал записи в матрицу 13 аргументов поиска (подается на четвертые 18 входы всех элементов памяти 14 матрицы 13 аргументов поиска);

39 — сигнал инициализации ассоциативного поиска; (подается на пятые 19 входы всех элементов памяти 14 матрицы 13 аргументов поиска и нэ входы записи первого 31 и второго 32 регистров фиксации реакций);

40 — сигнал инициализации одновременного параллельного сравнения содер5 жимого элементов памяти 2 накопителя 1 и соответствующих им элементов памяти 14 матрицы 13 аргументов поиска с маскированием производных строк и столбцов (подается на шестые 20 входы всех элементов

10 памяти 14 матрицы 13 аргументов поиска и на входы записи первого 31 и второго 32 регистров фиксации реакций);

41 — сигнал записи в первый 29 регистр маскирования;

15 42 — сигнал сброса в "0" первого 29 регистра маскирования;

43 — сигнал записи во второй 30 регистр маскирования;

44 — сигнал сброса в "0" второго 30 ре20 гистра маскирования.

На фиг, 2 приведен пример реализации элемента памяти 2 накопителя 1, состоящего из триггера 45 и элементов И-НЕ с первого 46 по шестой 51. Нэ фиг. 2 также представлены не показанные на фиг, 1 ограничительные 52 и 53 элементы в виде резисторов, На фиг, 3 показан пример реализации элемента памяти 14 матрицы аргументов

30 поиска 13, состоящего из триггера 54 и элементов И-HE с первого 55 по двенадцатый

66. На фиг. 3 также представлены не показанные на фиг. 1 ограничительные 67 — 70 элементы, выполненные в виде резисторов.

35 Устройство может работать в следующих режимах, запись информации по заданному адресу (груп па адресов) в ассоциативный накопитель; запись информации по заданному адресу (группе адресов)

40 в матрицу аргументов поиска; считывание по заданному адресу как строки, так и столбца ассоциативного накопителя; считывание информации по заданному адресу как строки, так и столбца матрицы аргументов по45 иска, конъюнктивное считывание как строк, так и столбцов ассоциативного накопителя; конъюнктивное считывание как строк, так и столбцов матрицы аргументов поиска; одновременное параллельное сравнение содер50 жимого элемента памяти ассоциативного, накопителя и соответствующих им элементов памяти матрицы аргументов поиска с маскированием произвольных строк и столбцов; параллельный ассоциативный маскируемый поиск ключевого аргумента из матрицы аргументов поиска по строкам, по столбцам и одновременно по строкам и столбцам ассоциативного накопителя по критерию "равно", конъюнктивный параллельный ассоциативный маскируемый по1805499 иск ключевых аргументов из матрицы аргу- ем того, что до подачи сигнала 40 единицы ментов поиска по строкам, по столбцам и должны быть записаны в те разряды первоодновременно по строкам и столбцам ассо- го 29 регистра маскирования, которые соотциативного накопителя по критерию "рав- ветствуют адресам считываемых из !!

5 ассоциативного накопителя 1 строк.

В режиме записи по заданному адрес в И йри конъюнктивном считывании. если ассоциативный накопитель 1 на информа- хотя бы в одном разряде соответствующей ционные входы 33 первого регистра 29 маски- линейки разрядов считываемых строк храрования данных подается дешифрированный нится ноль, то при подаче сигнала 40 второй адрес строки, который фиксируется в этом 10 12 выход этого элемента памяти 2, а следорегистре по сигналу записи 41. Затем или вательно, и вся линейка этого разряда обнуодновременно с этой операцией по сигналу ляется. И таким образом в соответствующий записи43 вовтором30 регистремаскирова- разряд второго 32 регистра фиксации реакния фиксируется эаписываемое с входов 34 ций запишется коньюнкция содержимого слово. И по сигналу записи 37 оно заносится 15 соответствующего разряда считываем ых

rio указанному адресу в ассоциативный на- строк, копитель 1. Так. как в первый 29 регистр В режиме считывания столбца из ассомаскирования записывается уже дешифро- ., циативного накопителя 1 в соответствуюванный адрес, то возможна мультизапись щий ему столбец матрицы 13 аргументов (запись одинаковой информации по группе 20 поиска должны быть записаны единицы, выделенных адресов). Единицы также заносятся во все разряды

Режим записи по заданному адресу в первого 29 регистра маскирования и в тот матрицу 13 аргументов поиска аналогичен разряд второго 30 регистра маскирования, вышеописанному, однако вместо сигнала который указывает на адрес считываемого записи 37 на устройство подается сигнал 25 из ассоциативного накопителя 1 столбца. записи 38. При подаче сигнала 40 считываемый столПри считывании строки из ассоциатив-, бец фиксируется в первом 31 регистре фикного накопителя 1 Ilo заданному адресу в сации реакций по заднему фронт этого мат и 13 а рице,3 аргументов поиска по этому же сигнала и выдачей считанного столбца на у т г адресу строки должны быть записаны еди- 30 первую 35 группу информационных выхоницы. Единицы также заносятся во все раз- дов устройства, ряды второго 30 регистра маскирования и в Режим коньюнктивного считывания . тот разряд первого 29 регистра маскирова- столбцов ассоциативного накопителя 1 анания, который указывает на адрес считывае- логичен вышерассмотренному за исключемой из ассоциативного накопителя 1 35 нием того, что до подачи сигнала 40 строки, И при подаче сигнала 40 произво- единицы должны быть записаны в те разрядится сравнение содержимого элемента па- ды второго 30 регистра маскирования, котомяти 2 выделенной строки ассоциативного рые соответствуют адресам считываемых из накопителя 1 и содержимого элементов па- ассоциативного накопителя 1 столбцов. мяти 14 соответствующей ей строки матри- 40 При считывании строки из матрицы арцы 13 аргументов поиска. При этом на гументов поиска по заданному адресу в асвыходах21и23элементапамяти14устано- социативный накопитель 1 по этому же вится единичный потенциал, который пода- адресу должны быть записаны единицы, ется на. входы 7 и 9 соответствующего Единицы также заносятся во все разряды элемента памяти 2. Если в триггере 45 эле- 45 второго 30 регистра маскирования и в тот мента памяти 2 хранится единица, то его разряд первого 29 регистра маскирования, выходы 11 и 12 сохранят потенциал логиче- который указывает на адрес считываемой из ской единицы и в соответствующий разряд матрицы 13 аргументов поиска строки, При второго 32. регистра фиксации реакций за- подаче сигнала 40 производится сравнение несется: единица по заднему фронту сигна- 50 содержимого элементов памяти 2 выделенла 40. Если же в триггере 45 записан ной строки ассоциативного накопителя 1 и логический "0"; то выходы элементов И 49 содержимого элементов памяти 14 соответи 51, а следовательно, и первый 11 и второй ствующей ей строки матрицы 13 аргумен о

12 ы т в выходы этого элемента памяти 2 обнулят- поиска. При этом если в триггере 54 злеменся и в соответствующий разряд второго 32 55 та памяти 14 хранится логическая единица, регистра фиксации реакций занесется ноль то на его выходах 21 и 23 установится едипо заднему фронту сигнала 40. ничный потенциал, Если хранится логический

Режим коньюнктивного считывания "0", то единичный потенциал установится на строк ассоциативного накопителя 1 анало- выходах 22 и 24. В первом случае выходы 11 гичен вышерассмотренному за исключени- и 12 соответствующего элемента памяти 2

1805499

20

30

40

55 сохранят потенциал логической единицы и в соответствующий разряд второго 32 регистра фиксации реакций занесется единица по заднему фронту сигнала 40, Во втором случае выходы элементов И 48 и 50, а следовательно, и первый 11 и второй 12 выходы этого элемента памяти 2 обнулятся, и в соответствующий разряд второго 32 регистра фиксации реакций занесется ноль по заднему фронту сигнала 40.

Режим конъюнктивного считывания строк матрицы 13 аргументов поиска аналогичен вышерассмотренному, за исключением того, что до подачи сигнала 40 единицы должны быть записаны в те разряды первого 29 регистра маскирования, которые соответствуют адресам считываемых из матрицы 13 аргументов поиска строк. И при коньюнктивном считывании, если хотя бы в одном разряде соответствующей линейки разрядов считываемых строк хранится ноль, то при подаче сигнала 40 второй 12 выход этого элемента памяти 2, а следовательно, и вся линейка этого разряда обнуляется.

Таким образом, в соответствующий разряд второго 32 регистра фиксации реакций запишется коньюнкция содержимого соответствующего разряда считываемых строк.

В режиме считывания столбца из матрицы 13,аргументов поиска в соответствующий ему столбец ассоциативного накопителя 1 должны быть записаны единицы. Единицы также заносятся во все разряды первого регистра маскирования и В тот разряд второго 30 регистра маскирования, который указывает на адрес считываемого из матрицы 13 аргументов поиска столбца.

И при подаче сигнала 40 считываемый столбец фиксируется в первом 31 регистре фиксации реакций по заднему фронту этого сигнала с выдачей считанного столбца на первую 35 группу информационных выходов устройства, Режим коньюнктивного считывания столбцов матрицы 13 аргументов поиска аналогичен рассмотренному, эа исключением того, что до подачи сигнала 40 единицы должны быть записаны в те разряды второго

30 регистра маскирования, которые соответствуют адресам считываемых из матрицы 13 аргументов поиска столбцов.

В режиме одновременного параллельного сравнения содержимого элементов памяти ассоциативного накопителя и соответствующих им элементов памяти матрицы аргументов поиска подается сигнал 40.

При этом, если содержимое соответствующей пары элементов памяти ассоциативного накопителя и матрицы аргументов поиска совпало, то не произойдет. обнуления перваго 11 и второго 12 выходов рассматриваеМого элемента памяти 2 ассоциативного накопителя. Если же хотя бы в одной паре элементов произойдет несовпадение, то обнуляется первый 11 и второй 12 выходы элемента памяти 2 из этой пары, и нулевой потенциал будет подан на соответствующую строчную и столбцовую линии, соединяющие соответствующие выходы элементов памяти 2 строк и столбцов, Нули, зафиксированные в этом режиме по заднему фронту сигнала 40 в соответствующих разрядах первого 31 и второго 32 регистров фиксации реакций, указывают на факт и место несовпадения.

В режиме параллельного ассоциативного маскирующего поиска ключевого аргумента из матрицы аргументов поиска по строкам ассоциативного накопителя в первом 29 регистре маскирования единица должна быть записана в тот разряд, который соответствует дешифрированному адресу строки-аргумента из матрицы аргументов поиска. по которому будет проводиться ассоциативный поиск, Маскирование определенных разрядов этой строки-аргумента поиска осуществляется записью нулей в соответствующие разряды второго 30 регистра маскирования. И при подаче сигнала 39 на выходах 25, 26, а также 27, 28 элементов памяти 14 строки-аргумента из матрицы аргументов поиска формируется одна из следующих комбинаций сигналов: "10" — поиск единиц; "01" — поиск нулей; "11" — маскирование поиска по этому разряду, Из фиг. 1 видно, что выходы 25 и 2б элементов памяти

14 соответствующих столбцов матрицы 13 аргументов поиска соединены между собой, поэтому на выходах 21, 22 всех элементов памяти соответствующего столбца установится единый признак сравнения: 10 — сравнение с единицей; 01 — сравнение с нулем;

00 — маскирование сравнения.

Если при сравнении содержимого элементов памяти 14 строки-аргумента поиска и элементов памяти 2 какой-либо строки ассоциативного накопителя произошло несовпадение содержимого хотя бы в одной паре этих элементов, то на выходе 11 соответствующего элемента памяти 2 установится потенциал логического нуля, который обнулит шину, соединяющую выходы 11 элементов 2 памяти этой строки, и на соответствующий вход первого 31 регистра фиксации реакций будет подан ноль, говорящий о несовпадении строки-аргумента поиска и строки ассоциативного накопителя, При полном совпадении строки-аргумента поиска и строки ассоциативного накопителя на соответствующий вход первого

1805499

5

20

30

31 регистра фиксации реакций поступает единица. Результат ассоциативного поиска по строкам фиксируется в регистр 31 по заднему фронту сигнала 39.

В режиме конъюнктивного параллельного ассоциативного маскируемого поиска по строкам ассоциативного накопителя в формировании строки-аргумента поиска участвуют несколько строк матрицы аргументов поиска.

Строка-аргумент поиска образуется в результате выполнения операций конъюнкции над соответствующими битами строк матрицы аргументов поиска, выделенных единицами в соответствующих разрядах первого 29 регистра маскирования, В том

„ случае, если в выделенных строках в соответствующей разрядной линейке, хотя бы в одной ячейке памяти 14 записан ноль, то на выходах 21, 22 всех элементов памяти 2 этого столбца установится единый признак сравнения с нулем — 01", В режиме параллельного ассоциативного маскируемого поиска ключевого аргумента из матрицы аргументов поиска по столбцам ассоциативного накопителя во втором 30 регистре маскирования единица должна быть записана в тот разряд, который соответствует дешифрирован ному адресу столбца-аргумента из матрицы аргументов поиска, по которому будет проводиться ассоциативный поиск, Маскирование определенных разрядов этого столбца-аргумента поиска осуществляется записью нулей в соответствующие разряды первого 29 регистра маскирования, И при подаче сигнала 39 на выходах 27, 28 (а также 25, 26) элементов памяти 14 строки-аргумента из матрицы аргументов поиска формируется одна из сле дующих комбинаций сигналов; 10 — поиск единиц; 01 — поиск нулей; 11 — маскирование поиска по этой линейке. Из фиг. 1 видно, что выходы 27 и 28 элементов памяти 14 соответствующих строк матрицы 13 соединены между собой, поэтому на выходах 23, 24 всех элементов памяти 14 соответствующей строки установится единый признак сравнения: 10 — сравнение с единицей; 01 — сравнение с нулем; 00 — маскирование сравнения, Если при сравнении содержимого элементов памяти 14 столбца-аргумента поиска и элементов памяти 2 какого-либо столбца ассоциативного накопителя произошло несовпадение содержимого хотя бы в одной паре этих элементов, то на выходе

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

12 элементов памяти 2 этого столбца, и на соответствующий вход второго 32 регистра фиксации реакций будет подан ноль, говорящий о несовпадении столбца-аргумента поиска и столбца ассоциативного накопителя, При полном совпадении столбца-аргумента поиска и столбца ассоциативного накопителя на соответствующий вход второго

32 регистра фиксации реакций поступает единица, Результат ассоциативного поиска по столбцам фиксируется в регистре 32 по заднему фронту сигнала 39.

В режиме коньюнктивного параллельного ассоциативного маскируемого поиска по столбцам ассоциативного накопителя в формировании столбца-аргумента поиска участвуют несколько столбцов матрицы аргументов поиска. Столбец-аргумент поиска образуется в результате выполнения операции конъюнкции над соответствующими битами столбцов матрицы аргументов поиска, выделенных единицами в соответствующих разрядах второго 30 регистра маскирования. В том случае, если в выделенных столбцах в соответствующей строчной линейке, хотя бы в одной ячейке памяти 14 записан ноль, то на выходах 23, 24 всех элементов памяти 2 этой строки установится единый признак сравнения с нулем — "01".

Режимы ассоциативного поиска (как простого, так и конъюнктивного) по строкам и столбцам могут быть совмещены.

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

Ассоциативное запоминающее устройство, содержащее матричный накопитель, первый и второй регистры маскирования данных, первый и второй регистры фиксации реакций, управляющие входы которых являются управляющими входами первой группы устройства, информационными выходами первой и второй групп которого являются соответственно выходы первого и второго регистров фиксации реакций, причем первые выходы элементов памяти соот1805499

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

10 выходам первого регистра маскирования данных, вторые и третьи входы элементов памяти соответствующих столбцов матрицы аргументов поиска объединены и подключены соответственно к первым и вторым выхо15 дрм соответствующей группы выходов второго регистра маскирования данных, четвертый, пятый и шестой входы элемента памяти матрицы аргументов поиска являются управляющими входами четвертой

20 группы устройства, выходы с первого по чет8epTblA каждого элемента памяти матрицы аргументов поиска подключены к входам с пятого по восьмой соответствующего элемен- та памяти матричного накопителя, пятые вы2S ходы элементов памяти соответствующих столбцов матрицы аргументов поиска объединены, шестые выходы также объединены, седьмые выходы элементов памяти соответствующих строк матрицы аргументов по30 иска объединены и восьмые выходы тоже объединены.

1805499 ЪГ.З

Составитель В, Борисов

Техред M.Ìîðãåíòàë - Корректор Н. Ревсквя

Редактор

Производственно-издательский комбийат "Патент", г, Чжгород, ул. Гагарина, 101

Заказ 944 Тираж Подписное . ВНИИПИ Государственного комитета.ио изобретениям и открытиям при ГКНТ СССР

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