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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 180549 0 ГОСУДАРСТВЕННОЕ ПАТЕНТНВЕДОМСТВО СССР(ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(71) Московский энергетический институт(57) Изобретение относится к вычислительной технике, в частности, к запоминающимустройствам, и может быть использовано вспециализированных системах хранения ицифровой обработки изображений, в ассоциативных параллельных процессорах прирешении информационно-логических задач,задач поиска и сортировки данных, в устИзобретение отйосится к вычислительной технике, в частности к запоминающим .устройствам, и может быть использовано в специализированных системах цифровой обработки изображений, в ассоциативных параллельных процессорах, при решении информационно-логических задач, задач .поиска и сортировки данных, в устройствах цифровой обработки сигналов в реальном масштабе времени.Целью изобретения является расшире. ние области применения устройств за счет осуществления как простого, так и конъюнктивного.параллельного маскируемого ассоциативного поиска по строкам, по столбцам и одновременно по строкам и столбцам ассоциативного накопителя по любым аргументам из матрицы аргументов поиска. ройствах цифровой обработки сигналов в реальном масштабе времени, Целью изобретения является расширение области применения устройства за счет обеспечения возможности осуществления как простого, так и коньюнктивного параллельного маскирующего ассоциативного поиска по строкам, по столбцам и одйовременно по строкам и столбцам ассоциативного накоф пителя по любым аргументам из матрицыаргументов поиска. Ассоциативное запоминающее устройство содержит матричный накопитель 1, в состав которого входят элементы памяти с восемью входами и двумя выходами, Устройство также содержит матрицу аргументов поиска, в состав которой.входят элементы памяти с шестью входами и восемью выходами каждый. В состав устрой- Я ства входят два регистра маскирования данных и два регистра фиксации реакции. 3 ил. На фиг. 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 - сигнал инициализации одновременного параллельного сравнения содер 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 и элементов И-НЕ с первого 55 по двенадцатый66. На фиг, 3 также представлены не показанные на фиг, 1 ограничительные 67 - 70элементы, выполненные в виде резисторов.35 Устройство может работать в следующих режимах, запись информации по заданному адресу (груп па адресов) вассоциативный накопитель; запись информации по заданному адресу (группе адресов)40 в матрицу аргументов поиска; считывание позаданному адресу как строки, так и столбцаассоциативного накопителя; считываниеинформации по заданному адресу как строки, так и столбца матрицы аргументов по 45 иска, конъюнктивное считывание как строк,так и столбцов ассоциативного накопителя;конъюнктивное считывание как строк, так истолбцов матрицы аргументов поиска; одновременное параллельное сравнение содер 50 жимого элемента памяти ассоциативного, накопителя и соответствующих им элементов памяти матрицы аргументов поиска смаскированием произвольных строк и столбцов; параллельный ассоциативный маски 55 руемый поиск ключевого аргумента изматрицы аргументов поиска по строкам, постолбцам и одновременно по строкам истолбцам ассоциативного накопителя покритерию "равно", конъюнктивный параллельный ассоциативный маскируемый по1805499иск ключевых аргументов из матрицы аргу- ем того, что до подачи сигнала 40 единицыментов поиска по строкам, по столбцам и должны быть записаны в те разряды первоодновременно по строкам и столбцам ассо- го 29 регистра маскирования, которые соотциативного накопителя по критерию "рав- ветствуют адресам считываемых из5 ассоциативного накопителя 1 строк.В режиме записи по заданному адрес в И йри коньюнктивном считывании. еслиассоциативный накопитель 1 на информа- хотя бы в одном разряде соответствующейционные входы 33 первого регистра 29 маски- линейки разрядов считываемых строк храрования данных подается дешифрированный нится ноль, то при подаче сигнала 40 второйадрес строки, который фиксируется в этом 10 12 выход этого элемента памяти 2, а следорегистре по сигналу записи 41. Затем или вательно, и вся линейка этого разряда обнуодновременно с этой операцией по сигналу ляется. И таким образом в соответствующийзаписи 43 вовтором 30 регистремаскирова- разряд второго 32 регистра фиксации реакния фиксируется эаписываемое с входов 34 ций запишется коньюнкция содержимогослово. И посигналузаписи 37 онозаносится 15 соответствующего разряда считываемыхпо указанному адресу в ассоциативный на- строк,копитель 1. Так. как в первый 29 регистр В режиме считывания столбца из ассомаскирования записывается уже дешифро- ., циативного накопителя 1 в соответствуюванный адрес, то возможна мультизапись щий ему столбец матрицы 13 аргументов(запись одинаковой информации по группе 20 поиска должны быть записаны единицы,выделенных адресов). Единицы также заносятся во все разрядыРежим записи по заданному адресу в первого 29 регистра маскирования и в тотматрицу 13 аргументов поиска аналогичен разряд второго 30 регистра маскирования,вышеописанному, однако вместо сигнала который указывает на адрес считываемогозаписи 37 на устройство подается сигнал 25 из ассоциативного накопителя 1 столбца.записи ЭЗ. При подаче сигнала 40 считываемый столПри считывании строки из ассоциатив-, бец фиксируется в первом 31 регистре фикного накопителя 1 по заданному адресу в сации реакций по заднему фронт этогомат и 13а рице 13 аргументов поиска по этому же сигнала и выдачей считанного столбца нау т гадресу строки должны быть записаны еди первую 35 группу информационных выхоницы. Единицы также заносятся во все раз- дов устройства,ряды второго 30 регистра маскирования и в Режим коньюнктивного считывания. тот разряд первого 29 регистра маскирова- столбцов ассоциативного накопителя 1 анания, который указывает на адрес считывае- логичен вышерассмотренному за исключемой из ассоциативного накопителя 1 35 нием того, что до подачи сигнала 40строки, И при подаче сигнала 40 произво- единицы должны быть записаны в те разрядится сравнение содержимого элемента па- ды второго 30 регистра маскирования, котомяти 2 выделенной строки ассоциативного рые соответствуют адресам считываемых изнакопителя 1 и содержимого элементов па- ассоциативного накопителя 1 столбцов.мяти 14 соответствующей ей строки матри При считывании строки из матрицы арцы 13 аргументов поиска. При этом на гументов поиска по заданному адресу в асвыходах 21 и 23 элемента памяти 14 устано- социативный накопитель 1 по этому жевится единичный потенциал, который пода- адресу должны быть записаны единицы,ется на. входы 7 и 9 соответствующего Единицы также заносятся во все разрядыэлемента памяти 2. Если в триггере 45 эле второго 30 регистра маскирования и в тотмента памяти 2 хранится единица, то его разряд первого 29 регистра маскирования,выходы 11 и 12 сохранят потенциал логиче- который указывает на адрес считываемой изской единицы и в соответствующий разряд матрицы 13 аргументов поиска строки, Привторого 32. регистра фиксации реакций за- подаче сигнала 40 производится сравнениенесется: единица по заднему фронту сигна содержимого элементов памяти 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 соответствующего элемента памяти 25 10 15 20 25 30 35 40 45 50 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 регистра фиксации реакций будет подан ноль, говорящий о несовпадении строки-аргумента поиска и строки ассоциативного накопителя,При полном совпадении строки-аргумента поиска и строки ассоциативного накопителя на соответствующий вход первого510 20 25 30 35 40 45 5055 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,Формула изобретен ия Ассоциативное запоминающее устройство, содержащее матричный накопитель, первый и второй регистры маскирования данных, первый и второй регистры фиксации реакций, управляющие входы которых являются управляющими входами первой группы устройства, информационными выходами первой и второй групп которого являются соответственно выходы первого и второго регистров фиксации реакций, причем первые выходы элементов памяти соответствующих строк матричного накопителя объединены и подключены к соответствующим входам первого регистра фиксации реакций, а вторые выходы элементов памяти соответствующих столбцов, матричного накопителя объединены и подключены к соответствующим входам второго регистра фиксации реакций, первые входы элементов памяти соответствующих строк матричного накопителя объединены и подключены к соответствующим выходам первого регистра маскирования данных, а вторые и третьи входы элементов памяти соответствующих столбцов матричного накопителя объединены и подключены соответственно к первым и вторым выходам соответствующей группе выходов второго регистра маскирования данных, четвертый вход элемента памяти матричного накопителя является входом записи в накопитель устройства, информационными входами второй группы которого являются информационные входы второго регистра,маскирования данных, управляющие входы которого являются управляющими входами второй группы устройства, информационными входами первой группы которого являются информационные входы первого регистра маскирования данных, управляющие входы которого являются управляющими входами третьей группы устройства, о тлича ю щ ее ся тем. что, с целью расширения области применения устройства за счет осуществления конъюнктивного параллельного маскируемого поиска в накопите ле по аргументам поиска, введена матрицаэлементов памяти аргументов поиска, причем первые входы элементов памяти соответствующих строк матрицы аргументов поиска объединены и подключены к соответствующим 10 выходам первого регистра маскированияданных, вторые и третьи входы элементов памяти соответствующих столбцов матрицы аргументОв поиска объединены и подключены соответственно к первым и вторым выхо дЭм соответствующей группы выходоввторого регистра маскирования данных, четвертый, пятый и шестой входы элемента памяти матрицы аргументов поиска являются управляющими входами четвертой 20 группы устройства, выходы с первого по четвертый каждого элемента.памяти матрицы аргументов поиска подключены к входам с пятого по восьмой соответствующего элемен-та памяти матричного накопителя, пятые вы ходы элементов памяти соответствующихстолбцов матрицы аргументов поиска объединены, шестые выходы также объединены, седьмые выходы элементов памяти соответствующих строк матрицы аргументов по иска объединены и восьмые выходы тожеобъединены.. Ревская каз 944 Тираж Подписное ВНИИПИ Государственного комитета.ио изобретениям и открытиям при ГКНТ ССС 113035, Москва, Ж, Раушская наб., 4/5 изводственно-издательский комбийат "Патент", г, Чжгород, ул. Гагарин оста витель В, Боехред М. Моргента овКорре