Browse Prior Art Database

Algorithm for High Speed Topological Sorting of a Large Network

IP.com Disclosure Number: IPCOM000045241D
Original Publication Date: 1983-Feb-01
Included in the Prior Art Database: 2005-Feb-06
Document File: 4 page(s) / 41K

Publishing Venue

IBM

Related People

Koo, CC: AUTHOR

Abstract

An algorithm for high speed topological sorting of large networks is designed to produce a forward chain and a backward chain through the outputs of the logic blocks so that each block in the chain is arranged in topological order. This topologically ordered chain guarantees that the timing analysis program will find all critical paths in a network by processing each block in the chain exactly once.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 73% of the total text.

Page 1 of 4

Algorithm for High Speed Topological Sorting of a Large Network

An algorithm for high speed topological sorting of large networks is designed to produce a forward chain and a backward chain through the outputs of the logic blocks so that each block in the chain is arranged in topological order. This topologically ordered chain guarantees that the timing analysis program will find all critical paths in a network by processing each block in the chain exactly once.

The algorithm may be described by the following steps. In step 1, the algorithm locates the backward trace starting point which may be either a primary output or a shift register latch. As shown in Fig. 1, the primary output (PO) may be either PO shown at 1 or 3.

Step 2 involves searching backward towards the input using a "pushdown/pop-up the stack" either have been leveled or are primary inputs, then (a) the block is added to the forward chain (the block then designated as "leveled") and (b) the block is removed from the stack (pop-up). In the second situation (b), if at least one input to the block comes from an unleveled block, then (a) the first unleveled input is chosen to continue the backward tracing, and (b) the "come from block" (predecessor block) of this unleveled input is located and added to the stack along with its input count (pushdown).

In the third step of the process, steps 1 and 2 are repeated until all primary outputs and shift register latches have been processed.

An example of the manner in which the algorithm operates may be had by reference to Fig. 1. In this example, we assume that the internal model is built as follows: FLAGS COME FROM COME FROM

BLOCK BLOCK IN POINTER LIST

INDEX NAME PI PO USE (CFP) (CPL)

1 PI1 1 1 1

2 P12 1 2 2

3 PI3 1 3 3

4 PI4 1 4 4

5 PI5 1 5 5

6 PI6 1 6 6

7 BLK1 0 7 1

8 BLK2 0 9 2

9 BLK3 0 11 7

10 BLK4 0 12 5

11 BLK5 0 14 8

12 BLK6 0 15 7

13 BLK7 0 17 14

14 BLK8 0 19 10

15 BLK9 0 20 3

16 BLK10 0 22 4

17 P01 0 1 23 12

18 P02 0 1 24 6

19 13

20 12

1

Page 2 of 4

21 9

22 15

23 11

24 16.

In the process to formulate the forward chain, the backward starting point (P0), shown as 1, is first located. The backward trace proceeds from BLK5 to BLK4 and then to BLK 1, with these blocks being placed "on stack". The inputs to BLK1 are primary inputs (PI1 and PI2), hence BLK1 is "leveled". BLK1 is placed on the forward chain and then removed from the stack. The first input to BLK4 is now leveled. The next unleveled pin to BLK4 comes from BLK8. Hence BLK8, BLK7 and BLK6 are placed on the stack (pushdown). Since the inputs to BLK6 are primary inputs, BLK6 is leveled. BLK6 is placed on the forward chain. BLK6 is then removed from the stack (pop-up).

The process is continued until BLK5 is leveled. At this time, the forward chain appears as follows:
FORWARD
BLK1
BLK6
BLK7
BLK5
BLK4
BLK5 0.

In the next step, the next backward trace starting point, shown at 3 in Fig. 1, is located. This backward trace proceeds through BLK10 and BLK9, which are place...