Устройство для решения задач сетевого планирования Советский патент 1980 года по МПК G06G7/122 

1

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

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

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

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

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

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

Поставленная цель достигается тем, что в устройство, содержащее генератор импульсов, выход которого подключен к первому входу блока управления, первый выход которого соединен с первыми входами моделей вершин и первой ячейки управляемого распределителя, первый вкод каждой из ячеек распределителя, кроме первой, соединен с первым выходом предыдущей ячейки управляемого распределителя, второй выход блока управления подключен ко вторым входам ячеек управляемого распределителя, вторые выходы ячеек управляемого распределителя соединены со вторыми входами соответствующих моделей вершин, первый выход каждой модели вершин соединен с третьим входом соответствующей модели вершины в соответствии с топологией моделируемого графа; введен элемент ИЛИ, первый вход которого соединен с выходом последней ячейки управляемого распределителя, второй вход элемента ИЛИ под ключей к третьему выходу блока управ- пения, выхоц элемента ИЛИ соединен с чегвертыми входами моделей вершин, вто рые выходы .моделей вершин подключены к четвертому входу соответствующей ячейки управляемого распределителя, кро ме того, модель вершины содержит счет- чик импульсов, два триггера и четыре элемента И, первый вкод первого из которых является первым вкодом модели, второй вкод первого элемента И соединен с первым входом второго элемента И и подключен к первому выходу первого три гера, вход которого является вторым входом модели, третьим и четвертым входами которой являются соответственно первый и второй входы третьего элемента И, выход которого через второй триггер подкгаочен к первому входу четвертого элемента И, соединенному со вторым входом второго элемента И, выход которого является вторым выходом модели, первым выходом которой является выход четвертого элемента И, второй вход которого соединен со вторым выходом первого триггера, выход первого элемента И подключен ко входу счетчика импульсов. На чертеже представлена функциональная схема устройства. Устройство содержит модели 1 - Ip вершин, однотипные ячейки 2 - 2 упра ляемого распределителя, блок 3 управления, генератор 4 импульсов и элемент 5 ИЛИ. Каждая модель 1 вершины, число которых соответствует количеству вершин заданного графа, состоит из счетчика 6 импульсов, триггеров 7, 8, элементов 9 - 12 И. А одель 1 | вершины предназ начена для формирования номера N вер шины графа в виде числа импульсов в счетчике 6. Каждая из моделе вершин своим вхо дом 13 и выходом 14 соединена с остал ными моделями вершин в соответствии с топологией заданного графа. Вход 15 и выход 16 модели вершинь соответстве но соединены с разрядным выходом и установочным входом соответствующей однотипной ячейки управляемого распределителя. Управляемый распределитель, состоящий из идентичных ячеек 2, число которых равно числу вершин заданного графа предназначен: для организации последовательного опроса моделей вершин, в которых сформирован номер в заданном графе. В состав каждой ячейки 2 управяб,-а1ого распределителя входят триггеры 17, 18, элементы 19-22 И. Устройство позволяет пронумеровать вершины графа с возрастанием от начальной к конечной вершинам. Устройство работает следующим образом. Первоначально счетчик 6, триггеры 7, 8 всех моделей вершин и триггеры 17, 18 всех однотипных ячеек управляемого распределителя устанавливаются в нулевое состояние. На вход 13 модели вершин, которая является начальной вершиной графа, подается разрешающий потенциал (установочные шины на чертеже не показаны). Процесс нумерации вершин графа начинается с момента подачи импульса Пуск блоком 3 управления, в функции которого входит также выработка на полюсах 23, 24 импульсов ГИ1 и ГИ2, сдвинутых относительно друг друга. Пуск с полюса 25 блока 3 управления поступает через элемент 5 ИЛИ на входы 26 всех моделей 1 вершин. Так как разрешающий потенциал присутствует на входе 13 модели 1 только начальой вершины, то импульс Пуск проходит в ней через элемент 10 И и устанавливает триггер 7 в единичное состояние. В результате на входах элемента 1.2 И появляется разрешение с нулевого выхода триггера 8 и единичного выхода триггера 7, которое проходит через элемент 12 И, выход 16 на установочный вход соответствующей ячейки 2 управляемого распределителя. Далее сигнал проходит через элемент. 19 И, на втором входе которого присутствует разрешение с нулевого триггера 18, и устанавливает триггер 17 в единичное состояние. Первый импульс ГИ1 с выхода (полюс 23) блока управления 3 поступает на полюса 27 всех моделей вершин. Пройдя в каждой модели через элемент 9 И, на втором входе которого присутствует разрешение,, импульс ГИ1 прибавляется к содержимому счетчика 6. Кроме того, этот же импульс ГИ1 поступает на вход (полюс 28) первой ячейки 2 управляемого распределителя и распространяется по распределителю, пока не доходит до выбранной ячейки, которая соответствует Модели вершины, сформировавшей номер в графе. Происходит это следующим образом. Предварительно .триггеры 17 и 18 устанавливаются в нулевое состояние. При ноявлении сигнала на установочном входе (полюсе) 16 ячейки 2- распределителя через элемент 19 И устанавливается в елиничное состояние триггер 17 ячейки. Вследствие этого на нулевом его выходе, соединенным со входом эле мента 20 И появляется запрещающий потенциал, а на единичном выходе - разрешающий. С появлением на полюсе 28 первого импульса серии ГИ1, триггер 18 ячей ки 2 управляемого распределителя через элемент 21 И устанавливается в еди ничное состояние (если триггер 17 этой ячейки находился в единичном состоянии) Тем самым снимается разрешающий потенциал со входа элемента 19 И и подается разрешающий потенциал на элемент 22 И. Импульс серии ГИ2, следующий за импульсом ГИ1, поступает на полюс ЗО;| ячейки и через элемент 22 И устанавливает триггер 17 в нулевое состояние, а также проходит iif. разрядный выход ячей ки (полюс 15). Нулевое состояние триг гера 17 выдает разрешение на прохождение импульсов ГИ1 со входа 28 ячейки на ее выход 29/( через элемент 20 И. С разрядного выхода этот импульс поступает на полюс 15 той модели- вершины, у которой появляется сигнал формирования номера вершины графа на полюсе 16, и устанавливает триггер 8 в единичное состояние. Единичное состояние триггера 8 блокирует вход элемента 9 И и поэтому в этой модели вершины в счетчик 6 не заносится больше ни один импульс ГИ1. Кроме того, единичный выход триггера 8 выдает разрешение через элемент 11 И на выход модели 1 вершины (полюс) 14. Следующий импульс ГИ1 поступает через полюса 27 в модели вершины, у которых не закончено формирование номе ра вершины, и прибавляется к содержимому счетчика 6, что соответствует возрастанию нумерации от начальной вершины к конечной. Импульс ГИ1 с полюса 28i первой ячейки 2, распределителя передается от ячейки к ячейке, пропус- . кая те ячейки, на входах элементов 19 И которых нет разрешения из моделей 1 вершин. Так импульс движения распространяется по распределителю, пока не появится на выходе 29г последней ячейки. Появившийся на выходе 29. управляемого распределителя импyльcJ пройдя элемент 5 ИЛИ, поступает через входы (полюса) 26 на вход элемента 10 И всех моделей 1 вершин. Так как модели 1 вершин, для которых присвоен номер вершины, имеют высокий потенциал на выходе (полюс 14), то этот разрешающий сигнал поступает На входной полюс 12 моделей 1 вершин согласно топологии заданного графа. Поэтому 1Пу1пульс с выхода распределителя проходит через элемент 10 И в моделях 1 вершин, на полосе 13 которых :присут- ствует разрешающий сигнал, и устанавливает триггер 7 в единичное состояние. Далее весь цикл работы устройства , повторяется аналогично описанному ранее. На полюсах 16 моделей 1 - 1 вершим появляются сигналы готовности нумерации, на основании которых последотельно производится нумерация вершин . графа. С каждым тактом в счетчик 6 заносится по одному тч1пульсу ГИ1, что соответствует возрастанию номера шин по графу. Если в процессе цикла нумерации оказывается, что две 1ши более моделей вершин выдали сигнал готовности нумерации на полюсе 16, то в этом случае устройство производит их нумерацию по мере возрастания номера ячейки управляемого распределителя соответствующей модели вершины. Это объясняется тем, что импульс ГИ1 первым появляется на разрядном выходе той ячейки распределителя, которая ближе к его началу. Работа устройства продолжается цикл за циклом до тех пор, пока не появится сигнал на выходном полюсе 14 модели 1 вершины, конечной по графу. По окончании нумерации графа в счетчике 6 каждой модели 1 вершины находится число импульсов, пропорциональное номеру N , вершины. Использование новых элементов - общего элемента ИЛИ, в каждой модели вершины второго триггера, второго, третьего и четвертого элементов И, включенных в соответствующую схему, позволяет решить задачу нумерации вершин графа. Нумерация вершин графа имеет большое практическое значение. Так, в частности, если граф (сетевой график) рассчитывается на устройстве с автоматическим формированием топологиИ5 то правильно занумерованный граф позволяет существенно повысить быстродействие устройства за счет уменьшения времени формирования топологии. Формула изобретения 1. Устройство для решения задач сетевого планирования, содержащее генератор импульсов, выход которого подключен к первому входу блока управления, первый выход которого соединен с первы ми вхбдами моделей вершин и первой ячейки управляемого распределителя, первый вход каждой из ячеек распредели теля, кроме первой, соединен с первым выходом предыдущей ячейки управляемо го распределителя, второй выход блока управления подключен ко вторым входам ячеек управляемого распределителя, вто« рые выходы ячеек управляемого распределителя соединены Со вторыми входами соответствующих моделей вершин, первый выход каждой модели вершин соединен с третьим входом соответствующей моде ли вершины в соответствии с топологией моделируемого графа, отличающееся тем, что, с целью расширения функциональных возможностей за счет обеспечения нумерации вершин графа, в устройство ввецен элемент ИЛИ, первый вход которого соединен с выхо дом последней ячейки управляемого распределителя, второй вход элемента ИЛИ подключен к третьему выходу блока упра ления, выход элемента ИЛИ соединен с четвертыми входами моделей вершин, вто рые выходы моделей вершин подключены к четвертому входу соответствующей ячейки управляемого распределителя. .. 2. Устройство по п. 1, отличающееся тем, что модель вершины содержит счетчик импульсов, два триггера R четыре элемента И, первый вход первого из которых является первым входом модели, второй вход первого элемента И соединен с первым входом второго элемента И и подключен к первому выходу первого триггера, вход которого является вторым входом модели, третьим и четвертым входами которой . являются соответственно первый и второй входы третьего элемента И, выход которого через второй триггер подключен к первому входу четвертого элемента И, соединенному со вторым входом второго элемента И, выход которого является вторым выходом модели, первым выходом которой является выход четвертого элемента И, вто- рой вход которого соединен со вторым выходом первого триггера, выход первого элемента И подключен ко входу счетчика импульсов. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР по заявке .№ 260О771/18-24 кл. G 06 G 7/122, 1978. 2.Авторское свидетельство СССР № 570060, кл. Q 06 G 7/122, 1975.