JPS60235242A - data processing equipment - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] [Technical Field of the Invention] The present invention relates to a method in which a logical circuit network of a data processing device is represented by an undirected graph l~, and the maximum cost of a pair of starting point node and ending point node is iY'"Relates to a data processing device that checks whether the total cost is within 1 samurai size."

[Prior art]

Conventionally, the maximum cost of 1,′j is the detection and checking of pairs of start and end nodes V′, Yv++,
11] For the computer and its software, write line 2 (.

It's me. Therefore, the logic network is large 1,11ν,
'1, the amount of data to be handled becomes enormous, and the high specification j(i'
ll.

Even if you use a personal computer, it will take a long time to control the computer.
This method has the disadvantage of requiring a long processing time.

[Object of the Invention 1] The object of the present invention is to eliminate the above-mentioned drawback of the conventional method requiring a long convoter processing time, and to detect a pair of a start node and an end node with the maximum cost in a short time! The object of the present invention is to provide a data processing device capable of checking whether the maximum cost is within the allowable maximum cost of an end node.

[Structure of the invention]

According to the present invention, the data processing device is a directed graph in which connections between nodes in which each sieve element has its own cost correspond to an edge (the end node has the maximum allowable cost in the end node call). a node select control unit that selects the data represented by m) as a starting point node and other nodes according to its node attributes; and a start node storage unit that records the selected starting point note.

A node storage unit that stores all nodes, an l/race control unit that detects adjacent nodes, a maximum cost calculation unit that calculates the maximum cost at the detected node, and the detected node is the end point node. a maximum cost check unit that checks whether the maximum cost calculated by the lowest cost calculation unit is within the allowable maximum cost of the end point node; and an output unit that outputs a pair of end point nodes.

[Embodiments of the invention]

Next, an embodiment of the data processing device according to the present invention will be given and explained in detail with reference to the drawings.
゜ Fig. 1 is a block diagram showing the configuration of an embodiment of the present invention.This embodiment has the following advantages: 1. The logic circuit network is expressed as a directed graph. In this data, one logic element is represented as a node, and IW p (1-) between the logic elements is represented as an edge, and each node has its own cost. 17. Each node has node attributes (start point, end point, etc.).

The number of branches that enter a node, the unique cost of the node, the maximum cost at that node size, and the starting point node that will be the maximum cost,
Furthermore, if that node is a destination node, it has the maximum allowable cost to reach that destination node.

In FIG. 1, data representing a logic circuit network as a directed graph is input from the outside to the node select control unit 1 through a data path 1°.

The node selection control unit 1 stores the starting point node from among these data in the starting node storage unit 2 via the data path 11, and stores all nodes including the starting point node in the node storage unit 3 via the data path 12. do. When all the data has been stored, the trace control unit 4 sequentially retrieves the nodes from the start node storage unit 2 via the data path 14 using a first-in, first-out method, and converts the nodes connected to the nodes into nodes. It is read from the storage unit 3 by the data path 15. This read node is sent to the maximum cost calculation unit 5 via the data path 17.

The maximum cost calculation unit 5 adds the maximum cost (a) of the node taken out from the start node storage unit 2 up to that node and the unique cost (b) of the node of the detected note, and calculates the result. Added cost (a-1-1
]) and the maximum cost (c) already possessed by the detected node. As a result, a+1
)≧C, in the data path 18, the maximum cost at the own node is transferred from C to a+1), and detected. The start point node held by the selected node is taken from the start node storage unit 2 and rewritten to the start point node held by the 11th node. a-1-1) (cl in case of c:.

The data path 18 does not rewrite the contents of the detected node in the node storage unit 3. moreover.

Maximum cost calculation unit 5 is connected through data path 19.

The detected nodes are sent to the node determination section 6.

If the node is the end node, the node determination unit 6 stores the pair node, the pair of the end node, the maximum cost at that time, and the maximum allowable cost of the end node through the data path 21 in the pair node storage unit 7. and send. If the node is not a destination node, subtract II II from the number of branches entering the node and transfer the data to data path 20.
The content of the node in the node storage unit 3 is rewritten through

When the number of branches of the node reaches 11011, the node is stored in the start node storage unit 2 via the data path 13. Then, the process moves to the trace control section 4.

When the data processing in -1- is continued until the nodes in the start node storage unit 2 become empty, the pair node records 1,
The pair of the starting point node and the ending point node having the maximum cost is stored in the 6th part 7. These pairs are sent to the maximum cost checker 8 via the data path 22. 11. Maximum cost check section 8. Compare the maximum cost at the destination node with the maximum allowable cost at the destination node.

Only the larger pair of the former is sent to the output 9 via the data path 23. The output unit 9 sequentially outputs the pairs through the data path 24.

FIG. 2 is a diagram showing an example of data representing a logical circuit network as a directed graph. In this figure.

Each start point node arrives at the end point node set (2) from the set (1) via a node i (3) that does not belong to the start point/end point node set. End node T, 1 start node S1
The end point from the start point node T1 is the end point from the start point node S, .Si, the end point from the start point node 1-'Tm11':l, the end point from the start point node S1...Sk...Sol. Therefore, the maximum cost at 'rat is a, the maximum cost at Tito is S, the maximum cost at TIT, -d is C.

The maximum allowable cost is X and j~, and the relationship between them is a
If < x , b > x , c < x, the only pairs that are output are those that have the end node T1 exceeding the maximum allowable cost l□x.

〔Effect of the invention〕

As is clear from the above explanation, according to the present invention, when a pair of a start node and an end node with a large cost I in a logic circuit network is detected, the maximum cost is determined by the allowable tolerance of the end node. It becomes possible to check in a short time whether the cost is within the maximum cost, and the effect of improving processing efficiency is significant.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing the configuration of an embodiment according to the present invention;
FIG. 2 is a diagram showing an example of data in which a logical circuit network applied to the embodiment of FIG. 1 is expressed as a directed graph. In the figure, 1 is a node select control section. 2 is a start node storage unit, 3 is a node storage unit, 4 is a trace control unit, 5 is a maximum cost calculation unit, 6 is a node determination unit, 7 is a pair node storage unit, 8 is a maximum cost check unit, 9 is the output part. 8-

Claims (1)

[Claims] 1. A logic circuit network is expressed as a directed graph in which logic elements have their own costs and connections between nodes correspond to edges (an end node has the maximum allowable cost up to that end node). a node select control unit that selects the selected data as a start node and other nodes according to its node attributes; a start node storage unit that stores the selected start node; and a node storage unit that stores all the nodes. , a trace control unit that detects adjacent nodes, a maximum cost calculation unit that calculates the maximum cost at the detected notes,
A node determination unit that determines whether a detected node is an end node; and a pair/note storage unit that stores a pair of a start node and an end node having the maximum cost. and a maximum cost check unit that checks whether the /ζ maximum cost calculated by the maximum cost calculation unit is within the allowable maximum cost of the end node. Data processing device 111j characterized in that it includes an output unit that outputs a pair of a starting point node and an ending point node.