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

 

(72) Авторы изобретения

B. П. Ильин и Я. И. Фет

Институт математики, Сибирского отделения AH СССР, Вычислительный центр Сибирского отделения АН СССР и Новосибирский государственный университет им. Ленинского комсомола (7)) Заявители (54) ACCOlIHATHBHOE ЗАПОМИНАЮЩЕЕ

УСТРОЙСТВО

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

Известно ассоциативное запоминающее устройство (АЗУ), содержащее блок управ- ления, блок памяти, регистр опроса и ре« гистр индикации, которые выполняют поиск в блоке памяти всех слоев, ассоциативные .признаки которых соответствуют содержимому регистра опроса - признаку опроса 13.0

Недостатком этого устройства являет ся ограниченный набор возможных условий ассоциативного поиска.

Наиболее близким техническим решением к предлагаемому является АЗУ, содержащее блок управления, блок памяти, состоящий из запоминающих ячеек, регистр опроса, группу схем сравнения и регистр индикации, причем выход каждой запоминающей ячейки блока памяти соединен с

20 первым входом одноименной схемы сравнения группы, вторые входы всех схем сравнения группы объединены и подклю2 чены к выходу регистра опроса, а выход каждой схемы сравнения группы соединен с единичным входом одноименного разряда регистра индикации (2) . В этом ус1 ройстве осуществляется ассоциативный поиск по различным критериям, а также поиск".чо многим признакам.

Однако поиски для нескольких различных признаков опроса, а также поиски по отдельным условиям сложного критерия поиска в известном устройстве производятся последовательно во времени, чем определяется основной недостаток этого устройства — малое быстродействие.

Бель изобретения - увеличение быстродействия АЗУ за счет параллельной обра4 ботки по множеству критериев.

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

3 963 1 равления, группу основных схем сравнения, первые входы которых подключены к выходам накопителя, а вторые входы со»» единены с выходом основного регистра ! опроса, введены дополнительные регистры опроса, группы дополнительных схем сравнения, дополнительные регистры индикации, формирователи сигналов результата поиска, первая и вторая группы элементов И и элементы ИЛИ, причем 1О первые входы. дополнительных схем сравнения подключены к выходам накопитЕля, вторые входы дополнительных схем срав» нения каждой группы подключены к выходу одноименного дополнительного регистра опроса, а выходы дополнительных схем сравнения каждой группы соединены с входами одноименных дополнительных регистров индикации, выходы основных схем сравнения подключены к первым входам элементов И первой группы, вторые входы которых соединены с четвертым выходом блока управления, одноименные выходы схем сравнения подключены к входам соответствующих формирователей сигналов 2 результата поиска, выходы которых соединены с одними из входов элементов И второй группы, другие входы которых подключены к пятому выходу блока управления, а выходы соединены с одними из входов элементов ИЛИ, другие входы которых соединены с выходами элементов

И первой гругпы, а выходы подключены к входам основного регистра индикации.

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

На фиг. 1 приведена функциональная схема предлагаемого АЗУ; на фиг. 2— структурная схема блока управления.

АЗУ (фиг. 1) содержит блок 1 управления, блок 2 памяти, состоящий из и запоминающих ячеек, основной 3 и дополнительные 3 — 3 регистры опроса

1 (где и и щ — целые числа}, группы основных 41 и дополнительных 4 1 — 4п1 схем сравнения, основной 5 и дополнительные 5 - 5„„регистры индикации, формирователи 6 q — 6„сигналов результата >> поиска, первую 7 и вторую 8 группы элементов И, элементы ИЛИ 9. Блок 1 управления имеет первый 10, второй 11, третий 12, четвертый 13 и пятый 14 вы» . ходы.

Блок 1 управления (фиг. 2) содержит регистр 15 команды, генератор 16 тактовых импульсов, дешифратор 17, микропрограммную матрицу 18 и регистр 19 микрокоманды. Блок 1 имеет вход 20.

Устройство работает следуюшим образом.

Слова массива-аргумейта хранятся в запоминающих ячейках блока 2 памяти, а пдизнаки опроса - в регистрах опроса

3„- З„Запоминающие ячейки блока памяти и регистры опроса могут иметь различную конструкцию (статические или динамические ЗУ, сдвиговые регистры, ЗУ на UMQ, дорожки врашаюшихся магнитных

ЗУ и т. д.). Однако они должны обеспечивать последовательное поразрядное обращение, а именно: при поступлении очередного управляющего импульса на вход блока 2 памяти с выхода каждой запоминаюшей ячейки считывается очередной разряд содержимого данной ячейки. Аналогично при поступлении управляющего импульса на вход любого из регистров опроса с выхода этого регистра считывается очередной разряд его содержимого.

Некоторые разряды (поля) блока 2 памяти содержат ассоциативные признаки слов массива-аргумента. В соответствуюших разрядах (полях) регистров опроса

3 — 3„1 находятся признаки опроса, по которым ведется поиск.

АЗУ может работать в различных режимах, в зависимости от подаваемого на вход 20 блока 1 управления кода оперании.

В режиме поиска по множеству критериев блок 1 управления вырабатывает следуюшую микропрограмму.

В первой микрокоманде выдается сигнал на выходе 12 блока 1 управления, который осуществляет установку в "0" всех разрядов регистров 5., - 5„. Во всех следующих микрокомандах выдаются сигналы на выходе 13 блока 1 управления, которые обеспечивают соединение выходов всех схем 4 сравнения через соответствующие элементы И 7 и элементы ИЛИ 9 с единичными входами соответствующих разрядов регистра 5. индикации. Кроме этого, в ряде последовательных микрокоманд выдается серия сигналов на выходах

1l и 10 блока 1 управления. .В результате разрядные срезы, принадлежащие полю ассоциативных признаков массива аргумента, считываются с выходов запоминающих ячеек блока 2 памяти и поступают параллельно на первые входы соответствующих схем 41 — 4 и сравнения.Одновременно соответствующие разряды

1-ro„...„ ï. -го признаков опроса поступают с выходов регистров 3 — 31п на вторые входы всех схем 41 — 4щ сравнения.

Следовательно в схемах 41 сравнения в каждом такте происходит сравнение дан» ного разряда всех ассоциативных признаков массива-аргумента с соответствующим!0 разрядом первого признака опроса. Одновременно в схемах 4 1 сравнения происходит сравнение данного разряда с соответствующим разрядом второго признака опроса и т. д. l5 цикл поиска по множеству признаков состоит в последовательной выборке всех разрядных срезов поля ассоциативных признаков с синхронной выборкой соответствующих разрядов признаков опроса. По окон- щ0 чании этого цикла в схемах 4 — 4 „1 сравнения оказываются выделенными те и только те схемы сравнения, где обрабатываются слова, соответствующие 1-му, ..;,р1 -му признаку опроса. Сигналы с выходов этих схем устанавливают в 1"

Ф ф соответствующие разряды регистров 51-

5 „. Под управлением этих регистров индикации из блока 2 памяти выбираются подмножества слов, ассоциативные признаки которых соответствуют 1-му,..., tn-му признаку опроса.

В простейшем случае схемы сравнения всех групп содержат одинаковые логические схемы, например схемы эквивалент35 ности, и тогда в каждой группе осуществляется один и тот же вид поиска, например поиск по совпадению. Однако можно в разных группах схем сравнения использовать логические схемы, реализующие разные виды сложного поиска, поиск ассоциативных признаков, больших (или меньших) по отношению к признаку опроса, поиск ближайшего большего (или меньшего) и т. д. При этом в предлагаемом АЗУ

45 за время одного цикла одновременно выполняются различные операции сложного поиска по отношению к различным признакам опроса.

В случае необходимости каждому из

50 регистров опроса может быть сопоставлен соответствующий регистр маски (не; показан). При этом для каждого из одновременно выполняемых поисков может использоваться индивидуальная маска.

В режиме поиска по сложному критерию, представляюшему собой логическую совокупность нескольких условий, блок 1

5 963 100 6 управления вырабатывает следующую микропрс грам му.

В первой микрокоманде выдается сигнал на выходе 12 блока 1 управления, который осуществляет установку в "0" всех разрядов регистров 51 - 5 .Во всех следующих микрокомандах выдаются сигналы на выходе 14 блока 1 управления, которые обеспечивают соединение выходов формирователей 6 — 6 через соответст

I вующие элементы И 8 и элементы ИЛИ 9 с единичными входами соответствующих разрядов регистра 51. Кроме того, микро программа выдает серии сигналов на вы ходах 11 и 10 блока 1 управления, обеспечивающие выборку обрабатываемой информации из блока 2 памяти и регистров 3 1 — 3п .

При этом схемы 4 . - 4 „сравнения выполняют поиски по отдельным условиям сложного критерия, а формирователи объединяют (для одноименных схем сравнения всех групп) результаты отдельных поисков.

Выход каждого из формирователей соединяется в этом режиме со входом. установки "1" соответствующего разряда регистра 5.„.

Формирователи 6. - 6,„могут иметь различные схемы, в зависимости от содержания сложного критерия. Так, например если сложный критерий состоит в опновременном выполнении условий поиска во всех схемах сравнения, то каждый из формирователей 6 q - 6д должен представлять собой уп-входовый элемент И, если сложный критерий состоит в выполнении хотя бы одного из условий поиска, то каждый формирователь представляет

3 собой rn-входовый элемент ИЛИ. и т. д.

По окончании цикла поиска по сложному критерию разряды регистра 51, установившиеся в "1", будут указывать слова массива-аргумента, соответствующие данному сложному кветипию.

В случае необходимости использования в процессе эксплуатации разных сложных критериев, формирователи 6 < — б„могут быть выполнены как многофункциональные логические схемы с перестройкой, обеспечивающей реаЛизацию различных заданных критериев.

Основным преимушеством предлагаемого АЗУ является высокая производительность, обусловленная возможностью параллельной обработки по множеству критериев, При выполнении собственно операций ассоциативного поиска быстродействие увеличивается в rn- раз (rn - количество каналов обработки, то есть наборов регистр

7 963 10 вопроса — группа схем сравнения» регистр

Индикации) по сравнению с известным (одноканальным) АЗУ. В то же время дополнительное оборудование, необходимое

Йля этого, хорошо приспособлено к производству средствами современной интегральной технологии, так как состоит из однородных структур.

Формула изобретения

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

Входы которых подключены к выходам на- 20 копителя, а вторые входы соединены с выходом основного регистра .опроса, о т л ич а ю щ е е с я тем,что с целью повышения быстродействия устройства, введены дополнительные регистры. опроса, группы 25 дополнительных схем сравнения, дополнительные регистры индикации, формирователи сигналов результата поиска, первая и вторая группы элементов И и элементы ИЛИ, причем первые входы дополнительных схем Зп сравнения подключены к выходам накопителя, вторые входы дополнительных схем сравнения каждой группы подключены к выходу одноименного дополнитепьного pet иHс т ра оoпDр осcа, а выходы дополнительных схем сравнения каждой группы соединены с входами одноименных дополнительных регистров индикации, выходы основных схем сравнения подключены к первым входам элементов И первой группы, вторые входы которых соединены с четвертым выходом блока управления, одноименные выходы схем сравнения подключены к входам соответствующих формирователей сигналов результата поиска, выходы которых соединены с одним из входов элементов И второй группы, другие входы которых подключены к пятому выходу блока управления,. а выходы соединены с одними из входов элементов ИЛИ, другие входы которых соединены с выходами элементов И первой группы, а выходы подключены к входам основного регистра индикации.

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

Источники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР

>¹ 277857, кл. 6 11 С 15/00, 1970.

2. Авторское свидетельство СССР

¹ 576609, кл. Q 11 С 15/00, 1975 (нрототип) .!

463 100

yg ff2151Ф

Фи .2.

Составитель В. Рудаков

Редактор Ю. Середа Техред С.Мигунова Корректор Е. Рошко

Заказ 7526/77 Тираж 622 П одписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4