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

(54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ 1 . . Изобретение относится к запоминающим устройствам и может быть использовано в качестве ассоциативного процессора для параллельной обработки информации. Известно ассоциативное запоминающее устройство (АЗУ), содержащее блок управ ления, блок памяти, регистр опроса и регистр индикашш, которые выполняют поис в блоке памяти всех слоев, ассоциативные признаки которых соответствуют содержимому регистра опроса - признаку опроса t Недостатком этого устройства является ограниченный набор возможных условий, ассоциативного поиска. Наиболее близким техническим решением к предлагаемому является АЗУ, содержащее блок управления, блок памяти, состоящий из запоминающих ячеек, регист опроса, группу схем сравнения и регистр индикации, причем выход каждой запоминающей ячейки блока памяти соединен с первым входом одноименной схемы сравнения группы, вторые входы всех схем сравнения группы объединены и подклюУСТРОЙСТВОчены к выходу регистра опроса, а выход каждой схемы сравнения группы соединен с единичным входом одноименного разряда регистра индикации 2 . В этом ycN ройстве осуществляется ассоциативный поиск по различным критериям, а также поискГ1О многим признакам. Однако поиски для нескольких различных признаков опроса, а также поиски по отдельным условиям сложного критерия поиска в известное- устройстве производятся последовательно во времени, чем определяется основной недостаток этого устройства - малое быстродействие. Цель изобретения - увеличение быстродействия АЗУ за счет параллельной обра- ботки по множеству критериев. , Поставленная цель достигается тем, что в ассоциативное запоминающее устройство, содержащее накопитель, основной регистр опроса и основной регистр индикации, управляющие входы которых подключены соответственно к первому, второму и третьему выходам блока управления, группу основных схем сравнения, первые входы которых подключены к выходам накопителя, а вторые входы соединены с выходом основного регистра опроса, введены . дополнительные ре- гистры опроса, группы дополнительных схем сравнения, дополнительные регист- ры индикации, формирователи сигналов результата поиска, первая и вторая группы элементов И и элементы ИЛИ, причем первые входы дополнительных схем сравнения подключены к выходам накопителя, вторые входы дополнительных схем сравнения каждой группы подключены к выход одноименного дополнительногр регистра епроса, а выходы дополнительных схем сравнения каждой группы соединены с входами одноименных дополнительных регистров индикации, выходы основных схем сравнения подключены к первым входам элементов И первой группы-, вторые входы которых соединены счетвертым выходом блока управления, одноименные выхо- ды схем сравнения подключены к входам соответствующих формирователей сигнало результата поиска, выходы которых соеди нены с одними из входов элементов И второй группы, другие входы которых подключены к пятому выходу блока управления, а выходы х;оейинены с одними из входов элементов ИЛИ, другие входы которых соединены с выходами элементов И первой группы, а выходы подключены к входам основного регистра индикации. Кроме того, блок управления содержит генератор тактовых импульсов и последовательно соединенные регистр команд, де шифратор, микропрограммную матрицу и регистр микрокоманд, выходы которого являются выходами блока, входом которо „ является вход регистра кода операции, причем выход генератора тактовых импул сов подключен к управляющему входу дешифратора. На фиг. 1 приведена функвдонал ная схема предлагаемого АЗУ; на фиг. 2 - структурная схема блока управления. АЗУ (фиг. -1) содержит блок 1 управления, блок 2 памяти, состоящий из п запоминающих ячеек, основной 3-, и дополнительные 3/) -3{у, регистры опроса (где пит- целые числа), группы основных 4,| и дополнительных 4ff схем сравнения, основной 5-, и дополнительные 5 2 5f регистры индикации, фор мирователи БЧ - бр сигналов результата поиска, первую 7 и вторую 8 группы эле ментов И, элементы ИЛИ 9. Блок 1 управления имеет первый 1О, второй 11, третий 12, четвертый 13 и пятый 14 выходы. Блок 1 управления (фиг. 2-) содержит регистр 15 команды, генератор 16 тактовых импульсов, дешифратор 17, микропрограммную матрицу 18 и регистр 19 микрокоманды. Блок 1 имеет вход 2О. Устройство работает следующим образом. Слова масеива-аргумвита хранятся в запоминающих ячейках блока 2 памяти, а признаки опроса - в регистрах опроса 3 - 3 Запоминающие ячейки блока памяти и регистры опроса могут иметь различную конструкцию (статические или динамические ЗУ, сдвиговые регистры, ЗУ на НМД, дорожки вращающихся магнитных ЗУ и т. д.). Однако они должны обеспечивать последовательное поразрядное обращение, а именно : при поступлении очередного управляющего импульса на вход блока 2 памяти с выхода каждой запоминающей ячейки считьтается очередной разряд содержимого данной ячейки. Анало- гично при поступлении управляющего им- пульса на вход любого из регистров опроса с выхода этого регистра считывается очередной разряд его содержимого, Некоторые разряды (поля) блока 2 памяти содержат ассоциативные признаки слов массива-аргумента. В соответствующих разрядах (полях) регистров опроса находятся признаки опроса, по которым ведется поиск. АЗУ может работать в различных режимах, в зависимости от подаваемого на вход 20 блока 1-управления кода операции. В режиме поиска по множеству критериев блок 1 управления вырабатывает следующую микропрограмму. В первой микрокоманде выдается сигнал на выходе 12 блока 1 управления, который осуществляет установку в О всех разрядов регистров 5х, - 5. Во всех следующих микрокомандах выдаются сигналы на выходе 13 блока 1 управления, которые обеспечивают соединение выходов всех схем 4 сравнения через соответствующие элементы И 7 и элементыИЛИ9 с единичными входами соответствующих разрядов регистра 5 индикации. Кроме этого, в ряде последовательных микрокоманд выдается серия сигналов на выходах 11 и 1О блока. управления. В результате разрядные срезы, принадлежащие полю ассоциативных признаков массивааргумента, считываются с выходов запоминающих ячеек блока 2 памяти и посту- пают параллельно- на первые входы соответствующих схем сравнения.Одновременносоответствующие разряды 1-ro,..,,/t признаков опроса поступают с выходов регистров 3-, - З на вторые входы всех схем 4 -, - 4 сравнения. Следовательно в схемах 4 сравнения в каждом такте происходит сравнение данного разряда всех ассоциативных признаков массива-аргумента с соответствуюши разрядом первого признака опроса. Одновременно в схемах 4/2 сравнения происходит сравнение данного разряда с соответс вующим разрядом второго признака опроса и т. д.. Никл поиска по множеству признаков состоит в последовательной выборке всех разрядных срезов поля ассоциативных при наков с синхронной выборкой соответствующих разрядов признаков опроса. По окон- 20 чании этого цикла в схемах сравнения оказываются выделенными те и только те схемы сравнения, где обрабатываются слова, соответствующие 1-му ...,гп -му признаку опроса. с выходов этих схем устанавливают в 1 соответствующие разряды регистров 5 - 5. Под управлением этих регистров инди кации из блока 2 памяти выбираются подмножества слов, ассоциативные признаки которых соответствуют 1-му, ..., т-му признаку опроса. В простейшем случае схемы срравнени всех групп содержат одинаковые логические схемы, например схемы эквивалентности, и тогда в каждой группе осуществ ляется один и тот же вид поиска, например поиск по совпадению. Однако можно в разных группах схем сравнения использовать логические схемы, реализующие разные виды сложного поиска, поиск ассоциативных признаков, больших (или мен ших) по отношению к признаку опроса, поиск ближайшего большего (или меньшего) и т. д. При этом в предлагаемом АЗ за время одного цикла одновременно выполняются различные операции сложного поиска по отношению к различным призна кам опроса. В случае необходимости каждому из регистров опроса может быть сопоставле соответствующий регистр маски (не, показан). При этом для каждого из одно временно выполняемых поисков может ис пользоваться индивидуальная маска. В режиме поиска по сложному критерию, представляющему собой логическую совокупность нескольких условий, блок 1 управления вырабатьтает следующую микропрограмму. В первой микрокоманде вьщается сигнал на выходе 12 блока 1 управления, который осуществляет установку в О всех разрядов регистров 5-, - 5, .Во всех следующих микрокомандах выдаются сигналы на выходе 14 блока 1 управления, которые обеспечивают соединение выходов формирователей 6-i - 6п через соответс- вуюшие элементы И 8 и элементы ИЛИ 9 с единичными входами соответствующих разрядов регистра 5-,. Кроме того, микропрограмма выдает серии сигналов на выходах 11 и 10 блока 1 управления, обеспечйвающие выборку обрабатываемой информации из блока 2 памяти и регист ров 3 - 3 . При этом схемы 4 х, - 4m сравнения выполняют поиски по отдельным условиям сложного критерия, а формирователи объединяют (для одноименных схем сравнения всех групп) результаты отдельных поисков. Выход каждого из формирователей соединяется в этом режиме со входом, установки I соответствующего разряда регистра 5. Формирователи могут иметь различные схемы, в зависимости от содержания сложного критерия. Так, например если сложный критерий состоит в одновременном выполненш условий поиска во всех схемах сравнения, то каждый из формирователей 6 i - 6п должен представлять собой шп-входовый элемент И, если сложный критерий состоит в выполнении хотя бы одного из условий поиска, то каждый формирователь представляет собой т-входовый элемент ИЛИ. и т. д. По окончании цикла поиска по сложному критерию разряды регистра 5, установившиеся в 1, будут указывать слова массива-аргумента, соответствующие данному сложному коетисию. В случае необходимости использования в процессе эксплуатации разных слохсных Критериев, формирователи 6,-6 могут быть вьшолнены как многофункциональные логические схемы с перестройкой, обеспечивающей реализацию различных заданных критериев. Основным преимуществом предлагаемого АЗУ является высокая производительность, обусловленная возможностью параллельной обработки по множеству критериев. При. выполнении собственно операций ассоциативного поиска быстродействие увеличивается в т- раз (т - количество каналов обработки, то есть наборов регистр bnpoca - группа схем сравнения - регистр |шдикваии) по сравнению с известным (одноканальным) АЗУ. В то же время дополнительное оборудование, необходимое iura этого, хорошо приспособлено к произбодству средствами современной интеграл ной технологии, так как состоит из однородных структур. Формула изобретения 1. Ассоциативное запоминающее устрой ство, содержащее накопитель, основной регистр опроса и основной регистр индикашш, управляющие входы. которых подклю чены соответственно к первому, второму и третьему выходам блока управления, группу основных схем сравнения, первые Входы которых подключены к выходам накопителя, а вторые входы соединены с вы ходом основного регистра .опроса, отли чающееся тем,что с целью повышения быстродействия устройства, введены дополнительные регистры, опроса, группы дополнительных схем сравнения, дополнительные регистры индикашш, формирователи сигналов результата понска,первая и вто рая группы элементов И и элементы ИЛИ, причем первые входы дополнительных схем сравнения подключены к выходам накопителя, вторые входы дополнительных схем сравнения каждой группы подключены к выходу одноименного дополнительного регистра опроса, а выходы дополнительных схем сравнения каждой группы соединены с входами одноименных дополнительных регистров индикации, выходы основных схем сравнения подключены к первым входам элементов И первой группы, вторые входы которых соединены с четвертым выходом блока управления, одноименные вы- . Ходы схем сравнения подключены к входам Соответствующих формирователей сигналов результата поиска, выходы которых соединены с одним из входов элементов И второй группы, другие входы которых подключены к пятому выходу блока управления,. а выходь соединены с одними из входов элементов ИЛИ, другие входы которых соединены с выходами элементов И первой группы, а выходы подключены к входам основного регистра индикации. 2. Устройство по п. 1, о т л и ч а ющ е е с я тем, что блок управления содержит генератор тактовых импульсов и последовательно соединенные регистр команд, дешифратор, и микропрограммную матрицу и регистр микрокоманд, выходы которого являются выходами блока, вхо- дом которого является вход регистра кода операций, причем выход генератора такте- вых импульсов подключен к управляющему входу дешифратора. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР /№ 277857, кл. Q 11 С 15/ОО, 1970. 2.Авторское свидетельство СССР № 5766О9, кл. G1. С 15/ОО, 1975 (прототип),

17

18

IS

19

10 1112.13 .i