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

 

ОП И(: НИЕ

ИЗОБРЕТЕН ИЯ

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

Союз Советских

Социалистических

Республик (ц 752362 (61) Дополнительное к авт. свид-ву— (22)Заявлено 10.07.78(21) 2642986/18 24 с присоединением заявки,%— (23) Приоритет—

Опубликовано 30.07.80. Бюллетень У&28

Дата опубликования описания 02.08.80

G 06 G 7/122

Государственный квинтет ссср но делан изобретений и открытий (53) УД К 681, .333(088,8) (72) Автор изобретения

А. М. Щетинин

Институт электродинамики АН Украинской ССР (71) Заявитель (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ СЕТЕВОГО

ПЛАНИРОВАНИЯ

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

Это устройство не обеспечивает нумерацию вершин графа.

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

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

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

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

На чертеже представлена функциональная схема устройства.

Устройство содержит модели 14 - 1д 30 вершин, оцн от и пн ые ячейки 2 4 - 2 г управляемого распределителя, блок 3 управления, генератор 4 импульсов и элемент

5 ИЛИ, 35

Каждая модель 1 вершины, число которых соответствует количеству вершин заданного графа, состоит из счетчика 6 импульсов, триггеров 7, 8, элементов

9 - 1 2 И. Модель 1 вершины предназ40 начена цля формирования номера N; вершины графа и вице числа импульсов в счетчике 6.

Каждая из моделей вершин своим входом 13 и выходом 14 соединена с осталь45 ными моделями вершин в соответствии с топологией заданного графа. Вход 15 и выход 16 модели вершины соответственно соединены с разрядным выходом и установочным входом соответствующей

S0 однотипной ячейки управляемого распределителя.

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

17, 18, элементы 19 - 22 И.

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

Первоначально счетчик 6, триггеры

7, 8 всех моделей вершин и триггеры

17, 18 всех однотипных ячеек управляемого распределителя устанавливаются в нулевое состояние. На вход 13 модели вершин, которая является начальной вершиной графа, подается разрешающий потенциал (установочные шины на чертеже не показаны).

Процесс нумерации вершин графа начинается с момента подачи импульса Пуск блоком 3 управления, в функции которого входит также выработка на полюсах 23, 24 импульсов ГИ1 и ГИ2, сдвинутых относительно друг друга.

Импульс "Пуск с полюса 25 блока 3 управления поступает через элемент 5

ИЛИ на входы 26 всех моделей 1 вершин„Так как разрешающий потенциал присутствует на входе 1 3 модели 1 только начальной вершины, то импульс Пуск" проходит в ней через элемент 10 И и устанавливает триггер 7. в единичное состояние. В результате на входах элемента 12 И появляется разрешение с нулевого выхода триггера 8 и единичного выхода триггера 7, которое проходит через элемент

12 И, выход 16 на установочный вход соответствующей ячейки 2 управляемого распределителя. Иалее сигнал проходит через элемент.19 И, на втором входе которого присутствует разрешение с нулевого триггера 1 8, и устанавливает триггер 17 в единичное состояние.

Первый импульс ГИ1 с выхода (полюс 23) блока управления 3 поступает на полюса 27 всех моделей вершин. Пройдя в каждой модели через элемент 9 И, на втором входе которого присутствует разрешение,, импульс ГИ1 прибавляется к содержимому счетчика 6. Кроме того, этот же импульс ГИ1 поступает на вход (полюс 28) первой ячейки 2 управляемого распределителя и распространяется по распределителю, пока не доходит до выбранной ячейки, которая соответствует модели вершины, сформировавшей номер в графе.

Происходит это следующим образом.

Предварительно .триггеры 17 и 1 8 устанавливаются в нулевое состояние.

S 752

При появлении сигнала на установочном входе (полюсе) 16 ячейки 2j распределителя через элемент 19 И устанавливается в единичное состояние триггер

17 ячейки. Вследствие этого на нулевом

его выходе, соединенным со входом элемента 20 И появляется запрещающий потенциал, а на единичном выходе - разрешающий, С появлением на полюсе 284 перво- 10 го импульса серии ГИ1, триггер 18 ячейки 2 (управляемого распределителя через элемент 21 И устанавливается в единичное состояние (если триггер 17 этой ячейки находился в единичном состоянии). 15

Тем самым снимается разрешающий потенциал со входа элемента 19 И и подается разрешающий потенциал на элемент

22 И. Импульс серии ГИ2, следующий за импульсом ГИ1, поступает на полюс 30(20 ячейки и через элемент 22 И устанавливает триггер 17 в нулевое состояние, а также проходит ь,", разрядный выход ячейки (полюс 15 ) . Нулевое состояние триггера 17 выдает разрешение на прохожде- 25 ние импульсов ГИ1 со входа 284 ячейки на ее выход 294 через элемент 20 И.

С разрядного выхода этот импульс поступает на полюс 15 той модели вершины, у которой появляется сигнал формирования номера вершины графа на полюсе 16, и устанавливает триггер 8 в единичное состояние. Единичное состояние триггера 8 блокирует вход элемента

9 И и поэтому в этой модели вершины в счетчик 6 не заносится больше ни один импульс ГИ1. Кроме того, единичный выход триггера 8 выдает разреше40 ние через элемент 11 И на выход модели 1 вершины (полюс) 14.

Следующий импульс ГИ1 поступает через полюса 27 в модели вершины, у которых не закончено формирование номе45 ра вершины, и прибавляется к содержимому счетчика 6, что соответствует возрастанию нумерации от начальной вершины к конечной. Импульс ГИ1 с полюса

28(первой ячейки 2А распределителя

50 передается от ячейки к ячейке, пропус- . кая те ячейки, на входах элементов 1 9

И которых нет разрешения из моделей 1 вершин. Так импульс движения распространяется по распределителю, пока не по55 явится на выходе 29г, последней ячейки.

Появившийся на выходе 29д управляемого распределителя импульс пройдя элемент 5 ИЛИ, поступает через входы

362 6 (полюса) 26 на вход элемента 10 И все х моделей 1 ве р шин.

Так как модели 1 вершин, для которых присвоен номер вершины, имеют высокий потенциал на выходе (полюс 14), то этот разрешающий сигнал поступает иа входной полюс 12 моделей 1 вершин согласно топологии заданного графа. Поэтому импульс с выхода распределителя проходит через элемент 10 И в моделях

1 вершин, на полосе 13 которых .присутствует разрешающий сигнал, и устанавливает триггер 7 в единичное состояние.

Далее весь цикл работы устройства повторя тся аналогично описанному ранее.

На полюсах 16 моделей 14 — 1 1 вершин появляются сигналы готовности ну« мерации, на основании которых последотельно производится нумерация вершин, графа. С каждым тактом в счетчик 6 заносится по одному импульсу ГИ1, что соответствует возрастанию номера вершин по графу.

Если в процессе цикла нумерации оказывается, что две или более моделей вершин выдали сигнал готовности нумерации на полюсе 16, то в этом случае устройство производит их нумерацию по мере возрастания номера ячейки управляемого распределителя соответствующей модели вершины. Это объясняется тем, что импульс ГИ1 первым появляется на разрядном выходе той ячейки распределителя, которая ближе к его началу.

Работа устройства продолжается цикл за циклом до тех пор, пока не появится сигнал на выходном полюсе 14 модели 1 вершины, конечной по графу. По окончании нумерации графа в счетчике 6 каждой модели 1 вершины находится число импульсов, пропорциональное номеру Й; вершины.

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

Нумерация вершин графа имеет большое практическое значение. Так, в частности, если граф (сетевой график) рассчитывается на устройстве с автоматическим формированием топологии, то пра вильно занумерованный граф позволяет существенно повысить быстродействие устройства за счет уменьшения времени формирования топологии.

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

1. Устройство для решения задач сетевого планирования, содержащее генераИсточники информации, принятые во внимание при экспертизе

1. Авторское свидетельство СССР по заявке . No 2600771/18-24 кл. G 06 S 7/122, 1978.

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

N 570060, кл. 5 06 5 7/122, 1975.

7 7523 тор импульсов, выход которого подключен к первому входу блока управления, первый выход которого соединен с первыми входами моделей вершин и первой ячейки управляемого распределителя, первый вход каждой из ячеек распределителя, кроме первой, соединен с первым выходом предыдущей ячейки управляемого распределителя, второй выход блока управления подключен ко вторым входам ячеек управляемого распределителя, вторые выходы ячеек управляемого распределителя соединены со вторыми входами соответствуюших моделей вершин, первый выход каждой модели вершин соединен с третьим входом соответствующей модели вершины в соответствии с топологией моделируемого графа, о т л и ч а ю— щ е е с я тем, что, с целью расширения функциональных возможностей за

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

62 8

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

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

752362

Составитель И. Загорбинина

Редактор Л. Веселовксая ТехредА.Щепанская Корректор Н. Григорук

Заказ 4750/9 Тираж 751 Подписное

ЦНИИПИ Государственного комитета СССР по делам изобретений и открытий

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

Филиал ППП "Патент, r. Ужгород, ул. Проектная, 4