Browse Prior Art Database

Hierarchical Path Analysis for Macro Design

IP.com Disclosure Number: IPCOM000045637D
Original Publication Date: 1983-Apr-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 2 page(s) / 38K

Publishing Venue

IBM

Related People

Ditlow, GS: AUTHOR

Abstract

In the design of VLSI systems, it is useful to know how sensitive an output is to an input. One measure of this sensitivity is a count of the number of paths from each input to an output. The algorithm presented here does not enumerate all paths, since it is well known that such a procedure is exponential in the worst case. Instead, we count paths by a procedure which closely resembles polynomial addition. The complexity of the algorithm is linear in the number of gates of a levelized combinational network, since only one pass is required from inputs to outputs.

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 69% of the total text.

Page 1 of 2

Hierarchical Path Analysis for Macro Design

In the design of VLSI systems, it is useful to know how sensitive an output is to an input. One measure of this sensitivity is a count of the number of paths from each input to an output. The algorithm presented here does not enumerate all paths, since it is well known that such a procedure is exponential in the worst case. Instead, we count paths by a procedure which closely resembles polynomial addition. The complexity of the algorithm is linear in the number of gates of a levelized combinational network, since only one pass is required from inputs to outputs.

Macros improve the performance for large problems. Each macro is analyzed separately, and a characteristic equation is generated. Each coefficient ofthe equation represents the number of paths from an input to an output. Each subsequent instance of the macro uses the information stored in the characteristic equation. The macros then hierarchically combine to form a new macro with a new characteristic equation at the next level.

The figures illustrate the concept of path addition by the use of polynomials. Cases 2 and 3 show how macros combine to form new macros at the next level. Case 0: An expanded exclusive OR is shown with inputs x, y and output z. By adding the inputs of each block and propagating forward, the value of z finally assumes the relationship 2(x+y). This vector (2,2) = (x,y) indicates that there are 2 paths from x to z and 2 paths from y to z. Th...