SU798854A1 - Устройство дл моделировани сетевыхгРАфОВ - Google Patents

Description

Изобретение относитс  к вычислительной технике и может быть использовано при исследовании параметров сетевых графов. Известно устройство дл  определени  критического пути в графе , содержащее модель сети, блок управлени генератор импульсов, формирователь весов дуг, по числу столбцов матрицы элементы ИЛИ, И, триггеры l. Однако устройство позвол ет определить только величину кратчайшего пути, численно равную числу импульсов , отсчитываемому в блоке управлени . Наиболее близким по технической сущности к предлагаемому  вл етс  устройство дл  моделировани  сетевых гра.фов, содержащее блок управлени , импульсный вход которого соединен с выходом генератора импульсов, элементы И по числу столбцов матрич ной модели сети, цепочки из последо вательно соединенных счетчика и. триггера по числу строк и столбцов матричной модели сети. Выход тригге ра каждого, столбца подключен к информационному входу элемента И соответствующего столбца 2, Недостатком -этого устройства  вл етс  мала  точность моделировани . Цель изобретени  - повышение точности . Указанна  цель достигаетс  тем, что в устройство дл  моделировани  сетевых граЛ)Ов, содержащее матрицу формирователей весов дуг, каждый из которых содержит триггер и счетчик, выход которого подключен к входу триггера, выход триггера ка;кдого столбца матрицы Формирователей дуг соединен с информационным входом соответствующего элемента И первой группы, генератор тактовых импульсов , выход которого подключен к входу распределител  импульсов, введены элементЕ, НЕ, группы элементов И, группы счетчиков, схемы сравнени  и триггеры, счетные входы каждого из которых подключены к выходу соответствующей схемы сравнени , первые входы каждой из которых соединены с .первым выходом распределител  импульсов , второй выход которого подключен к первым входам элементов И второй группы, вторые входы которых соединены с выходами элементов НЕ, вхохИ которых подключены к выходам соответствующих элементов И первой группы

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

,ia чертеже представлена-структурна  схема устройства.

Устройство содер((ит матричную моель 1 сети, распределитель 2 импульсов , генератор 3 тактовых импульсов, по числу строк и столбцов матрицы формирователи 4 весов- дуг, .включаюие счетчики 5 и триггеры-в, по чису столбцов матрицы первую группу элементов И 7, элементы НЕ 8, третью группу элементов И 9, вторую группу элементов И 10 и четвертую группу элементов И 11, группы счетчиков 12 и 13, схемы 14 сравнени  и триггеры 15.

Модель 1 сети представл ет собой матрицу однородных  чеек Формирователей весов дуг размером пхп,где пмаксимальное число узлов моделируемого графа.

Устройство работает сл едующим образом .

В исходном состо нии все триггеры 15, счетчики 12 и 13 наход тс  в нулевом состо нии. Распределитель 2 подает разрешающий сигнал на управл ющий вход элемента И 10. Первоначально в модель 1 заноситс  информаци  о топологии моделируемого графа сети. При этом триггеры б формирователей 4, моделирующих ветви графа, устанавливаютс  в единичное состо ние . Соответствующий формирователь 4 определ етс  пepece Jeниeм строки с номером, равным номеру начального узла моделируемой ветви, и столбца с номером, равным номеру ее конечного узла. В счетчики 5 соответствующих формирователей 4 занос тс  числа импульсов, дополн ющие длительности ветвей до полной емкости счетчиков . После занесени  исходной информации на входах элементов И 7, объедин ющих выходы формирователей 4 в столбцах, соответствующих начальным узлам моделируемого графа, будут высокие потенциалы. Это объ сн етс  тем, что в однонаправленном графе без циклов и петлей начальные узлы не содержат вход щих ветвей, а, следовательно , и триггеры 6 формирователей 4, наход щихс  в этом столбце, будут в нулевом состо нии (элементы

и 7 соединены.нулевыми входами триггеров 6. Определение вершин графа, образующих критический путь, осуществл етс  в три этапа.

На первом этапе осуществл етс  определение наиболее равных моментов начала свершени  событий дл  вершин исследуемого графа. Дл  этого с по влением пускового сигнала распределитель 2 разрешает прохождение импульсов с выхода генератора 3 на входы всех элементов И 9 и 10. При этом импульсы проход т на входы тех счетчиков 5, соответствующие столбцы матрицы 1 которых моделируют веса дуг, исход щих из начальных узлов. Эти же импульсы через элементы И 10 проход т на счетчики 12 всех вершин графа , кроме начальной, так как на выходе соответствующего элемента НЕ 8- высокий потенциал.

Отсчитав число импульсов, пропорциональное весу моделируемой дуги, счетчик 5 одного из формирователей переполн етс , устанавливает в нулевое состо ние соответствуюший триггер б, и на вход соответствуюгцего элемента И 7 поступает разрешение с нулевого- выхода этого триггера. Если на остальных входах этого элемента И 7 - разрешающие потенциалы, то на его выходе по вл етс  разрешающий синал . Это свидетельствует о том, что веса дуг, вход щих в узел, номер которого соответствует номеру столбца формирователей 4, объединенных этим элементом И -1, сформированы. При этом формируетс  разрешение, поступлени  импульсов на входы счетчиков 5 формирователей 4, моделирующих ветви графа, исход щих из сформированного узла. Одновременно с этим на вход элемента столбца подаетс  высокий потенциал, а с его выхода - низкий , следовательно, подача импульсов на вход счетчика 12 через элемент И 10 прекращаетс  и на выходе счетчика 12 зафиксируетс  врем  наиболее раннего момента начала свершени  событи  дл  данной вершины исследуемого графа. Вычислительный процесс продолжаетс  до тех пор, пока на входах всех элементов И 7 не будут присутствовать высокие потенциошы. Это свидетельствует о том, что все узлы исслеjjyeMoro графа сформированы. Распределитель 2 при этом прекращает подачу импульсов на входы элементов И 9 и 10. Число импульсов, зафиксированное насчетчиках 12, соответствует моментам наиболее раннего начала свершени  событий. На этомпервый этап работы предлагаемого устройства заканчиваетс . /

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

С по влением пускового сигнала распределитель 2 разрешает прохождение импульсов с выхода генератора 3 на входы всех элементов И 9 и далее на входы элементов И 11 соответствующего столбца и счетчиков 5 одноименной строки матрицы. Кроме этого распределитель 2 подает разрешающий сигнал на управл емый вход элементов И 11,поэтому импульсы далее поступают на счетные входы счетчиков 13. Отсчитав число импульсов, пропорциональное весу моделируемой дуги , счетчик 5 одного из формирователей переполн етс , и на вход соответствующего элемента И 7 поступает разрешающий сигнал с этого триггера. Если на остальных входах элемента И 7 - разрешающие потенциалы, то на выходе элемента И9 по вл ютс  импульсные сигналы, которые поступают на счетчики 5 одноименной строки матрицы и через элементы И 11 на счетчики 13 и т.д. Вычислительный процес на втором этапе продолжаетс  до тех пор, пока на выходах всех элементов И 7 не будут присутствовать высокие потенциалы.

Третий этап работы устройства заключаетс  в сравнении показаний счетчиков 12 и.13, соответствующих наиболее ранним и наиболее поздним моментам свершени  событий, путем подачи распределителем 2 управл ющего сигнала на схемы 14 сравнени . С выхода схем 14 сигнал сравнени  перебрасывает триггеры 15 в единичное состо ние. Единичные состо ни  триггеров 15- соответствуют вершинам графа, образующих максимальный критический путь.

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

Claims (2)

1.Авторское свидетельство СССР № 525954, кл.С Об F 15/20, 1976. .

5

2.Авторское свидетельство СССР № 491132, кл.б Об F 15/20, 1974

(прототип).