Устройство для анализа параметров графа

 

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

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

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

РЕСПУБЛИК (я)з G 06 F 15/419

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

k 3

iQO

Ql ,О О

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4865192/24 (22) 25,07.90 (46) 30.12.92. Бюл. ¹ 48 (71) Институт проблем моделирования в энергетике АН УССР

{72) В.В.Васильев, O,Н.Голованова, Е.А.Ралдугин и В.Д.Бакуменко (56) Авторское свидетельство СССР

¹ 1413650, кл. G 06 G 7/122, 1986.

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

¹ 907552, кл. G 06 F 15/20, 1980. (54) УСТРОЙСТВО ДЛЯ АНАЛИЗА ПАРАМЕТРОВ ГРАФА

Изобретейие относится к специализированным вычислительным устройствам и может быть использовано для анализа графов и решения задач в графовой постановке, Известно устройство для анализа параметров графа, содержащее элементы задержки, триггеры, элементы И, ИЛИ, HE u наборные поля. Это устройство используется для определения внешнего радиуса любой вершины в графе.

Недостатком этого устройства является ручная коммутация, в соответствии с топологией анализируемого графа.

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

„„ Ы,, 1785000 А1

2 (57) Изобретение относится к вычислительной технике и может быть использовано при построении специализированных вычислительных устройств для исследования графов. Цель изобретения — расширение функциональных возможностей за счет осуществления процедуры поиска в глубину. Цель достигается эа счет того, что в состав каждой модели вершины и блока управления перебором вершин введены триггер, блок элементов И, блок формирования сигналов управления.

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

И, к третьему выходу модели и к первому первый и второй регистры сдвига, триггер, входу шестого элемента И, второй вход ко- 5 первый, второй, третий и четвертый элементорого соединен с пятым входом модели и с ты И, элемент ИЛИ, первый вход которого первым входом седьмого элемента И, выход подключен к выходу третьего элемента И, которого подключен к первому входу треть- первый вход которого подключен к первому его элемента ИЛИ, выход которого соеди- входувторогоэлементаИиявляется входом нен с четвертым выходом модели, шестой 10 сигнала опроса модели, первый вход первовход "которой подключен к первому входу ro элемента И подключен ко второму входу восьмого элемента И, выход которого сое- ipeTbего элемента И и к выходу первого динен с вторым входом третьего элемента регистра сдвига, входы реверса и сдвига

ИЛИ, выход первого элемента И подключен второго регистра сдвига являются соответк второму входу второго элемента ИЛИ и к 15 ственно входами реверса и сдвига модели, единичному входу первого разряда первого первый вход четвертого.элемента И подклюрегистра, нулевой выход первого разряда чен к выходу триггера, дополнительно ввекоторогосоединенсвторымвходомседьмо- даны в каждую модель вершины первый и — го элемента И, выход второго элемента И второй элементы НЕ, блок элементов И, выподключен к первому входучетвертого зле- 20 ход которого является информационным мента ИЛИ, второй вход которого соединен выходом модели, первый вход — входом зас выходом шестого элемента И и с единич- дания кода номера вершины, а второй вход ным входом четвертого триггера, единич- подключен к выходу младшего разряда втоный выход которого подключен к второму рого регистра сдвига, вход записи которого входу восьмога элемента И, выход первого 25 подключен ко второму входу элемента ИЛИ элемента ИЛИ соединен с нулевым входом... и является входом задания начальной вертретьего триггера и с нулевым входом пер- шины модели, а вход управления записью ваго разряда второго регистра, вход сдвига подключен к выходу четвертого элемента И, . и вход реверса которого соединен соответ- второй вход которого подключен к выходу ственно с входом сдвига и с входом реверса 30 третьего элемента И, выход элемента ИЛИ первого регистра и подключены соответст-, подключен к установочному входу триггера, венно к седьмому входу модели, выход чет- выход которого подключен ко второму входу вертого элемента ИЛИ является выходным первого элемента И, выход которого подполюсом модели.: . -: ключен к входам соответственно первого и

Недостаток этого устройства — невоз- 35 второго элементов HE. выход йервого из можность решения широко распространен- которых является осведомительным выхоной задачи пометки вершин графа методом . дом модели, а выход второго подключен Ко поиска в глубину и ручная коммутация свя- второму входу второго элемента И, выход зей в графе;: которого является вйходом сигнала опроса

Цель изобретения — расширение класса 40 модели, вторым входом сдвига которой яврешаемых задач за счет осуществления про- ляется вход первого регистра сдвига, а блок цедуры поиска в глубину. Поставленная управления перебором вершин содержит. цель достигается тем, что в устройстве для блок формирования сигналов управления, анализа параметров графа, содержащем первый и второй элементы И, элемент:: блокуправления перебором вершин, группу 45 ИЛИ, первый и второй счетчики импульсов, последовательно соединенных моделей триггер, генератор импульсов; выход котовершин, причем выход сигнала опроса рого подключен соответственно к первым предыдущей модели вершины группы под- входам первого и второго элементов И, втоключен к входу сигнала опроса последую- рые входы которых подключены соответстщей модели вершины группы, вход сигнала 50 венно к прямому и обратному выходам опроса первой модели вершины группы триггера, выход второго элемента И подподключен к выходу опроса блока управле- ключен к входу запуска блока формир6вания перебором вершин, выход сигнала ðå- ния сигналов управления, а выход первого верса, первый выход сигнала сдвига, вход элемента И является вторым аыходом сигосведомительного сигнала и информацион- 55 нала сдвига блока и подключен к входу выный вход которого подключены соответст- читания первого счетчика импульсов и ко венно к группб входов реверса. к первой входу второго счетчика импульсов, выход группе входов сдвига, к группе осведоми- которого подключен к первому входу элетельных выходов и к группе информацион- мента ИЛИ, выход которого подключен к ных выходов моделей вершин группы; а установочному входутриггера, второй вход

1785000 является входом управления пуском блока, 30 опроса модели 2 вершины, В групп вхоа третий вход подключен к выходу первого дов 31 задания кода номера вершины. счетчика импульсов, установочный вход Множество моделей 2 вершин, связанкоторого подключен к информационному ных с блоком 1 управления образуют паралвходублокаформированиясигналовуправ- 5 лельную моделирующую структуру, в ления и является информационным входом которой все В одноименных полюсов 23, 24, блока, а вход стробирования подключен к 25, 26, 28 электрически соединены вместе. тактовому выходу блока формирования сиг- Выходной полюс 29 К-ой модели 2 вершины налов управления, выход сброса которого соединен с входным полюсом 30 К - 1-й подключен к входу сброса триггера, а выхо- 10 модели 2 вершины. ды опроса, реверса, сдвига и осведомитель- Устройство работает следующим обраный вход, являются соответственно 30М. выходами сигнала опроса, сигнала реверса, Пусть необходимо сформировать спипервым выходом сигнала сдвига и входом сок вершин графа, начиная с заданной, в осведомительного сигнала блока, причем 15 порядке, определяемом процедурой поиска второйвыходсигналасдвигаблокауправле- в глубину на графе, структура которого ния перебором вершин подключен ко вто- представлена на фиг. 2. Зададим в качестве рой группе входов сдвига моделей вершин начальной вершину с номером 1. группы, группы входов задания начальной Перед началом работы в регистры 4 вершины и задания кода номера вершйны 20 сдвига первой группы заносится информакоторой являются соответственно первой и ция о структуре связей в графе, Триггеры 3 второй группами входов задания устройст- устанавливаются в исходное единичное сова, а выход сигнала опроса последней моде- стояние, Регистры 5 сдвига второй групйы в ли вершины группы является выходом исходном состоянии настроены на сдвиг в устройства. 25 сторону старших разрядов (прямой ход) и

На фиг. 1 представлена функциональ- содержат нули во всех разрядах, Блок 15 ная схема устройства для анализа парамет- формирования сигналоЬ управления в ис-. ров графа; на фиг.2 — пример анализируемого ходном состоянии не вырабатывает никаких графа; на фиг, 3 — блок-схема алгоритма фун- сигналов на своих выходах (1) — (5). кционирования устройства, 30 Сигналом пуска на полюсе 22; прошедУстройство содержит блок 1 управле- шим через элемент 21 ИЛИ блока 1 управния, перебором вершин, модель 2 вершины, ления перебором вершин, устанавливается повторенную В раз ( — число вершин в в единицу триггер 18 блока 1 и запускается графе). Здесь и далее цифрами в скобках, генератор14импульсов,импульсы которого стоящим после номеровпозиций на чертеже, 35 через элемент 19 И блока 1 поступают на обозначены порядковые номера совершенно вход (2) блока формирования сигналов уподинаковых по своему функциональному на- равления. Под действием этих импульсов значению и техническому исполнению бло- . блок 15 начинает формировать сигналы упков, уэлов и элементов, а просто цифрами в равления. Одновременно с этим сигнал пускобках возле контуров блоков и узлов — 40 ска поступает на К-й .полюс 27 задания порядковые номера входов и выходов дан- начальной вершины. По сигйалу на последного блока или узла. В каждую модель 2 нем полюсе устанавливается s нулевое совершины входит триггер 3, регистры 4, 5 стояние К-й триггер 3 и записывается . сдвига, элементы 6, 7, 8, 9, И, элементы 10 единица в младший (первый) разряд К-го . ИЛИ, элементы 11,.12 НЕ, блок элементов 45 регистра 5 сдвига, На К-ой группе входов 31

13 И из М элементов (M =- log28). Блок 1 задания кода вершины присутствует код, управления перебором вершин включает ге-. соответствующий номеру К-ой вершины, конератор 14 импульсов, блок формирования тарый передается на информационные высигналов управления 15, счетчики 16; 17 им- ходы 26 устройства через блок 13 элементов пульсов,триггер 18, элементы 19,20 И,эле- 50 И. На выходе (4) вырабатывается импульс мент 21 ИЛИ. стробирования счетчика 16 импульсов. По

Кроме этого, на фиг, 1 цифровые обоз- этому сигналу код номера вершины (1) заноначения имеют вход 22 управления пуском, сится в счетчик 16 импульсов. Затем выраосведомительный вход 23 блока 1 управле- батывается сигнал на выходе (5), который ния, перебором вершин, выход 24 реверса 55 переводит в нулевое состояние триггер 18 блока 1, первый выход 25 сдвига блока 1, блока 1: элемент 19 И блока 1 закрывается, информационный выход 26 устройства, В а элемент 20 И того ие блока открывается, входов 27 задания начальной вершины гра- и тактовые импульсы начинают поступать на фа, второй выход 28 сдвига блока 1 управле- входы счетчиков 16, 17 импульсов и на пония, выход 29 опроса модели 2 вершин, вход люс 28. T.ê, в счетчик 16 импульсов записан

1785000

15 код 1 и он работает на вычитание, то, приняв один импульс, он сформирует сигнал обнуления, который через элемент 21 ИЛИ блока

1 переведет триггер 18 в единицу. Подача тактовых импульсов на полюс.28 прекратится. Таким образом, на выход 28 сигнала сдвига блока 1 управления поступит один импульс, который одновременно сдвинет все регистры 4 на один разряд. В регистрах

4 моделей (2) и (3) вершин на выходе сформируется сигнал единицы, Переключение триггера 18 в единицу продолжит работу блока формирования сигналов управления

15 под действием тактовых импульсов на

его входе (2): опрашивается состояние осведомительного сигнала на полюсе 23. На выходах элементов 12 НЕ в моделях (2) и (3) вершин к этому моменту сформируются нулевые сигналы, поэтому и на полюсе 23 будет такой же сигнал, При нулевом сигнале нэ полюсе 23 формируется импульс сдвига, поступающий с выхода (3) на полюс 25.

Сдвиг регистров 5 второй группы на один разряд приводит к тому, что на информационнных выходах 26 пропадает код номера вершин (1), Затем сигнал с полюса 30. проходит через первый элемент 7 И, появляется на полюсе 29 узла 2 (1) вершины, поступает на полюс 30 модели 2 (2) вершины, на выход

29 которой уже не проходит, т.к, на выходе элемента 11 HE в этом узле в данный момент присутствует нулевой сигнал, В этой модели 2(2) вершины сигнала опроса с полюса 30 пройдет через элементы 6, 7. И и запишет единицу в младший разряд регистра 5 сдвига, выходной сигнал которого через элементы И блока 13 установит на информационных выходах 26 устройства код верши- ны (2). Блоки 13 элементов И в остальных моделях вершин в этот момент закрыты нулевым сигналом с выходов регистров 5 сдвига, Заметим, что всякий раз нэ соответствующем такте единица записывается только в один регистр 5 сдвига. После этого триггер 18 блока 1 переводится в нулевое состояние, и тактовые сигналы с выхода элемента 20 И продолжают заполнение счетчиков 16, 17 импульсов блока 1 управления и сдвиг регистров 4. Импульс переполнения счетчика 17 импульсов вернет триггер 18 в единичное состояние. К этому моменту информация в кольцевых регистрах 4 восстано. вит исходное состояние. На информационных выходах 26 устройства установлен код вершины (2), регистр 4 находится в исходном состоянии и можно продолжить процедуру поиска в глубину и формирование списка номеров вершин, Блок 15 формирования сигналов управления формирует импульс стробировэния для счетчика 16 блока 1 управления, в который теперь занесется код вершины (2), и описанный выше процесс повторится. В ходе поиска в глубину триггеры 3 в моделях 2 вершин переводятся в нулевое состояние, а коды номеров вершин выдаются нэ информационные выходы 26 устройства.

Пусть в ходе выполнения описанных действий на полюсах 26 сформирован код вершины (5). К этому моменту все триггеры

3 уже переведены в нулевое состояние, поэтому на полюсе 23 сформируется сигнал единичного уровня, после опроса которого блок 15 перейдет к выполнению обратного хода: установит признак обратного хода на полюсе 24 и затем сдвинет регистры 5 на один разряд назад. В результате возврата на полюсах 26 установится код вершины (4).

Далее идут описанные уже действия по передаче кода вершины в счетчик 16 импульсов, отсчет импульсов счетчиками 16, 17 и одновременный сдвиг регистров 4. Опрос осведомительного сигнала на полюсе 23 снова покажет наличие единицы, т,е. из вершины (4) при заданной в примере структуре графа тоже нельзя продолжить движение в глубину(прямой ход), т.к, триггеры 3 переведены в нулевое состояние. Сравнив после этого код на полюсах 26 с кодом, в котором во всех разрядах присутствуют единицы (признак окончания процедуры поиска) и получив отрицательный ответ, блок 15 проведет новый цикл возврата. Если после очередного шага возврата осведомительный сигнал на полюсе 23 примет нулевое значение, то это будет означать, что еще есть непросмотренные вершины, и устройство продолжит работу, перейдя в режим прямого хода. В рассматриваемом примере непомеченных вершин уже нет, поэтому после пяти циклов возврата на полюсах 26 образуется код с единицами во всех разрядах, т.к, после пяти сдвигов в сторону младших разрядов информация во всех регистрах 5 сотрется, что и будет признаком конца процедуры поиска, На фиг.,3 приведена блок-схема алгоритма функционирования устройства для анализа параметров графа.

Начала — инициализация устройства и формирование сигнала пуска.

Блок 32- запись кода номера вершины в счетчик 16 импульсов блока управления, перебором вершин..

Блок 33 — формирование импульсов сдвига регистров 4,с участием счетчиков

16, 17.

Блок 34 — анализ состояния осведомительного сигнала на полюсе 23, Если "0"— перейти на блок 35, иначе —. на блок 37.

1785000

Блок 35 — подача одиночного импульса гистра сдвига являются соответственно вхосдвига на полюс 25 для сдвига регистров 5. дами реверса и сдвига модели, первый вход

Блок 36 — подача одиночного импульса четвертого элемента И подключен к выходу на полюс 30, связанный с выходом (1) блока . триггера, о т л и ч а ю щ е е с я тем, что, с

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

Блок 38 — подача одиночного импульса сдвига блока управления перебором верна полюс 25 для сдвига назад регистров 5. шин подключен к второй группе входов

Блок 39 — передача кода номера верши- 10 сдвига моделей вершин группы, группы вхоны в счетчик (6) (аналогично блоку 32). дов задания начальной вершины и задания

Блок 40- сдвиг регистров 4 (аналогично . кода номера вершины которой являются соблоку 33). ответственно первой и второй группами

Блок 41 — то же, что и в блоке 34. Если входов задания устройства, а выход сигнала

"0" — перейти на блок42, иначе- на блок 43. 15 опроса последней модели вершины группы

Блок 42 — установить признак прямого является выходом устройства, причем в кажхода на полюсе 24 и перейти на блок 35. дую модель вершины введены первый и втоБлок 43 — сравнить код на полюсах 26 с рой элементы НЕ, блок элементов И, выход кодом, содержащим единицы во всех разря- которого является информационным выходах, Если "0" — то перейти на блок 38, иначе 20 дом модели, первый вход — входом задания — конец, кода номера вершины, а второй вход подИспользование изобретения позволяет ключен к выходу младшего разряда второго распараллелить на аппаратном уровне r1po-" регйстра сдвига, вход записи которого подцесс поиска, а также обеспечивает опреде- ключен к второму входу элемента ИЛИ и ленную степень универсальности в области 25 является входом задания начальной верширешения задач на графах для специализиро- . ны модели, а вход управления записью подванных вычислительных систеМ. ключен к выходу четвертого элемента И, второй вход которого подключен к выходу

Ф о р м у л а и з о б р е т е н и я - третьего элемента И, выход элемента ИЛИ

Устройство для анализа параметров 30 подключен к установочному входу триггера, графа, содержащее блок управления пере- выход которого подключен к второму входу .бором вершин, группу последовательносо- первого элемента И, выход которого подединенных моделей вершин, причем выход ключен к входам соответственно первого и сигнала опроса предыдущей модели верши- второго элементов НЕ, выход первого из ны группы подключен к входу сигнала опро- 35 которых является осведомительным выхо.са последующей модели вершины группы, дом модели, а выход второго подключен к вход сигнала опроса первой модели верши- второму входу второго элемента И, выход ны группы подключен к выходу опроса бло- которого является выходом сигнала опроса ка управления перебором вершин, выход устройства, вторым входом сдвига которого сигнала реверса, первый выход сигнала 40 является вход первого регистра сдвига, а сдвига, вход осведомительного сигнала и блок управления перебором вершин содеринформационный вход которого подключе- жит блок формирования сигналов управлены соответственно к группе входов реверса, ния, первый и второй элементы И, элемент первой группе входов сдвига, группе осве- ., ИЛИ, первый и второй счетчики импульсов, домительных выходов и к группе информа- 45 триггер, генератор импульсов, вйход котоционных выходов моделей вершин группы,: рого подключен соответственно к первым а вход управления пуском блока управления входам первого и второго элементов И, втоперебором вершин является входом пуска рые входы которых подключены соответстустройства, причем каждая модель верши- венно к прямому и обратному выходам ны группы содержит первый и второй реги- 50 триггера, выход второго элемента И подстры сдвига, триггер, первый второй, ключен к входу запуска блока формироватретий и четвертый элементы И, элемент ния сигналов управления, а выход первого

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

1Т85000 а третий вход подключен к выходу первого счетчика импульсов, установочный вход которого подключен к информационному входу блока формирования сигналов управления и является информационным входом блока, а вход стробирования подключен к тактовому выходу блока формирования сигналов управления, выход сброса которого подключен к входу сброса триггера, а выходы опроса, реверса, сдвига и осведомительный вход являются соответственно

5 выходами сигнала опроса, сигнала реверса, первым выходом сигнала сдвига и входом осведомительного сигнала блока.

1785000

NumgugO СЮЕ цнОСлри, ф

Фиа Г

Фиг.3

Составитель О.Голованова

Техред М,Моргентал Корректор О.Густи

Редактор В.Коляда

Заказ 4366 Тираж Подписное

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

113035, Москва, Ж 35, Раушская наб., 4/5

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