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

• US 5,841,673 A
• Filed: 01/30/1996
• Issued: 11/24/1998
• Est. Priority Date: 01/30/1995
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Kobayashi, Noriya, Malik, Sharad
• Primary Examiner(s): Trans, Vincent N.
• Assistant Examiner(s): Siek, Vuthe
• Application Number:
  US08/593,569
• Time in Patent Office: 1,029 Days
• Field of Search: 364/488-491, 364/578, 395/500
• US Class Current: 716/108
• CPC Class Codes: G06F 30/3312 Timing analysis

Abstract

A delay network of logic circuit delay data composed of a first set of vertices containing first to fourth vertices, and a first set of weighted directional edges containing a first directional edge extending from the first vertex to the fourth vertex, a second directional edge extending from the second vertex to the third vertex, a third directional edge extending from the first vertex to the third vertex, and a fourth directional edge extending from the second vertex to the fourth vertex, is converted into a delay network composed of a second set of vertices containing the first to fourth vertices and an added fifth vertex, and a second set of weighted directional edges containing a fifth directional edge extending from the first vertex to the fifth vertex, a sixth directional edge extending from the second vertex to the fifth vertex, a seventh directional edge extending from the fifth vertex to the third vertex, and an eighth directional edge extending from the fifth vertex to the fourth vertex.

Claims

1. A system for processing data representing delays in a logic network, comprising:

a data holding means for holding a first set of graphic data representing a first delay network composed of;

a first set of vertices comprising a first vertex, a second vertex, a third vertex, and a fourth vertex, and

a first set of weighted directional edges extending between elements of the first set of vertices and containing a first directional edge extending from the first vertex to the fourth vertex having a weight x1, a second directional edge extending from the second vertex to the third vertex having a weight x2, a third directional edge extending from the first vertex to the third vertex having a weight p1, and a fourth directional edge extending from the second vertex to the fourth vertex having a weight p2;

means for determining that the first set of delay data meets the condition (x1+x2)=(p1+p2); and

a data processing means for processing the first set of graphic data to obtain a second set of graphic data representing a second delay network composed of;

a second set of vertices comprising the first vertex, the second vertex, the third vertex, the fourth vertex, and a fifth vertex not contained in the first set of vertices, and

a second set of weighted directional edges extending between elements of the second set of vertices and containing a fifth directional edge extending from the first vertex to the fifth vertex having a weight of zero, a sixth directional edge extending from the second vertex to the fifth vertex having a weight (x2-p1), a seventh directional edge extending from the fifth vertex to the third vertex having a weight p1, and an eighth directional edge extending from the fifth vertex to the fourth vertex having a weight x1.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

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

21. A method for processing data representing delays in a logic network, comprising the steps of:

holding a first set of graphic data representing a first delay network composed of;

a first set of vertices comprising a first vertex, a second vertex, a third vertex, and a fourth vertex, and

a first set of weighted directional edges extending between elements of the first set of vertices and containing a first directional edge extending from the first vertex to the fourth vertex having a weight x1, a second directional edge extending from the second vertex to the third vertex having a weight x2, a third directional edge extending from the first vertex to the third vertex having a weight p1, and a fourth directional edge extending from the second vertex to the fourth vertex having a weight p2;

determining that the first set of delay data meets the condition (x1+x2)=(p1+p2); and

processing the first set of graphic data to obtain a second set of graphic data representing a second delay network composed of;

a second set of vertices comprising the first vertex, the second vertex, the third vertex, the fourth vertex, and a fifth vertex not contained in the first set of vertices, and

a second set of weighted directional edges extending between elements of the second set of vertices and containing a fifth directional edge extending from the first vertex to the fifth vertex having a weight of zero, a sixth directional edge extending from the second vertex to the fifth vertex having a weight (x2-p1), a seventh directional edge extending from the fifth vertex to the third vertex having a weight p1, and an eighth directional edge extending from the fifth vertex to the fourth vertex having a weight x1.

22. 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.

23. 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.

24. 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.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.

30. 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.

31. 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.

32. 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.

33. 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.

34. 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.

35. 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.

37. 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.

38. 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.

39. 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.

40. 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.

41. 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.

42. 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.

36. 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.