Browse Prior Art Database

Cluster-Based Stack Optimization Algorithm for Very Large-Scale Integration

IP.com Disclosure Number: IPCOM000039969D
Original Publication Date: 1987-Sep-01
Included in the Prior Art Database: 2005-Feb-01
Document File: 3 page(s) / 30K

Publishing Venue

IBM

Related People

Cagle, JW: AUTHOR [+3]

Abstract

A stack optimization algorithm for very large-scale integration (VLSI) is disclosed which depends on hierarchical cluster information and a recursive search routine to reduce the number of possible placements to test from n! to 2D (log2n

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

Page 1 of 3

Cluster-Based Stack Optimization Algorithm for Very Large-Scale Integration

A stack optimization algorithm for very large-scale integration (VLSI) is disclosed which depends on hierarchical cluster information and a recursive search routine to reduce the number of possible placements to test from n! to 2D (log2n<D<n-1) or roughly n2 . It provides CPU time improvement over current methods that search through possibilities selected semi-randomly from among n!. VLSI design frequently requires solving the stack placement problem, i.e., placing n macros in a stack in the best order according to some criteria. The problem requires an algorithmic solution because for n objects there are n! (n factorial: n(n-1)...(2)(1) ) possible solutions and in VLSI n is often 50 or more. Current approaches to the problem begin with an arbitrary order and choose partial reorderings at random. If the new order is better per the chosen criteria, then it is preserved; otherwise, it is rejected and another selected. Refinements to this incremental improvement approach involve better initial orders based on I/O's, finding `coalitions' (macro groups) to move, and occasionally permitting bad moves in the hope of escaping local minima in the criteria score (thermal annealing). The algorithm disclosed here solves the stack placement problem by joining the n macros into a hierarchy of clusters and then rearranging the macros only into placements that preserve the clusters. Clustering requires computer processing time proportional to n2 . 2(n-1) cluster preserving arrangements exist so placement can certainly be solved in 2(n-1) time. Further simplifications allow solution in roughly n2 time. The clustering step hierarchically groups n objects into (n-1) nested clusters. The entire cluster hierarchy can be viewed as a binary tree, as illustrated in Fig. 1 for n=5. The clustering begins by searching through all pairs of A, B, C, D, and E for the pair that has the greatest C2C value. In this case it is A and B, so these two are clustered. Next, on searching through A-B, C, D, and E, A-B and C are found to have the greatest C2C and are clustered. All (5-1) clusters can be formed in n2 processing time. The sequencing step regards the order of the leaves of the tree as the placement order of the macros in the stack. Any starting order is acceptable for which the clustering hierarchy can be drawn without crossing lines, as illustrated in Fig. 1. Sequencing capitalizes on the independence of adjacent nodes in the stack to reduce computation. In Fig. 1, for example, the internal arrangement of the node at 3 has little effect on the internal arrangement of node 2. In fact, evaluation methods can be chosen for which the effect is zero. One such criterion is the cutting line score counted over each macro. Nets that connect nodes 2 and 3 apply to 2's score the same way when they pass out of 2 no matter how deeply they penetrate 3. This independence implies that the score ove...