System and method for processing graphic delay data of logic circuit to reduce topological redundancy

Claim 3

A delay data processing system according to claim 1, wherein an arbitrary one of the first to fourth directional edges extending between associated two of the first to fourth vertices in the first delay network is weighted by a first weight representing a delay therealong, wherein the associated two vertices have in the second delay network an edge route therebetween consisting of corresponding two of the fifth to eighth directional edges, and wherein the edge route has a total weight therealong equivalent to the first weight.

Claim 4

A delay data processing system according to claim 1, wherein the data holding means holds the second set of graphic data as the first set of graphic data.

Claim 5

A delay data processing system according to claim 1, wherein the data processing means is operable to process the second set of graphic data as the first set of graphic data.

Claim 6

A delay data processing system according to claim 1, wherein the first set of vertices contains: a first concerned vertex; a second concerned vertex; a third concerned vertex; and a fourth concerned vertex, and the first set of weighted directional edges contains: a first concerned edge extending from the first concerned vertex to the second concerned vertex; a second concerned edge extending from the second concerned vertex to the third concerned vertex; and a third concerned edge extending from the second concerned vertex to the fourth concerned vertex, and wherein the data processing means is operable to process the first set of graphic data to obtain a third set of graphic data representing a third delay network composed of: a third set of vertices containing: the first concerned vertex, the third concerned vertex, and the fourth concerned vertex, and a third set of weighted directional edges extending between elements of the third set of vertices, the third set of weighted directional edges containing: a ninth directional edge extending from the first concerned vertex to the third concerned vertex, and a tenth directional edge extending from the first concerned vertex to the fourth concerned vertex, the ninth and tenth directional edges being not contained in the first set of weighted directional edges.

Claim 7

A delay data processing system according to claim 5, wherein the first concerned edge has a first weight, the second concerned edge has a second weight, and the third concerned edge has a third weight, and wherein the ninth directional edge has a weight equivalent to a sum of the first weight and the second weight, and the tenth directional edge has a weight equivalent to a sum of the first weight and the third weight.

Claim 8

A delay data processing system according to claim 5, wherein the data holding means holds the third set of graphic data as the first set of graphic data.

Claim 9

A delay data processing system according to claim 5, wherein the data processing means is operable to process the third set of graphic data as the first set of graphic data.

Claim 10

A delay data processing system according to claim 1, wherein the first set of vertices contains: a first concerned vertex; a second concerned vertex; a third concerned vertex; and a fourth concerned vertex, and the first set of weighted directional edges contains: a first concerned edge extending from the first concerned vertex to the third concerned vertex; a second concerned edge extending from the second concerned vertex to the third concerned vertex; and a third concerned edge extending from the third concerned vertex to the fourth concerned vertex, and wherein the data processing means is operable to process the first set of graphic data to obtain a third set of graphic data representing a third delay network composed of: a third set of vertices containing: the first concerned vertex, the second concerned vertex, and the fourth concerned vertex, and a third set of weighted directional edges extending between elements of the third set of vertices, the third set of weighted directional edges containing: a ninth directional edge extending from the first concerned vertex to the fourth concernd vertex, and a tenth directional edge extending from the second concerned vertex to the fourth concerned vertex, the ninth and tenth directional edges being not contained in the first set of weighted directional edges.

Claim 11

A delay data processing system according to claim 9, wherein the first concerned edge has a first weight, the second concerned edge has a second weight, and the third concerned edge has a third weight, and wherein the ninth directional edge has a weight equivalent to a sum of the first weight and the third weight, and the tenth directional edge has a weight equivalent to a sum of the second weight and the third weight.

Claim 12

A delay data processing system according to claim 9, wherein the data holding means holds the third set of graphic data as the first set of graphic data.

Claim 13

A delay data processing system according to claim 9, wherein the data processing means is operable to process the third set of graphic data as the first set of graphic data.

Claim 14

A delay data processing system according to claim 1, wherein the first set of vertices contains: a first concerned vertex; and a second concerned vertex, and the first set of weighted directional edges contains: a first concerned edge extending from the first concerned vertex to the second concerned vertex and having a first weight; and a second concerned edge extending from the first concerned vertex to the second concerned vertex and having a second weight not exceeding the first weight, and wherein the system further comprises another data processing means for processing the first set of graphic data to obtain a third set of graphic data representing a third delay network composed of: a third set of vertices containing: the first concerned vertex, and the second concerned vertex; and a third set of weighted directional edges extending between elements of the third set of vertices, the third set of weighted directional edges containing: the first concerned edge, the third set of weighted directional edges not containing the second concerned edge.

Claim 15

A delay data processing system according to claim 13, wherein the data holding means holds the third set of graphic data as the first set of graphic data.

Claim 16

A delay data processing system according to claim 13, wherein the data processing means is operable to process the third set of graphic data as the first set of graphic data.

Claim 17

A delay data processing system according to claim 1, wherein the first set of vertices contains: a first concerned vertex; a second concerned vertex; a third concerned vertex; a fourth concerned vertex; and a fifth concerned vertex, and the first set of weighted directional edges contains: a first concerned edge extending from the first concerned vertex to the fifth concerned vertex; a second concerned edge extending from the second concerned vertex to the fifth concerned vertex; a third concerned edge extending from the fifth concerned vertex to the third concerned vertex; and a fourth concerned edge extending from the fifth concerned vertex to the fourth concerned vertex, and wherein the data processing means is operable to process the first set of graphic data to obtain a third set of graphic data representing a third delay network composed of: a third set of vertices containing: the first concerned vertex, the second concerned vertex, the third concerned vertex, and the fourth concerned vertex, the third set of vertices not containing the fifth concerned vertex; and a third set of weighted directional edges extending between elements of the third set of vertices, the third set of weighted directional edges containing: a ninth directional edge extending from the first concerned vertex to the fourth concerned vertex, a tenth directional edge extending from the second concerned vertex to the third concerned vertex, an eleventh directional edge extending from the first concerned vertex to the third concerned vertex, and a twelfth directional edge extending from the second concerned vertex to the fourth concerned vertex, the ninth to twelfth directional edges being not contained in the first set of weighted directional edges.

Claim 18

A delay data processing system according to claim 16, wherein the data holding means holds the third set of graphic data as the first set of graphic data.

Claim 19

A delay data processing system according to claim 16, wherein the data processing means is operable to process the third set of graphic data as the first set of graphic data.

Claim 20

A delay data processing system according to claim 1, wherein the second set of weighted directional edges does not contain the first directional edge, the second directional edge, and the fourth directional edge.

Claim 21

A delay data processing system according to claim 19, wherein the second set of weighted directional edges does not contain the third directional edge.

Claim 24

A delay data processing method according to claim 21, further comprising holding the second set of graphic data as the first set of graphic data.

Claim 25

A delay data processing method according to claim 21, wherein the first set of vertices contains: a first concerned vertex; a second concerned vertex; a third concerned vertex; and a fourth concerned vertex, and the first set of weighted directional edges contains: a first concerned edge extending from the first concerned vertex to the second concerned vertex; a second concerned edge extending from the second concerned vertex to the third concerned vertex; and a third concerned edge extending from the second concerned vertex to the fourth concerned vertex, and wherein the method further comprises processing the first set of graphic data to obtain a third set of graphic data representing a third delay network composed of: a third set of vertices containing: the first concerned vertex, the third concerned vertex, and the fourth concerned vertex, and a third set of weighted directional edges extending between elements of the third set of vertices, the third set of weighted directional edges containing: a ninth directional edge extending from the first concerned vertex to the third concernd vertex, and a tenth directional edge extending from the first concerned vertex to the fourth concerned vertex, the ninth and tenth directional edges being not contained in the first set of weighted directional edges.

Claim 26

A delay data processing method according to claim 23, further comprising holding the third set of graphic data as the first set of graphic data.

Claim 27

A delay data processing method according to claim 23, further comprising processing the third set of graphic data as the first set of graphic data.

Claim 28

A delay data processing method according to claim 21, wherein the first set of vertices contains: a first concerned vertex; a second concerned vertex; a third concerned vertex; and a fourth concerned vertex, and the first set of weighted directional edges contains: a first concerned edge extending from the first concerned vertex to the third concerned vertex; a second concerned edge extending from the second concerned vertex to the third concerned vertex; and a third concerned edge extending from the third concerned vertex to the fourth concerned vertex, and wherein the method further comprises processing the first set of graphic data to obtain a third set of graphic data representing a third delay network composed of: a third set of vertices containing: the first concerned vertex, the second concerned vertex, and the fourth concerned vertex, and a third set of weighted directional edges extending between elements of the third set of vertices, the third set of weighted directional edges containing: a ninth directional edge extending from the first concerned vertex to the fourth concernd vertex, and a tenth directional edge extending from the second concerned vertex to the fourth concerned vertex, the ninth and tenth directional edges being not contained in the first set of weighted directional edges.

Claim 29

A delay data processing method according to claim 26, further comprising holding the third set of graphic data as the first set of graphic data.

Claim 30

A delay data processing method according to claim 26, further comprising processing the third set of graphic data as the first set of graphic data.

Claim 31

A delay data processing method according to claim 21, wherein the first set of vertices contains: a first concerned vertex; and a second concerned vertex, and the first set of weighted directional edges contains: a first concerned edge extending from the first concerned vertex to the second concerned vertex and having a first weight; and a second concerned edge extending from the first concerned vertex to the second concerned vertex and having a second weight not exceeding the first weight, and wherein the mehtod further comprises processing the first set of graphic data to obtain a third set of graphic data representing a third delay network composed of: a third set of vertices containing: the first concerned vertex, and the second concerned vertex; and a third set of weighted directional edges extending between elements of the third set of vertices, the third set of weighted directional edges containing: the first concerned edge, the third set of weighted directional edges not containing the second concerned edge.

Claim 32

A delay data processing method according to claim 29, further comprising holding the third set of graphic data as the first set of graphic data.

Claim 33

A delay data processing method according to claim 29, further comprising processing the third set of graphic data as the first set of graphic data.

Claim 34

A delay data processing method according to claim 21, wherein the first set of vertices contains: a first concerned vertex; a second concerned vertex; a third concerned vertex; a fourth concerned vertex; and a fifth concerned vertex, and the first set of weighted directional edges contains: a first concerned edge extending from the first concerned vertex to the fifth concerned vertex; a second concerned edge extending from the second concerned vertex to the fifth concerned vertex; a third concerned edge extending from the fifth concerned vertex to the third concerned vertex; and a fourth concerned edge extending from the fifth concerned vertex to the fourth concerned vertex, and wherein the data processing method further comprising processing the first set of graphic data to obtain a third set of graphic data representing a third delay network composed of: a third set of vertices containing: the first concerned vertex, the second concerned vertex, the third concerned vertex, and the fourth concerned vertex, the third set of vertices not containing the fifth concerned vertex; and a third set of weighted directional edges extending between elements of the third set of vertices, the third set of weighted directional edges containing: a ninth directional edge extending from the first concerned vertex to the fourth concerned vertex, a tenth directional edge extending from the second concerned vertex to the third concerned vertex, an eleventh directional edge extending from the first concerned vertex to the third concerned vertex, and a twelfth directional edge extending from the second concerned vertex to the fourth concerned vertex, the ninth to twelfth directional edges being not contained in the first set of weighted directional edges.

Claim 35

A delay data processing method according to claim 32, further comprising holding the third set of graphic data as the first set of graphic data.

Claim 36

A delay data processing method according to claim 32, further comprising processing the third set of graphic data as the first set of graphic data.

Claim 37

A logic circuit delay data holding system for holding a set of delay data of a target logic circuit having a multiplicity of inputs and a multiplicity of outputs, the system comprising: a delay network generation means for responding to set of constitutional data of the logic circuit to generate delay network composed of: a plurality of source vertices corresponding to a plurality of input terminals of the logic circuit, a plurality of sink vertices corresponding to a plurality of output terminals of the logic circuit, a plurality of internal vertices lying on a plurality of paths connecting the source vertices with the sink vertices, and a plurality of directional edges each interconnecting two of the source, sink and internal vertices, the directional edges being each weighted so that a largest weighted path length between any concerned one of the source vertices and any concerned one of the sink vertices is in accord with a delay time between a corresponding one of the input terminals of the logic circuit and a corresponding one of the output terminals of the logic circuit; a delay network hold means for holding the set of delay data, as it represents the delay network; and a delay network transform means for transforming the delay network to reduce a quantity of the delay data in the delay network hold means so that all paths of the delay network are represented and the largest weighted path length between the concerned source vertex and the concerned sink vertex is in accord with the delay time between the corresponding input terminal of the logic circuit and the corresponding output terminal of the logic circuit.

Claim 38

A logic circuit delay data holding system for holding a set of delay data of a target logic circuit having a multiplicity of inputs and a multiplicity of outputs, the system comprising: a delay network generation means for responding to set of constitutional data of the logic circuit to generate delay network composed of: a plurality of source vertices corresponding to a plurality of input terminals of the logic circuit, a plurality of sink vertices corresponding to a plurality of output terminals of the logic circuit, a plurality of internal vertices lying on a plurality of paths connecting the source vertices with the sink vertices, and a plurality of directional edges each interconnecting two of the source, sink and internal vertices, the directional edges being each weighted so that a largest weighted path length between any concerned one of the source vertices and any concerned one of the sink vertices is in accord with a delay time between a corresponding one of the input terminals of the logic circuit and a corresponding one of the output terminals of the logic circuit; a delay network hold means for holding the set of delay data, as it represents the delay network; and a delay network transform means for transforming the delay network to reduce a quantity of the delay data in the delay network hold means so that all paths of the delay network are represented and the largest weighted path length between the concerned source vertex and the concerned sink vertex is in accord with the delay time between the corresponding input terminal of the logic circuit and the corresponding output terminal of the logic circuit.

Claim 39

A logic circuit delay data holding method for holding a set of delay data of a logic circuit with a multiplicity of inputs and a multiplicity of outputs, the logic circuit being a target of a delay computation, the method comprising: a first step of responding to a set of constitutional data of the logic circuit to generate a delay network including: a plurality of source vertices corresponding to a plurality of input terminals of the logic circuit, a plurality of sink vertices corresponding to a plurality of output terminals of the logic circuits, and a plurality of paths cooperatively connecting the source vertices with the sink vertices, the plurality of paths consisting of a plurality of directional edges each weighted so that a total weight along a most-weighted path between any concerned one of the source vertices and any concerned one of the sink vertices is in accord with a delay time between one of the input terminals corresponding to the concerned source vertex and one of the output terminals corresponding to the concerned sink vertex; a second step of holding the set of delay data, as it represents the delay network; and a third step of transforming the delay network to reduce a quantity of the delay data so that all paths of the delay network are represented and the total weight along the most-weighted path between the concerned source vertex and the concerned sink vertex is kept in accord with the delay time between said one of the input terminals corresponding to the concerned source vertex and said one of the output terminals corresponding to the concerned sink vertex.

Claim 40

A logic circuit delay data holding method for holding a set of delay data of a logic circuit with a multiplicity of inputs and a multiplicity of outputs, the logic circuit being a target of a delay computation, the method comprising: a first step of responding to a set of constitutional data of the logic circuit to generate a delay network including: a plurality of source vertices corresponding to a plurality of input terminals of the logic circuit, a plurality of sink vertices corresponding to a plurality of output terminals of the logic circuits, and a plurality of paths cooperatively connecting the source vertices with the sink vertices, the plurality of paths consisting of a plurality of directional edges each weighted so that a total weight along a most-weighted path between any concerned one of the source vertices and any concerned one of the sink vertices is in accord with a delay time between one of the input terminals corresponding to the concerned source vertex and one of the output terminals corresponding to the concerned sink vertex; a second step of holding the set of delay data, as it represents the delay network; and a third step of transforming the delay network to reduce a quantity of the delay data so that all paths of the delay network are represented and the total weight along the most-weighted path between the concerned source vertex and the concerned sink vertex is kept in accord with the delay time between said one of the input terminals corresponding to the concerned source vertex and said one of the output terminals corresponding to the concerned sink vertex.

Claim 41

A logic circuit delay data holding method according to claim 35, wherein said first step comprises: generating a first one of the source vertices corresponding to a first one of the input terminals; generating a first one of the sink vertices corresponding to a first one of the output terminals having a signal-transmittable relationship relative to the first input terminal; generating a first one of the directional edges connecting the first source vertex with the first sink vertex and having a sense thereof according to a signal transmission direction between the first input terminal and the first output terminal; calculating a delay time between the first input terminal and the first output terminal; and providing the first directional edge with a first weight representing the delay time.

Claim 42

A logic circuit delay data holding method according to claim 37, wherein the delay network further includes one or more internal vertices corresponding to one or more gates of the logic circuit, and wherein said first step further comprises: generating a first one of the internal vertices corresponding to a first one of the gates connected by a first net to at least one of the first input and first output terminals as a related terminal of the logic circuit; generating a second one of the directional edges corresponding to the first net, the second directional edge connecting the first internal vertex with one of the first source and first sink vertices corresponding to the related terminal and having a sense thereof according to a signal transmission direction of the first net; providing the second directional edge with a second weight representing a delay time of the first net; and additionally providing the second directional edge with a third weight representing a delay time of the first gate.

Claim 43

A logic circuit delay data holding method according to claim 38, wherein the delay network includes a first graph composed of a pair of triangles joining each other at one point, where they are angled, and wherein said third step comprises transforming the first graph into a second graph composed of a quartet of line segments joining each other at one point, where they end.

Claim 44

A logic circuit delay data holding method according to claim 39, wherein said third step further comprises transforming the first graph into a third graph composed of another triangle and a pair of line segments ending at one angle of said another triangle.

Claim 45

A logic circuit delay data holding method according to claim 39, wherein the delay network includes a third graph composed of a triple of line segments joining each other at one point, where they end, and wherein said third step further comprises transforming the third graph into a fourth graph composed of a pair of line segments joining each other one point, where they end.

Claim 46

A logic circuit delay data holding method according to claim 41, wherein the delay network includes a fifth graph composed of a pair of line segments joining each other at two points, where they end, and wherein said third step further comprises transforming the fifth graph into a sixth graph composed of a single line segment ending at the two points.