Устройство для исследования графов Советский патент 1986 года по МПК G06F15/173 

1чЭ

о

О) 00 , 1 Изобретение относится к вычислительной технике и может быть исполь зовано для исследонания графов, в частности для охфеделения доступности графа для любой вершины наличи циклов в графе и максимального пути в графе. Цель изобретения - повьшение быс родействия. На фиг. 1 приведена функциональная схема предлагаемого устройства для исследования графов; на фиг. 2 структура блока связи; на фиг. 3 структура узла связи; на фиг. 4 структура блока записи связей; на фиг. 5 - элемент связи; на фиг. 6 временные диаграммы, Функциональная схема устройства для исследования графов включает счетчик 1, линию 2 задеротси, управл емые ключевые элементы 3, триггеры 4 тактовьй вход 5 устройства, вход 6 начальной установки устройства, вы ход 7 конца испытания устройства, элементы ИЛИ 8, первый многовходово элемент ИЛИ 9, второй многовходовой элемент ИЛИ 10, третий многовходовой элемент ИЛИ 11, элемент НЕ 12, триггеры 13 состояния, элемент И 14 входы 15 состояния (вторые информац онные входы) устройства, блоки 16 записи связей, блок 17 связи, входы 18изменения адреса (вход задания логической единицы) устройства, вхо 19задания режима, первые информаци онные входы 20 (ответа),, входы 21 разрешения записи, информационные выходы 22 блоков записи связей и адресные входы блока связи, выходы От вета блока связи.и входы ответа бло записи связей 23, выходы запроса бл ка записи связей и входы запроса бл ка связи 24, входы 25 ответа блока связи, выходы 26 запроса блока связ модели вершин 27.1-27.2N, вход. 28 сброса блока связи. Блок 17 связи включает регистры 29, образующие пары регистров 30.130.N, блок 31 синхронизации, узлы связи 32.1,1-32, NM, образующие матрицу КхМ, входы 33 ответа узла связи, выходы 34 ответа узла связи, выходы 35 запроса узла связи, входы 36 запроса узла связи, адресные, выходы 37 узла связи, адресные входы 3 узла связи, входы .39 синхронизации узла связи. 763 .2 . Схема узла 32 связи включает элементы И 40, образзтощие группы элементов И 41.1-41.2, элементы связи 42.142.2, второй вход ответа узла 43 связи, второй выход 44 ответа узла связи, первый адресный вход 45 элемента связи, второй адресный вход 46 элемента связи, первый вход 47, второй вход 48. Функциональная схема блока 15 записи связей включает узел 49 памяти, элемент ИЛИ 50, счетчик 51 адреса, элемент 52 сравнения, регистр 53, вход 54 сброса, тактовый вход 55. Функциональная схема элемента 42 связи включает первый элемент ИЛИ 56, элемент 57 запрета, первые элементы И 58, второй триггер 59, мультиплексор 60, второй элемент ИЛИ 61, первый триггер 62, вторые элементы И 63. Рассмотрим функционирование устройства при определении максимального пути в графе по фиг. 1. Исходное состояние блоков устройства-следу- . ющеео В счетчике 1 находится О, который заносится сигналом с шины 6, одновременно приводящем в состояние готовности блок 17 связи через элемент ИЛИ 11. В блоки 16 записи связей занесены исходящие связи соответствующих вершин в )зиде двоичных номеров вершин, связанных с данной. Функционирование блока 1b записи связей , при записи рассмотрим по фиг. 4. Исходящие связи заносятся через вход 20. Адрес записи очередной исходящей -связи определяется содержанием счетчика 51, которое наращивается при помощи подачи единиц на вход 18. После записи последней исходящей связи в счетчик 51 добавляется еще одна 1 и в регистр 53 заносится новое содержимое счетчика 51 при помощи подачи разрешающего сигнала на вход 21. Режи1 1 записи в узле 49 памяти определяется состоянием шины 19. В исходном состоянии содержимое счетчика 51 равно О, т„е. он указьгоает на адрес хранения первой исходящей связи. Если некоторая вершина не имеет исходящих связей, то содержимое счетчика 51 будет равно содержимому регистра 53 и тогда схема 52 сравнения вырабатывает О на инверсном выходе. Если у данной вершины имеется хотя бы одна исходящая связь, то содержимое счетчика 51 в исходном состоянии 3 и регистра 53 не совпадают и на инверсном выходе схемы 52 сравнения будет 1. Таким образом, если данная вершина не имеет исходящих связей, то на выходе 24 будет О, в противном случае - 1. Если на выходе 24 некоторого блока 16 имеется О, то соответствующий управляемый ключевой элемент 3 будет закрыт. В противном случае, соответствующий элемент 3 будет открыт, так как триггеры 13 состояния в исходном состоянии находятся в единичном состоянии, а триггеры 4 - в нулевом. Если хотя бы в одном из блоков 16 записана исходящая связь, то на выходе элемента ИЛИ 10 будет I, а на первом входе счетчика 1 появится 0. На выходе окончания испытания 7 также-будет 0. Единргчное сост,ояние триггеров13 устанавливается в исходный момент путем установки триггеров 4 в единич ное состояние через щины (входы) 15 и последующей переписи их состояния в триггеры 13 после окончания записи в блоки 16 сигналом с выхода элемента НЕ 12. Сигнал с выхода блока 10, пройдя через линию 2 задержки, сбросит триггеры 4 в О и приведет в исходное состояние счетчик 51. Устройство работает следующим образом. При подаче тактовых импульсов на вход 6 импульсы проходят через откры тые управляемые ключевые элементы 3 на тактовые входы блоков 49 (линия 1 на фиг, 6). Рассмотрим ситуацию, когда в двух соседних вершинах с номерами 2 к 1 и 2к + 2 имеются исходящие связи и первые разряды обоих адресов равны 1 а следующие разряды - соответственно О и 1. Из узлов 49 памяти производителя на выходы 22 чтение исходящей связи по адресу, определяемому содер жимым счетчика 51. По сигналу на вхо де 28 производится сброс всех узлов 32 связи в- исходное состояние и запись содержимого шин (входов) 22 в регистры 29. При поступлении на тактовый выход 35 импульсов производится вьщвижение очередного разряда исходящей связи на выход (линии 2 и 3) При появлении на выходе первого раз ряда исходящей связи на первом выход 31.1 блока 31 синхронизации появляет ся тактовый импульс, который являет- 63 ся разрешающи - для узлов 32 связи первого столбца (линия 4, фиг. 6). Единицы с входов запроса 24 обоих моделей вершин поступают на входы 36 запроса ( К + 1)-го узла 32 связи первого столбца (линии 5 и 6 на фиг. 6). Если запрос отсутствует, то на выходах обоих пар элементов И 40 будет 0. При наличии запроса, если разряд адреса равен О, то единица появится на выходе левого элемента И, в противном случае - на выходе правого элемента И (линии 7 и 8 на фиг. 6). На входы 45 и 46 могут быть поданы следующие сочетания сигналов: либо две единицы, либо два нуля, либо ноль и единица (общим случаем являются две единицы). При подачена входы 45 и 46 двух единиц на выходе элемента ИЛИ 61 появится единица (линия 9, фиг. 6). Элемент 57 запрета выдает на выходе нуль (линия 10, фиг. 6). Таким образом, на установочном входе триггера 62 будет 1, а на установочном входе триггера 59-0. При приходе разрешаемого сигнала по шине 39 триггеры установятся в соответствующее состояние (линии 11 и 12). Выход триггера 62 формирует разрешающий сигнал для мультиплексора 60, который подключает один из входов на выход в соответствии с состоянием адресного входа, который определяется выходом триггера 59о При наличии О на выходе триггера 59 на выход мультиплексора 60 подключается первый вход 47, в противном случае - второй вход 48. При подаче следующего сигнала на вход 5 разрешающий сигнал из блока 31 синхронизации подается только на узлы связи второго столбца, а на выходах сдвиговых регистров 29 появляется следуюпщй разряд исходящей связи (линии 2 и 3 на фиг. 6). Он проходит по каналу связи, подключенному первым разрядом адреса в узлах 32 связи первого столбца на входы 38 соответствующего узла связи второго столбца (линия 13, фиг. 6). Описанный процесс повторяется до тех пор, пока на соответствующих выходах 35 запроса узлов связи 32 / -го столбца не появится единица. Пусть на первом выходе 35 8 -го уэла рвязи столбца появилась 1, причем этот выход соответствует адресу первой исходящей связи вершины с номером +1 51 (линия 14, фиг. 6), Адресные выходы 32 узлов связи последнего столбца не используются. При появлении на выхо дах 26 запроса единицы триггер 4 через элемент ИЛИ 8 перейдет в единичное состояние - линия 15„ На первый вход 33 ( , |W )-го,.узла связи постзшит 1. В зависимости от состояния триггера 59 единица с входа 33 появится на выходе либо первого 58, либо второго элемента И 63. Если на входе 33 будет О, то в формировании состояния выхода 34 принимает участи вход 43 через элемент ИЛИ 56. Рассмотрим описанный процесс для (И +1) то узла связи 1-го столбца. В этом случае на первом входе 33 будет 1, а на втором - О (линии 16 и 17). Тогда на выходе с номером (2К +1) появится 1, а на выходе 23 с номером (2К +2) - О (линии 18 и 19). В случа 1 через элемент ИЛИ 50 в счетчик 51 добавляется 1 и производится чтение следующей исходящей связи из запоминающего устройства 49 на выходы 22. В то же время через элемент ИЛИ 11 на вход 28 подается 1, которая сбросит в О триггеры 59 и 62-(линии 20, 11 и 12) и разрешит запись информации в 29. Описанный процесс будет повторяться до тех пор, пока из всех блоков 16 записи связей, в которых были записаны адреса исходящих связей, не будут отправлены все связи и полу „чены ответы. Если из некоторого бло- ка 16 записи связей был отправлен запрос, но ответ не пришел, то в следующем передачи запрос отправляется по старому адресу во второй раз, так как содержимое счетчика 51 не изменилось. Если из данного блока 16 записи связей прочитаны все исходящие связи и получены ответы, то содержимое счетчика 51. равно содержимому регистра 53 и ин версный выход элемента 52 сравнения устанавливается в 0. Когда на всех выходах 24 окажутся О (линии 4 и 5), то на выходе элемента ИЛИ 10 появитс О, после чего на первом входе блока 14 появится единица (линии 21 и 22). В это время состояние выхода 7 равно единице, что позволяет добавить в счетчик 1 единицу. Одновременно по сигналу с выхода 12 содержимое триггеров 4 перепишется в триггеры 13. Если имеется хотя бы одна вершина с исходящими связями, у которой со63держимое триггера 13 равно единице, то описанный процесс повторяется снова, но предварительно через линию Т задержки сигналом с выхода злеме{ та ИЛИ 10 будут сброшены в О триггеры 4 (линия 15) и счетчики 51 в блоках 16 записи связей. Когда после очередного цикла ни один из триггеров 4 не будет находится в единичном состояНИИ, на выходе 7 будет также О и в счетчик 1 не будет добавляться единицы. Это говорит об успешном окончании испытания, а содержимое счетчика равно максимальному пути в графе. Для определения доступности некоторой вершины необходимо в исходном состоянии установить триггер 13 состояния вершины нужной вершины в единичное состояние,, а все остальное в 0. Дальнейшее аналогично описанному. Для опреде.ления наличия циклов . в графе исходное состояние устанавливается как для случая определения максимального пути в графе. Если в процессе функционирования в счетчике 2 окажется число, большее числа вершин в графе, то это говорит о наличии циклов в исследуемом графе. Время решения задачи равно сумме двух времен: времени настройки устройства на структуру исследуемого графа и времени определения требуемых характеристик. За счет исполь- зования введенных блоков появляется возможность быстро изменять структуру исследуемого графа и производить перенастройку на новую структуру. вследствие чего достигается сокращение времени решения задачи в 2,5 раза по сравнению с известным устройством. Формула изобретения Устройство для исследования графов, содержащее счетчик, линию задержки, 2N моделей вершин (где N 2), каждая из которых включает управляемый ключевой элемент, элемент ИЛИ и триггер, причем тактовый вход устройства соединен с первыми управляющими входами всех управляемых ключевых элементов 2N моделей вершин, входначальной установки устройства подключен к входу сброса счетчика, во всех моделях вершин выход элемента ИЛИ соединен с единичным входом триггера, отличающееся тем, что, с целью повышения быстродействия, введены три многовходовых элемента ИЛИ, элемент НЕ, элемент И, блок связи, включающий N пар регистров, узел синхронизации и матрицу из N х М узлов связи (где М log22N), каждый из которыхвключает две группы из двух элементов И и два элемента связи, каждый из которых состоит из ;двух элементов ИЛИ, первого и второго элементов И, двух триггеров, элемента запрета и мультиплексора, каждую модель вершины введен тригге состояния и блок записи связей, включающий узел памяти, элемент ИЛИ .счетчик, элемент сравнения и регист причем в каждом блоке записи связей пе вый вход элементов ИЛИ соединен с вход задания логической единицы устройства а выход элемента ИЛИ подключен к счетному входу счетчика, выход которо соединен с адресным входом узла пам ти, первым входом элемента сравнени и входом регистра, вход разрешения записи которого подключен к входу разрешения записи устройства, а выход - соединен с вторым входом элемента сравнения, первый информационный вход устройства соединен с информационным входом узла памяти, вход записи считывания которого сое динен с входом задания режима устро ства, в каждой модели вершины тактовый вход узла памяти соединен с выходом управляемого ключевого элемента, информационный вход которого подключен к выходу элемента сравнения блока задания записи связей, второй управляемый вход управляемого ключевого элемента каждой модели вершины соединен с выходом триггера состояния, вход которого подключен к выходу триггера модели вершины, . первый вход элемента ИЛИ модели вершины соединен с вторым информационным входом устройства, выходы всех триггеров всех моделей вершин соединены с соответствующими входами первого многовходового элемента ИЛИ, выход которого подключен к выходу окончания испытания устройства и первому входу элемента И устройства, второй вход которого соединен с разрешающими входами всех триггеров состояния моделей вершин, выход элемента И устройства соединен со счетным входом счетчика, выход вторагх многовходового элемента ИЛИ соединен с входом элемента НЕ и входом линии задержки, входы второго многовходового ,элемента ИЛИ подключены к выходам соответствующих элементов сравнения блоков записи связей соответствующих моделей вершин, выход линии задержки соединен с нулевыми входами триггеров и входами сброса счётчиков блоков записи связей всех моделей вершин, вторые входы элементов ИЛИ блоков записи связей моделей вершин соединены с соответствующими входами группы третьего многовходового элемента ИЛИ, вход которого соединен с входом начальной установки устройства, информационные выходы узла, памяти блока записи связей (2к+1) и (2R+2)-и моделей вершин соединены соответственно с входами первого и второго регистров (К + 1)-й пары блока связи (где К 1, N), выходы первых элементов ИЛИ первого и второго элементов связи (х+1)-го узла связи первого столбца матрицы блока связи соединены соответственно с вторыми входами элементов ИЖ блоков записи связей (2Ы-1) и (2к+2)-й моделей вершин, выходы элементов сравнения которых подключены соответственно к прямому входу первого и первому входу второго элементов И первой и второй групп (к + 1 )-го узла связи первого столбча матрицы блока связи, выходы триггеров (2К+1) и (2к + 2)-й модели вершин соединены соответственно с первыми входами элементов И первого и второго элементов связи (К + 1)-го узла связи М-го столбца матрицы блока связи, вькоды первых триггеров которых подключены соответственно к вторым входам элементов ИЛИ (2К + 1) и (.К + 2)-й моделей вершин, выход третьего многовходового элемента ИЛИ соединен с входами сброса первого и второго триггеров связи и разрешающими входами регистров блока связи, сдвиговые входы которых подключены к тактовому входу устройства и входу узла синхронизации, i -и выход которого соединен с разрешающими входами триггеров элементов связи -го столбца матрицы из NxM узлов связи, первые входы элементов И и первой и второй групп (X, i )-го столбца блока связи соединены с выходом первого элемента ИЛИ соответствующего элемента связи соответствующего узла связи (j+1)-ro столбца матрицы блока связи, прямой вход первого и первый вход второго элементов И соответствующей группы которого подключены к выходу перво триггера, разрешающему входу мульти плексора и вторым входам элементов элемента связи (K,j)-ro узла связи выход мультиплексора которого соединен с инверсным входом первого элемента И и вторым входом второго элемента И соответствующей группы соответствующего узла связи (i+1)-r столбца матрицы, причем в каждом узле связи второй вход второго элемента И первой группы подключен к первому входу мультиплексора второг элемента связи и второму входу с мультиплексора первого элемента свя зи, выход первого элемента И первой группы подключен к первым входам второго элемента ИЛИ и элемента запрета первого элемента связи, выход второго элемента И первой группы соединен с вторыми входами второго элемента ИЛИ и элемента запрета второго элемента связи,, выход второго элемента И которого подключен 63 к первому входу первого элемента ИЛИ первогоэлемента связи, выход второго элемента И которого соединен с вторым входом первого эле 1ента ИЛИ второго элемента связи, выход первого элемента И второй группы подключен к вторым входам второго элемента ИЛИ и элемента запрета первого элемента связи, выход второго элемента И второй группы соединен с первыми входами второго элемента ИЛИ и элемента запрета второго элемента связи, второй вход второго элемента И второй группы соединен с первым входом мультиплексора первого элемента связи и вторым входом мультиплексора второго элемента связи, причём в каждом элементе свягзи выход первого элемента И соединен с вторым входом первого элемента ИЛИ, выход второго элемента ИЛИ подключен к установочному входу первого триггера, выход, элемента запрета соединен с установочным входом первого триггера, ВЫХОД которого соединен с адресным входом мультиплексора, инверсным входом первого элемента И и третьим входом второго элемента И.

Риг.З

J5 38

.f

48

Фиг. 5

Изобретение относится к области вычислительной техники и может быть использовано для исследования графов, в частности, для определения доступности графа для любой вершины, наличия циклов в графе и максимального пути в графе. Цель изобретения - повышение быстродействия. Для достижения указанной цели устройство дополнительно содержит элементы ИЛИ, И, триггеры состояния, блоки записи связей и блок связи. Данное устройство имеет в 2,5 раза большее быстродействие и, кроме определения доступности любой вершины графа, позволяет а определять максимальный путь в графе и наличие циклов в нем, 6 ил. (Л