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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 14682 А 1 51)5 6 11 С 15/О САНИЕ ИЗОБРЕТЕНИЯ ТО щ ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР О У 1 У СВИДЕТЕЛЬСТВУ(71) Киевский политехнический институт им.50-летия Великой Октябрьской социалистической революции(56) Авторское свидетельство СССР М 1324071, кл. 0 11 С 15/00, 1987.Авторское свидетельство СССР М 1363307, кл. 6 11 С 15/00, 1987.(54) АССОЦИАТИВНОЕ ОПЕРАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО(57) Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано в цифровых системах параллельной обработки информации. Цель изобретения - уменьшение информационной избыточности.и упрощение устройства, Устройство содержит блок памяти, выходной регистр, адресный коммутатор, промежуточный коммутатор, коммутатор записи, входной коммутатор, регистр числа,.регистр начальИзобретение относится к вычислительной технике, в частности к запоминающим устройствам, и можетбыть использовано в цифровых системах параллельной обработ-. ки информации.Целью изобретения является уменьшение информационной избыточности и упроение устройства.На фиг.1 представлена структурная схема ассоциативного оперативного запоминающего .устройства; на фиг.2 - пример: реализации блока управления; на фиг.3-8- алгоритмы выполнения соответствеййо опеного адреса, регистр промежуточного хранения, регистр текущего адреса, реверсивный счетчик, регистр признака опроса, первый элемент неравнозначности, мультиплексор, второй и третий элементы неравнозначности, элемент И, элемент ИЛИ, инвертор, блок управления. Цель изобретения достигается тем, что информация:в блоке памяти хранится в виде и-ярусного графа (п-разрядность), причем каждая вершина - яруса ( = 1,п) соответствует подмножеству записанных слов, совпадающих встарших разрядах. Соответственно весь объем блока памяти разделен по числу ярусов на и зон, каждая из которых содержит а ячеек разрядностью(о 92 т+ 3). Три младших разряда каждой ячейки содержат маркерные биты Р, у, а, указывающие соответственно на соответствие ячейки вершине графа ( Р = 1), на наличие ветвления в вершине графа (у=1), на значение -го бита подмножества слов, соответствующих ячейке в (+1) зоне, ад- Я рес которой совпадает с адресом в зонеячейки, порождающей ветвление. 9 ил., 1 табл. раций записи, исключения слова, поиска по совпадению; поиска экстремума, поиска ближайшего к заданному, считывания слова по его адресу; на фиг.9 - граф совокупности чисел, хранимых в устройстве, соответствующих примеру, иллюстрирующему работу устройства.Ассоциативное оперативное запоминающее устройство (фиг,1) содержит блок 1 памяти, выходы которого подключены к входам (г+3)-разрядного выходного регистра 2(г- оцге, в - емкость в словах ассоциативно- го оперативного запоминающего. устройстЦикл поиска в зоне начинается считыванием слова, адресуемого кодом на регистре 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). Если маркерный бит Р считанного слова окажется равным нулю, то выполняется блок 4 алгоритма. Указанная ситуация соответствует вхождению считываемой ветви в обобщающую, В этом случае адрес последней указан в поле ссылки кода, содержащегося на выходном регистре 2, и подлежит пересылке в регистр 8 числа. Блок 24 управления формирует код 01 на выходах 37, код 00 на выходах 39, единичные сигналы на выходах 34,31, которые инициируют пересылку кода с выходного регистра 2 через входной коммутатор.6 на регистр 8 и одновремеНное считывание из блока 1 памяти слова, адресуемое кодом, поступающим с выходного регистра 2, через адресный коммутатор 3 на адресные входы блока 1 памяти,Анализируется маркерный бит у считанного слова, поступающий по входу ,27: если у = О, то по заданному адресу нет записанного слова и блок 24 управления выдает единичный сигнал на выход 58, свидетельствующий о том, что поиск неуспешно завершился, В противном случае выполняется блок 5 алгоритма на фиг,8, в котором блок 24 управления выдает код 00на выходах 41, единичные сигналы на выходах 50, 45, 53, которые обеспечивают уменьшение на единицу содержимого счетчика 13, сдвиг регистра 15 с заполнением освобождающегося разряда инверсией бита а, хранящегося на регистре 2, причем инвертирование сигнала. поступающего с млад шего разряда регистра 2, осуществляетсяэлементом 20 неравнозначности.Если счетчик 13 выдает сигнал переполнения на вход 25 блока 24 управления, последний сформирует единичный сигнал на выходе 57 устройства, а код искомого слова может быть считан с выходов 16 устройства,Формула изобретения Ассоциативное оперативное запомина 10 ющее устройство, содержащее блок памяти,25 выходу элемента ИЛИ, первый, второй и третий выходы блока управления соединены соответственно с синхровходом регистра числа, с входами управления считыванием и защиты блока памяти, первая группа выходов блока управления под 30 ключена к управляющим входам входного коммутатора, пятый и шестой выходы блока управления являются выходами положительного и отрицательного результатов по 35 иска, о т л и ч а ю щ е е с я тем, что, с целью уменьшения информационной избыточности и упрощения устройства, в него введены реверсивный счетчик, регистр текущего адреса, регистр начального адреса, выход 40 ной регистр, регистр промежуточного хранения, регистр признака опроса, адресный коммутатор, коммутатор записи, промежуточный коммутатор, мультиплексор, причем информационные выходы блока памяти 45 подключены к входам (г+3)-разрядного выходного регистра (г = 1 одге, т - количество слов, хранящихся в устройстве), выходы старших разрядов которого соединены с информационными входами первой группы коммутатора записи, промежуточного коммутатора и адресного коммутатора, а также с информационными входами второй группы входного коммутатора, информационные входы второй группы адресного 50 55 коммутатора. и коммутатора записи подключены к выходам регистра промежуточного хранения, информационные входы которого соединены с выходами промежуточного коммутатора, информационные входы второй группы которого подключены к инфоррегистр числа, входной коммутатор, элемент ИЛИ, элемент НЕ, элемент И, блок управления, входы группы которого являются входами кода команды устройства, а пер вый и второй входы являются входомтактовых импульсов и входом начальной установки устройства, информационные входы первой группы входного коммутатора являются адресными входами устройства, 20 выходы входного коммутатора соединены синформационными входами регистра числа, выходы которого являются информационными выходами первой группы устройства, третий вход блока управления подключен кмационным входам третьей группы входного коммутатора, к информационным входам регистра начального адреса, к выходам ад- . ресного коммутатора и к младшим адресным входам блока памяти, старшие 5 адресные входы которого соединены с информационными входами регистра текуще го адреса и с информационными выходами реверсивного счетчика, установочные входы которого подключенык выходам регист ра текущего адреса, информационные входы третьей группы адресного коммутатора соединены с выходами регистра начального адреса, информационные входы четвертой группы адресного коммутатора 15 подключены к выходам, регистра числа и к информационным входам третьей группы .коммутатора записи, выходы которого сое-: динены со старшими информационными входами блока памяти, информационные 20 входы и выходы младших разрядов регистра признака опроса являются соответственно информационными входами и информационными выходами второй группы устройства,.выход старшего разряда регистра 25 признака опроса соединен с первым входом первого элемента неравноэначности, второй вход которого является входом задания направления поиска устройства, а выход которого.подключен к первому входу второго 30 элемента неравноэначности, второй вход. .которого соединен с первым входом третьего элемента неравноэначности и с (г+1)-м выходом выходного регистра, (г+2)-й выход которого подключен к четвертому входу бло . ка управления, пятый вход которого соединенс (г+З-м выходом выходного регистра и с первым входом элемента И. выход которо- . : го подключен к шестому входу блока управления и к первому входу элемента ИЛИ; 40 второй вход, которого соединен с выходом элемента НЕ, вход которого подключен к выходу второго элемента неравнозначности и к второму входу элемента И, первый, второй и третий информационные входы мультиплексора соединены соответственно с выходами третьего и первого элементов не- равнозначности и с четвертым выходом блока управления, пятый выход которого ., подключен к второму входу третьего элемента неравнозначности выход мульти.плексора соединенс входом записи при сдвиге регистра признака опроса, синхровходы регистра начального адреса регистра, текущего адреса выходного. регистра, регистра промежуточного хранения. и регистра признака опроса подключены соответственно к шестому, седьмому, второму, восьмсцчу и девятому выходам блока управления, группы выходов с второй по пятую которого соединены соответственно с управляющими входами коммутатора записи, адресного коммутатора, промежуточного коммутатора и мультиплексора, входы .установки нуля, единицы, инкрементирования,декрементирования и управления реверсивного счетчика подключены к выходам блока управления с десятого по четырнадцатый, вывод переполнения реверсивного счетчика подключен к седьмому входу блока управления; восьмой вход которого соединен с выходом первого элемента неравнозначности, пятнад- . цатый и шестнадцатый выходы блока управления, а также выход мультиплексора подключены к соответствующим информационным входам младших разрядов блока памяти, входы сдвига, установки в "0" и "1" регистра признака опроса соединены соот-. ветственно с семнадцатым, восемнадцатым и девятнадцатым выходами блока управления,1714682 оц +Составитель О.ИсаеТех е М,Мо гента едактор С.Пекарь р д р л Корректор М.Пож акаэ.698 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб 4/5роизводственно-издательский комбинат Патент", г. Ужгород. ул. Гагарина, 1поиска, выходами блока 24 управления яв. ляются выход 57 "Положительный результат операции" и выход 58 "Отрицательный результат операции",Блок 24 управления может быть выполнен в виде микропрограммного устройств управления (фиг.2) и содержит блок 59.постоянной памяти начальных адресов микропрограмм, блок 60 элементов ИЛИ, счетчик ва), три младших разряда которого являются маркерными, а г старших - информационными, адресный коммутатор 3, промежуточный коммутатор 4, коммутатор 5 записи; входной коммутатор 6, адресные входы 7 устройства, регистр 8 числа, информационные выходы первой группы 9 устройства, регистр 46 начального адреса, регистр 11 промежуточного хранения, М-разрядный регистр 12 текущего адреса (М й 1 о 92 п, и - разрядность слов, хранимых в ассоциативном запоминающем устройстве), реверсивный счетчик 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; 41 - мультиплексора 18, вход 42 установки "0" и вход 43 установки в "1" всех разрядов реверсивного счетчика 13, суммирующий счетный вход 44, вычитающий счетный вход 45; вход 46 управления реверсивного счетчика 13, вход 47 управления записью блока 1 памяти, второй 48 и третий 49 младшие разряды информационных входов блока 1 памяти, вход 50 управления сдвигом, вход 51 установки в "1" и вход 52 установки в "0" всех разрядов регистра 15 признака опроса, второй вход 53 третьего элемента 20 неравнойначности, третий вход 54 мультиплексора 18. Внешними входами блока 24 управления являются входы 55 задания кода команды, внешний вход 56 задания направления 10 61 адреса микрокоманд, мультиплексор 62(+1)-й зоне, адрес которой совладает с адресом в зоне 1 ячейки, .порождающей ветвление. При этом в ячейке 1-й зоны, адрес условий ветвления микропрограмм, элемент И 63, элемент ИЛИ 64, вход 65 тактовых импульсов, блок 66 постоянной памяти микропрограмм, регистр 67 микропрог рамм, выходы 31-54, 57 и 58 являются выходами блока 24 управления, а выходы 68 и 69 подключены соответственно к входам установки в "1" и "0" триггера 70, выход 71 которого является, как и входы 25-30 блока 20 24 управления, входом мультиплексора.62,вход 72 является входом начальной установки.Информация в блоке 2 памяти в видеп-ярусного графа (и - разрядность), причем 25 каждая вершина 1-го яруса ( - 1,о) соответствует подмножеству хранящихся слов, совпадающих между собой в 1 старших разрядах, Соответственно число вершин на 1-м уровне графа равно количеству слов, от личающихся в 1 старших разрядах. Каждаяиз вершин содержит информацию о ветвлении на 1-м ярусе, Вершины нижнего и-го уровня соответствуют словам. хранящимся в блоке 1 памяти.35 Соответственно объем блока 1 памятиразбит по числу ярусов графа на и эон, адресуемых кодом с выходом счетчика 13.Каждая из зон содержит т ячеек разрядностью (1 о 92 а + 3). В пределах зоны ячейки 40 адресуются кодом с выходом адресногокоммутатора 3. Три младших разряда каждой ячейки содержат маркерные биты соответственно а,ф,у, а остальные разряды указывают на адрес ветвления. Единичное 45 значение битаф указывает на соответствиеячейки вершине графа. Единичное значение бита у указывает на наличие ветвления в вершине, соответствующей данной ячейке.В случае наличия ветвления ячейке в 1:зоне 50 сответствуют две ячейки в (1+1)й зоне, причем адрес в зоне одной из них совпадает с адресом в зоне рассматриваемой ячейки из 1-й зоны. а адрес другой указывается в информационных разрядах ячейки из 1-й зоны.55 Бита соответствует значению 1-го бита под-.множества слов, соответствующих ячейке вкоторой указывается порождающей ветвление ячейки, указывае ся адрес последней. бит.а равен нулю,Если вершине. соответствует нескЬлькослов с различными адресами, то адрес соответствующей этой вершине ячейки определяется адресом слова, записанного раньшепо времени, Организация хранения информации в блоке 1 памяти может быть иллюстрирована следующим примером,Пусть в блок 1 памяти последовательно 10записываются 8-разрядные слова по соответствующим адресам: 2,3,1,0 (и = 8, гп = 4)10101100 -201111111. -310111101 -1 1510101101 -0Соответствующий граф представлен нафиг.9.Информация в АЗУ разместится согласно таблице. 20Устройство работает следующим образом.В устройстве реализуются следующиекоманды, код которых поступает на входы55: "Запись информации по адресу"; "Считывание информации по адресу"; "Исключение информации по адресу"; "Поиск адресаячейки, содержимое которой совпадает сзаданным признаком опроса"; "Поиск адреса ячейки, содержащей экстремальный (минимальный или максимальный) код"; "Поискадреса, содержащего код, являющийся ближайшим (большим или меньший) к заданному признаку опроса".При записи слова в блоке 1 памяти кода 35команда "Запись информации по адресу"подается на входы 55, одновременно адресподается на адресные входы 7 устройства,а само слово - на информационные входы14 устройства. Алгоритм выполнения команды записи представлен на фиг,З. В частности, блок 24 управления с получениемкоманды записи по входам 55 формируетединичные сигналы на своих выходах 31, 36и 42, а на выходах 37 - код 00, который 45управляет работой коммутатора б таким образом, что адресные входы 7 оказываютсяскоммутированными на входы регистра 8числа (соответственно, под действием сигнала с выхода 31 код адреса фиксируется на 50регистре 8 числа), Одновременно, под управлением сигнала на выходе 36 на регистре 15.фиксируется код слова, подлежащегозаписи, по сигналу на выходе 42 счетчик 13устанавливается в "0", 55В следующем такте (блок 2 на фиг.3)блоком 24 управления формируется код 10на выходах 39 и единичные сигналы на выходах 34,40,35, по которым соответственно коммутируется код, хранящийся на регистре 10 начального адреса, коммутатором 3 на адресные входы младших разрядов блока 1 памяти, производится считывание соответствующей ячейки блока 1 памяти на выходной регистр 2, коммутация через коммутатор 4 и прием на регистр 11 промежуточного хранения кода с регистра 10 начального адреса. В содержательном. плане приведенные микрооперации соответствуют опросу ячейки, соответствующей "корню" графа. адрес которой хранится на регистре 10 начального адреса (в приведен- . ном примере - ячейка с адресом 10 в зоне 000), Если значение бита р в считанном слове равно нулю(сигнал на входе 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 управления равен логической единице, то это значит, что записываемое слово совпадает в текущем разряде со словом, на адрес которого указывает ссылка ветвления. В этом случае в последующей зоне необходимо анализировать содержимое ячейки с адресом, указанным в поле ссылки ячейки, считанной в текущей зоне. Для этого в последующем такте (блок 5 алгоритма на фиг.3) блок управления формирует единичные сигналы на выходах 35,44,60, по которым соответственно содержимое поле ссылки выходного регистра 2 через коммутатор 4 (сигнал на управляющем входе 40 которого равен нулю) записывается на ре-.гистр 11 промежуточного. хранения, содержимое реверсивного счетчика 13 увеличивается на единицу и содержимое регистра 15 признака опроса сдвигается на один разряд, При отсутствии сигнала переполнения на входе 25 производится считывание содержимого ячейки в следующей зоне (фиг,З, блок 9), которое обеспечивается выдачей блоком 24 кода 01 на выходе 39 и единичного сигнала на выходе 34. Цикл анализа повторяется.В елучае, если при опросе ячейки блока1 памяти на входе 30 блока 24 управления будет сформирован сигнал нулевого уровня (что соответствует отсутствию ранее записанных слов, совпадающих в предшествующем и текущем разряде с записываемым), то необходимо выставить маркерный бит.у перехода в единицу, в поле ссылки указать адрес записываемого слова применительно к считанной в текущей зоне ячейки и запиеэть в ячейку по адресу вводимого слова код адреса ячейки, которая содержит ссылку, Для этого блок 24 управления (блок 6 алгоритма на фиг.З) формирует код 01 на выходах 39, код 10 на выходах 38, код 00 на выходах 41, единичные сигналы на выходах 47-49., которые инициируют запись в ячейку, адрес которой содержится в регистре 11 промежуточного хранения (т.е, в ячейку, содержимое которой считывалось в предшествующем такте. считывания) маркерного бита , с 8.этой же ячейки без изменения (через элемент 20 неравнозначности, на второй вход 53 которого подается нуль, и мультиплексор 18), единицы в маркерный бит ф(с выхода 48). единицы в маркерный бит у (с выхода 49), адреса, содержащегося на регистре 8 числа (через коммутатор 5 записи),В следующем такте(блок 7 алгоритма нафиг.З) блоком 24 управления формируется35404550 ся, По окончании процесса записи блок 24 управления выдает сигнал на выходе 57 устройства,. При исключении слова из блока 1 памяти код команды "Исключение информациипо адресу " подается на входы 55,. одновременно адрес подается на адресные входы 7 устройства. Алгоритм: выполнениякоманды исключения представлен на фиг.4 Блок 24 управления в первом такте (блок 1алгоритма на фиг.4) формирует код 00 навыходах 37,единичные сигналы на выходах 31,43,69, которые обеспечивают запись адреса исключаемого слова с входов 7 на регистр 8 числа; установку всех разрядов реверсивного счетчика 13 в единицу, установку триггера 70 в "0".В следующем такте производится считывание содержимого ячейки с адресом исключаемого слова на выходной регистр 2. Этообеспечивается выдачей блоком 24 управле.ния (блок 2.алгоритма на фиг.4) кода 11 на выходах 39 и единичного сигнала на выходе 34.Если бит ф равен единице, то анализируется состояние триггера 70, индицируекод 11 на выходах 39, код 01 на выходах 38, единичные сигналы на выходах 47,44,50, ко-.торые обеспечивают запись в блок 1 памяти. по адресу, содержащемуся в регистре 8 чис ла, нуля в маркерные биты Р, у (с выходом48,49), адреса, содержащегося на регистре 11 промежуточного хранения через коммутатор 5 записи, а также увеличение на единицу содержимого реверсивного счетчика 13 и 10 сдвига содержимого регистра 15 признакаопроса.Если при увеличении содержимого реверсивного счетчика 13 возникает сигнал переполнения, который поступает навход 15 25 блока 24 управления, то операция записизаканчивается. В противном случае в следующей зоне записывается по адресу вводимого слова бит р присутствия и текущий разряд признака опроса в бит а. Для этого 20 блок 24 управления формирует коД 11 навыходах 39, код 01 на выходах 41 и единичные сигналы на выходах 47,48,44,50; которые обесйечивают запись по адресу из регистра 8 числа единицы в маркерный битф 25 (с выхода 48) и бита текущего разряда записываемого слова в регистре.16 в маркерный бит а(через элемент 17 неравнозначности, на второй выход 56 которого подается нулевой сигнал, и мультиплексор 18), произво- ЗО дится также увеличение содержимогосчетчика 13 и сдвиг. регистра 15. При отсутствии сигнала переполнения счетчика 13, подаваемого на вход 25, указанные действия (блок 8 алгоритма на фиг.З) повторяютмое сигналом на входе 71 блока 24 управления. Если триггер 70 установлен в "0", то анализируется бит у считанного из блока 1 памяти слова (вход 27). Если бит у равеннулю, то считанное слово не содержит ссы- лок и,.следовательно, исключение слова в текущей зоне состоит в установке маркер- ного бита Р в "0". Далее блок 24 управления формирует код 11 на выходах 39, единичные сигналы на выходах 47,45 (блок 3 алгоритма на фиг,4), которые обепечивают запись нуля (с выхода 48) в маркерный бит Р ячейки, адрес которой определяется содержимым регистра 8 числа. Одновременно содержимое реверсивного счетчика 13 уменьшается на единицу, Опять повторяется цикл считывания, если нет сигнала на входе 25.Если исключаемая ячейка в текущей зоне содержит ссылку, а триггер 70 установлен в "0", то указанная ситуация соответствует тому, что от исключаемой ветви графа, хранящегося в блоке 1 памяти; отходит неисключаемая ветвь. Признаком наличия такой ветви, отходящей от исключаемой, является единичное состояние триггера 70. Поэтому при обнаружении ветвления в исключаемой ветви триггер 70 необходимо установить в "1 ф и продублировать.исключаемую ветвь по адресу отходящей. Для этого адрес отходящей ветви графа следует за.фиксировать на регистре 11 промежуточного хранения. Блок 24 управления формирует (блок 4 алгоритма на фиг.4) код 00 на выходах 39, код 00 на выходах 41 и единичные сигналы на выходах 35,47,48,68,53, которые инициируют передачу кода из выходного регистра 2 через открытый нулевым сигналом с выхода 40 блока 24 коммутатор 4 на регистре 11 промежуточного хранения и запись в ячейку с адресом, определяемым кодом ссылки на выходном регистре 3 единичного маркерного бита Р (с выхода 48) и бита а, формируемого как инверсия аналогичного бита исключаемого слова,(указанная инверсия осуществляется элементом 20 неравнозначности, на вход 53 которого подается единичный сигнал), поскольку текущий бит слова, ветвь которого отходит от исключаемого, не совпадает с текущим битом исключаемого слова. Далее выполняется описанный такт установки в "0" маркера присутствия исключаемого слова(блок 3 алгоритма на фиг,4),Если и рй анализе ячейки, соответствующей в текущей зоне исключаемому слову, триггер 70 установлен в "0", то анализируется бит у считанного слова, которыми указы. вает на наличие ветвления на более высоких50 55 если все разряды счетчика 13 не обнулены.Если при анализе считанной в текущей зоне ячейки, соответствующей исключаемому алову ячейки, обнаружится, что маркерный бит Р присутствия равен нулю, то зто означает, что исключаемая ветвь графа на текущем уровне ответвляется от другой, адрес которой зафиксирован в поле ссылки, .считанной с ячейки. Очевидно, что если не было ответвлений от исключаемой ветви, то уровнях графа, Так, если бит у равен единице (имеется сигнал единичного уровня на выходе 27 блока 24 управления), то необходимо переписать по адресу, хранящемуся в 5 регистре 11 промежуточного хранения, содержимое исключаемой ячейки, а в поле ссылки ячейки, на которую имеется ссылка в исключаемой ячейке, записать адрес, хранящийся на регистре 11 промежуточного.10 хранения. Указанные микрооперации выполняются в два такта. В первом такте (блок 5 алгоритма на фиг,4) блок 24 управления формирует код 01 на выходах 39, код 10 на выходах 38, код 00 на выходах 41, единич ные сигналы на выходах 47-49, которымиобеспечивается запись маркерного разряда а из регистра 2 (через элемент 20 неравнозначности, на второй вход 53 которого подается нулевой сигнал, и мультиплексор 18) в 20 поле маркера й , запись единиц в полеостальных маркерных разрядов, запись кода с регистра 2 в поле ссылки ячейки, адрес которой определяется кодом, хранящимся на регистре 11, Во втором такте (блок 6 25 алгоритма на фиг,4) блок 24 управления формирует код 00 на выходах 39, код 01 на выходах 38, единичные сигналы на выходе47, которые обеспечивают запись в ячейкупо адресу, определяемому кодом, храня щимся на регистре 2 маркерного бита Р,равного нулю, кода с регистра 11 промежуточного хранения. После указанных корректировок при ненулевом коде на счетчике 13 осуществляется переход к описанному так ту установки в "0" маркера присутствия исключаемого слова (блок 3 алгоритма на фиг.4). Если исключаемое слово на текущемуровне графа не содержит ветвлений (Ч (27)== 0), то содержимое исключаемой ячейки 40 переписывается, по адресу,. зафиксированному в регистре 11.промежуточного хранения. Соответственно, блок 24 управления формирует код 01 на выходах 39, код 10 на выходах 38, код 00 на выходах 11 и единичныесигналы на выходах 47,48 (блок 7 алгоритма на фиг.4), которые обеспечивают выполнение указанной записи. Дальше следует такт установки в "0" маркера присутствия исключаемого слова (блок 3 алгоритма на фиг,4),необходимо установить в "0" маркерный Процесс исключения может иллюстрибитветвления в слове, содержащем ссылку роваться следующим примером.ветвления нэ исключаемую ветвь. Указан- Пусть в условиях предыдущего примера ная микрооперация обеспечивается выда- из блока 1 памяти исключается слово, запичей блоком 24 управления кода 00 на 5 санное по адресу 10. В первом цикле на выходах 39, кода 00 на выходах 41 и единич- счетчике 13 устанавливается код 111, на реных сигналов на выходах 47,48,53 (блок 8 гистре 8 числа-код 10, Маркерныеразряды алгоритма на фиг,4). соответствующего слова равны а = 1, Р = 1,.В случае наличия ответвлений в исклю-- 1, Следовательно, выполняется блск 4 чаемой ветви (триггер 70 установлен в "1") 10 алгоритма, представленного на фиг,4;тригосуществлетсязаписьвполессылкиячейки, гер 70 устанавливается в "1", в ячейку.00 указывающей на исключаемую ветвь, адре- зоны 111 записывается код а=О В = 1,у са ветви,ответвляющейся от исключаемой,а =1, блоком 3 алгоритма бит Р в ячейке 10 также запись адреса ячейки, содержащей устанавливается в "0", в регистр 11 записыссылку на исключаемую ветвь в поле сылки 15 вается код 00, Содержимое счетчика 13 стаячейки, соответствующей ветви, отходящей новится равным 110. Так как в ячейке с от исключаемой. Указанные действия осу- адресом 10 в этой зоне, как и в последующествляются в два такта, В первом такте щихзонах 101,100; ф=1,у =О,то выполняблоком 24 управления (блок 9 алгоритма на ются блоки 7 и 3 алгоритма на фиг.4, которые фиг,4) выдается код 00 на выходах 39, код 00 20 реализуют запись в ячейку 00 маркеров а= на выходах 41, код 01 на выходах 38 иеди- = 0 (для зоны 110) или а = 1 (для зон ничные сигналы на выходах 47 - 49,53, кото,100),р =О,у =О. В зоне 011 маркерные рые инициируют запись в ячейку, биты в ячейке 10 имеютзначение а =О, Р= определяемую адресом, хранящимся в поле = 1, у = 1, Следовательно, выполняются ссылки выходного регистра 2, следующей 25 блоки 5,6,3 алгоритма на фиг.4. Блоком 5 в информации; в поле ссылок - код с выходов ячейку 00 заносится код 01101, блоком 6 в регистра 11 промежуточного хранения, в по- ячейку 01 заносится код ХОХОО. В зонах 010 ле маркерных битов р,у - единиц(с выхо- и 001 выполняются операции, аналогичные дов 48, 49), в поле маркерного бита а - выполнявшимся взонах 101,100. Взоне 000 инверсное значение соответствующего бита 30 маркерные биты слова, хранящегося в ячейвыходного регистра 2. Во второмтакте бло- ке 10, равны а =1,Р =1,у =1,Соответстком 24 управления выдается (блок 10 алго- венно выполняют блоки 5,6,11,12 ритма на фиг,4) код 01 на выходах 39, код 10 алгоритма,. изображенного на фиг.4, в ячей, на выходы 38, единичные потенциалы на ку 00 загружается код 111 11, в ячейку 11 выход 48, которые инициируют запись в 35 загружается код 0000 00, маркерный бит Р ячейку по адресу, совпадающему с кодом на в ячейке 10 устанавливается в "0", Код 00 регистре 11 промежуточного хранения, мар- загружается в регистр 10 начального адреса керных битов Р иу, равных нулю, и кода с вместо ранее там находившегося кода 10.вьходов регистра 2, Поокончании выполне- При поиске слова по совпадению код ния указанных микрокоманд(после выпол команды "Поиск адреса ячейки, содержинения блоков 8 или 10 алгоритмов на фиг.4) мое которой совпадает с заданным признаблок 24 управленияформируетнавыходе 57 ком опроса", подается на входы55 сигнал конца операции, устройства, одновременно код слова подаПосле выполнения блоков 4,6,7 алгорит- ется на информационные входы 14 устройма на фиг,4 выполняется описанный блок 3 45 ства, Алгоритм выполнения команды поиска микроопераций установки в "0" маркерного по совпадению представлен на фиг.5.бита р присутствия исключаемого слова и Выполнение команды начинается (блок уменьшения на единицу,содержимого счет алгоритма на фиг.6) выдачей блоком 24 чика 13. Если в результате указанного управления единичных сигналов на выходах уменьшения счетчик 13 выдает сигнал пере 46,42,31, кодов 10 на выходах 39 и 37, кото- полнения на вход 25 блока 24 управления, рыми инициируется прием кода признака то в следующем такте(блок 11 алгоритма на опроса на регистр 15, пересылка кода с рефиг.4) блок 24 управления формирует код 00 гистра 10 начального адреса через коммутана выходах 39 и единичный сигнал на выхо- торы 3 и 6 на регистр 8 числа, установка в де 32, которые обеспечивают пересылкуад "0" разрядов реверсивного счетчика 13, В реса ветви, отходящей от исключаемой, из следующем такте (блок 2 алгоритма на регистра 11 промежуточного хранения че- фиг,5) выдачей блоком 24 управления кода рез адресный коммутатор 3 на регистр 10 11 на выходах 39 и единиц ого сигнала на.начального адреса. Операция исключения выходе 47 обеспечивается считывание из заканчивается,10 30 35 40 блока 1 памяти содержимого ячейки, соответствующей "корню" дерева слов, записанных в блоке 1. Дальнейшее функционирование устройства определяется значением сигналов на входах 29 и 30 блока 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 устройства. 45 При поиске экстремума код команды "Поиск ячейки, содержащей экстремальный код", подается на входы 55, а на вход,56 подается бит, определяющий направление поиска, равный нулю при поиске максимума 50 и единице при поиске минимума. Пусть для. определенности ищется максимум среди чисел, хранящихся в устройстве, В первом такте поиска (блок 1 на алгоритме поиска экстремума, представленном на фиг.6) блок 55 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.числа, установку в "0" реверсивного счетчика 13, прием кода признака опроса с входов 14 на регистр 15 признака опроса, установку в "0" триггера 70. Цикл прохода зон начинается считыванием на выходной регистр 2 содержимого ячейки блока 1 памяти, адресуемой кодом с регистра 8 числа (блок 2 алгоритма на фиг.7). Укаэанные микрооперации реализуются выдачей блоком 24 управления кода 11 на выходах 39 и единичного сигнала на выходе 34.Дальнейшая последовательность следования микрокоманд зависит от сигналов, поступающих на входы 28 - 30 блока 24 управления, В частности, если имеется единичный сигнал совпадения на входе 30, что соответствует совпадению ветви числа - признака опроса и одной из ветвей графа, хранящегося в блоке 1 памяти, то анализи- руется значение текущего разряда призна 10 ка опроса, выдаваемое на вход 28 блока 24 в прямом коде, если ищется ближайшее большее, и в инверсном, если ищется ближайшее меньшее, Ели сигнална входе 28 не равен нулю (что свидетельствует о невозможности ответвления в направлении,соответствующем критерию поиска), то анализируется сигнал на выходе 29 блока 24 управления; если укаэанный сигнал равен нулю, то ветвь признака опроса совпадает с 20 25 прямым продолжением ветви, хранящейся в блоке 1, а если единице; то ветвь признака опроса совпадает с отходящим участком ветви и, следовательно, для продолжения поиска необходимо изменить адрес при обращении в последующей зоне. В первом случае выполняется блок 4 алгоритма, представленного на фиг.7, а во втором - блок 3. Соответственно в первом случае блоком 24 управления формируются единичные сигналы на выходах 44,50, которые управляют увеличением на единицу содержимого счетчика 13 и сдвигом регистра 15. Во втором случае дополнительно к упомянутым микро- операциям выдачей блоком 24 управления 30 35 кода 01 на выходах 37 и единичного сигнала на выходе 31 осуществляется загрузка регистра 8 числа кодом ссылки с выходного регистра 2.Если сигнал на входе 28 равен нулю, то на входе 29 блока 24 управления. Если ука-,.занный сигнал равен нулю, то это соответ 45 ствует тому, что от ветви с адресом,зафиксированным на регистре 9, совпадающей с ветвью признака опроса, ответвляется ветвь, адрес которой зафиксирован на выходном регистре 2, соответствующая чис- БО лам большим признаку поиска,Соответственно блоком 24 управления (блок 5 алгоритма на фиг,7) формируются единичные сигналы на выходах 35,44,50,68, которые инициируют передачу кода из поля 55 ссылок выходного регистра 2 через откры.тый нулевым сигналом с выходом 40 коммутатор 4 на регистр 11 промежуточного хранения, увеличение на единицу содержимого счетчика 13, сдвиг содержимого регистра 15 признака опроса, установку в "1" 40возможно ответвление ветви, соответствующей числам, большим заданного признака опроса, В этом случае анализируется сигналтриггера 70, единичное состояние которогосвидетельствует о фиксации начальной ветви подграфа чисел, больших заданного признака опроса, В последующем такте (блок.балгоритма на фиг.7) сигналом с выхода 33 5, блока 24 управления осуществляется фиксация содержимого счетчика 13 нэ фиксирующем регистре 12,Еслй сигнал на входе 291 блока 24 управления равен единице, то это соответствует тому, что ветвь с адресом,зафиксированным в поле ссылок выходногорегистра 2, совпадающая с ветвью признакаопроса, ответвляется от ветви, адрес. которой зафиксирован на регистре 8 и которая 15соответствует числам, большим заданногопризнака опроса, Соответственно блоком24 управления (блок 7 алгоритма на фиг,7)формируются код 11 на выходах 39, код 01на выходах 37, единичные сигналы на выходах 35,40,31,44,50,68, которые инициируютпересылку кода с регистра 8 через коммута-.хранения, пересылку кода с поля ссылок,выходного регистра 2 через коммутатор 6 на 25регистр 8 числа, увеличение на единицу содержимого счетчика 13, сдвиг содержимогорегистра 15, установку в единичное состояние триггера 70,В последующем такте выполняется микрокоманда, соответствующая блоку 6 алгоритма на фиг,7, Если в результатеописанных микроопераций появится сигнална входе 25 блока 24 управления, то процесспоиска закончен и адрес искомого слова 35может быть считан с выходов 9 устройства.В противном случае начинается обработкаинформации в последующей зоне блока 1памяти.Если в результате считывания очередного фрагмента графа, осуществляемогоблоком 2 алгоритма на фиг.7, окажется, чтосигнал на входе 30 блока 24 управленияравен нулю, то это соответствует тому, чтоветвь, соответствующую признаку опроса, 45не совпадает далее ни с одной из ветвейграфа, хранящегося в блоке 1 памяти, и необходимо переходить к поиску. минимального элемента на подграфе чисел, большихзаданного 50Если очередной разряд признака опроса равен нулю (соответственно и равен нулюсигнал на выходе 28 блока 24 управления),то подграф множества чисел ближайшихбольших заданного признака .опроса порождается продолжением ветви, адрес ко-.торой зафиксирован на регистре 8:чйслэ.Блок 24 управления формирует сигнал единичного уровня на своем выходе 52, которым все разряды регистра 15 устанавливаются в "0" (блок 8 алгоритма) и " далее управление передается микроподп-. рограмме (блоки 11-13 алгоритма на фиг,7), которая реализует поиск минимального числа в подграфе, корень которого задан адресом в регистре 8 числа. Если значение текущего разряда признака опроса. (а значит, и сигнал нэ входе 28 блока 24 управления) равен единице, то минимальное число следует искать по подграфу, порождающий корень которого зафиксирован на регистре 12 текущего адреса и регистре 11 промежуточного хранения. Для этого предварительно анализируется состояние триггера 70: если последний установлен в "0", то среди записанных в блоке 1 памяти чисел нет больших заданного, соответственно блоком 24 управления выдается сигнал неуспешного поиска с выхода 58 устройства, В противном случае выполняется блок 10 алгоритма на фиг.7, в котором блок 24 управления выдает единичные сигналы нэ своих выходах 46, 31, 52, код 01 на выходах 39 и код 11 на выходах 37; которые инициируют прием кода с регистра 12 текущего адреса на реверсивный счетчик 13, пересылку кода с регистра 11 промежутоного хранения через коммутаторы 3,6 на регистр 8 числа, установку в "0" всех разрядов регистра 15,Процесс поиска минимума, реализуемый подпрограммой, задаваемой блоками 11-14 алгоритма на фиг,7, аналогичен описанной процедуре поиска экстремума за тем исключением, что при переходе к следующей зоне в блоке 1 памяти сдвиг содержимого регистра 15 не производится. По выдаче счетчиком 13 сигнала переполнения на вход 25 блока 24 управления искомый адрес фиксируется на регистре 8 и выдается посредством выходов 9, блок 24 формирует единичный сигнал конца операции на выходе 57.При считывании слова по его адресу код соответствующей команды подается на входы 55, код адреса подается,на входы 7 устройства. Алгоритм выполнения команды считывания слова по адресу представлен на фиг,8,Первая микрокомандэ (блок 1 алгоритма на фиг.8) устанавливает исходное состояние устройства. Соответственно блоком 24 управлейия формируется код ОО на выходах 37 и единичные. сигналы на выходах 31,43, под управлением которых код адреса с входов 7, поступая через входной коммутатор 6, фиксируется на регистре 8 числа, все разряды счетчика 13 устанавливаются в "1". Таким образом, восстановление слова по его адресу начинается с последней зоны блока 1 памяти.