Ассоциативное запоминающее устройство Советский патент 1993 года по МПК G11C15/00 

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

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

На фиг. 1 представлена схема ассоциативного запоминающего устройства; на фиг. 2 - схема элемента памяти ассоциативного накопителя; на фиг. 3 - схема элемента памяти матрицы аргументов поиска.

Устройство (фиг. 1) содержит ассоциативный накопитель 1, в состав которого входят элементы памяти накопителя 2 со входами с первого 3 по восьмой 10 и с первым 11 и вторым 12 выходами 10. Устройство также содержит матрицу аргументов поиска 13, в состав которой входят элементы памяти матрицы 14 со входами с первого 15 по шестой 20 и с выходами с первого 21 по восьмой 28. В состав устройства входят первый 29 и второй 30 регистры маскирования данных и первый 31 и второй 32 регистры фиксации реакций.

ч

Информационные входы 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 - сигнал инициализации одновременного параллельного сравнения содержимого элементов памяти 2 накопителя 1 и соответствующих им элементов памяти 14 матрицы 13 аргументов поиска с маскированием производных строк и столбцов (подается на шестые 20 входы всех элементов

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

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

5 42 - сигнал сброса в О первого 29 регистра маскирования;

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

44 - сигнал сброса в О второго 30 ре0 гистра маскирования.

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

5 представлены не показанные на фиг. 1 ограничительные 52 и 53 элементы в виде резисторов.

На фиг. 3 показан пример реализации элемента памяти 14 матрицы аргументов

0 поиска 13, состоящего из триггера 54 и элементов И-НЕ с первого 55 по двенадцатый 66. На фиг. 3 также представлены не показанные на фиг. 1 ограничительные 67-70 элементы, выполненные в виде резисторов.

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

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

В режиме записи по заданному адрес в ассоциативный накопитель 1 на информационные входы 33 первого регистра 29 маскирования данных подается дешифрированный адрес строки, который фиксируется в этом регистре по сигналу записи 41. Затем или одновременно с этой операцией по сигналу записи 43 во втором 30 регистре маскирования фиксируется записываемое с входов 34 слово. И по сигналу записи 37 оно заносится по указанному адресу в ассоциативный накопитель 1. Так как в первый 29 регистр маскирования записывается уже дешифрованный адрес, то возможна мультизапись (запись одинаковой информации по группе выделенных адресов).

Режим записи по заданному адресу в матрицу 13 аргументов поиска аналогичен вышеописанному, однако вместо сигнала записи 37 на устройство подается сигнал записи 38.

При считывании строки из ассоциативного накопителя 1 по заданному адресу в матрице 13 аргументов поиска по этому же адресу строки должны быть записаны единицы. Единицы также заносятся во все разряды второго 30 регистра маскирования и в тот разряд первого 29 регистра маскирования, который указывает на адрес считываемой из ассоциативного накопителя 1 строки. И при подаче сигнала 40 производится сравнение содержимого элемента памяти 2 выделенной строки ассоциативного накопителя 1 и содержимого элементов памяти 14 соответствующей ей строки матрицы 13 аргументов поиска. При этом на выходах 21 и 23 элемента памяти 14 установится единичный потенциал, который подается на входы 7 и 9 соответствующего элемента памяти 2. Если в триггере 45 элемента памяти 2 хранится единица, то его выходы 11 и 12 сохранят потенциал логической единицы и в соответствующий разряд второго 32 регистра фиксации реакций занесете единица по заднему фронту сигнала 40. Если же в триггере 45 записан логический то выходы элементов И 49 и 51, а следовательно, и первый 11 и второй 12 выходы этого элемента памяти 2 обнулят- ся и в соответствующий разряд второго 32 регистра фиксации реакций занесется ноль по заднему фронту сигнала 40.

Режим конъюнктивного считывания строк ассоциативного накопителя 1 аналогичен вышерассмотренному за исключением того, что до подачи сигнала 40 единицы должны быть записаны в те разряды первого 29 регистра маскирования, которые соответствуют адресам считываемых из 5 ассоциативного накопителя 1 строк.

И При конъюнктивном считывании, если хотя бы в одном разряде соответствующей линейки разрядов считываемых строк хранится ноль, то при подаче сигнала 40 второй

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

5 соответствующего разряда считываемых строк.. ,

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

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

5 из ассоциативного накопителя 1 столбца. При подаче сигнала 40 считываемый стол- с- бец фиксируется в первом 31 регистре фиксации реакций по заднему фронту этого сигнала и выдачей считанного столбца на

0 первую 35 группу информационных выходов устройства.

Режим конъюнктивного считывания столбцов ассоциативного накопителя 1 аналогичен вышерассмотренному за исключе5 нием того, что до подачи сигнала 40 единицы должны быть записаны в те разряды второго 30 регистра маскирования, которые соответствуют адресам считываемых из ассоциативного накопителя 1 столбцов.

0 При считывании строки из матрицы аргументов поиска по заданному адресу в ассоциативный накопитель 1 по этому же адресу должны быть записаны единицы. Единицы также заносятся во все разряды

5 второго 30 регистра маскирования и в тот разряд первого 29 регистра маскирования, который указывает на адрес считываемой из матрицы 13 аргументов поиска строки. При подаче сигнала 40 производится сравнение

0 содержимого элементов памяти 2 выделенной строки ассоциативного накопителя 1 и содержимого элементов памяти 14 соответствующей ей строки матрицы 13 аргументов поиска. При этом если в триггере 54 элемен5 та памяти 14 хранится логическая единица, то на его выходах 21 и 23 установится единичный потенциал. Если хранится логический О, то единичный потенциал установится на выходах 22 и 24, В первом случае выходы 11 и 12 соответствующего элемента памяти 2

сохранят потенциал логической единицы и в соответствующий разряд второго 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 ассоциативного накопителя. Если же хотя бы в одной паре элементов произойдет несовпадение, то обнуляется первый 1.1 и второй 12 выходы элемента памяти 2 из этой пары, и нулевой потенциал будет подан на соответствующую строчную и столбцовую линии, соединяющие соответствующие выходы

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

В режиме параллельного ассоциативного маскирующего поиска ключевого аргумента из матрицы аргументов поиска по строкам ассоциативного накопителя в пер0 вом 29 регистре маскирования единица должна быть записана в тот разряд, который соответствует дешифрированному адресу строки-аргумента из матрицы аргументов поиска, по которому будет проводиться ас5 социативный поиск. Маскирование определенных разрядов этой строки-аргумента поиска осуществляется записью нулей в соответствующие разряды второго 30 регистра маскирования. И при подаче сигнала 39

0 на выходах 25, 26, а также 27, 28 элементов памяти 14 строки-аргумента из матрицы аргументов поиска формируется одна из следующих комбинаций сигналов: 10 - поиск единиц; 01 - поиск нулей; 11 - маскиро5 вание поиска по этому разряду. Из фиг. 1 видно, что выходы 25 и 26 элементов памяти 14 соответствующих столбцов матрицы 13 аргументов поиска соединены между собой, поэтому на выходах 21, 22 всех элементов

0 памяти соответствующего столбца установится единый признак сравнения: 10-сравнение с единицей; 01 - сравнение с нулем; 00 - маскирование сравнения.

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

При полном совпадении строки-аргумента поиска и строки ассоциативного на- копителя на соответствующий вход первого

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 - сравнение с единицей; 0.1

- сравнение с нулем; 00 - маскирование сравнения,

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

соответствующий вход второго 32 регистра фиксации реакций будет подан ноль, ГОРО- рящий о несовпадении столбца-аргумента поиска и столбца ассоциативного накопите- 5 ля.

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

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

В режиме конъюнктивного параллельного ассоциативного маскируемого поиска

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

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

Таким образом, достигается расширение области применения устройства за счет

5 обеспечения возможности осуществления как простого, так и конъюнктивного параллельного маскируемого ассоциативного поиска по строкам, по столбцам и одновременно по стокам и столбцам по любым аргументам из

0 матрицы аргументов поиска. В предлагаемом устройстве обеспечивается оптимизация управления процедурой ассоциативного поиска, что ведет к-увеличению производительности систем обработки информации.

5 Все блоки предлагаемого устройства могут быть реализованы на элементах логики, например, на микросхемах серии К155,

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

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

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

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