Dynamic propagation delay calculation using an array of storage cells

• US 5,764,526 A
• Filed: 04/08/1996
• Issued: 06/09/1998
• Est. Priority Date: 04/08/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Douceur, John R.
• Primary Examiner(s): Voeltz, Emanuel Todd
• Assistant Examiner(s): Siek, Vuthe
• Application Number:
  US08/629,274
• Time in Patent Office: 792 Days
• Field of Search: 364/488-491, 364/578, 395/555, 395/200.17, 395/500
• US Class Current: 716/108
• CPC Class Codes: G06F 30/33 Design verification, e.g. functional simulation or model checking

Abstract

Described herein is a computer-implemented method of dynamically determining propagation delays through a system of directedly interconnected components. An array of storage cells is maintained in a computer. The storage cells are logically referenced by row and column numbers. As components are added to the system, they are assigned enumerated component numbers. A particular storage cell corresponds to a potential network of directed paths between upstream and downstream components having component numbers equal to the row and column numbers of the particular storage cell, respectively. When the array is maintained in accordance with the invention, a cell contains the propagation delay from the corresponding upstream component to the corresponding downstream component if there is a path from the upstream component to the downstream component. Upon specifying a new component in the system, the array is increased in size by one row and one column. The invention includes writing the individual propagation delay of the new component to the storage cell having row and column numbers equal to the component number of the new component. Upon specifying a new connection from a component q to a component p, all storage cells are identified that correspond to a directed path network including a non-looping directed path completed by the new connection. The cells so identified are those that are both (a) in a column having a propagation delay entry in row p, and (b) in a row having a propagation delay entry in column q. Identified storage cells are updated with the propagation delay of the newly completed path, but only if the new value is greater than the prior entry and the path does not contain a loop.

Claims

1. A computer-implemented method of dynamically maintaining propagation delays in an array of computer storage cells, wherein each storage cell corresponds to a potential directed path network from an upstream component to a downstream component in a system containing a plurality of directedly interconnected components with associated individual propagation delays;

the method comprising the following steps;

initializing the storage cells to values indicating an absence of the corresponding directed path networks;

upon specifying a new component in the system, writing the individual propagation delay of the new component to a storage cell corresponding to a directed path network from the new component to itself;

upon specifying a new connection from a first component to a second component, identifying any storage cell corresponding to a directed path network that includes a non-looping directed path completed by the new connection;

for each identified storage cell, calculating the propagation delay from the upstream component to the downstream component of the corresponding directed path network;

writing the calculated propagation delays to the storage cells corresponding to the directed path networks.

2. A method as recited in claim 1, wherein the identifying step comprises identifying any particular storage cell corresponding to a directed path network from an upstream component to a downstream component, wherein said particular storage cell satisfies both of the following two conditions:

a first storage cell corresponding to the directed path network from said upstream component to the first component contains a value indicating the presence of a directed path network; and

a second storage cell corresponding to the directed path network from the second component to said downstream component contains a value indicating the presence of a directed path network.

3. A method as recited in claim 1, wherein the calculating step comprises:

calculating the propagation delay between the upstream component and the downstream component through the non-looping directed path completed by the new connection;

taking the maximum of (a) the calculated propagation delay between the upstream component and the downstream component through the non-looping directed path completed by the new connection and (b) any previous calculated propagation delay written to the storage cell corresponding to the directed path network between the upstream component and the downstream component.

4. A method as recited in claim 3, wherein the step of calculating the propagation delay between the upstream component and the downstream component through the non-looping directed path completed by the new connection comprises:

summing (a) the propagation delay from the upstream component to the first component and (b) the propagation delay from the second component to the downstream component.

5. A method as recited in claim 3, wherein the step of calculating the propagation delay between the upstream component and the downstream component through the non-looping directed path completed by the new connection comprises:

reading a first propagation delay from the storage cell corresponding to the potential directed path network from the upstream component to the first component;

reading a second propagation delay from the storage cell corresponding to the potential directed path network from the second component to the downstream component;

summing the first and second propagation delays.

6. A method as recited in claim 1, further comprising a step of detecting a loop in the directed path completed by the new connection, said detecting step comprising determining whether the storage cell corresponding to the directed path network from the second component to the first component contains a value indicating the presence of a directed path network.

7. A method as recited in claim 1, further comprising a step of detecting a loop in the directed path completed by the new connection, said detecting step comprising:

reading the storage cell corresponding to the directed path network from the second component to the first component;

concluding that the directed path completed by the new connection is a loop if the storage cell corresponding to the potential directed path network from the second component to the first component contains a value indicating the presence of a directed path network.

8. A method as recited in claim 1 and further comprising a step of finding the maximum propagation delay contained in the array of storage cells.

9. A method as recited in claim 8, wherein the step of finding the maximum propagation delay comprises a step of taking the maximum of (a) a previous value of the maximum propagation delay and (b) the calculated propagation delay from the upstream component to the downstream component.

10. A computer-implemented method of dynamically maintaining propagation delays through a system of directedly interconnected components, each such component having a respective individual propagation delay, the method comprising the following steps:

enumerating a component number for each component added to the system;

maintaining an array of storage cells in computer memory for containing propagation delay entries, the storage cells being logically referenced by row and column numbers;

upon specifying a new component in the system, writing the individual propagation delay of the new component to the storage cell having row and column numbers equal to the component number of the new component;

upon specifying a new connection from a component q to a component p, identifying any storage cell with row number x and column number y such that both (a) the storage cell having row number x and column number q contains a propagation delay entry, and (b) the storage cell having row number p and column number y contains a propagation delay entry;

for each identified storage cell having row number x and column number y, calculating the propagation delay from component x to component y and writing the calculated propagation delay to the identified storage cell.

11. A method as recited in claim 10, wherein the calculating step comprises:

calculating the propagation delay between component x and component y through a non-looping directed path completed by the new connection;

taking the maximum of (a) the calculated propagation between component x and component y through the non-looping directed path completed by the new connection and (b) any previous propagation delay entry in the storage cell having row number x and column numbers.

12. A method as recited in claim 11, the step of calculating the propagation delay between component x and component y through the non-looping directed path completed by the new connection comprising:

summing the propagation delay entries of (a) the storage cell having row number x and column number q, and (b) the storage cell having row number p and column number y.

13. A method as recited in claim 11, further comprising:

for each identified storage cell with row number x and column number y, reading a first value from the storage cell with row number x and column number q, and reading a second value from the storage cell with row number p and column number y;

the step of calculating the propagation delay between component x and component y through the non-looping directed path completed by the new connection comprising a step of summing the first and second values.

14. A method as recited in claim 11, further comprising a step of detecting a looping directed path completed by the new connection, said detecting step comprising determining whether the storage cell having row number p and column number q contains a propagation delay entry.

15. A method as recited in claim 10 and further comprising a step of finding the maximum propagation delay entry contained in the array of storage cells.

16. A method as recited in claim 15, wherein the step of finding the maximum propagation delay entry comprises taking the maximum of (a) any previous propagation delay entry and (b) the propagation delay contained in the storage cell having row number x and column numbers.

17. A system for maintaining propagation delays through directedly interconnected components, each such component having a respective individual propagation delay, comprising:

a data processor;

read/write memory associated with the data processor;

an array of storage cells in computer memory for containing propagation delay entries, the storage cells being logically referenced by row and column numbers;

the data processor being programmed to perform the following steps;

enumerating a component number for each component specified in the system;

when a new component is specified in the system, writing the individual propagation delay of the new component to the storage cell having row and column numbers equal to the component number of the new component;

when a direct connection is specified from a component q to a component p, identifying any storage cell with row number x and column number y such that both (a) the storage cell having row number x and column number q contains a propagation delay entry, and (b) the storage cell having row number p and column number y contains a propagation delay entry;

for each identified storage cell having row number x and column number y, calculating the propagation delay from component x to component y and writing the calculated propagation delay to the identified storage cell.

18. A system as recited in claim 17, the programmed calculating step comprising further steps as follows:

calculating the propagation delay between component x and component y through a non-looping directed path completed by the new connection;

taking the maximum of (a) the calculated propagation between component x and component y through the non-looping directed path completed by the new connection and (b) any previous propagation delay entry in the storage cell having row number x and column number y.

19. A system as recited in claim 18, the step of calculating the propagation delay between component x and component y through the non-looping directed path completed by the new connection comprising:

summing the propagation delay entries of (a) the storage cell having row number x and column number q, and (b) the storage cell having row number p and column number y.

20. A system as recited in claim 18, the data processor being further programmed to perform the following step:

for each identified storage cell with row number x and column number y, reading a first value from the storage cell with row number x and column number q, and reading a second value from the storage cell with row number p and column number y;

the step of calculating the propagation delay between component x and component y through the non-looping directed path completed by the new connection comprising a step of summing the first and second values.

21. A system as recited in claim 18, the data processor being further programmed to perform a step of detecting a looping directed path completed by the new connection, said detecting step comprising determining whether the storage cell having row number p and column number q contains a propagation delay entry.

22. A system as recited in claim 17, the data processor being further programmed to perform a step of finding the maximum propagation delay entry contained in the array of storage cells.

23. A system as recited in claim 22, wherein the programmed step of finding the maximum propagation delay entry comprises taking the maximum of (a) any previous propagation delay entry and (b) the propagation delay contained in the storage cell having row number x and column number y.

24. A system as recited in claim 17, the data processor being further programmed to perform the following step:

for each identified storage cell with row number x and column number y, reading a first value from the storage cell with row number x and column number q, and reading a second value from the storage cell with row number p and column is number y;

the step of calculating the propagation delay between component x and component y through the non-looping directed path completed by the new connection comprising;

summing the first and second values;

taking the maximum of (a) the summed first and second values and (b) any previous propagation delay entry in the storage cell having row number x and column number y.

25. A system as recited in claim 24, the data processor being further programmed to perform a step of detecting a looping directed path completed by the new connection, said detecting step comprising determining whether the storage cell having row number p and column number q contains a propagation delay entry.