Устройство для адресации по содержанию блока памяти

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

15Р 4 G 06 F 12/00, 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

i1O ИЗОБ ЕтЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4275545/24-24 (22) 05.05.87 (46) 07.03.89. Бюл. К- 9 (71) Обнинский институт атомной энергетики (72} Т.П.Корниец, Б.А.Кулик и Э.В.Кулик (53) 681.325(088.8) (56) Авторское свидетельство СССР

Ф 1164718, кл. G 06 F 12/00, 1982.

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

N- 1322292, кл, G 06 F 12/00, 1986. (54) УСТРОЙСТВО ДЛЯ АДРЕСАЦИИ ПО С0ДЕРЖАНИЮ БЛОКА ПАМЯТИ (57) Изобретение относится к области вычислительной техники и может быть использовано в автоматизированных системах обработки информации для адресации по содержанию блока памяти

„ЛК„, 14 4364 А1

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

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

Ф ф-лы, 3 ил.

1464164

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

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

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

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

1 и сигнала ГОтОВнОсть °

Блоки ассоциативных признаков 1 и 30 логических векторов 2 (фиг. 2), на пример,, могут . представлять собой соотве"гственно двоичный счетчик 8, счетный вход (.) которого соединен со счетным Входом (3) блока, вход (2) начальной установки соединен с информационным входом (1) блока 1, вход (3) обнуления соединен с входом (4} сброса блока 1, а выход (параллельный) соединен с выходом (2) блока 1, и запоминающее устройство 9, в пространстве запоминающих элементов которого помещается построчно матрица из и и-разрядных строк с адресным механизмом поиска строки, адресный вход (1) которого соединен с входом (2) блока 2, с механизмом чтения (вход (2) управляющего сигнала "Чтение" соединен с входом (3) блока 2) и с выхоцом (1) — выходной п-разрядной шиной чтения, соединенной с Выходом (t) блока 2.

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

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

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

10 выполняет операцию накапливающего логического сложения и-разрядных слов, поступающих на вход (8), с содержимым аккумулятора при подаче сигнала на вход (5), загрузку аккумулятора и-разрядным словом, поступающим на вход 7, при подаче сигнала на вход (4) и операцию арифметического вычитания иэ накопленного в аккумуляторе значения и-разрядного слова, поданного на вход (3) при поступлении сигнала на вход (6). Результирующее значение иэ аккумулятора выдается с выхода (1)>,а с выхода (2) выдается признак нулевого результата в аккумуляторе.

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

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

Для примера, граф из n = 7 вершин с

1464164

3 4 б 7

5 2

35

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

5 соединена с вершинами 6 и 2, веро шина 2 соединена с вершиной 7. Матрица векторов 7х7. г

1 2 3 4 5 б 7

В аналитической форме процесс нахождения вектора связанных вершин, например, с вершиной 1 {начальная вершина) осуществляется так: вектор начальной вершины а „„д = С„

1001100 указывает на то, что вершины 1, 4, 5 связаны. Находится логическая сумма их векторов:

1001100 V 1001100 V 1101110 =

1101110.

Находится разность G G

= 0100010, которая указывает, что .связанными еще являются вершины 2 и

6. Находится логическая сумма векторов вершин 2 и б: 1101110 + 0100101+ .+ 0000110 =- 1101111 = G и разность

G — С, = 0000001 — связанная еще, вершина 7 логическая сумма С +

+ вектор вершин 7 равна 1101111

= G- разность G - G = 0 — это при55 знак, что G — вектор связанных вер,шин. Интерпретация результата G =

1101111: единица вектора G указывает на столбцы, имена которых являются именамн связанных вершин — зто

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

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

Подается сигнал "Начальная установка" по линии 5 и код вектора вершины, для которой устанавливаются связанные с ней вершины по шине 4.

Сигчалом "Начальная установка" приводятся в исходное состояние узлы блока анализа связности вершин графа и запускается генератор (цепи установки исходного состояния не показаны). Этим же сигналом через элемент

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

Одновременно импульсы от генератора поступают на счетный вход (1) счетчика 8 и увеличивают его содержимое.

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

9 в соответствии с кодом в счетчике

8 и накапливающее логическое cvr а рование в АЛУ 10. После сдвига из

5 146 регистра 11 последней единицы по нуЛевому значению кода распределителем

15 импульсов вырабатывается сигнал йриема в регистр 13 кода с выхода (1) результата АЛУ 1О (содержимое акКумулятора), через „с выхода (2) распределителя импульсов подается на

gïðàBëÿâùHé вход (6) логического вычитания АЛУ сигнал и выполняется вычитание иэ значения „накопленного аккумуляторе АЛУ„ значения, храня/ егося в регистре 12„еще через с с выхода 3 распределителя импульсов сигнал поступает на вход (3) сброса счетчика и устанавливает его в нуле вое состояние, одновременно пройдя !

|через элемент ИЛИ 17 на вход управ ления записью регистра 11, разрешает ( через сборку 19 перезапись результата вычитания иэ АЛУ в регистр 11, через 4 сигнал с выхода 4 распределителя импульсов поступает на вход ( (4) разрешения перезаписи АЛУ, а через элемент ИЛИ 18 - на вход (2) управления записью регистра 12, и код из регистра 13 переписывается в аккумулятор и в регистр 12. Следующий импульс генератора 14 повторяет описанный процесс до момента, когда в результате вычитания в АЛУ будет за, фиксирован нулевой результат, и с выхода (2} признака нулевого результата АЛУ признак нулевого результата поступает на выход (7) признака готовности блока анализа связности, что указывает на то, что в регистре

13 и на выходе (б) блока анализа связности получен вектор связности.

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

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

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

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

35 кода первого регистра соединен с первым входом первого элемента ИЛИ и с входом запуска распределителя

40 импульсов соответственно„ выход генератора импульсов соединен с входом сдвига первого регистра и с выходом опроса блока, вход начальной установки которого соединен с первыми вхо-дами второго и третьего элементов

ИЛИ и с вторым входом первого .элемента ИЛИ, выход которого соединен с выходом управления чтением блока и с входом тактирования арифметико5О логического узла, выход результата которого соединен с вторым входом первого блока элементов ИЛИ и с информационным входом третьего рег,истра, выход которого соединен с входом перезаписи арифметико-логического узла, 55 вторым входом второго блока элементов

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

14641 64 ходу распределителя импульсов, вто-. рой выход которого соединен с управляющим входом арифметико-логического узла, третий выход распределителя импульсов соединен с выходом сброса блока и с вторым входом второго элемента И3%, выход которого подключен к входу управления записью первого регистра, четвертый выход {) распределителя импульсов соединен с вторым входом третьего элемента ИЛИ и с входом разрешения перезаписи арифметико-логического узла, вход вычитаемого которого соединен с выходом второго регистра, вход управления записью которого соединен с выходом третьего элемента ИЛИ, выход признака нулевого результата арифметико-логического узла соединен с вы" ходом признака готовности устройства.

1 464 I 64

Составитель ЕО.Тислеико

Техред A. Кравчук Корректор М Лароши

Редактор Н.Яцола

Заказ 826/52 Тираж 667 Подписное

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

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

Производственно"издательский комбинат "Патент", г. Ужгород, ул. Гагарина,ЕОЕ