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

(19) (111 4 С 06 Р 12/00, 15/2 ПИСАНИЕ ИЗОБРЕТЕНИ ЕЛЬСТВУ ТОРСКОМУ СВИ но ПП 1 ПО СО 4) УСТРОЙСТВО ДЛЯ АДРЖАНИЮ БЛОКА ПАМЯТИ(57) Изобретение о вычислительной те использовано в ав системах обработк адресации по соде я к област может быть тносит хники и томатиз и инфор ржанию нн ации дллока и ти ГОСУДАРСТВЕННЫЙ КОМИТЕТ11 О ИЗСБ ЕТЕНИЯМ И ОТНРЫТИМПРИ ГКНТ СССР(71) Обнинский институт атом йэнергетики(56) Авторское свидетельство СССРУ 1164718, кл. С 06 Г 12/00, 1982.Авторское свидетельство СССРУ 1322292, кл, С 06 Р 12/00, 1986,Ов применении к задачам получения . вектора связанных вершин и и-мерного графа. Целью изобретения является . расширение класса решаемых задач за счет аппаратной реализации алгоритма связанных вершин для ненаправленного графа, представленного в виде симметричной матрицы векторов вершин. Для реализации алгоритма поиска в устройство введен блок 3 анализа связности вершин графа, осуществляющий функцию управления блоком 1 Формирования ассоциативных признаков при отыскании векторов связанных вершин из блока 2 памяти логических векторов. Устройство обеспечивает нахождение групп связанных вершин, начиная с произвольной вершины, причем в группе вершин может быть от . одной до п связанных вершин. 1 з.п,Фф-лы, 3 ил.Изобретение относится к вычислительной технике и может быть использовано в автоматизирова.нных системахобработки информации с помощью ЭВМ.5Цель изобретения - расширениекласса решаемых задач за счет аппаратной реализации .:алгоритма Формирования вектора связанных вершин нетнаправленного графа, 10На фиг. 1 приведена схема устройства для адресации по содержаниюблока памяти на Фиг. 2пример выполнения блока формирования ассоциативных признаков и блока памяти логических векторов на фиг.3 - примервыполнения блока анапиза связностивершин графа (в скобках указаны порядковые номера входов),Устройство для адресации по со-20держанию блока памяти (Фиг. 1) содержит блок 1 Формирования ассоциативных признаков, блок 2 памяти логических векторов, блок 3 анализасвязности вершин графа, пину 4 входов аргумента поиска, линию 5 "Начальная установка", выходную шину 6вектора связанных верши:н и линию 71 исигнала ГотовностьБлоки ассоциативных признаков 1 и 3 Ологических векторов 2 (Фиг, 2), например могут , представлять собойсоответственно двоичный счетчик 8,счетный вход (.) которого соединенсо счетным входом (3) блока, вход(2) начальной установки соединен синформационным входом (1) блока 1,вход (3) обнуления соединен с входом(4) сброса блока 1, а выход (параллельный) соединен с выходом (2) блока 1, и запоминающее устройство 9, впространстве запоминающих элементовкоторого помещается построчно матрица из и и-разрядных строк с адресным механизмом поиска строки, адресный вход (1) которого соединен свходом (2) блока 2, с механизмомчтения (вход (2) управляющего сигнала "Чтение" соединен с входом (3)блока 2) и с выхоцом (1) - выходнойи-разрядной шиной чтения, соединен- фной с выходом (1) блока 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) выдается признак нулевого результата в аккумуляторе.Устройство работает следующим образом.В основе автоматического получения вектора связанных вершин с помощью предлагаемого устройства положено следующее. Состояния какого-либо явления (процесса, Физического поля и и т.п.) могут быть интерпретированы как вершины графа, связность между вершинами отражают соединяющие их дуги. Композиция вершин и дуг - ненаправленный, граф может быть представлена в виде закодированных описаний вершин - векторов вершин с по" мощью двумерной матрицы с именами . вершин, расположенными по строкам и столбцам, а помеченные единицами клетки матрицы отражают дуги графа (матрица симметрична относительно диагонали, диагональ для ненаправленного графа заполнена единицами). Дг 1 я примера, граф из и = 7 вершин с1464164 3 4 6 7 10 20 30 5 100 110111 номерами 1-7. Вершины 1, 4, 5 связаны дугами в треугольник, вершина 5 соединена с вершинами 6 и 2, верошина 2 соединена с вершиной 7. Матрица векторов 7 х 7.г 1 2 3 4 5 6 7 В аналитической форме процесс нахождения вектора связанных вершин, например, с вершиной 1 (начальная вершина) осуществляется так: вектор начальной вершины анан = Со1001100 указывает на то, что вершины 1, 4, 5 связаны. Находится логическая сумма их векторов;1001100 ч 1001 Ч 1101110 = 45Находится разность С, С = 0100010, которая указывает, что .связанными еще являются вершины 2 и 6. Находится логическая сумма вектороввершин 2 и 6: 1101110 + 0100101+ .+ 0000110 =- 1101111 = С , и разность50 С - С, = 0000001 - связанная еще, вершина 7 логическая сумма С + + вектор вершин 7 равна 1101111 = С разность С - С = 0 - это при 55 знак, что С - вектор связанных вершин, Интерпретация результата Сэ =1101111: единица вектора С указывает на столбцы, имена которых являются именамн связанных вершин - зто 1, 2, 4 - 7. Легко убедиться, что с вершиной 3 нет связанных вершин.В запоминающем устройстве 9 блока памяти логических векторов известным способом записаны п и-разрядных векторов. Чтобы адрес ячейки можно было использовать в качестве ассоциативного признака вектора вершины, при записи должно соблюдаться соответствие номера ячейки номеру вершины графа.Подается сигнал "Начальная установка" по линии 5 и код вектора вершины, для которой устанавливаются связанные с ней вершины по шине 4. Сигчалом "Начальная установка" приводятся в исходное состояние узлы блока анализа связности вершин графа и запускается генератор (цепи установки исходного состояния не показаны). Этим же сигналом через элемент сИЛИ 16 выполняется чтение из запоминающего устройства 9 вектора вер 1 ш- ны в соответстствии с кодом, содержащемся в счетчике 8, связанным с адресным входом (1) запоминающего устройства. Значение вектора вершины с инФормационного выхода (1) запоьалнаюшего устройства 9 поступает на вход (8) накапливающего суммирования АЛУ 10 и сигналом с выхода элемента ИЛИ 16 осуществляется его логическое суммирование в АЛУ, одновременно пройдя сборки 19 и 20 тем же сигналом начальной установки, поступившим через элементы ИЛИ 17 и 18, значение кода вектора принимается в регистры 11 и 12. Спустя время Т,после подачи сигнала "Начальная установка" (время, достаточное для выполнения указанных действий), генератор 14 с периодом Т начинает выГЕНрабатывать импульсы, поступление каждого импульса на вход (3) сдвига регистра 11 осуществляет сдвиг его содержимого на один разряд влево. Одновременно импульсы от генератора поступают на счетный вход (1) счетчика 8 и увеличивают его содержимое,Появление единицы напоследовательном информационном выходе (2) регистра 11 осуществляет через элемент ИЛИ 16 описанным способом чтение вектора из запоминающего устройства 9 в соответствии с кодом в счетчике 8 и накапливающее логическое суммирование в АЛУ 10. После сдвига из5 146 регистра 11 последней единицы по нуЛевому значению кода распределителем 15 импульсов вырабатывается сигнал приема в регистр 13 кода с выхода 1) результата АЛУ 1 О (содержимое аккумулятора), через 7 с выхода (2) распределителя импульсов подается на управляющий вход (6) логического вычитания АЛУ сигнал и выполняется вычитание иэ значения накопленного аккумуляторе АЛУ значения, хранятегося в регистре 12 еще через с с выхода 3 распределителя импульсов сигнал поступает на вход (3) сброса счетчика и устанавливает его в нулевое состояние, одновременно пройдя через элемент ИЛИ 17 на вход управления записью регистра 11, разрешает через сборку 19 перезапись результата вычитания иэ АЛУ в регистр 11, через 4 сигнал с выхода 4 распределителя импульсов поступает на вход (4) разрешения перезаписи АЛУ, а через элемент ИЛИ 18 " на вход (2) управления записью регистра 12, и код из регистра 13 переписывается в аккумулятор и в регистр 12. Следующий импульс генератора 14 повторяет описанный процесс до момента, когда в результате вычитания в АЛУ будет за, фиксирован нулевой результат, и с выхода (2) признака нулевого результата АЛУ признак нулевого результата поступает на выход (7) признака готовности блока анализа связности, что указывает на то, что в регистре 13 и на выходе (б) блока анализа связности получен вектор связности. Формула изобретения1. Устройство для адресации по содержанию блока памяти, содержащее блок памяти логических векторов и .блок формирования ассотиативных признаков, информационный вход которого является входом аргумента поиска устройства, выход соединен с адресным входом блока памяти логических векторов, отличающеес я тем, что, с целью расширения класса решаемьж задач за счет аппаратной реализации алгоритма Формирования вектора связанных вершин не" направленного графа, в него введен блок анализа связности вершин графа, выход опроса которого ссединен со счетнь 1 м входом блока формирования 4164Оассоциативных признаков, выход сброса блока анализа связности вершинграфа соединен с входом сброса блокаформирования ассоциативных признаков, 5выход блока памяти логических векторов соединен с информационным входом блока анализа связности вершинграфа, выход управления чтениемкоторого соединен с входом разрешения чтения блока памяти логическихвекторов, информационный выход блокаанализа связности вершин графа является выходом вектора связанныхвершин графа устройства, выход признака готовности и вход начальной установки блока анализа связности вершин графа являются соответственноодноименными выходом и входом устройства.2, Устройство по п, 1, о т л и -ч а ю щ е е с я тем, что блок анализа связности вершин графа. содержитарифметико-логический узел, три ре гистра, генератор импульсов, делительимпульсов, три элемента ИЛИ, дваблока элементов ИЛИ, причем информационный вход блока соединен с входомнакапливающего суммирования арифметико-логического узла и с первымивходами первого и второго блоковэлементов ИЛИ, выходы которых соединены с информационными входами первого и второго регистров соответственно, последовательный информационный выход и выход признака нулевого 35кода первого регистра соединен спервым входом первого элемента ИЛИи с входом запуска распределителяимпульсов соответственно выход гене.ратора импульсов соединен с входомсдвига первого регистра и с выходомопроса блока, вход начальной установки которого соединен с первыми входами второго и третьего элементов дИЛИ и с вторым входом первого элемента ИЛИ, выход которого соединенс выходом управления чтением блокаи с входом тактирования арифметико Ологического узла, выход результатакоторого соединен с вторым входом первого блока элементов ИЛИ и с информационным входом третьего рег,истра, выходкоторого соединен с входом перезаписи арифметико-логического узла, 55вторым входом второго блока элементовИЛИ и с выходом вектора связанныхвершин графа блока, а вход разрешения записи подключен к первому вы1464164ходу распределителя импульсов, второй выход которого соединен с управляющим входом арифметико-логического узла, третий выход распределителя импульсов соединен с выходом сброса блока и с вторым входом второго элемента И 3%, выход которого подключен к входу управления записью первого регистра, четвертый выход 10 распределителя импульсов соединен с вторым входом третьего элемента ИЛИи с входом разрешения перезаписиарифметико-логического узла, входвычитаемого которого соединен с выходом второго регистра, вход управления записью которого соединен с выходом третьего элемента ИЛИ, выходпризнака нулевого результата арифметико-логического узла соединен с вы"ходом признака готовности устройства.14641 64 Составитель 10,Тисленкодактор Н.Яцопа Техред А. Кравчук Корректор М Лароши Производственно"издательский комбинат "Патент", г. Ужгород, ул. Гагарина,101 Заказ ВНИИПИ б 52сударс Тираж 667 Подписноенного комитета по изобретениям и открытиям при ГКНТ ССС 3035, Москва, Ж, Рауаская наб., д. 4/5