SU1075268A1

SU1075268A1 - Device for simulating network graphs

Info

Publication number: SU1075268A1
Application number: SU823529159A
Authority: SU
Inventors: Виктор Алексеевич Титов; Владимир Львович Гайдуков; Владимир Валентинович Зотов
Original assignee: Военная Ордена Ленина,Ордена Октябрьской Революции И Ордена Суворова Академия Им.Ф.Э.Дзержинского
Priority date: 1982-12-27
Filing date: 1982-12-27
Publication date: 1984-02-23

Abstract

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ СЕТЕВЫХ ГРАФОВ, содержащее матричную модель графа, ij -и узел которой включает триггер, первый и второй элементы И, причем выход триггера подключен к первым входам первого и второго элементов И, первую и вторую группы элементов ИЛИ, первую и вторую группы триггеров, элемент И, генератор тактовых импульсов, счетчик, причем выход (-го (; ...п) .триггера первой группы подключен к вторым входам первых элементов И i -и с троки матричной модели графа, выход -го триггера второй группы соединен с вторыми входами вторых элементов И i-го столбца матричной модели графа, выход первого элемента И Ц -го узла матричной модели графа подключен к соответствующему входу i -го элемента ИЛИ первой группы, выход второго элемента И ij -го узла матричной модели графа соединен с соответствующим входом i -го элемента ИЛИ второй группы, выход i-го элемента ИЛИ первой группы подключен к единичному входу i -го триггера первой группы , выход i-го элемента ИЛИ второй группы соединен с единичным входом i-ro триггера второй группы, отличающеес тем, что, с целью повышени быстродействи , в него введены дешифратор и элемент i задержки, выход которого подключен к нулевым входам триггеров первой (Л и второй групп, выход генератора тактовых импульсов соединен с первым входом элемента И, второй вход которого вл етс входом запуска устройства , выход элемента И подключен к входу элемента задержки и входу счетчика, выход которого соединен с входом дешифратора, выходы которого подключены соответственно к входам элементов ИЛИ первой и второй групп.A DEVICE FOR SIMULATION OF NETWORK GRAPHS, containing a matrix graph model, ij - and the node of which includes a trigger, first and second elements AND, the trigger output connected to the first inputs of the first and second elements AND, the first and second groups of elements OR, the first and second groups of triggers , element I, clock generator, counter, the output (th (; ... n). trigger of the first group is connected to the second inputs of the first elements AND i - and from the row of the matrix model of the graph, output of the second trigger of the second group is connected to second inputs second the elements of the i-th column of the matrix model of the graph, the output of the first element of the C node of the matrix model of the graph is connected to the corresponding input of the i-th element OR of the first group, the output of the second element AND of the ij-th node of the matrix model of the graph is connected to the corresponding input of i - the second element OR of the second group, the output of the i-th element OR of the first group is connected to the single input of the i-th trigger of the first group, the output of the i-th element OR of the second group is connected to the single input of the i-ro trigger of the second group, characterized in that to increase speed entered a decoder and a delay element i, the output of which is connected to the zero inputs of the first triggers (L and second groups, the output of the clock generator is connected to the first input of the And element, the second input of which is the device start input, the output of the And element is connected to the input of the delay element and the input of the counter, the output of which is connected to the input of the decoder, the outputs of which are connected respectively to the inputs of the OR elements of the first and second groups.

Description

Изобретение относитс к вычислительной технике и может быть использовано при исследовании параметров сетевых графов, а также при аппаратной реализации в специализированных процессорах макрокоманды определени вершин/ образующих транзитивное и обратное транзитивное замыкание дл всех вершин моделируемого графа . I Известно устройство дл моделиров ни сетевых графов, содержащее блок управлени , первый вход которого сое динен с выходом генератора тактовых импульсов, счетчик импульсов, тригге ры формирователей дуг по числу строк и столбов матричной модели сети, по числу столбцов матричной модели сети элементы ИЛИ,| элементы И, регистрирующие счетчики, схемы сравнени , выходы каждой из которой подключены к нулевым входам триггеров одноименной со столбцом строки матричной модели сети, а первые входы - к Bfcixoдам регистрирующих счетчиков, вторые входы схем сравнени подключены к выходу счетчика импульсов, вход кото рого подключен к выходу блока управлени , первые входы элементов И подключены к выходу блока управлени , вторые входы элементов И подключены к выходам элементов ИЛИ, входы которых подключены к выходам триггеров формирователей дуг одноименного столбца матричной модели сети ij . Известное устройство обеспечивает только возможность распределени вершин графа по рангам и не позвол ет определ ть вершины, образующие транзитивное и обратное транзитивное замыкани дл отдельных вершин моделируемого графа. Наиболее близким к изобретению вл етс устройство дл моделировани сетевых графов, содержащее блок управлени , первый вход которого Соединен с выходом генератора тактовых импульсов, счетчик импульсов, триггеры формирователей дуг по числу строк и столбцов матричной модели сети,по числу столбцов матричной модели сети первые элементы ИЛИ, элемен ты-И, регистрирующие счетчики, схемы сравнени , входы каждой из которых подключены к нулевым входам триггеров одноименной со столбцом строки матричной модели сети, а первые входы - к выходам регистрирующих счетчиков, вторые входы схем сравнени подключены к выходу счетчика импульсов , вход которого подключен к выходу блока управлени , первые входы элементов И подключены к выходу блока управлени , вторые входы элементов И подключены к выходам соответствующих первых элементов ИЛИ, входы которых подключены к выходам триггеров формирователей дуг одноименного столбца матричной модели сети, элемент НЕ, элемент И, выход которого через элемент НЕ подключенк управл емому входу блока управлени , по числу столбцов матричной модели сети вторые и третьи элементы ИЛИ, триггеры пр мого и обратного отображени , управл ющие триггеры , по числу строк и столбцов матричной модели сети первые и вторые элементы И, информационные входы каждого из которых подключены к входу соответствующего триггера формировател дуг, входы каждого второго элемента ИЛИ подключены к выходам первых элементов И одноименного столбца матричной модели сети, а выходы - к входам соответствуюцих триггеров пр мого отображени , выходы которых подключены к управл емым входам первых элементов И одноименной строки матричной модели сети, входы каждоготретьего элемента ИЛИ подключены к выходам вторых элементов И одноименной строки матричной модели сети, а выходы - к входам соответствующих триггеров обратного Отображени , выходы которых подключены к управл емым входам вторых элементов И одноименного столбца матричной модели сети, входы каждого управл ющего триггера подключены к выходам соответствующей схемы сравнени , а выходы - к одноименным входам первого элемента И 2 . Недостатком известного устройства вл етс низкое быстродействие при определении вершин, образующих транзитивное и обратное транзитивное замыкани дл всех вершин моделируемого графау из-за необходимости дополнительного сбрасывани триггеров пр мого и обратного отображени , а также установки триггеров очередной вершины в единичное состо ние. Целью изобретени влйетс повышение быстродействи . Поставленна цель достигаетс тем, что в устройство дл моделировани сетевых графов, содержащее матричную модель графа, ij -и узел которой включает триггер, первый и второй элементы И, причем выход триггера подключен к первым входам первого и второго элементов И, первую и вторую группы элементов ИЛИ, первую и вторую группы триггеров, элемент И, генератор тактовых импульсов, счетчик , причем выход i -го (, ...,п) триггера первой группы подключен ко вторым входам первых элементов И i-и строки матричной модели графа, выход -го триггера второй группы соединен со вторыми входами вторых элементов И -го столбца матричной модели графа, выход первогоThe invention relates to computing technology and can be used in the study of network graph parameters, as well as in hardware implementation in specialized processors of the macro vertex / generating generators for the transitive and reverse transitive closure for all the vertices of the simulated graph. I A device for modeling network graphs is known, which contains a control unit, the first input of which is connected to the clock generator output, a pulse counter, triggers of arc drivers by the number of rows and columns of the network matrix model, by the number of columns of the matrix network model OR, | elements AND, registering counters, comparison circuits, the outputs of each of which are connected to the zero inputs of triggers of the network model of the same name with a column, and the first inputs to the Bfcixes of the registering counters, the second inputs of the comparison circuits connected to the output of the pulse counter, the input of which is connected to the output of the control unit, the first inputs of the AND elements are connected to the output of the control unit, the second inputs of the AND elements are connected to the outputs of the OR elements, whose inputs are connected to the outputs of the triggers of the arc drivers of the same name Foot of the column of the matrix model ij network. The known device provides only the possibility of distributing the vertices of the graph by ranks and does not allow determining the vertices that form the transitive and reverse transitive closures for the individual vertices of the simulated graph. Closest to the invention is a device for modeling network graphs containing a control unit, the first input of which is connected to the output of a clock generator, a pulse counter, triggers of arc drivers by the number of rows and columns of the matrix model of the network, by the number of columns of the matrix model of the network first elements OR , I-elements, registering counters, comparison circuits, the inputs of each of which are connected to the zero inputs of triggers of the matrix model of the network of the same name with a column, and the first inputs to the outputs of the the second counters are connected to the output of the pulse counter whose input is connected to the output of the control unit, the first inputs of the AND elements are connected to the output of the control unit, the second inputs of the AND elements are connected to the outputs of the corresponding first OR elements whose inputs are connected to the outputs of the trigger drivers arcs of the same column of the matrix network model, the element is NOT, the element is AND, whose output through the element is NOT connected to the controlled input of the control unit, by the number of columns of the matrix model networks second and third OR elements, forward and reverse mapping triggers, control triggers, by the number of rows and columns of the matrix network model, the first and second AND elements, the information inputs of each of which are connected to the input of the corresponding arc driver trigger, the inputs of each second element OR connected to the outputs of the first elements of the same column of the matrix model of the network, and outputs to the inputs of the corresponding direct mapping triggers, the outputs of which are connected to the controlled inputs of the first elements of the same the rows of the matrix model of the network, the inputs of each third element OR are connected to the outputs of the second elements AND the same name of the matrix network model, and the outputs - to the inputs of the corresponding reverse display triggers, the outputs of which are connected to the controlled inputs of the second network elements of the same name of the matrix network model, the inputs of each the control trigger is connected to the outputs of the corresponding comparison circuit, and the outputs are connected to the same inputs of the first element 2. A disadvantage of the known device is the low speed in determining the vertices that form the transitive and reverse transitive closures for all the vertices of the simulated graph due to the need to additionally reset the forward and reverse mapping triggers, and also install the next vertex triggers in a single state. The aim of the invention is to improve speed. The goal is achieved by the fact that the device for modeling network graphs contains a matrix model of a graph, the ij-node of which includes a trigger, the first and second elements AND, the trigger output being connected to the first inputs of the first and second elements AND, the first and second groups of elements OR, the first and second groups of triggers, the AND element, the clock pulse generator, the counter, the output of the i -th (, ..., n) trigger of the first group is connected to the second inputs of the first elements And the i -th row of the matrix model of the graph, output - second trigger ppa is connected to the second inputs of the second elements of the AND column of the matrix model of the graph, the output of the first

элемента И ij -го узла матричной модели графа подключен к соответствующему входу i-го элемента ИЛИ первой группы, выход второго элемента И 1)-го узла матричной модели графа соединен с соответствующим входом i-ro элемента ИЛИ второй группы, выход i -го элемента ИЛИ первой группы подключен к единичному входу -го триггера первой группы, выход i-го элемента ИЛИ второй группы соединен сединичным входом i-ro триггера, второй группы введены дешифратор и элемент задержки, выход которого подключен к нулевым входам триггеров первой и второй групп, выход генера тора тактовых импульсов соединен с первым входом элемента И, второй вход которого вл етс входом запуска устройства, выход элемента И подключен к входу элемента задержки и входу счетчика, выход которого соединен с входом дешифратора, выходы которого подключены соответственно к входам элементов ИЛИ первой и второй групп.element of the ij-th node of the matrix model of the graph is connected to the corresponding input of the i-th element OR of the first group, the output of the second element AND 1) of the node of the matrix model of the graph is connected to the corresponding input of the i-ro element OR of the second group, the output of the i-th element OR of the first group is connected to the single input of the first trigger of the first group, the output of the i-th element OR of the second group is connected to the trigger input of the i-ro trigger, the second group includes the decoder and the delay element whose output is connected to the zero inputs of the first and second trigger points, output g The clock generator is connected to the first input of the element I, the second input of which is the device start input, the output of the element AND is connected to the input of the delay element and the input of the counter, the output of which is connected to the input of the decoder, the outputs of which are connected respectively to the inputs of the elements OR first and second groups.

На чертеже представлена структурна схема устройства.The drawing shows a block diagram of the device.

Устройство .содержит матричную модель 1 графа, триггеры 2 (формирователей дуг), первые 3 и вторые 4 элементы И, по числу столбцов матричной модели графа первые 5 j, ..., 5 п и вторые 6f, ..., 6п элементы ИЛИ, первые ,l , , . . , 7 и и вторые 8 I, . . ., 8 ц триггеры, дешифратор 9, счетчик 10, элемент 11 задержки, элемент И 12, генератор 13 тактовых импульсов, вход 14 запуска, выходы 15, ..., 15,1, 16i , . .., 1б„ и 17. . The device contains a matrix model of 1 graph, triggers 2 (formers of arcs), the first 3 and second 4 elements AND, by the number of columns of the matrix model of the graph the first 5 j, ..., 5 n and the second 6f, ..., 6n elements OR , first, l,,. . , 7 and the second 8 I,. . ., 8 C triggers, decoder 9, counter 10, delay element 11, element 12, generator 13 clock pulses, start input 14, outputs 15, ..., 15.1, 16i,. .., 1b „and 17..

Матрична модель 1 графа представл ет собой матрицу п ХЦ, где п - максимальное число вершин в графе, однородных чеек в составе триггера 2, первого 3 и второго 4 элементов И.Matrix model 1 of the graph is a matrix of n HZ, where n is the maximum number of vertices in the graph, homogeneous cells as part of trigger 2, first 3 and second 4 elements I.

Устройство дл моделировани сетевых графов работает следующим образом.A device for simulating network graphs operates as follows.

Первоначально в нулевое положение, устанавливаютс все триггеры 7, 8 и счетчик 10. Информаци о топологии моделируемого графа заноситс путем установки соответствующих триггеров 2 в единичное состо ние. Соответствующий триггер 2jj (i,j l, ...,n) формировател дуги опред ел етс пересечением -и строки ( i - номер начальной вершины моделируемой ветви грифа) с J-м столбцом (j - номер конечной вершины моделируемой ветви графа).Initially, all the triggers 7, 8 and the counter 10 are set to zero. Information about the topology of the simulated graph is entered by setting the corresponding triggers 2 to one state. The corresponding trigger 2jj (i, j l, ..., n) of the arc former is determined by the intersection of the –and line (i is the number of the initial vertex of the simulated neck branch) with the Jth column (j is the number of the final vertex of the simulated branch of the graph).

Определение вершин графа, образующих транзитивное замыкание, а также обратное транзитивное замыкание дл всех вершин начинаетс после занесени исходной информацииThe definition of the vertices of the graph that form the transitive closure, as well as the reverse transitive closure for all vertices begins after entering the initial information

на соответствующие триггеры 2 и обнулени триггеров 7 и 8, а также счетчика 10. После подачи управл ющего сигнала на вход 14 импульсы с генератора 13 начинают поступать через элемент И 12 на вход счетчика 10 и элемента .11 задержки. С выхода счетчика 10 код (первоначально 0...01) поступает на вход дешифратора 9, на выходе которого возбуждаетс только одна шина (вначале перва ), после чего единичный сигнал через элементы ИЛИ 5 и 6 перебрасывает в единичное состо ние соответствующие триггеры 7 и В (вначале триггеры 7 и 8с) .to the corresponding triggers 2 and zeroing triggers 7 and 8, as well as counter 10. After the control signal is applied to input 14, pulses from generator 13 begin to flow through element 12 at the input of counter 10 and delay element 11. From the output of counter 10, the code (initially 0 ... 01) is fed to the input of the decoder 9, at the output of which only one bus is excited (first, first), after which the single signal through the elements OR 5 and 6 flips the corresponding triggers 7 and In (first triggers 7 and 8c).

Единичный сигнал с выхода триггера 7 (,-,П ) поступает на вторые входы элементов. И 3 i -и строки матричной модели, вторые входы которых подсоединены к выходу одноименного триггера 2, а выход - к одноименному входу элемента ИЛИ 5j, (j-l,...,n) единичным сигналом с выхода которого устанавливаетс в единичное состо ние триггер 7J, и т.д. Так определ ютс все вершины, образующие транзитивное замыкание дл 1 -и вершины. Таким вершинам соответствует единичное состо ние тригеров 7, и соответствунвдий код снимаетс с выходов 15 устройства. В этом коде единица в j -м разр де соответствует номеру вершины, вход щей в транзитивное замыкание дл jj-й вершины моделируемого графа.A single signal from the output of the trigger 7 (, -, P) is fed to the second inputs of the elements. And 3 i - and rows of the matrix model, the second inputs of which are connected to the output of the same trigger 2, and the output to the same input of the element OR 5j, (jl, ..., n) with a single signal from the output of which is set to one state trigger 7J , etc. This is how all vertices forming the transitive closure for the 1st vertex are defined. Such vertices correspond to the unit state of triggers 7, and the corresponding code is removed from the outputs 15 of the device. In this code, the unit in the jth bit corresponds to the number of the vertex entering the transitive closure for the jjth vertex of the simulated graph.

Одновременно единичный сигнал с выхода триггера 8| (-1,.,,,п поступает на вторые входы элементов И 4 I -го столбца матричной модели , вторые входы которых подсоединены к выходу одноименного триггера 2, а выход - к одноименному входу элемента б (j-l,...,n), единичным сигналом с выхода которого устанавливаетс в единичное состо ние триггер 8J, и т.д. Так определ ютс все вершины, образующие обратное транзитивное замыкание дл -и вер шины. Таким вершинам соответствует единичное состо ние триггеров 8, а соответствующий код снимаетс с выходов 16 устройства.Simultaneously, a single signal from the output of the trigger 8 | (-1,. ,,, p goes to the second inputs of AND 4 elements of the I-th column of the matrix model, the second inputs of which are connected to the output of the same trigger 2, and the output to the same input of element b (jl, ..., n) , a single signal from the output of which is set to a single state trigger 8J, etc. This is how all vertices forming the reverse transitive closure for and vertices of the bus are determined. Such vertices correspond to the single state of triggers 8, and the corresponding code is removed from the outputs 16 devices.

Далее, после завершени всех перходных процессов по определению транзитивного и обратного транзитивного замыканий, единичный сигнал с выхода элемента 11 задержки перебррсывает все триггеры 7 и 8 в нулевое состо ние. ..Further, after completion of all transient processes, by the definition of transitive and reverse transitive closures, a single signal from the output of the delay element 11 refreshes all triggers 7 and 8 to the zero state. ..

На вход счетчика 10 поступает оч едной импульс, и транзитивное и обратное транзитивное замыкани определ ютс дл второй вершины моделируемого графа и так далее, до тех пор, пока на счетчике не зафиксируетс код числа И, после чего с приходом очередного импульса счетчик 10 переполн етс , о чем свидетельствует единичный сигнал наBbf-; ходе 17 устройства.A single pulse arrives at the input of counter 10, and the transitive and reverse transitive closures are determined for the second vertex of the simulated graph, and so on, until the code of the number I is recorded on the counter, then with the arrival of the next pulse, the counter 10 overflows, as evidenced by a single signal on Bbf-; course 17 devices.

Таким образом, устройство обеспечивает определение транзитивного и обратного транзитивного замыканий одновременно дл всех вершин моделируемого графа.Thus, the device provides the definition of transitive and reverse transitive closures simultaneously for all vertices of the simulated graph.

i«r;.. jsi "r; .. js

Claims

DEVICE FOR MODELING NETWORK GRAPHS, containing a matrix model of the graph (the jth node of which includes a trigger, the first and second AND elements, the trigger output connected to the first inputs of the first and second AND elements, the first and second groups of OR elements, the first and second groups triggers, AND element, clock generator, counter, and the i-ro output (ϊ ... η). The trigger of the first group is connected to the second inputs of the first elements of And the ίth row of the graph matrix model, the output of the ΐth trigger of the second group connected to the second inputs of the second elements s And the ΐ-th column of the matrix model of the graph, the output of the first element J Jj-th node of the matrix model of the graph is connected to the corresponding input of the ί-th element OR of the first group, the output of the second element And the ij-th node of the matrix model of the graph is connected to the corresponding input ί of the ith element of the second group, the output of the ίth element of the first group is connected to a single input of the ίth trigger of the first group, the output of the ith element of the second group is connected to a single input (of the second trigger of the second group, characterized in that, in order to improve performance, not o a decoder and a delay element are introduced, the output of which is connected to the zero inputs of the triggers of the first and second groups, the output of the clock pulse generator is connected to the first input of the And element, the second input of which is the device start input, the output of the And element is connected to the input of the delay element and the counter input, the output of which is connected to the input of the decoder, the outputs of which are connected respectively to the inputs of the OR elements of the first and second groups.