SU752362A1 - Устройство дл решени задач сетевого планировани - Google Patents

Description

1

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

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

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

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

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

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

Claims (2)

1. Поставленна  цель достигаетс  тем, что в устройство, содержащее генератор импульсов, выход которого подключен к первому входу блока управлени , первый выход которого соединен с первыми входами моделей вершин и первой  чейки управл емого распределител , первый вкод каждой из  чеек распределител , кроме первой, соединен с первым выходом предыдущей  чейки управл емого распределител , второй выход блока управлени  подключен ко вторым входам  чеек управл емого распределител , вторые выходы  чеек управл емого распределител  соединены со вторыми входами соответствующих моделей вершин, первый выход каждой модели вершин соединен с третьим входом соответствующей модели вершины в соответствии с топологией моделируемого графа; введен элемент ИЛИ, первый вход которого соединен с выходом последней  чейки управл емого распределител , второй вход элемента ИЛИ под ключей к третьему выходу блока управ- пени , выхоц элемента ИЛИ соединен с чегвертыми входами моделей вершин, вто рые выходы .моделей вершин подключены к четвертому входу соответствующей  чейки управл емого распределител , кро ме того, модель вершины содержит счет- чик импульсов, два триггера и четыре элемента И, первый вкод первого из которых  вл етс  первым вкодом модели, второй вкод первого элемента И соединен с первым входом второго элемента И и подключен к первому выходу первого три гера, вход которого  вл етс  вторым входом модели, третьим и четвертым входами которой  вл ютс  соответственно первый и второй входы третьего элемента И, выход которого через второй триггер подкгаочен к первому входу четвертого элемента И, соединенному со вторым входом второго элемента И, выход которого  вл етс  вторым выходом модели, первым выходом которой  вл етс  выход четвертого элемента И, второй вход которого соединен со вторым выходом первого триггера, выход первого элемента И подключен ко входу счетчика импульсов. На чертеже представлена функциональна  схема устройства. Устройство содержит модели 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. 2.Авторское свидетельство СССР № 570060, кл. Q 06 G 7/122, 1975.