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

ОПИСАНИЕИЗОБРЕТЕН ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоциалистическихРеспублик иц 752362во делец изобретений и открытий(72) Автор изобретения А, М, Щетинин Институт электродинамики АН Украинской ССР(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЗАДАЧ СЕТЕВОГО ПЛАНИРОВАНИЯ15 Изобретение относится к вычислительной технике и может быть использовано для решения задач теориии графов,Известно устройство для решения задач сетевого планирования, содержащее блок ввода-вывода, блок управления, генератор импульсов, блок автоматического формирования топологии, счетчик, блок вычисления ресурсов и блок моделей ветвей 1). Это устройство не обеспечивает нумерацию вершин графа,Наиболее близким по техническомурешению к предлагаемому является устройство, содержашее блок управления,генератор импульсов, модели вершин иуправляемый распределитель 2 .Недостатком этого устройства является то, что оно не позволяет решатьзадачу нумерации вершин графа.Цель изобретения - создание устройства, обеспечивающего нумерацию вершин графа,Поставленная цель достигается тем, что в устройство, содержащее генератор импульсов, выход которого подключен к первому входу блока управления, первый выход которого соединен с первыми входами моделей вершин и первой ячейки управляемого распределителя, первый вход каждой из ячеек распределителя, кроме первой, соединен с первым выходом предыдущей ячейки управляемого распределителя, второй выход блока управления подключен ко вторым входам ячеек управляемого распределителя, вторые выходы ячеек управляемого распределителя соединены со вторыми входами соответствующих моделей вершин, первый выход каждой модели вершин соединен с третьим входом соответствуюшей модели вершины в соответствии с топологией моделируемого графа; введен элемент ИЛИ, первый вход которого соединен с выходом последней ячейки управляемого распределителя, второй вход элемента ИЛИ подключен к третьему выходу блока управ 3 7523ления, выход элемента ИЛИ соединен счетвертыми входами моделей вершин, вторые выходы, моделей вершин подключенык четвертому входу соответствующейячейки управляемого распределителя, кро 5ме того, модель вершины содержит счетчик импульсов, два триггера и четыреэлемента И, первый вход первого из которых является первым входом модели,второй вход первого элемента И соединен 10с первым входом второго элемента И иподключен к первому выходу первого триггера, вход которого является вторымвходом модели, третьим и четвертымвходами которой являются соответственно первый и второй входы третьего элемента И, выход которого через второйтриггер подключен к первому входу четвертого элемента И, соединенному совторым входом второго элемента И, выход которого является вторым выходоммодели, первым выходом которой является выход четвертого элемента И, второйвход которого соединен со вторым выходом первого триггера, выход первого 25элемента И подключен ко входу счетчикаимпульсов.На чертеже представлена функциональная схема устройства.Устройство содержит модели 14 - 1 о30вершин, однотипные ячейки 24 - 2 г управляемого распределителя, блок 3 управления, генератор 4 импульсов и элемент5 ИЛИ,35Каждая модель 1 вершины, число которых соответствует количеству вершинзаданного графа, состоит из счетчика 6импульсов, триггеров 7, 8, элементов9 - 12 И. Модель 1) вершины предназ 40начена для формирования номера )ч; вершины графа и вице числа импульсов всчетчике 6,Каждая из моделей вершин своим входом 13 и выходом 14 соединена с осталь 45ными моделями вершин в соответствиис топологией заданного графа. Вход 15и выход 16 модели вершины соответственно соединены с разрядным выходом иустановочным входом соответствующей50однотипной ячейки управляемого распределителя.Управляемый распределитель, состоящий из идентичных ячеек 2, число которых равно числу вершин заданного графа,предназначен; для организации последовательного опроса моделей вершин, в которых сформирован номер в заданномграфе. В состав каждой ячейки 2 управ 62 фляелого распределителя входят триггеры17, 18, элементы 19 - 22 И.Устройство позволяет пронумероватьвершины графа с возрастанием от начальной к конечной вершинам,Устройство работает следующим образом.Первоначально счетчик 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 устанавливаются в нулевое состояние.5 752При появлении сигнала на установочномвходе (полюсе) 16 ячейки 2 распределителя через элемент 19 И устанавливается в единичное состояние триггер17 ячейки. Вследствие этого на нулевомего выходе, соединенным со входом элемента 20 И появляется запрещающий потенциал, а на единичном выходе - разрешающий,С появлением на полюсе 284 первого импульса серии ГИ 1, триггер 18 ячейки 2 ( управляемого распределителя через элемент 21 И устанавливается в единичное состояние (если триггер 17 этойячейки находился в единичном состоянии), 15Тем самым снимается разрешающий потенциал со входа элемента 19 И и подается разрешающий потенциал на элемент22 И. Импульс серии ГИ 2, следующий заимпульсом ГИ 1, поступает на полюс 30( 20ячейки и через элемент 22 И устанавливает триггер 17 в нулевое состояние, атакже проходит ьа разрядный выход ячейки (полюс 15,. Нулевое состояние триггера 17 выдает разрешение на прохождение импульсов ГИ 1 со входа 284 ячейкина ее выход 294 через элемент 20 И,С разрядного выхода этот импульс поступает на полюс 15 той модели вершины, у которой появляется сигнал формирования номера вершины графа на полюсе 16, и устанавливает триггер 8 в единичное состояние. Единичное состояние триггера 8 блокирует вход элемента 9 И и поэтому. в этой модели вершины в счетчик 6 не заносится больше ни один импульс ГИ 1, Кроме того, единичный выход триггера 8 выдает разреше 40 ние через элемент 11 И на выход модели 1 вершины (полюс) 14,Следующий импульс ГИ 1 поступает через полюса 27 в модели вершины, у которых не закончено формирование номе 45 ра вершины, и прибавляется к содержимому счетчика 6, что соответствует возрастанию нумерации от начальной вершины к конечной, Импульс ГИ 1 с полюса 28( первой ячейки 24 распределителя50 передается от ячейки к ячейке, пропус- . кая те ячейки, на входах элементов 1 9 И которых нет разрешения из моделей 1 вершин. Так импульс движения распространяется по распределителю, пока не по 55 явится на выходе 29 г, последней ячейки.Появившийся на выходе 29 д управляемого распределителя импульс пройдя элемент 5 ИЛИ, поступает через входы 362О(полюса) 26 на вход элемента 10 Ивсех моделей 1 вершин.Так как модели 1 вершин, для которых присвоен номер вершины, имеют высокий потенциал на выходе (полюс 14),то этот разрешающий сигнал поступаетиа входной полюс 12 моделей 1 вершинсогласно топологии заданного графа. Поэтому импульс с выхода распределителяпроходит через элемент 10 И в моделях1 вершин, на полосе 13 которых .присутствует разрешающий сигнал, и устанавливает триггер 7 в единичное состояние,Далее весь цикл работы устройстваповторятся аналогично описанному ранее.На полюсах 16 моделей 14 - 11 вершин появляются сигналы готовности нумерации, на основании которых последотельно производится нумерация вершин,графа. С каждым тактом в счетчик 6 заносится по одному импульсу ГИ 1, чтосоответствует возрастанию номера вершин по графу.Если в процессе цикла нумерацииоказывается, что две или более моделейвершин выдали сигнал готовности нумерации на полюсе 16, то в этом случаеустройство производит их нумерацию помере возрастания номера ячейки управляемого распределителя соответствующеймодели вершины. Это объясняется тем,что импульс ГИ 1 первым появляется наразрядном выходе той ячейки распределителя, которая ближе к его началу,Работа устройства продолжается циклза циклом до тех пор, пока не появитсясигнал на выходном полюсе 14 модели 1вершины, конечной по графу, По окончаниинумерации графа в счетчике 6 каждой модели 1 вершины находится число импульсов, пропорциональное номеру Й; вершины.Использование новых элементов - общего элемента ИЛИ, в каждой модели вершины второго триггера, второго, третьего и четвертого элементов И, включенныхв соответствующую схему, позволяетрешить задачу нумерации вершин графа.Нумерация вершин графа имеет большое практическое значение, Так, в частности, если граф (сетевой график) рассчитывается на устройстве с автоматическим формированием топологии, то правильно занумерованный граф позволяетсущественно повысить быстродействиеустройства за счет уменьшения времениформирования топологии.формула изобретения1. Устройство для решения задач сетевого планирования, содержащее генераИсточники информации,принятые во внимание при экспертизе 1. Авторское свидетельство СССР по заявке .М 2600771/18-24 кл. 6 06 6 7/122, 1978,2, Авторское свидетельство СССР Ио 570060, кл. 5 06 6 7/122, 1975, 7 7523тор импульсов, выход которого подключен к первому входу блока управления,первый выход которого соединен с первыми входами моделей вершин и первойячейки управляемого распределителя,первый вход каждой из ячеек распределителя, кроме первой, соединен с первымвыходом предыдущей ячейки управляемого распределителявторой выход блокауправления подключен ко вторым входамячеек управляемого распределителя, вторые выходы ячеек управляемого распределителя соединены со вторыми входамисоответствуюших моделей вершин, первыйвыход каждой модели вершин соединенс третьим входом соответствующей модели вершины в соответствии с топологиеймоделируемого графа, о т л и ч а ю -щ е е с я тем, что, с целью расширения функциональных возможностей за2 Осчет обеспечения нумерации вершин графа, в устройство введен элемент ИЛИ,первый вход которого соединен с выходом последней ячейки управляемого распределителя, второй вход элемента ИЛИподключен к третьему выходу блока управления, выход элемента ИЛИ соединен счетвертыми входами моделей вершин, вторые выходы моделей вершин подключенык четвертому входу соответствующейячейки управляемого распределителя. 62 82. Устройство по и. 1, о т л и ч аю щ е е с я тем, что модель вершины содержит счетчик импульсов, два триггера и четыре элемента И, первый вход первого из которых является первым входом модели, второй вход первого элемента И соединен с первым входом второго элемента И и подключен к первому выходу первого триггера, вход которого является вторым входом модели, третьим и четвертым входами которой, являются соответственно первый и второй входы третьего элемента И, выход которого через второй триггер подключен к первому входу четвертого элемента И, соединенному со вторым входом второго элемента И, выход которого является вторым выходом модели, первым выходом которой является выход четвертого элемента И, второй вход которого соединен со вторым выходом первого триггера, выход первого элемента И подключен ко входу счетчика импульсов.752362 Составитель И. Загорбининадактор Л. Веселовксая ТехредА.Щепанская Корректор Н, Григору 51 Подписноеого комитета СССРи открытийшская наб., д, 4/5 каз 4750/9 Тираж 7 ЦНИИПИ Государственн по делам изобретени 113035, Москва, Ж, Рау