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

72) Авторы изобретен П. Ил Я. И. Фет Сибирского отделения АН СССР,Сибирского отделения АН СССРарственный университеткого комсомола Институт математики Вычислительный цент и Новосибирский гос им, Лени1) Заявители ОБИАТИВНОЕ ЗАПОМИНАЮЩЕ УСТРОЙСТВО а, а выходпы соединеннного разряВ этом усФциативный сновистр Изобретение относится к запоминающимустройствам и может быть использованов качестве ассоциативного процессора дляпараллельной обработки информации,Известно ассоциативное запоминающееустройство (АЗУ), содержащее блок управ-ления, блок памяти, регистр опроса и регистр индикации, которые выполняют поискв блоке памяти всех слоев, ассоциативные.признаки которых соответствуют содержимому регистра опроса - признаку опросаООНедостатком этого устройства является ограниченный набор возможных условий ассоциативного поиска.Наиболее близким техническим решением к предлагаемому является АЗУ содержащее блок управления, блок памяти,состоящий из запоминающих ячеек, регистропроса, группу схем сравнения и регистриндикации, причем выход каждой запоминающей ячейки блока памяти соединен с20первым входом одноименной схемы сравнения группы, вторые входы всех схемсравнения группы объединены и подключены к выходу регистра опроскаждой схемы сравнения групс единичным входом одноимеда регистра индикации 2,ройстве осуществляется ассопоиск по различным критериям, а такжепоиск".о многим признакам,Однако поиски для нескольких различных признаков опроса, а также поискипо отдельным условиям сложного критерия поиска в известном устройстве производятся последовательно во времени, чемопределяется основной недостаток этогоустройства - малое быстродействие,Бель изобретения - увеличение быстродействия АЗУ за счет параллельной обра 4ботки по множеству критериев,Поставленная цель достигается тем,что в ассоциативное запоминающее устройство, содержащее накопитель, оной регистр опроса и основной региндикации, управляющие входы которыхподключены соответственно к первому,второму и третьему выходам блока упоо ф 3 963 1 равления, группу основных схем сравнения, первые входы которых подключены к выходам накопителя, а вторые входы со единены с выходом основного регистра опроса, введены . дополнительные регистры опроса, группы дополнительных схем сравнения, дополнительные регистры индикации, формирователи сигналов результата поиска, первая и вторая группы элементов И и элементы ИЛИ, причем 10 первые входы дополнительных схем сравнения подключены к выходам накопитЕля, вторые входы дополнительных схем срав нения каждой группы подключены к выходу одноименного дополнительного регистра опроса, а выходы дополнительных схем сравнения каждой группы соединены с входами одноименных дополнительных регистров индикации, выходы основных схем сравнения подключены к первым входам элементов И первой группы, вторые входы которых соединены с четвертым выходом блока управления, одноименные выходы схем сравнения подключены к входам соответствующих формирователей сигналов 2 результата поиска, выходы которых соединены с одними из входов элементов И второй группы, другие входы которых подключены к пятому выходу блока управления, а выходы соединены с одними из входов элементов ИЛИ, другие входы которых соединены с выходами элементов И первой гругпы, а выходы подключены к входам основного регистра индикации.Кроме того, блок управления содержит генератор тактовых импульсов и последовательно соединенные регистр команд, дешифратор, микропрограммную матрицу и регистр микрокоманд, выходы которого являются выходами блока, входом которого является вход регистра кода операций, причем выход генератора тактовых импульсов подключен к управляющему входу де-шифратора.На фиг. 1 приведена функциональная схема предлагаемого АЗУ; на фиг, 2 - структурная схема блока управления.АЗУ (фиг. 1) содержит блок 1 управления, блок 2 памяти, состоящий из и запоминающих ячеек, основной 3 и дополнительные 3 - 3 регистры опроса (где п и щ- целые числа), группы основных 41 и дополнительных 4 1 - 4 п схем сравнения, основной 5 и дополнительные 5,1- 5 регистры индикации, формирователи 6 1 - 6 сигналов результата 5 поиска, первую 7 и вторую 8 группы элементов И, элементы ИЛИ 9. Блок 1 управления имеет первый 10, второй 11,третий 12, четвертый 13 и пятый 14 вы .ходы,Блок 1 управления (фиг, 2) содержитрегистр 15 команды, генератор 16 тактовых импульсов, дешифратор 17, микропрограммную матрицу 18 и регистр 19микрокоманды. Блок 1 имеет вход 20.Устройство работает следующим образом,Слова массива-аргумейта хранятся взапоминающих ячейках блока 2 памяти, а пдизнаки опроса - в регистрах опроса 3- 3 Запоминающие ячейки блока памяти и регистры опроса могут иметь различную конструкцию (статические или динамические ЗУ, сдвиговые регистры, ЗУ на ЦМД, дорожки вращающихся магнитных ЗУ и т. д,). Однако они должны обеспечивать последовательное поразрядное обращение, а именно: при поступлении очередного управляющего импульса на вход блока 2 памяти с выхода каждой запоминающей ячейки считывается очередной разряд содержимого данной ячейки. Аналогично при поступлении управляющего импульса на вход любого из регистров опроса с выхода этого регистра считывается очередной разряд его содержимого,Некоторые разряды (поля) блока 2 памяти содержат ассоциативные признаки слов массива-аргумента, В соответствующих разрядах (полях) регистров опроса 3 - 31 находятся признаки опроса, по которым ведется поиск. АЗУ может работать в различных режимах, в зависимости от подаваемого на вход 20 блока 1 управления кода оперании.В режиме поиска по множеству критериев блок 1 управления вырабатывает следующую микропрограмму.В первой микрокоманде выдается сигнал на выходе 12 блока 1 управления, который осуществляет установку в "0" всех разрядов регистров 5., - 5. Во всех следующих микрокомандах выдаются сигналы на выходе 13 блока 1 управления,которые обеспечивают соединение выходоввсех схем 4 1 сравнения через соответствующие элементы И 7 и элементы ИЛИ 9с единичными входами соответствующихразрядов регистра 5. индикации. Кромеэтого, в ряде последовательных микрокоманд выдается серия сигналов на выходах11 и 10 блока 1 управления. В результате разрядные срезы, принадлежащиеполю ассоциативных признаков массивааргумента, считываются с выходов запоминающих ячеек блока 2 памяти и поступают параллельно на первые входы соответствуюших схем 4 - 41 п сравнения.Одновременно соответствующие разряды 1-го1 п. -го признаков опроса поступают с выходов регистров 31 - 31 п на вторые входы всех схем 4 - 4 щ сравнения. Следовательно в схемах 4 сравнения в каждом такте происходит сравнение дан ного разряда всех ассоциативных признаков массива-аргумента с соответствуюшим 10 разрядом первого признака опроса, Одновременно в схемах 41 сравнения происходит сравнение данного разряда с соответствующим разрядом второго признака опросаит,д, 35цикл поиска по множеству признаков состоит в-последовательной выборке всехразрядных срезов поля ассоциативных признаков с синхронной выборкой соответствующих разрядов признаков опроса. По окон- щ 0 чании этого цикла в схемах 4- 4сравнения оказываются выделенными те и только те схемы сравнения, где обрабатываются слова, соответствующие 1-му, ;,р -му признаку опроса. Сигналы с д выходов этих схем устанавливают в "1"Ф соответствующие разряды регистров 5-51, Под управлением этих регистров индикации из блока 2 памяти выбираются подмножества слов, ассоциативные признаки которых соответствуют 1-му в-му признаку опроса.В простейшем случае схемы сравнения всех групп содержат одинаковые логические схемы, например схемы эквивалент 35 ности, и тогда в каждой группе осуществляется один и тот же вид поиска, например поиск по совпадению. Однако можно в разных группах схем сравнения использовать логические схемы, реализующие разные виды сложного поиска, поиск ассоциативных признаков, больших (или меньших) по отношению к признаку опроса, поиск ближайшего большего (или меньшего) и т. д, При этом в предлагаемом АЗУ45 за время одного цикла одновременно выполняются различные операции сложного поиска по отношению к различным признакам опроса.1 В случае необходимости каждому из50 регистров опроса может быть сопоставлен соответствующий )егистр маски (не;показан), При этом для каждого из одновременно выполняемых поисков может использоваться индивидуальная маска.В режиме поиска по сложному критерию, представляюшему собой логическую совокупность нескольких условий, блок 1 5 963 100 6управления вырабатывает следующую микропрс грам му,В первой микрокоманде выдается сигнал на выходе 12 блока 1 управления,который осуществляет установку в "0"всех разрядов регистров 5 - 5 ,Во всехследующих микрокомандах выдаются сигналы на выходе 14 блока 1 управления,которые обеспечивают соединение выходовформирователей 6 ч - 61 через соответстс 1вуюшие элементы И 8 и элементы ИЛИ 9с единичными входами соответствующихразрядов регистра 5. Кроме того, микропрограмма выдает серии сигналов на выходах 11 и 10 блока 1 управления, обеспечивающие выборку обрабатываемой информации из блока 2 памяти и регистров 3 1 - ЗтПри этом схемы 4. - 4 сравнениявыполняют поиски по отдельным условиямсложного критерия, а формирователи объединяют (для одноименных схем сравнениявсех групп) результаты отдельных поисков,Выход каждого из формирователей соединяется в этом режиме со входом, установки "1" соответствующего разряда регистра 5.Формирователи 6. - 6,могут иметьразличные схемы, в зависимости от содержания сложного критерия, Так, например если сложный критерий состоит в одновременном выполнении условий поискаво всех схемах сравнения, то каждый изформирователей 6- 6 д должен представлять собой т-входовый элемент И,если сложный критерий состоит в выполнении хотя бы одного из условий поиска,то каждый формирователь представляетсобой т-входовый элемент ИЛИ. и т, д,По окончании цикла поиска по сложномукритерию разряды регистра 5, установившиеся в "1", будут указывать слова массива-аргумента, соответствующие данномусложному кретирию.В случае необходимости использованияв процессе эксплуатации разных сложныхкритериев, формирователи 6- бмогутбыть выполнены как многофункциональныелогические схемы с перестройкой, обеспечивающей реаЛизацию различных заданныхкритериев,Основным преимушеством предлагаемого АЗУ является высокая производительность, обусловленная возможностью параллельной обработки по множеству критериев,При.выполнении собственно операций ассоциативного поиска быстродействие увеличивается в щ- раз ( щ - количество каналов обработки, то есть наборов регистрО 7 96310 вопроса - группа схем сравнения регистр Индикации) по сравнению с известным (одноканальным) АЗУ. В то же время дополнительное оборудование, необходимое Ьля этого, хорошо приспособлено к производству средствами современной интегральной технологии, так как состоит из однородных структур. формула изобретения 1. Ассоциативное запоминающее устройство, содержащее накопитель, основной регистр опроса и основной регистр инди кации, управляющие входы. которых подключены соответственно к первому, второму и третьему выходам блока управления, группу основных схем сравнения, первые входы которых подключены к выходам на копителя, а вторые входы соединены с выходом основного регистра .опроса, о т л ич а ю щ е е с я тем,что с целью повышения быстродействия устройства, введены дополнительные регистры. опроса, группы 25 дополнительных схем сравнения, дополнительные регистры индикации, формирователи сигналов результата поиска, первая и вторая группы элементов И и элементы ИЛИ, причем первые входы дополнительных схем Зп сравнения подключены к выходам накопителя, вторые входы дополнительных схем сравнения каждой группы подключены к выходу одноименного дополнительного реГистра опроса, а выходы дополнительных схем сравнения каждой группы соединены с входами одноименных дополнительных регистров индикации, выходы основных схем сравнения подключены к первым входам элементов И первой группы, вторые входы которых соединены с четвертым выходом блока управления, одноименные выходы схем сравнения подключены к входам соответствующих формирователей сигналов результата поиска, выходы которых соединены с одним из входов элементов И второй группы, другие входы которых подключены к пятому выходу блока управления,. а выходы соединены с одними из входов элементов ИЛИ, другие входы которых соединены с выходами элементов И первой группы, а выходы подключены к входам основного регистра индикации,2. Устройство по и. 1, о т л и ч а ющ е е с я тем, что блок управления содержит генератор тактовых импульсов и последовательно соединенные регистр команд, дешифратор, и микропрограммную матрицу и регистр микрокоманд, выходы которого являются выходами блока, входом которого является вход регистра кода операций, причем выход генератора тактовых импульсов подключен к управляющему входу дешифратора. Источники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР963 100 10ИЪ.Е Составитель В. Рудаковереда Тех ред С.Мигунова Корректор Е. Рош акто ака Подписноомитета СССР чиал ППП Патент г ужгород ул Проектная526/77 Тираж 622 В Н ИИП И Государственного по делам изобретений 113035, Москва, Ж, Ра