Устройство для моделирования сетевых графиков

(22) Заявлено 1508,77(21) 2516245/18-24с присоединением заявки Нов(23) ПриоритетОпубликовано 050180 Бюллетень М 1Дата опубликования описания 08.01.80 Государственный комитет СССР по делам изобретений н открытий(71) Заявитель Институт электродинамики Академии Наук УССР(54), УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФИКОВИзобретение относится к области вычислительной техники, в частности, к электронным моделирующим устройствам, и может быть использовано при построении цифровых специализированных машин для решения задач исследования операций.Известно устройство для моделирования путей в графе, содержащее триггеры, формирователь временного интер 10 вала, задатчики адресов и элементы И 11Недостатком известного устройства является большой расход оборудования.Наиболее близким по технической 15 сущности к предложенному изобретению является устройство для моделирования сетевых графиков, содержащее блок моделей ребер по числу работ исследуемого графика, каждая из ко торых выполнена в виде первого и второго задатчиков адресов, выход второго задатчика адреса подключен к первому входу первого элемента И, в од которого соединен с перв м25 входом элемента ИЛИ, второй вход которого подключен к выходу элемента НЕ, вход которого соединен свыходом второго задатчика адреса, первого триггера, первый выход которо- ЗО го подключен ко второму входу первогоэлемента И, второй выход первоготриггера соединен с первым входомвторого элемента И, выход которогоподключен к первому входу формирователя временных интервалов, выход которого соединен с первыми входамипервого и второго триггеров, блокформирования топологии, выполненныйв виде первого элемента ИЛИ, входыкоторого соединены с выходами вторыхтриггеров всех модулей ребер, выходпервого элемента ИЛИ через элементНЕ подключен к первому входу первогоэлемента И, выход которого соединенсо вторыми входами формирователейвременных интервалов всех моделей ребер, выход первого элемента ИЛИ подключен к первому входу второго элемента И, выход которого соединен спервым входсы второго элемента ИЛИ,выход которого подключен ко входампервого и второго задатчиков адресоввсех моделей ребер, третьего элемента И, входы которого соединены свыходами элементов ИЛИ всех моделейребер, выход третьего элемента Иподключен к первому входу третьегоэлемента ИЛИ, выход которого соединен со вторыми входами вторых элементов И всех моделей ребер, генераторимпульсов, первый и второй выходыкоторого подключены соответственнок о вторым в ходам перв ого и в торо гоэлементов И блока формировани-я топологии, блок управления, первый 5выход которого соединен со вторымвходом второго элемента ИЛИ блока Формирования топологии, второй выходблока управления подключен ко второму входу третьего элемента ИЛИ блока формирования топологии, выходкоторого соединен со входом блокауправления (2) . 15 Недостатком известного устройства являются узкие функциональныевозможности.Цель изобретения - расширениекласса решаемых задач за счет обеспечения ассоциативного поиска и сокращение оборудования. 20Поставленная цель достигается,тем, что во все модели ребер введены первый и второй блоки сравнения,третий и четвертый триггеры, третийи четвертый элементы И, а в блокформирования топологии дополнительно введен четвертый элемент ИЛИ,причем входы четвертого элемента,ИЛИ блока формирования топологий соединены с выходами третьих элементовИ всех моделей ребер, выход четвертого элемента ИЛИ блока формирования топологии подключеи к первымвходам первых и вторых блоков сравнения всех моделей ребер, выходпервого блока сравнения каждой модели З 5ребер соединен со входом третьеготриггера, первый выход которого подключен к третьему входу элемента ИЛИ,второй выход третьего триггера соединен с третьим входом первого элементаИ и с первым входомтретьегоэлемента И, второй вход которогосоединен со вторым входом первогоблока сравнения и подключен к выходу второго задатчика адреса, третийвход третьего элемента И соединен.с выходом второго триггера, второйвход которого подключен к выходучетвертого элемента И, первый входкоторого соединен со вторым выходомтретьего триггера, выход первого50задатчика адреса подключен ко второму входу второго блока сравнения,выход которого соединен со входомчетвертого триггера, выход которогоподключен к третьему входу второго 55элемента И, и четвертые входы вто рых элементов И всех моделей реберсоединены с третьим выходом блокауправления, четвертый выход которого подключен ко вторым входам четвертых элементов И всех моделей.На фиг. 1 изображена функциональная схема предложенного устройства;на фиг2, 3, 4, 5 показаны Фрагменты моделируемых графов, Устройство содержит блок 1 моделей ветвей, блок2 формирования топологии, блок 3управления, генератор импульсов 4,Каждая модель ветви содержит эадатчики 5, 6 адресов начального и конечного узлов соответственно, выполненные в виде кольцевых сдвиговых регистров (далее называемые ЗАНУ и ЗАКУ), формирователь 7 временных интервалов, триггеры 8-11, блоки сравнения 12, 13, элементы И 14-17, инвертор 18, элемент ИЛИ 19. Блокформирования топологии содержит элементы И 20-22, инвертор 23, элементы ИЛИ 24-27. На фиг. 2 а, За, 4 а и 5 кружками обозначены узлы графа, стрелками - ветви графа. Номера узлов проставлены над их изображениями. На фиг. 2 б, Зб, 4 б показано содержимое задатчиков адресов начальных и конечных узлов (ЗАНУ или ЗАКУ)в начале цикла. В этих задатчикахотмечен разряд, отведенный для запислогической функции узла (ЛФУ) . Неоконченные в рассматриваемый моментвремени входящие ветви обозначенына фиг. 2 а, За, 4 а пунктиром.Работу устройства рассмотрим напримерах.1, Пусть в графе моделируетсякратчайший путь, т.е,. все узлы типаИЛИ. Пусть узлу 41 (фиг. 2 а) инцидентны 6 ветвей. 3 входящих (а, Ь, с) и 3 выходящих (х, у, г). В ЗАКУ моделей ветвей а,Ь,с и в ЗАНУ моделей ветвей х, у, г записан двоичный код числа 41, Содержимое этихзадатчиков при условии, что задатчики семиразрядные, приведено на фиг,2 б. В седьмом разряде, предназначенном для записи ЛФУ, запиСан нуль.Работу устройства рассмотрим с момента окончания одной из ветвей, входящих в узел 41 (например, ветви О.) .В момент окончания формирования временного интервала триггер 8 модели ветви а, устанавливается в единицу, и через элемент ИЛИ 24 и инвертор 23 на первый вход элемента И 21 блока формирования топологии подается запрещающий сигнал. Поэтому импульсы серии А перестают поступать на формирователи временныхинтервалов всех моделей ветвей, Сигнал с выхода элемента ИЛИ 24 разрешает поступление импульсов серии Б на выход элемента И 22 и черезэлемент ИЛИ 26 - на входы всех задатчиков 5, 6. До начала каждого цикла формирования топологии триггеры 10,11 всех моделей ветвей устанавливаются в единичное состояние (установочные входы на фиг. 1 не показаны)На задатчики начинают поступатьимпульсы серии Б, сдвигающие вправо содержимое задатчиков, После первого импульса серии Б на выходе ЗАКУ лмоделей ветвей Я, д, с (ЗАНУ моделей ветвей х, у, г ) появляется единичный сигнал. Поскольку на двухвходах элемента И 16 модели ветви О.присутствуют разрешающие сигналы, этот единичный сигнал через третий вход элемента И 16 поступит наего вход и на выход элемента ИЛИ 25блока формирования топологии, откуда он поступает на первые входыблоков сравнения всех моделей. ветвей. Поскольку в этот момент единичный сигнал присутствует на выходахЗАНУ моделей ветвей х,; у, г, то навыходе блока сравнения 12 упомянутыхмоделей ветвей будут нулевые сигналы и триггеры 10 тех же моделей останутся в единичном состоянии. Триггеры 10 моделей ветвей, на выходеЗАНУ которых в этот момент будетнулевой сигнал, сустанавливаются наэтом такте в.нулевое состбяние (таккак на выходах соответствующих блоковсравнения 12 присутствуют единичныесигналы). Аналогично этому, остаются в единичном состоянии триггеры 11моделей ветвей а, Ь, с (так как навыходах соответствующих блоков сравнения 13 будут нулевые сигналы)Триггеры 11 моделей ветвей, на выходах ЗАКУ которых в этом такте присутствуют нулевые сигналы, устанавливаются в нулевое состояние. На( следующем такте на выходе элементаИ 16 модели ветви 0 присутствуетнулевой сигнал.(так как во второмразряде ЗАКУ модели ветви 0 стоитнуль). Поскольку ветвь а - единственная из ветвей, окончившаяся в предыдущем периоде поступления импульсов серии А ( т.е. в рассматриваемомцикле формирования топологии находится в единичном состоянии единственный триггер 8, принадлежащий мо-.дели ветви а), то на выходах всехэлементов И 16, а, следовательно,на выходе элемента ИЛИ 25, тожебужет нулевой сигнал. В этом тактена выходах блоков сравнения 13 (12)моделей ветвей а, Ь, с (х, у, г)тоже будут нулевые сигналы, и триггеры 11 (10) упомянутых моделей ветвей остаются в единичном состоянииПосле этого такта в единичном состоянии остаютсятриггеры 10 (11)тех моделей ветвей, в задатчиках5(6) которых в первом и втором разрядах справа записана комбинация 01В нулевом состоянии находятся триггеры 10 (11) тех моделей ветвей, взадатчиках 5 (,6) которых в первом ивтором разрядах справа записана любая комбинация, отличная от 01 (т.е00,11,10). Формирование топологиипроисходит аналогичным образом в течение последующих четырех тактов.После шестого такта рассматриваемогоцикла формирования топологии в единичном состоянии останутся триггеры . 11 моделей ветвей а, Ь, с и триггеры 10. моделей ветвей х, У г. Далее,на седьмом такте, производится формирование логической функции узла.В последнем такте каждого цикла формирования топологии остаются в единичном состоянии триггеры 11 моделей ветвей, входящих в моделируемыйузел. Триггеры 11 всех остальных моделей в етв ей наход ятс я в нулевомс ос то янин . В рас сматрив аемом примере в седьмом такте в единичномсостоянии находятся триггеры моделей ветвей и, Ь, с. Встальные триггеры 11 находятся в нулевом состоянии, их нулевые выходы через элементыИЛИ 19 соответствующих моделей ветвей обеспечивают наличие единичныхсигналов на соответствующих входахэлемента И 20 блока формирования топологии, Нулевые сигналы с выходов 20 ЗАКУ моеелей ветвей а, Ь, с в седь. мом так э через инверторы 18 и элементы ИЛИ 1 9 также обеспечивают единичные сигналы на соответствующих входах элемзнта И 20. Таким образом, в 25 седьмом такте рассматриваемого цикла формирования топологии на всехвходах элемента И 20 блока формирования топологии присутствуют единичные сигналы, вследствие чего на выходе элемента И 20 также присутствует единичный сигнал. Этот сигнал через элемент ИЛИ 27 Поступает на первые вход 1 элементов И 14 всех моделей ветв й. Синхронно с последним импульсом сдвига в каждом цикле (т.е.в данном случае синхронно с седьмымимпульсом сдвига) блок 3 управления.выдает разрешающий сигнал на вторыевходы элементов И 14 всех моделейветвей, Поскольку триггеры 10 мо делей ветвей х, у, г остались вединичнсм состоянии, а триггерытех же моделей ветвей находятся внулевом состоянии (ветви х, у, гне окончены), то на всех входах эле ментов И 14 моделей ветвей х, у, гприсутствуЫт единичные сигналы.Следовательно, на выходах упомянутыхэлементов появляются единичные сигналы, которые поступают на формирователи временных интервалов в моделейветви х, у, г, разрешая этим формирователям отсчет импульсов серии А.Через время 1 = 1 пф и, где 1 пфв, -время подготовки формирователя котсчету импульсов серии А, блок 3управления выдает единичный сигнална первые входы элементов И 15 всехмоделей ветвей, Так как триггеры 11моделей ветвей О, Ь, с находятся вединичном состоянии, единичные сиг налы появляются на выходах упомянутых элементов, Сигнал с выхода элемента И 15 модели ветви а устанавливает триггер 8 модели а в нулевоесостояние. Состояния триггеров 8 мо делей ветвей Ь и с не изменяются (таккак эти триггеры находятся в нулевом состоянии). Поскольку все триггеры 8 находятся в нулевом состоянии, на выходе элемента ИЛИ 24 появляется нулевой сигнал, который через инвертор 23 и элементы И 21, 22 запрещает пос тупление импульсов серии Б и разрешает поступление импульсов серии А на модели ветвей. Отсчет импульсов серии А производится всеми формирователями, на которые было подано разре шение, в том числе Формирователями моделей ветвей х, у, г.Рассмотрим цикла формирования топологии в том случае, когда непосредственно перед его началом одновре менно окончились две ветви, входящие в разные узлы (ветви в, Й, входящие в узлы 21 и 49 соответственно, Фиг, 3) .В течение рассматриваемого цикла формирования топологии находятся 20 в единичном состоянии триггеры 8 моделей в, Й . Поскольку в первом и втором разрядах справа в ЗАКУ моделей ветвей щ и д записана одинаковая комбинация 01 (см. Фиг. Зб), 2 то первые два такта цикла происходят, как описано выше. На третьем такте цикла Формирования топологии на выходе элемента И 16 моделей ветви щ присутствует единичный сигнал ЗО (так как триггеры 8 и 11 модели ветви находятся в единичном состоянии, и в третьем справа разряде ЗАКУ модели ветви щ записана единица) . Следовательно, единичный сигнал присутствует также на выходе элемента ИЛИ 25 блока формирования топологии. На выходе ЗАКУ модели ветви б в этот момент присутствует нулевой сигнал. Поэтому на выходе блока сравнения 13 модели ветви й появляется 4 О единичный сигнал (по первому входу этого элемента от элемента ИЛИ 25 поступает единичный сигнал, по второму входу от ЗАКУ - нулевой сигнал). Единичный сигнал с выхода блока 13 45 модели ветви устанавливает в нуль триггер 11 той же модели. Поэтому в течение остальных тактов рассматриваемого цикла на одном иэ входов, а следовательно,. на выходе элемента 50 И 16 модели ветви Й присутствует нулевой сигнал. Таким образом, далее в этом цикле производится проверка совпадения адресов с конечным адресом ветви в (т,е. с 21) 55 Цикл продолжается и оканчивается, как описано выше, выдачей разрешения на формирователи моделей г, р, с. После окончания цикла триггер 8 модели ветви й выходным сигналом элемента И 15 той же модели ветви Й не устанавливается в нулевое состояние, так как на одном из входов элемента И 15 той же модели, а, следовательно, и на выходе присутствует нулевой сигнал, обусловленный нулевым состоянием триггера 11 той же модели. Поэтому единичный сигнал с выхода; элемента ИЛИ 24 через янвертор 23 по-прежнему запрещает поступление импульсов серии А и разрешает поступление импульсов серии Б на модели ветвей. Таким образом, организуетсяследующий цикл формирования топологии. В этом цикле выбранным адресом, т.е. адресом, с которым производится сравнение, является конечный адрес ветви с 1 (т.е.49) . Поскольку триггер 8 модели вет ви щ находится в нулевом состоянии, на выходе элемента И 16 той же модели в течение этого цикла присутствует нулевой сигнал. В конце уцикла поступают разрешающие сигналы на формирователи моделей ветвей Й, у, Аналогично производится выбор одного из адресов в каждом цикле, если одновреммно окончилось большее число ветвей.2. Работа устройства в режиме моделирования длиннейшего пути (т.е., когда в узлах выполняется функция коньюнкции) .иллюстрируется фиг. 4 а, 4 б. Пусть моделируется узел 37 (фиг, 4 а), и к началу рассматриваемого цикла Формирования топологии окончилась одна ветвь - а. Первые шесть тактов цикла формирования топологии происходит совершенно так же, как описано выше. На седьмом такте цикла формирование топологии на выходах всех элементов ИЛИ 19, кроме элемента ИЛИ 19 модели ветви Ъ, присутствуют единичные сигналы. Действительно, после шестого такта формирования топологии все триггеры 11, кроме триггеров 11 моделей ветвей й, Ь, находятся в нулевом состоянии и единичные сигналы с их нулевых выходов поступают на входы соответствующих элементов ИЛИ 19, На выходе элемента И 17 модели ветви а присутствует единичный сигнал, так как триггеры 9 и 11 модели ветви а находятся в единичном состоянии, а в седьмом разряде ЗАКУ моделей ветвей а, Ь записана единица, Последнее обуславливает также наличие нулевых сигналов на выходах инвесторов 18 моделей ветвей ц, Ъ . Таким образом, на выходе элемента ИЛИ 19 присутствует единичный сигнал, обусловленный единичным сигналом с выхода элемента И 17 той же модели. На выходе элемента И 17 модели ветви в имеется нулевой сигнал, так как триггер 9 модели ветви Ь находится в нулевом состоянии (ветвь не окончена) . Поскольку на остальных входах элемента ИЛИ 19 модели ветви.Ь также имеются нулевые сигналы, на выходе упомянутого элемента также присутствует нулевой сигнал,Таким образом, в этом такте на выходе элемента И 20 блока формирования топологии, а,следовательно, ина соответствующих входах элементов И 14 всех моделей ветвей присутствуют нулевые сигналы, вследствие чего ча формирователи моделей ветвей с, Й . не поступает разрешение на счет импульсов серии А. Как описано ранее, выходной сигнал элемента И 15 устанавливает в нуль триггер 8 модели ветви О. Поступление импульсов серии Б прекращается, начинается поступление импульсов серии А. Когда формирователь 7 модели ветви в закончит свою работу, в следующем цикле формирования топологии будет снова проверяться адрес 37. Первые шесть тактов цикла происходит так описано выше. В седьмом такте на выходе элемента И 17 модели ветви Ь присутствует единичный сигнал, так как триггер 9 этой модели ветви установился в единичное состояние. Таким образом, в этом такте единичные сигналы присутствуют на всех входах элемента И 20, а значит и на его выходе. Следовательно, в этом такте на всех входах элементов И 14 моделей ветвей с имеются разрешающие сигналы и на формирователи упомянутых моделей ветвей поступают сигналы, разре- шающие счет импульсов серии А. Таким образом, произошло формирование функции конъюнкции в узле 37 (т.е. разрешение на формирование ветвей с и д выдано только после того, так окончились ветви а и Ь). 3, Предложенное устройстВо может также моделировать пути в сложном графе, то есть в графе, часть узлов которого выполняет функцию дизъюнкции, а другая часть - функцию конъюнкции. Фрагмент сложного графа показан на фиг, Ь. Узлы 15 и 47 - узлы типа И, то есть ветвь е (Е) начинается только тогда, когда окончи- лись ветви а и 13 (с и й), узел 2 б узел типа ИЛИ (т.е. ветвьначинается, когда окончилась ветвь е или Й)Пусть все задатчики адресов-семиразрядные. Тогда в седьмом разряде ЗАКУ (ЗАНУ) моделей ветвей е, 1 (у) записывается нуль, а в седьмом разряде ЗАКУ (ЗАНУ) моделей ветвей й, Ь, с, д (е,й ) записывается единица, При моделировании узлов 15 и 47 устройство функционирует, как описано в примере 2, а при моделировании узла 26 - как описано в примере 1.4. Возможность выполнения устройством ассоциативного поиска рассмотрим на примере поиска по упорядоченной совокупности признаков. В этом случае формирователи выполняют роль ячеек памяти данных, а ЗАКУ - роль ячеек памяти ассоциативных признаков. А именно, каждый разряд ЗАКУ соответствует определенному признаку. Единица в 1-м разряде ЗАКУ и-й модели ветви означает, что 5 10 35 20 25 40 45 50 55 60 65 информация, хранящаяся в формирователе 7 этой модели ветви, обладает 1-м признаком. Например, если в ЗАКУ ) -й модели ветви записан код 00-"- 0101, это означает, что содержимое формирователя обладает первым и третьим признаками.При установке всех триггеров 8 и 9 в единицу, устройство может производить ассоциативный поиск по различным совокупностям признаков . Если, например, подавать разрешающие сигналы из блока управления на, элементы И 14 синхронно первым и вторым импульсами серии Б в каждом цикле формирования топологии, то в первую очередь выбираются формирователи, информация в которых обладает первым и вторым признаками (те. формирователи тех моделей ветвей, в ЗАКУ которых записан код 11), далее формирователи моделей ветвей, ,в ЗАКУ которых записаны коды 01, 10,00. (Под выбором формирователя понимается подача на его вход разрешающего сигнала с выхода соответствующего элемента И 14) . Подобным образом можно организовать ассоциативный поиск информации по другим совокупностям признаков. Предложенное устройство благодаряналичию новых элементов и связеймежду ними позволяет решать задачуассоциативного поиска на исследуемом1сетевом графике. Формула изобретения Устройство для моделирования сетевых графиков, содержащее блок моделей ребер по числу работ исследуемого графика, каждая иэ которых выполнена в виде первого и второго задатчиков адресов, выход второго. задатчика адреса подключен к первому вход первого элемента И, выхбд которого соединен с первым входом элемента ИЛИ, второй вход которого подключен к выходу элемента НЕ, вход которого соединен с выходом второго задатчика адреса первого триггера, первый. выход которого под" ключен ко второму входу первого. элемента И, второй выход первого: триггера соединен с первым входом второго элемента И, выход которого подключен к первому входу формирователя временных интервалов, выход которого соединен с первыми входами пер. вого и второго триггеров, блок формирования топологии, выполненйый в виде первого элемента ИЛИ, входы которого соединены с выходами вторых триггеров всех моделей ребер, выход первого элемента ИЛИ через элемент НЕ подключен к первому входу первого элемента И, выход которого соединен со вторыми входами формирователей временных интервалов всех моделей ребер, выход первого элемента ИЛИ подключен к первому входу второго элемента И, выход которого соединен с первым входом второго элемента ИЛИ, выход которого подключен ко входам первого и второго задатчиков адресов всех моделей ребер, третьего элемента И, входы которого соединены с выходами элементов ИЛИ всех моделей ребер, выход третьего элемента И подключен к .первому входу третьего элемента ИЛИ, выход которого соединен со вторыми входами вторых элементов. И всех моделей ребер, генератор импульсов, первый и второй выходы которого подключены соответственно ко вторым входам первого и второго элементов И блока формирования топологии, блок управления, первый выход которого соединен со вто рыМ входом второго элемента ИЛИ бло ка формирования топологии, второй выход блока управления подключен ко второму входу третьего элемента ИЛИ блока формирования топологии, выход Я которого соединен со входом блока управления, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых задач за счет ассоциативного поиска и сокращения оборудования, ЗО во все модели ребер введены первый и второй блоки сравнения, третий и четвертый триггеры, третий и четвертый элементы И, а в блок формирования топологии дополнительно введен четвертый элемент ИЛИ, причем входы чет-вертого элемента ИЛИ блока формирования топологии соединены с выходами третьих элементов И всех моделей ребер, выход четвертого элемента ИЛИблока формирования топологии подключен к первым входам .первых и вторыхблоков сравнения всех моделей ребер,выход первого блока сравнения каждой модели ребра соединен со входомтретьего триггера, первый выход которого подключен к третьему входуэлемента ИЛИ, второй выход третьеготриггера соединен с третьим входомпервого элемента И и с первьм входом третьего элемента И, второй входкоторого соединен со вторым входомпервого блока сравнения и подключенк выходу второго эадатчика адреса,третий вход третьего элемента И соединен с выходом второго триггера,второй вход которого подключен квыходу четвертого элемента И, первый вход которого соединен со вторым выходом третьего триггера, выход первого задатчика адреса подключен ко второму входу второго блокасравнения, выход которого соединенсо входом четвертого триггера, выход которого подключен к третьемувходу второго элемента И, четвертыевходы вторых элементов И всех моделей ребер соединены с третьим выходом блока управления, четвертыйвыход которого подключен ко вторымвходам четвертых элементов И всехмоделей ребер. Источники информации,принятые во внимание при экспертизе1. Авторское свидетельство СССРпо заявке Р 2199427, 06.07,772. Авторское свидетельство СССРР 422002, кл. 6 06 С 7/48, 30.03.741 прототип) .,рруун г ЯфРс у.РФ Составитель А. КолчинРедактор Д. Зубов Техред М.Келемеш Корректор И. Михеева 75 Заказ 8 Филиал ППП Патент, г. Ужгород, ул ктна О/45 Тираж ЦНИИПИ Государствепо делам изобр 3035, Москва, Ж,ого комений иаушска 34 ну Гзл ну) НадЕдей РююУй Р Р/с а/ Рюрик 7 6 хдг у