Устройство для адресации по содержанию блока памяти Советский патент 1989 года по МПК G06F15/173 G06F12/00 

О) 4ib

Изобретение относится к вычислительной технике и может быть использовано в автоматизированных системах обработки информаи(ии с помощью ЭВМ.

Цель изобретения - расширение .класса решаемых задач за счет аппа- ратной реализации .:алгоритма формирования вектора связанных вершин нет направленного графа.

На фиг, 1 приведена схема устройства для адресации по содержанию блока памятиJ на фиг. 2 - пример вьг полнения блока формирования ассоциативных признаков и блока памяти логических, вектор ов на фиг.З - пример выполнения блока анализа связности вершин графа (в скобках указаны порядковые номера входов).

Устройство для адресации по со- держанию блока памяти (фиг, 1) содержит блок 1 формирования ассоциативных признаков э блок 2 памяти логических векторов, блок 3 анализа связности вершин графа, имну 4 входов аргумента поиска,, ли;гшю 5 Начальная установка, выходную шину 6 вектора связанных верти;н и линию 7 сигнала Готовность.

Блоки ассоциативных признаков 1 и логических векторов 2 (фиг. 2), на пример., могут .представлять собой соответственно двоичный счетчик.8, счетньш вход (О которого соединен со счетным входом (3) блока, вход (2) начальной установки соединен с информациоиньм входом (1) блока 1, вход .(3) обнуления соединен с входом (4) сброса блока 1, а выход (параллельный) соединен с ВЬЕСОДОМ (2) блока 1s и запоминающее устройство 9, в пространстве запоминаюгщих элементов которого помещается построчно матрица из п п-разрядных строк с адресным механизмом поиска строки, ад- ресньш вход (1) которого соединен с входом (2) блока 2, с механизмом чтения (вход (2) управляющего сигнала Чтение соединен с входом (3) блока 2) и с выходом (1) - выходной п разрядной шиной чтения, соединенной с выходом (1) блока 2,

Блок. 3 анализа связк:ости вершин графа содержит арифметико-логический узел (А,ЛУ) 10, три регистра 11-13, генератор 14, распреде.ттк:тель 15 им- , три элемента ЖИ 16-18 и дв сборки 19 и 20 двухвходовых элементов ИЛИ.

0

5

0

5

0

5

0

5

0

Сборки элементов ИЛИ 19 и 20 содержат по п элементов.

Распределитель 15 импульсов из п- разрядного входного сигнала формирует: на выходе (1) - сигнал нулевого значения входного сигнала и задержанные по отношению к этому сигналу и относительно друг друга сигналы на выходах (2), (3) и (4), причем задержка сигнала на вьгходе (2) по отношению к сигналу на выходе (1) , - на время, достаточное для приема информации из АЛУ в регистр 13, задержка сигнала на выходе (3) по отношению к сигналу на вь1ходе (2) fg - на время осуществления в АЛУ операции вычитания, задержка сигнала на выходе (4) по отношению к сигналу на выходе (3) € j - на время приема информатдии в регистр 11 из АЛУ. АЛУ 10 выполняет операгщю накапливающего логического сложения п--разрядных слов, поступаюшр х на вхоц (8), с содержимым аккугчулятора при подаче сигнала на вход (5), загрузку аккумулятора п-разрядным словом, поступающим на вход 7, при подаче сигнала на вход (4) и операцию арифметического вычитания из накопленного в аккумуляторе значения п-разрядного слова, поданного на вх од (3) при поступлении сигнала на вход (6). Результирующее значение из аккумулятора вьщается с выхода (1), ас выхода (2) выдается признак нулевого результата в аккумуляторе.

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

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

. 314641

номерами 1-7. Вершины 1, 4, 5 свя- заны дугами в треугольник, вершина 5 соединена с вершинами 6 и 2, вершина 2 соединена с вершиной 7. Мат- - рица векторов 7x7.

В аналитической форме процесс нахождения вектора связаннык вершин, например, с вершиной 1 (начальная вершина) осуществляется так: вектор начальной вершины а G 1001100 указывает на то, что вершины 1j 4, 5 связаны. Находится логическая сумма их векторов:

1001100 V 1001100 V1101110 1101110.

Находится разность G - о ОЮОрЮ, которая указывает, что .связанными еще являются вершины 2 и 6 о Находится логическая сумма векторов вершин 2 и 6: 1101110 + 0100101+ + 0000110 1101111 G,, и разность Gj - G, 0000001 - связанная еще вершина логическая сумма G + + вектор вершин 7 равна 1101111

Х-

э

разность Gj - G, О - это приI-

знак, что G - вектор связанных вер- , шинс Интерпретация результата G ,. 1101111: единица вектора G указывает на столбцы, имена которых явля-

-

fO

20

25

64А

ются именами связанных веривш - зто 1, 2, 4-7. Легко убедиться, что с вершиной 3 нет связанных вершин,

В запоминающем устройстве 9 блока памяти логических векторов извecтнь)f способом записаны п п-разрядных векторов. Чтобы адрес ячейки можно бьшо использовать в качестве ассоциативного признака вектора вершины, при записи должно соблюдаться соответствие номера ячейки номеру вершины графа.

Подается сигнал Начальная уста- 15 новка по линии 5 и код вектора вершины, для которой устанавливаются связанные с ней вериины по шине. 4. Сигналом Начальная установка приводятся в исходное сос ояние узлы блока анализа связности вершин графа и запускается генератор (цепи установки исходного состояния не показа- ны). Этим же сигналом через элемент ИЛИ 16 вьшолняется чтение из запоминающего устройства 9 вектора верилг- ны в соответстствии с кодом, содержащемся в счетчике 8, связанным с адресным входом (1) запоминающего устройства. Значение вектора вершины с информационного выхода (1) запоминающего устройства 9 поступает на вход (8) накапливающего суммирования .АЛУ 10 и сигналом с выхода элемента МИ 16 осуществляется его логическое суммирование в АЛУ, одновременно пройдя сборки 19 и 20 тем же сигналом начальной установки, поступившим через злементы ИЛИ 17 и 18, значение кода вектора принимается в регистры 11 и 12. Спустя время Т,. после подачи сигнала Начальная установка (время, достаточное для выполнения указанных действий), генератор 14 с периодом Т. начинает вырабатывать импульсы, поступление каждого импульса на вход (3) сдвига регистра 11 осуществляет сдвиг его содержимого на один разряд влево. . Одновременно импульсы от генератора поступают на счетный вход (1) счетчика 8 и увеличивают его содержимое.

Появление единицы на последовательном информационном выходе (2) регистра 11 осуществляет через элемент ИЛИ 16 описанным способом вектора из запоминающего устройства 9 в соответствии с кодом в счетчике 8 и накапливающее логическое cyNw-ш- рование в АПУ 10. После сдвига из

30

5

0

5

0

514641646

регкстра 11 последней едидацы по ну-ассоциативных признаков,, выход сброЛевому значению кода распределителем 15 импульсов вырабатывается сигнал Приема в регистр 13 кода с выхода (1) результата АЛУ 10 (содержимое ак Нумулятора), через , с выхода (2) распределителя импульсов подается на управляющий вход (6) логического вычитания АЛУ сигнал и выполняется |вычитанке из значения,, накопленного {в аккущ ляторе АЛУ,, значения, храня10

са блока анализа связности вершин графа соединен с входом с(5роса блока формирования ассоциативньЕс признаков выход блока памяти логических векторов соединен с информационным входом блока анализа связности вершин графа, выход управления чтением которого соединен с входом разрешения чтения блока памяти логических векторов, информационный выход блока анализа связности вершин графа является выходом вектора связанных -15 вершин графа устройства, выход признака готовности и вход начальной установки блока анализа связности вершин графа являются соответственно одноименными выходом и входом устрой ства.

f

,егося в регистре 12s, еще через с,

са блока анализа связности вершин графа соединен с входом с(5роса блока формирования ассоциативньЕс признаков, выход блока памяти логических векторов соединен с информационным входом блока анализа связности вершин графа, выход управления чтением которого соединен с входом разрешения чтения блока памяти логических векторов, информационный выход блока анализа связности вершин графа является выходом вектора связанных -15 вершин графа устройства, выход признака готовности и вход начальной установки блока анализа связности вершин графа являются соответственно одноименными выходом и входом устройства.

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

С выхода 3 распределителя импульсов сигнал поступает на вход, (3) сброса счетчика и устанавливает его в нулевое состояние, одновременно пройдя через элемент ИЛИ 17 на вход управ- ления записью регистра 11, разрешает через сеЗорку 19 перезапись результата вычитания из АЛУ в регистр 11, через t, сигнал с выхода 4 распределителя )№тульсов поступает на вход (4) разрешения перезаписи АЛУ, а через элемент ИЛИ 18 - на вход (2) уп- 25 гистра, генератор импульсов, делитель равления записью регистра 12, и код иштульсов, три элемента КШИ, два

из регистра 13 переписывается вблока элементов ИЛИ, причем информааккумулятор и в регистр 12. Следующий ционный вход блока соединен с входом

:и fflyльc генератора 14 повторяет описанный процесс до момента, когда в ,

; результате вычитания в АХ У будет зафиксирован нулевой результат, и с выхода (2) признака нулевого результата АЛУ признак нулевого результата поступает на выход (7) признака готовности блока анализа связности, что указывает на то, что в регистре 13 к к. вькоде (6) блока анализа связности получен вектор связности.

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

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

ассоциативных признаков,, выход сбро

са блока анализа связности вершин графа соединен с входом с(5роса блока формирования ассоциативньЕс признаков, выход блока памяти логических векторов соединен с информационным входом блока анализа связности вершин графа, выход управления чтением которого соединен с входом разрешения чтения блока памяти логических векторов, информационный выход блока анализа связности вершин графа является выходом вектора связанных вершин графа устройства, выход признака готовности и вход начальной установки блока анализа связности вершин графа являются соответственно одноименными выходом и входом устройства.

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

гистра, генератор импульсов, делитель иштульсов, три элемента КШИ, два

ционный вход блока соединен с входом

накапливающего суммирования арифме- . 0 тико-логического узла и с первыми входами первого и второго блоков элементов ШШ, выходы которых соединены с информационными входами первого и второго регистров соответственно, последовательный информационный выход и выход признака нулевого кода первого регистра соединен с первым входом первого элемента ИЛИ и с входом запуска распределителя импульсов соответственно,, выход генератора импульсов соединен с входо сдвига первого регистра и с выходом опроса блока, вход начальной установки которого соединен с первыми вхо- да№1 второго и третьего элементов ИЛИ и с вторым входом первого элемента ШМ, выход которого соединен с выходом управления чтением блока и с входом тактирования арифметико- логического узла, вькод эезультата которого соединен с вторым: входом первого блока элементов ИЖ и с информагщон- ным входом третьего рег;истра, выход которого соединен с входом перезаписи арифметико-логического узла, вторым входом второго блока элементов ИЛИ и с выходом вектора связанных вершин графа блока, а вход разрешения записи подключен к первому вы5

0

55

ходу распределителя импульсов, второй выход которого соединен с управляющим входом арифметико-логического узла, выход распределителя импульсов срвдинен с вькодом сброса блока и с вторьм входом второго элемента ИЖ, вькод которого подключен к входу управления записью первого регистра, четвертый выход распределителя импульсов соединен с

41648

вторьт входом третьего элемента ИЛИ и с входом разрешения перезаписи арифметико-логического узла, вход

вычитаемого которого соединен с выходом второго регистра, вход упраз- ления записью которого соединен с выходом третьего элемента ИЛИ, вькод признака нулевого результата арифме10 тико-логического узла соединен с вы- ходом признака готовности устройства.

Изобретение относится к области вычислительной техники и может быть использовано в автоматизированных системах обработки информации для адресации по сод ержанию блока памяти в применении к задачам получения вектора связанных вершин и п-мер.ного графа. Целью изобретения является расширение класса решаемых задач за счет аппаратной реализации алгоритма связанных вершин для ненаправленного графа, представленного в виде симметричной матрицы векторов веримн. Для реализации алгоритма поиска в устройство введен блок 3 анализа связности вершин графа, осу- ществлякиций функцию управления блоком 1 формирования ассоциативных признаков при отыскании векторов связанных вершин из блока 2 памяти логических векторов. Устройство обеспечивает нахождение групп связанных вершин, начиная с произвольной вершины, причем в группе вершин может быть от одной до п связанных вершин. 1 з.п. ф-лы, 3 ил. § (Л

«,

т

д & 11)

13)

д

/а

cjJai.z

Фиг,3