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

ва). три младших разряда которого являются маркерными, а г старших - информационными, адресный коммутатор 3, промежуточный коммутатор 4, коммутатор 5 записи; входной коммутатор б, адресные входы 7 устройства, регистр 8 числа, информационные выходы первой группы 9устройства, регистр 4Ю начального адреса, регистр 11 промежуточного хранения, k-разрядный регистр 12 текущегоадреса (k i logan, n разрядность слов, хранимых в ассоциативном запоминающем устройстве), реверсивный счетчик 13, информационные входы 14 устройства, регистр 15 признака опроса, информационные выходы второй группы 16 устройства, первый элемент 17 неравнозначности, мультиплексор 18, второй элемент 19 неравнозначности, третий элемент 20 неравнозначности, элемент И 21, элемент ИЛИ 22, инвертор 23,

Кроме того, ассоциативное оперативное запоминающее устройство содержит блок 24 управления, входами которого являются выход 25 переполнения реверсивного счетчика 13, выход 26 второго разряда выходного регистра 2, выход 27 третьего разряда указанного регистра, выход 28 первого элемента 17 неравнозначности, выход 29 элемента И 21, выход 30 элемента ИЛИ 22, а выходами блока 24 управления являются соответственно вход 31 управления приемом кода регистра 8 числа, вход 32 управления приемом кода регистра 10 начального адреса, вход 33 управления приемом кода регистра текущего адреса 12, объединенные входы 34 управления считыванием блока Гпамяти и приема кода выходного регистра .2, вход 35 управления приемом кода регистра 11 промежуточного хранения, вход 36 управления приемом кода регистра 15 признака опроса. Управляющие входы: 37 входного коммутатора 6; 38 - коммутатора 5 записи; 39 - адресного коммутатора 3: 40 - промежуточного коммутатора 4; 4,1 - мультиплексора 18, вход 42 установки О и вход 43 установки в Г всех разрядов реверсивного счетчика 13, суммирующий счетный вход 44, вычитающий счетный вход 45, вход 46 управления реверсивного счетчика 13, вход 47 управления записью блока 1 памяти, второй 48 и третий 49 младшие разряды информационных входов блока 1 памяти, вход 50 управления сдвигом, вход 51 установки в 1 и вход 52 установки и О всех разрядов регистра 15 признака опроса, второй вход 53 третьего элемента 20 неравно5начности, третий вход 54 мультиплексора 18. Внешними входами блока-24 управления являются входы 55 задания кода команды, внешний вход 56 задания направления

поиска, выходамиблока 24 управления являются выход 57 Положительный результанте операции и выход 58 Отрицательный результат операции.

Блок 24 управления может быть выполнен в виде микропрограммного устройству управления (фиг.2) и содержит блок 59 пог стоянной памяти начальных адресов микрсипрограмм, блок 60 элементов ИЛИ, счетчик

6t адреса микрокоманд мультиплексор 62 условий ветвления микропрограмм, элемент И 63, элемент ИЛИ 64, вход 65 тактовых импульсов, блок 66 постоянной памяти микропрограмм, регистр 67 микропрограмм, выходы 31-54,57 и 58 являются выходами блока 24 у правления, а выходы 68 и 69 подключены соответственно к входам установки в Г и О триггера 70, выход 71 которого является, как и входы 25-30 блока

24 управления, входом мультиплексора 62. вход 72 явл;яется входом начальной установки.

Информация в блоке 2 памяти в виде п-ярусного графа (п - разрядность), причем

каждая вершина 1-го яруса (i 1,п) соответствует подмножеству хранящихся слов, совпадающих между собой в I старших разрядах. Соответственно число вершин на i-M уровне графа равно количеству слов, отличающихся в I старших разрядах. Каждая из вершин содержит информацию о ветвлении на 1-м ярусе. Вершины нижнего п-го уровня соответствуют словам, хранящимся в блоке 1 памяти.

Соответственно объем блока 1 памяти разбит по числу ярусов графа на п зон, адресуемых кодом с выходом счетчика 13. Каждая из зон содержит m ячеек разрядностью (logam + 3). В пределах зоны; ячейки

адресуются кодом с выходом адресного коммутатора 3. Три младших разряда каждой ячейки содержат маркерные биты соответственно а,/3, у, а остальные разряды указывают на адрес ветвления. Единичное

значение бита)3 указывает на соответствие ячейки вершине графа. Единичное значение бита у указывает на наличие ветвления в вершине, соответствующей данной ячейке. В случае наличия ветвления ячейке в } -зоне

сответствуют две ячейки в (1+1)-й зоне, причем адрес в зоне одной из них совпадает с адресом в зоне рассматриваемой ячейки из 1-й зоны, а адрес другой указывается в информационных разрядах ячейки из 1-й зонь|.

Бита соответствует значению 1-го бита подмножества слов, соответствующих ячейке в {1+1)-й зоне, адрес которой совгтадает с адресом в зоне i ячейки, порождающей ветвление. При этом в ячейке -и зоны, адрес

которой указывается порождающей ветвление ячейки, указывае ся адрес последней, бит о. равен нулю.

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

Пусть в блок 1 памяти последовательно записываются 8-разрядные слова по соответствующим адресам; 2,3,1,0 (п 8, m 4)

101Q1100 -2

01111111.3

10111101 -1

10101101 -О

Соответствующий граф представлен на фиг.9.

Информация в АЗУ разместится согласно таблице..

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

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

При записи слова в блоке 1 памяти кода команда Запись информации по адресу подается на входы 55, одновременно адрес подается на адресные входы 7 устройства, а само слово - на информационные входы .14 устройства. Алгоритм выполнения команды записи представлен на фиг.З. В частности, блок 24 управления с получением команды записи по входам 55 формирует единичные сигналы на своих выходах 31, 36 и 42, а на выходах 37 код 00, который управляет работой коммутатора 6 таким образом, что адресные входы 7 оказываются скоммутированными на входы регистра 8 числа (соответственно, под действием сигнала с выхода 31 код адреса фиксируется на регистре 8 числа). Одновременно, под управлением сигнала на выходе 36 на регистре 15 фиксируется код слова, подлежащего записи, по сигналу на выходе 42 счетчик 13 устанавливается .

В следующем такте (блок 2 на фиг.З) блоком 24 управления формируется код 10 на выходах 39 и единичные сигналы на выходах 34.40,35, по которым соответственно

коммутируется код, хранящийся на регистре 10 начального адреса,коммутатором 3 на адресные входы младших разрядов блока 1 памяти, производится считывание соответствующей ячейки блока 1 памяти на выходной регистр 2, коммутация через коммутатор 4 и прием на регистр 11 промежуточного хранения кода с регистра 10 начального адреса. В содержательном.плане приведенные микрооперации соответствуют опросу ячейки, соответствующей корню графа, адрес которой хранится на регистре 10 начального адреса (в приведенном примере - ячейка с адресом 10 в зоне 000). Если значение бита у5 в считанном слове равно нулю (сигнал на входе 26 блока 24 управления равен нулю), то корень дерева отсутствует, т.е. в блоке 1 памяти не записано ни одного слова. В этом случае записываемое слово будет первым и его адрес станет адресом корня дерева слов, хранящихся в устройстве. Для этого блок 24 управления сигналами с выходов 32,35,40, кодом 11 с выходов 39 инициирует запись содержимого регистра 8 числа через адресный коммутатор 3 на регистр 10 начального адреса и регистр, 11 промежуточного хранения (блок 3 алгоритма на фиг.З).

Если значение бита/ (сигнал на входе 26) равно единице, то работой блока 24 управления управляет сигнал совпадения, формируемый на его входе 30- Указанный сигнал и.меет единичное значение, если текущий разряд признака опроса равен биту а считанного слова либо бит ссылки у не равен нулю, и формируется на выходе элемента ИЛИ 22. Фактически единичное значение сигнала на входе 30 свидетельствует о том, что в блоке 1 памяти хранятся слова, совпадающие в текущем и предшествующих разрядах с записываемым. В этом случае анализируется сигнал с выхода элемента И 21 (вход 29 блока 24 управления). Указанный сигнал имеет нулевое значение, если записываемое слово совпадает текущим разрядом со словом, лежащим в корне дерева слов. В этом случае необходимо в следующей зоне обращаться к ячейке, имеющей тот же адрес, что и ячейка, считанная в текущей зоне. Указан мая операция обеспечивается выполнением в следующем такте (блок 3 алгоритма на фиг.З) выдачи блоком 24 управления сигналов с выходов 44,50, по которым соответственно увеличивается на единицу содержимое реверсивного.счетчика 13 (осуществляется переход к последующей зоне и сдвигается содержимое регистра 15 признака опроса), т.е. при рбращении к последующей зоне

блока 1 памяти анализируется знамени последующего разряда признака опроса.

Если сигнал на входе 29 блока 24 управления равен логической единице, то это значит, что записываемое слово совпадает в текущем разряде со словом, на адрес котоiporo указывает ссылка ветвления. В этом случае в последующей зоне-необходимо анализировать содержимое ячейки с адресом, указанным в поле ссылки ячейки, считанной в текущей зоне. Для этого в последующем такте (Ьлок 5 алгоритма на фиг.З) блок управления формирует единичные сигналы на выходах 35,44,60, по которым соответственно содержимое поле ссылки выходного регистра 2 через коммутатор 4 (сигнал на управляющем входе 40 которого равен нулю) записывается на регистр 11 промежуточного хранения, содержимое реверсивного счетчика 13 увеличивается на единицу и содержимое регистра 15 признака опроса сдвигается на один разряд. При отсутствии сигнала переполнения на входе 25 производится считывание содержимого ячейки в следующей зоне (фиг.З, блок 9), кот-орое обеспечивается выдачей блоком 24 кода 01 на выходе 39 и единичного сигнала на выходе 34. Цикл анализа повторяется.

В случае, если при опросе ячейки блока 1 памяти на входе 30 блока 24 управления будет сформирован сигнал нулевого уровня (что соответствует отсутствию ранее записанных слов, совпадающих в предшествующ м и текущем разряде с записываемым), то необходимо выставить маркерный бит у пе|№хода в единицу, в поле ссылки указать адрес записываемого слова применительно к считанной в текущей зоне ячейки и запиеать в ячейку по адресу вводимого адреса ячейки, которая содержит ссылку. Для этого блок 124 управления (блок 6 алгоритма на фиг.З) формирует код 01 на выходах 39, код 10 на выходах 38, код 00 на выходах 41, единичные сигналы на выходах 47-49., которые инициируют запись в ячейку, адрес которой содержится в регистре 11 промежуточного хранения (т.е. в ячейку, содержимое которой считывалось в предшествующем такте считцвания) маркерного бита .cf:этой же ячейки без изменения (через элемент 20 неравнозначности, на второй вход 53 которого подается нуль, и мультиплексор 18), единицы в маркерный бит /9 (с выхода 48), единицы в маркерный бит у (с выхода 49), адреса, содержащегося на регистре 8 числа (через коммутатор 5 записи).

В следующем такте (блок 7 алгоритма на фиг.З) блоком 24 управления формируется

код 11 на выходах 39, код 01 на выходах 38, единичные сигналы на выходах 47,44,50, которые обеспечивают запись в блок 1 памяти по адресу, содержащемуся в регистре 8 числа, нуля в маркерные биты/3,х (с выходом 48,49), адреса,содержащегося на регистре 11 промежуточного хранения через коммутатор 5 записи; а также увеличение на единицу содержимого реверсивного счетчика 13 и

сдвига содержимого регистра 15 признака опроса.

Если при увеличении содержимого реверсивного счетчика 13 возникает сигнал переполнения, который поступает на вход

25 блока 24 управления, то операция записи заканчивается. В противном случае в следующей зоне записывается по адресу вводимого слова бит /3 присутствия и текущий разряд признака опроса в бит а. Для этого

блок 24 управления формирует коД 11 на выходах 39, код 01 на выходах 41 и единичные сигналы на выходах 47,48,44,50, которые обеспечивают запись по адресу из регистра 8 числа единицы в Маркерный блт

(с выхода 48) и бита текущего разряда записываемого слова в регистре 16 в маркерный бит а (через элемент 17 неравнозначности, на второй выход 56 которого подается нулевой сигнал, и мультиплексор 18), производится также увеличение содержимого счетчика 13 и сдвиг регистра 15. При отсутствии сигнала переполнения счетчика 13, подаваемого на вход 25, указанные действия (блок 8 алгоритма на фиг.З) повторяются. По окончании процесса записи блок 24 управления выдает сигнал на выходе 57 устройства.

. При исключении слова из блока 1 памяти код команды Исключение информации

по адресу ; подается на входы 55,,. одновременно адрес подается на адресные входы 7 устройства. Алгоритм выполнения команды исключения представлен на фиг.4. Блок 24 управления в первом такте (блок 1

алгоритма на фиг.4) формирует код 00 на выходах 37,единичные сигналы на выходах 31,43,69, KOTOpbie обеспечивают запись адреса исключаемого слова с входов 7 на регистр 8 числа, установку всех разрядов

реверсивного счетчика 13 в единицу, установку триггера 70 в О.

В следующем такте производится считывание содержимого ячейки с адресом исключаемого слова на выходной регистр 2. Это

обеспечивается выдачей блоком 24 управле ния (блок 2 алгоритма на фиг.4) кода 11 на выходах 39 и единичного сигнала на выходе 34. Если бит/S равен единице, то анализируется Состояние триггера 70. индицируемое сигналом на входе 71 блока 24 управления. Если триггер 70 установлен в О, то анализируется бит усчитанного из блока 1 памяти слова (вход 27). Если бит у равен нудю, то считанное слово не содержит ссылок и, следовательно, исключение слова в текущей зоне состоит в установке маркернога бита /3 в О. Далее блок 24 управления формирует код 11 на выходах 39, единичные сигналы на выходах 47,45 (блок 3 алгоритма на фиг.4). которые обепечивают запись нуля (с выхода 48) в маркерный бит S ячейки, адрес которой определяется соержимым регистра 8 числа. Одновременно содержимое реверсивного счетчика 13 уменьшается на единицу. Ог1ять повторяется цикл считывания, если нет сигнала на входе 25.

Если исключаемая ячейка в текущей зо не содержит ссылку, а триггер 70 установлен в то указанная ситуация соответствует тому, что от исключаемой ветви графа, хранящегося в блоке 1 памяти, отходит неисключаемая ветвь. Признаком наличия такой ветви, отходящей от исключаемой, является единичное состояние триггера 70. Поэтому при обнаружении ветвления в исключаемой ветви триггер 70 необходимо установить в продублировать-исключаемую ветвь по адресу отходящей. Для этого адрес отходящей ветви графа следует зафиксировать на регистре 11 промежуточного хранения. Блок 24 управления формирует (блок 4 алгоритма на фиг.4) код 00 на выходах 39, код 00 на выходах 4l и единичные сигналы на выходах 35,47,48,68,53, которые инициируют передачу кода из выходного регистра 2 через открытый нулевым сигналом с выхода 40 блока 24 Коммутатор 4 на регистре 11 промежуточного хранения и запись в ячейку с адресом, определяемым кодом ссылки на выходном регистре 3 единичного маркерного бита /9 (с выхода 48) и бита а , формируемого как инверсия аналогичного бита исключаемого слова.(указанная инвер: сия осуществляется элементом 20 неравнозначности, на вход 53 которого подается единичный сигнал), поскольку текущий бит слова, ветвь которого отходит от исключа мого, не совпадает с текущим битом исключаемого слова. Далее выполняется описанный такт установки в О маркера присутствия исключаемого слова (блок 3 алгоритма на фиг.4).

ЕСЛИ при анализе ячейки, соответствующей в текущей зоне исключаемому слову, риггер70 установлен в О, то анализ11руетя бит у считанного слова, которы( указывает на наличие ветвления на более высоких

уровнях графа. Так, если бит у равен единице (имеется сигнал единичного уровня на выходе 27 блока 24 управления), то необходимо переписать по адресу, хранящемуся в

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

хранения. Указанные микрооперации выполняются в два такта. В первом такте (блок 5 алгоритма на фиг.4) блок 24 управления формирует код 01 на выходах 39, код 10 на выходах 38, код 00 на выходах 41, единичные сигналы на выходах 47-49, которыми обеспечивается запись маркерного разряда а из регистра 2 (через элемент 20 неравнозначности, на второй вход 53 которого подается нулевой сигнал, и мультиплексор 18) в

поле маркера С .запись единиц в поле остальных маркернь1х разрядов, запись кода с регистра 2 в поле ссылки ячейки, адрес которой определяется кодом, хранящимся на регистре 11. Во втором такте (блок 6

алгоритма на фиг.4) блок 24 управления формирует код 00 на выходах 39, код 01 на выходах 38, единичные сигналы на выходе 47, которые обеспечивают запись в ячейку по адресу, определяемому кодом, хранящимся на регистре2 маркерного бита /б, равного нулю, кода с регистра 11 промежуточного хранения. После указанных корректировок при ненулевом коде на счетчике 13 осуществляется переход к описанному такту установки в О маркера присутствия исключаемого слова (блок 3 алгоритма на фиг.4). Если исключаемое слово на текущем уровне графа не содержит ветвлений (V (27) 0), то содержимое исключаемой ячейки

переписывается,по адресу, зафиксированному в регистре 11 промежуточного хранения. Соответственно, блок 24 управления формирует код 01 на выходах 39, код 10 на выходах 38, кодОО на выходах 11 и единичные

сигналы на выходах 47,4« (блок 7 алгоритма на фиг.4), которые обеспечивают выполнение указанной записи. Дальше следует такт установки в О маркера присутствия исключаемого слова (блок 3 алгоритма на фиг.4),

если все разряды счетчика 13 не обнулены. Если при анализе считанной в текущей зоне ячейки, соответствующей исключаемому слову ячейки, обнаружится, что маркерный бит ft присутствия равен нулю , то это

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

необходимо установить в О маркерный бит ветвления в слове, содержащем ссылку ветвления на исключаемую ветвь. Указанная микрооперация обеспечивается выдачей блоком 24 управления кода 00 на выходах 39, кода 00 на выходах 41 и единичных сигналов на выходах 47,48,53 (блок 8 алгоритма на фиг.4).

В случае наличия ответвлений в исключаемой ветви (триггер 70 установлен в 1) осуществлется запись в поле ссылки ячейки, указывающей на исключаемую ветвь, адреса ветви,ответвляющейся от исключаемой, а также запись адреса ячейки, содержащей ссылку на исключаемую ветвь в поле сылки ячейки, соответствующей ветви, отходящей от исключаемой. Указанные действия осуществляются в два такта. В первом такте блоком 24 управления (блок 9 алгоритма на фиг.4) выдается код 00 на выходах 39, код 00на выходах 41, код 01 на выходах 38 и единичные сигналы на выходах 47-49,53,,которые инициируют запись в ячейку, определяемую адресом, хранящимся в поле ссылки выходного регистра 2, следующей информации: в поле ссылок - код с выходов, регистра 11 промежуточного хранения, в поле маркерных битов ,у- единиц (с выходов 48,49), в поле маркерного бита а инверсное начение соответствующего бита выходного регистра 2. Во втором такте блоком 24 управления выдается (блок 10 алгоритма на фиг.4) код 01 на выходах 39, код 10 ,на выходы 38, единичные потенциалы на выход 48, которые инициируют запись в ячейку по адресу, совпадающему с кодом на регистре 11 промежуточного хранения, маркерных битов /3 иу , равных нулю, и кода с выходов регистра 2. По окончании выполнения указанных микрокоманд (после выполнения блоков 8 или 10 алгоритмов на фиг.4) блок 24 управления формирует на выходе 57 сигнал конца операции.

После выполнения блоков 4,6,7 алгоритма на фиг,4 выполняется описанный блок 3 микроопераций установки в О маркерного бита jS присутствия исключаемого слова и уменьшения на единицу,содержимого счетчика 13. Если в результате указанного уменьшения счетчик 13 выдает сигнал переполнения на вход 25 блока 24 управления, то в следующем такте (блок 11 алгоритма на фиг.4) блок 24 управления формирует код 00 на выходах 39 и единичный сигнал на выходе 32, которые обеспечивают пересылку адреса ветви, отходящей от исключаемой, из регистра 11 промежуточного хранения через адресный коммутатор 3 на регистр 10 начального адреса. Операция исключения заканчивается.

Процесс исключения может иллюстрироваться следующим примером.

Пусть в условиях предыдущего примера из блока 1 памяти исключается слово, записанное по адресу 10. В первом цикле на счетчике 13 устанавливается код 111, на регистре 8 числа - код 10. Маркерные разряды соответствующего слова равны , 1, У . Следовательно, выполняется блцк 4 алгоритма, представленного на фиг.4,-триггер 70 устанавливается в 1, в ячейку 00 зоны 111 записывается код « 0 1 ,у 1, блоком 3 алгоритма бит Д в ячейке 10 устанавливается в О, в регистр 11 записывается код 00. Содержимое счетчика 13 становится равным 110, Так как в ячейке с адресом 10 в этой зоне, как и в последующих зонах 101, 100, /3 1,у О, то выполняются блоки7иЗ алгоритма на фиг. 4, которые реализуют запись р ячейку 00 маркеров as О (для зоны 110) или а 1 (для зон 101,100),/ 0.у 0. В зоне 011 маркерные биты в ячейке 10 имеют значение а 0, /3 1, у 1. Следовательно, выполняются блоки 5,6,3 алгоритма на фиг.4. Блоком 5 в ячейку 00 заносится код 01101, блоком 6 в ячейку ol заносится код ХОХОО. В зонах 010 и 001 выполняются операции, аналогичные выполнявшимся взонах 101,100. ВзонеООО маркерные биты слова, хранящегося в ячейке 10, равны а 1,;3 1,у 1. Соответственно выполняют блоки 5,6,11,12 алгоритма, изображенного на фиг,4, в ячейку 00загружается код 111 11, в ячейку 11 загружается код 0000 00, маркерный бит /3 в ячейке 10 устанавливается в О. Код 00 загружается в регистр 10 начального адреса вместо ранее там находившегося кода 10.

При поиске слова по совпадению код команды Поиск адреса ячейки, содержимое которой совпадает с заданным признаком опроса, подается на входы 55 устройства, одновременно код слова подается на информационные входы 14 устройства. Алгоритм выполнения команды поиска по совпадению представлен на фиг.5.

Выполнение команды начинается (блок

Iалгоритма на фиг.6) выдачей блоком 24 управления единичных сигналов на выходах 46,42,31, кодов 10 на выходах 39 и 37, которыми инициируется прием кода признака опроса на регистр 15, пересылка кода с регистра 10 начального адреса через коммутаторы 3 и 6 на регистр 8 числа, установка в О разрядов реверсивного счетчика 13. В следующем т;акте (блок 2 алгоритма на фиг.5) выдачей блоком 24 управления кода

IIна выходах 39 и единичного сигнала на. выходе 47 обеспечивается считывание из блока 1 памяти содержимого ячейки, соот- ветствующей корню дерева слов, записанных в блоке 1. Дальнейшее функционирование устройства определяется значением сигналов на входах 29 и ЗО блока 24 управления. Если сигнал на входе 30 равен нулю, то операция поиска оканчивается выдачей сигнала с выхода 58 устройства, свидетельствующего об отсутствии в блоке 1 памяти слова, совпадающего с признаком опроса. В случае, если единичный сигнал на входе 30 есть, анализируется сигнал на входе 29: если он равен нулю, то, следовательно, признак опроса в текущем разряде совпадает с соответствующим разря,дом слова, отражаемого в блоке 1 памяти прямым участком ветви. В противном случае текущий разряд признака опроса совпадает с соответствующим разрядом словЭ/ отражаемого ответвлением. Соответственно в первом случае (блок 4 алгоритма на фиг.5) блок 24 управления сигналами с выходов 44,50 осуществляет увеличение содержимого счетчика 13 и сдвиг содержимогорегистра 15 признака опроса. Затем цикл анализа повторяется. Во втором случае производится переход к новому адресу в последующей зоне (блок 3 алгоритма на фиг.5), блок 24 управления формирует единичные сигналы на выходах 44,50,31 и код 01 на выходах 37, которые инициируют кроме .прибавления единицы к содержимому счетчика 13 и сдвига регистра 15 занесение через входной коммутатор кода ссь1лкИ с выходного регистра 2 на регистр 8 числа.Ебли счетчик 13 в результате прибавления единицы не обнуляется, выдавая при этом сигнал на вход 25 блока 24 упраления, то цикл поиска повторяется, в противном случае по сигналу с входа 25 блок 24 управления формирует единичный сигнал конца операции на выходе 57, а адрес искомого слова, совпадающего с признаком поиска, фиксируется при этом на выходах 9 устройства. При поиску экстремума код команды Поиск ячейки, содержащей экстремальный код, подается на входы 55, а на вход, 56 подается бит, определяющий направление поиска, равный нулю при поиске максимума и единице при поиске минимума. Пусть дли определенности ищется максимум среди чисел, хранящихся в устройстве. В первом такте поиска (блок 1 на алгоритме поиска экстремума, представленном на фиг.6)блок 24 управления формирует коды 10 на выходах 39 и 37, единичные сигналы на выходах 31,42,51. которые обеспечивают запись кода, хранящегося на регистре 10 начального адреса через коммутаторы 3 и 6 на регистр 8 числа, обнуление всех разрядов реверсивного счетчика 13 и установку в 1 всех разрядов регистра 15 признака опроса. В последующем такте (блок 2 алгоритма на фиг.6) выполняется считывание на выходной регистр 2 содержимого ячейки с адресом, зафиксированным на регистре 8 числа. Для этого блок 24 управления формирует код 11 на своих выходах 39 и единичный сигнал на выходе 34. Выбор следующей микрокоманды, подлежащей выполнению, осуществляется в зависимости от сигналов на входах 29,30 блока 24 управления. Так, если сигнйл совпадения (сигнал на входе 30 блока 24) равен нулю, то необходимо инвертировать текущий разряд признака опроса и перейти к следующей зоне. Соответственно блок 24 управления формирует единичные сигналы на своих выходах 44,50 и код 10 на выходах 41, которые инициируют увеличение содержимого счетчика 13 на единицу и сдвиг содержимого регистра 15 на один разряд с запоминанием освободившегося разряда нулем, сигнал которого поступает с выхода 54 блока 24 управления через мультиплексор 18. Если счетчик 13 не выдает сигнала переполнения на вход 25 блока 24 управления, вновь выполняется микрокоманда, соответствующая блоку 2 алторитма на фиг.6. В случае, если сигнал совпадения на входе 30 равен единице, анализируется сигнал на выходе 29. который определяет ветвь графа (прямую или отходящую), с которой выявлено совпадение. Если, в частнрсти, сигнал на входе 29 равен нулю (Соответствует совпадению по прямой ветви), то блок 24 управления выдает единичные сигналы на выходах 44,50,54 и код 10 на выходах 41 (блок 3 алгоритма на фиг.6),которыми осуществляется увеличение содержимого реверсивного .счетчика 13 на единицу, сдвиг содержимого регистра 15 с заполнением освободившегося при этом разряда единицей, поступающей с выхода 54 через мультиплексор 18. Если сигнал на входе 29 равен еди-нице, то выполняется блок 4 алгоритма на фиг.6 - блок 24 управления в дополнение ко всем сигналам, выдаваемым в блоке 3 алгоритма: формируется код 01 на выходах 37 и сигнал на выходе 31, соответственно, в дополнение к описанным микрооперациям выполняется занесение кода с регистра 2.через Ъходной коммутатор 37 на регистр 8 числа. Если при переходе на следующую зону содержимое счетчика 13 обнулится, то на входе 26 блока 24 управления сформируется единичный сигнал, по которому последний выдаст сигнал конца операции на входе 57,

код максимального слова будет зафиксирован при этом на выходах 16 устройства, а его адрес - на выходах 9 устройства.

При поиске минимума на вход 56 подается потенциал единичного уровня и результат с выходов 16 считывается в инверсном коде.

При поиске числа, ближайшего к заданному, код команды Поиск адреса, содержащего код, являющийся ближайшим (большим или меньшим) к признаку опроса, подается на входы 55, код признака опроса подается на входы 14 устройства, а направление поиска задается сигналом на входе 56 (при поиске ближайшего большего - нулевой сигнал, при поиске меньшего - единичный). Алгоритм работы устройства при, реализации указанного вида-поиска представлен на фиг.7. Пусть для определенности ищется ближайшее большее заданного. Суть процесса поиска ближайшего состоит в следующем.

. В п-ярусном графе, представляющем числа, хранящиеся в блоке 1 памяти, выделяется ветвь, отходящая от ветви заданного признака опроса в направлении, соответствующем критерию поиска на ярусе с наибоНьшим значением. В подграфе, порождаемом указанной отходящей ветвью, отыскивается ветвь, соответствующая минимальному числу. Если, например, ищется ближайшее большее в графе чисел, представленной на фиг.9, к числу 10100000, то ветвью заданного числа будет ветвь, расположенная по адресу 10 от зоны 000 до зоны 1000. Отходящая ветвь начинается в зоне 100 по адресу 10 и порождает подграф, в котором минимальное число соответствует адресу 10. Следовательно, искомый код равен 10101100.

Установка узлов устройства в исходное состояние реализуется микрокомандой 1 алгоритма на фиг.7, в которой блок 24управления формирует коды 10 на выходах 39 и 37, единичные сигналы на выходах 31,42,36,69, которые инициируют пересылку кода корня дерева с,регистра 10 начального адреса через коммутаторы 3,6 на регистр 8 числа, установку в О ревё рсивного счетчика 13, прием кода признака опроса с входов 14 на регистр 15 признака опроса, установку в О триггера 70.

Цикл прохода зон начинается считыванием на выходной регистр 2 содержимого ячейки блока 1 памяти, адресуемой кодом с регистра 8 числа (блок 2 алгоритма на фиг.7). Указанны.е микрооперации реализуются выдачей блоком 24 управления кода 11 на выходах 39 и единичного сигнала на выходе34.

Дальнейшая последовательность следования микрокоманд зависит от сигналов, поступающих на входы 28-30 блока 24 управления. В частности, если имеется единичный сигнал совпадения на входе 30, что / соответствует совпадению ветви числа признака опроса и одной из ветвей графа, хранящегося в блоке 1 памяти, то анализируется значение текущего разряда признака опроса, выдаваемое на вход 28 блока 24 в прямом коде, если ищется ближайшее большее, и в инверсном, если ищется ближайшее меньшее. Ели сигнална входе 28 не равен нулю (что свидетельствует о невозможности ответвления в направлении,соответствующем критерию поиска), то анализируется сигнал на выходе 29 блока 24 управления; если указанный сигнал равен нулю, то ветвь признака опроса совпадаете

0 прямым продолжением ветви, хранящейся в блоке 1, а если единице,- то ветвь признака опроса совпадает с отходящим участком ветви и, следовательно, для продолжения поиска необходимо изменить адрес при обращении в последующей зоне. В первом случае выполняется блок 4 алгоритма, представленного на фиг.7, а во втором - блок 3. Соответственно в первом случае блоком 24 управления формирукэтся единичные сигналы на выходах 44,50, которые управляют увеличением на единицу содержимого счетчика 13 и сдвигом регистра 15. Во втором случае дополнительно к упомянутым ми1 рооперациям выдачей блоком 24 управления

5 кода 01 на выходах 37 и единичного сигнала на выходе 31 осуществляется загрузка регистра 8 числа кодом ссылк1/г с выходного регистра 2.

Если сигнал на входе 28 равен нулю, то

0 возможноответвление ветви, соответствующей числам, большим заданного признака опроса, В этом случае анализируется сигнал на входе 29 блока 24 управления. Если ука-. занный сигнал равен нулю, то зто соответствует тому, что от ветви с адресом, зафиксированным на регистре 9, совпадающей с ветвью признака Ьпроса,ответвляется ветвь, адрес которой зафиксирован на выходном регистре 2, соответствующая числам большим признаку поиска. Соответственно блоком 24 управления (блок 5 алгоритма на фиг.7) формируются единичные сигналы на выходах 35,44,50,68, которые инициируют передачу кода из поля

5 ссылок выходного регистра 2 через откры-тый нулевым сигналом с выходом 40 коммутатор 4 на регистр 11 промежуточного хранения, увеличение на единицу содержимого счетчика 13, сдвиг содержимого регистра 15 признака опроса, установку в 1 триггера 70, единичное состояние которого свидетельствует о фиксации начальной ветви подграфа чисел, больших заданного признака опроса. В последующем такте (блок :6 алгоритма на фиг.7) сигналом с выхода 33 блока 24 управления осуществляется фиксация содержимого счетчика 13 на фиксирующем регистре 12. Если сигнал на входе 29 i блока 24управления равен единице, то это соответствует тому, что ветвь с адресом, зафиксированным в поле ссылок вьгходного регистра 2, совпадающая с ветвью признака опроса, ответвляется от ветви, адрес которой з.афиксирован на регистре 8 и которая соответствует числам, большим заданного признака опроса. Соответственно блоком 24 управления (блок 7 алгоритма на фиг.7) формируются код 11 на выходах 39, код 01 на выходах 37, единичные сигналы на выходах 35,40,31,44,50,68. которые инициируют пересылку кода с регистра 8 через коммутаторыЗи4 на регистр 11 промежуточного хранения, пересылку кода с поля ссылок, выходного регистра 2 через коммутатор 6 на регистр 8 числа, увеличение на единицу содержимого счетчика 13, сдвиг содержимого регистра 15, установку в единичное состояние триггера 70. В последующем такте выполняется микрокоманда, соответствующая блоку б алго.ритма на фиг.7. Если в результате описанных микроопераций появится сигнал на входе 25 блока 24 управления, то процесс поиска закончен и адрес искомого слова может быть считан с выходов 9 устройства. В противном случае начинается обработка информации в последующей зоне блока 1 памяти. Если в результате считывания очередного фрагмента графа, осуществляемого блоком 2 алгоритма на фиг.7. окажется, что сигнал на входе 30 блока 24 управления равен нулю, то это соответствует тому, что ветвь, соответствующую признаку опроса, не совпадает далее ни с одной из ветвей графа, хранящегося в блоке 1 памяти, и необходимо переходить к поиску минимaльVoго элемента на подграфе чисел, больших заданного.. Если очередной разряд признака опроса равен нулю (соответственно и равен нулю сигнал на рыхрде 28 блока 24 управления), то подграф множества чисел ближайших больших заданного признака ;опроса порождается продолжением ветви, адрес которой зафиксирован на регистре 8 числа; Блок 24 управления формирует сигнал единичного уровня на своем выходе 52, которым все разряды регистра t5 устанавливаются в О (блок 8 алгоритма) и далее управление передается микроподпрограмме (блоки 11-13 алгоритма на фиг.7), которая реализует поиск минимального числа в подграфе, корень которого задан адресом в регистре 8 числа. Если значение текущего разряда признака опроса (а значит, и сигнал на входе 28 блока 2-4 управления) равен единице, то минимальное число следует искать по подграфу, порождающий корень которого зафиксирован на регистре 12 текущего адреса и регистре-11 промежуточного хранения. Для этого предварительно анализируется состояние триггера 70: если последний установлен в О, то среди записанных в блоке 1 памяти чисел нет больших заданного, соответственно блоком 24 управления выдается сигнал неуспешного поиска с выхода 58 устройства. В противном случае выполняется блок 10 алгоритма на фиг.7, в котором блок 24 управления выдает единичные сигналы на своих выходах 46, 31, 52, код 01 навыходах39 и код 11 на выходах 37, которые инициируют прием крда с регистра 12 текущего адреса на реверсивный счетчик 13, пересылку кода с регистра 11 промежутоного хранения через коммутаторы 3,6 на регист э .8 числа, установку в О всех разрядов регистра 15. Процесс поиска минимума, реализуемый подпрограммой, задаваемой блоками 11-14 алгоритма на фиг.7, аналогичен описанной процедуре поиска экстремума за тем исключением, что при переходе к следующей зоне в блоке 1 памяти сдвиг содержимого регистра 15 не производится. По счетчиком 13 сигнала переполнения на вход 25 блока 24 управления искомый адребфиксируется на регистре 8 и выдается посредством выходов 9, блок 24 формирует единичный сигнал конца операции на выходе 57. При считывании слова по его адресу код соответствующей команды подается на входы 55, код адреса подается на входы 7 устройства. Алгоритм выполнения команды счить1вания слова по адресу представлен на фиг.8., Первая микрокоманда (блок 1 алгоритма на фиг.8) устанавливает исходное состояниеустройства. Соответственно блоком 24 управления формируется код 00 на выходах 37 и единичные сигналы на выходах 31,43, под управлением которых код адреса с входов 7. поступая через входной коммутатор 6, фиксируется на регистре 8 числа, все разряды счетчика 13 устанавливаются в . Таким образом, восстановление слова по его адресу начинается с последней зоны блока 1 памяти.

Цикл поиска в зоне начинается считыванием слова, адресуемого кодом на регистре 8 из блока 1 памяти на выходной регистр 2 (блок 2 алгоритма на фиг.8), что обеспечивается выдачей блоком 24 управления кода 11 на выходах 39 и единичного сигнала на выходе 34. Если маркерный бит / считанного на регистр 2 слова (сигнал на входе 26 блока 24) равен единице, то производится сдвиг содержимого регистра 15с заполнением освободившегося разряда маркерным битом а слова .считанного на регистр 2, при этом сигнал с младшего разряда регистра 2 поступает через элемент 20 неравнозначности, на другой вход 53 которого подается нулевой сигнал, и мультиплексор 18. Содержимое счетчика 13 уменьшается на единицу. Все эти микрооперации, объединенные в блок 3 алгоритма на фиг,8, реализуются под Действием кодов 00 на выходах 41, единичных,сигналов с выходов 50,45, формируемых блоком 24 управления. При отсутствии сигнала переполнения счетчика 13 вновь повторяется микрооперация считывания (блок 2 алгоритма на фиг.8).

Если маркерный бит /3 считанного слова окажется равным нулю, то выполняется блок 4 алгоритма. Указанная ситуация соответствует вхождению считываемой ветви в обобщающую. В этом случае адрес последней указан в поле ссылки кода, содержащегося на выходном регистре 2, и подлежит пересылке в регистр 8 числа. Блок 24 управления формирует код 01 на выходах 37, код 00 на выходах 39, единичные сигналы на выходах 34,31, которые инициируют пересылку кода с выходного регистра 2 через входной коммутатор 6 на регистр 8 и одновременное считывание из блока 1 памяти слова, адресуемое кодом, поступающим с выходного регистра 2, через адресный коммутатор 3 на адресные входы блока 1 памяти. Анализируется маркерный бит усчитанного слова, поступающий по входу .27: если у 0. то по заданному адресу нет записанного слова и блок 24 управления выдает единичный сигнал на выход.58, свидетельствующий о том, что поиск неуспешно завершился. В противном случае выполняется блок 5 алгоритма на фиг.8, в котором блок 24 управления выдает код 00 на выходах 41, единичные сигналы на выходах 50,45,53, которые обеспечивают уменьшение на единицу содержимого счетчика 13, сдвиг регистра 15с заполнением освобождающегося разряда инверсией бита а , хранящегося на регистре 2. причем инвертирование сигнала, поступающего с младшегр разряда регистра 2. осуществляется элементом 20 неравнозначности.

Если счетчик 13 выдает сигнал переполнения на вход 25блока 24 управления, последний сформирует единичный сигнал на выходе 57 устройства, а код искомого слова может быть считан с выходов 16 устройства. Формула изобретения Ассоциативное оперативное запоминающее устройство, содержащее блок памяти, регистр числа, входной коммутатор, элемент ИЛИ, элемент НЕ, элемент И, блок управления, входы группы которого являются входами кода команды устройства, а первый и второй входы являются входрм тактовых импульсов и входом начальной установки устройства, информационные входы первой группы входного коммутатора являются адресными входами устройства, ,выходы входного коммутатора соединены с информационными входами регистра числа, выходы которого являются информационн,ыми выходами первой группы устройства, третий вход блока управления подключен к выходу элемента ИЛИ, первый, второй и третий выходы блока управления соединены соответственно с синхровходом регистра числа, с входами управления считыванием и защиты блока памяти, первая группа выходор блока управления подключена к управляющим входам входного коммутатора, пятый и шестой выходы блока управления являются выходами положительного и отрицательного результатов поиска, отличающееся тем, что, с целью уменьшения информационной избыточности и упрощения устройства, в него введены реверсивный счетчик, регистр текущего адреса, регистр начального адреса, выходной регистр, регистр промежуточного хранения, регистр признака опроса, адресный коммутатор, крммутатор записи, промежуточный коммутатор, мультиплексор, причем информационные выходы блока памяти подключены к входам (г+3)-разрядного выходного регистра (г logam, ш - количество слов, хранящихся в устройстве), выходы старших разрядов которого соединены с информационными входами первой группы коммутатора записи, промежуточного коммутатора и адресного коммутатора, а также с информационными входами второй группы входного коммутатора, информационные входы второй группы адресного коммутатора и коммутатора записи подключены к выходам регистра промежуточного хранения, информационные входы которого соединены с выходами промежуточного коммутатора, информационные входы второй группы которого подключены к информациоиным входам третьей группы входного коммутатора, к информационным входам регистра начального адреса, к выходам адресного коммутатора и к младшим адресным входам блока памяти, старшие адресные входы которого соединены с ин формационными входами регистра текуще го адреса и с информационными выходами реверсивного счетчика, установочные входы которого подключены к выходам реГиСт-ра текущего адреса, информационные входы третьей группы адресного коммутатора соединены с выходами регистра начального адреса, информационные входы четвертой группы адресного коммутатора подключены к выходам, регистра числа и к информационным входам третьей группы коммутатора записи, выходы которого соединены со старшими информационными входами блока памяти, информационные входы и выходы младших разрядов регистра признака опроса являются соответственно информационными входами и информационными выходами второй группы устройства, выход старшего разряда регистра признака опроса соединен с первым входом первого элемента неравнозначности, второй вход которого является входом задания направления поиска устройства, а выход которого чподключен к первому входу второго элемента неравнозначности, второй входкоторого соединен с первым входом третьего элемента неравнозначности и с (г+1)-м выходом вь1ходного регистра, (г+2)-й выход которого подключен к четвертому входу блрка управления, пятый вход которого соединен с ()-м выходом выходного регистра и с Первым входом элемента И, выход которого подключен к шестому входу блока управления и к первому входу элемента ИЛИ,

второй вход.которого соединен с выходом элемента НЕ, вход которого подключен к выходу второго элемента неравнозначности и к второму входу элемента И, первый, второй и третий информационные входы мультиплексора соединены соответственно с выходами третьего и первого элементов неравнозначности и с четвертым выходом блока управления, пятый выход которого подключен к второму входу третьего элемента неравнозначности, . выход мультиплексора соединен )с входом записи при сдвиге регистра признака опроса, синхровходы |регистра начального адреса регистра, текущего адреса выходного, регистра, регистра промежуточного хранения и регистра признака опроса подключены соответственно к шестому, седьмому, второму. восьмо иу и девятому выходам блока управления, группы выходов с второй по пятую которого соединены соответственно с управляющими входами коммутатора записи, адресного коммутатора, промежуточного коммутатора и мультиплексора, входы установки нуля, единицы, инкрементирования, декрементирования и управления реверсивного счетчика подключены к выходам блока управления с десятого по четырнадцатый, вывод переполнения реверсивного счетчика подключен к седьмому входу блока управления, восьмой вход которого соединен с вь1ходом первого элемента неравнозначности, пятнадцатый и шестнадцатый выходы блока управления, а также выход мультиплексора подклк)чены к соответствующим информационным входам младших разрядов блока памяти, входы Сдвига, установки в О и 1 регистра признака опроса соединены соответственное семнадцатым, восемнадцатым и девятнадцатым выходами блока управления.

Продолжение таблицы

Изобретение относится к вычислительной технике, в частности к запог^нающим устройствам, и может быть использовано в цифровых системах параллельной обработки информации. Цель изобретения -уменьшение информационной избыточности и упрощение устройства. Устройство содер^ жйт блок пймяти, выходной регистр, адрес-^ ный комм'утатор» промежуточный коммутатор, коммутатор записи, входной коммутатор, регистр числа, регистр началь-.ного адреса, регистр промежуточного хранения, регистр текущего адреса, реверсивный счетчик, регистр признака опроса, первый злемент неравнозначности, мультиплексор, второй и третий элементы нерав- нозначности, элемент И, элемент ИЛИ, инвертор, блок управления. Цель изобретения достигается тем. что информация в блоке памяти хранится в виде п-ярусного графа (п-разрядн^сть), причем каждая вершина I- яруса (I = ITiT) соответствует подмножеству записанных слов, совпадающих в i старших разрядах. Соответственно весь обьем блока памяти разделен по числу ярусов на п зон. каждая из которых содержит m ячебк разрядностью (Iog2m + 3). Три младщих разряда каждой ячейки содержат маркерные биты Д.у.а, указывающие соответственно на соответствие ячейки вершине гра^а (/9=1), на наличие ветвления в вершине графа (у = ~1), на значение i-ro бита пoдм)^oжecтвa слов, соответствующих ячейке в

Фиг.1

С конец 3

Фиг.5

(начало У

р

шп-т

Ш

Фиед

(ачаАсГ

r-l-JL

U(39) Ю U(37) fO

и(зт.зб.б9М

7

U(33)J1

ВДН-50

иШ}-01 68)r

и If о 77 f6.

б-.Л« U(33l-7

Г

lumsojn J

W(iff,50)J

U(37)OJ

±

em

UI57)1

( Конец

10 Ш9}-ОГ

wblM52)J

JT-i

U(39) 7;

d/a7

СНаяйАО

(37)OQ

U(31M)-1

1

-2

( U(3f)1

Нет

( Конец

Фиг.8

I I --1--I--I-.-4-i

-4--4

I I

I I

I I t I

ojr т

I I I I

Фиг.9