Kristofer Vorwerk
email: kpvorwer@cheetah.vlsi.uwaterloo.ca

Andrew Kennings
email: akenning@cheetah.vlsi.uwaterloo.ca

An Improved Multi-Level Framework for Force-Directed Placement *

One of the greatest impediments to achieving high quality placements using force-directed methods lies in the large amount of overlap initially present in these techniques. This overlap makes the determination of cell ordering difficult and can lead to the inadvertent separation of highlyconnected cells by the spreading forces. We show that a multi-level clustering strategy can minimize the ill effects of overlap and improve the quality of placements generated by the force-directed tool FDP. Moreover, we present a means of improving initial cell ordering through the unification of min-cut partitioning and force-based placement, and describe an enhanced median improvement heuristic which further aids in minimizing HPWL. Numerical results are presented showing that our flow generates placements which are, on average, 15% better than mPG and 4% better than Capo 9.0 on mixed-size designs.

Introduction

As problem instances have increased in size and complexity, placement has become the bottleneck in deep sub-micron design. Typically, placement seeks to minimize wire length subject to the constraint that cells be placed into prescribed locations without overlap. Several different approaches to this problem are possible, including simulated annealing [START_REF] Swartz | Timing driven placement for large standard cell circuits[END_REF], top-down partitioning [START_REF] Caldwell | Can recursive bisection alone produce routable placements?[END_REF][START_REF] Khatkhate | Recursive bisection based mixed block placement[END_REF], and analytic techniques [START_REF] Eisenmann | Generic global placement and floorplanning[END_REF][START_REF] Kahng | Implementation and extensibility of an analytic placer[END_REF][START_REF] Viswanathan | Fastplace: Efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model[END_REF][START_REF] Vorwerk | Engineering details of a stable analytic placer[END_REF]. Combinations of these techniques are often employed; for example, GORDIAN [START_REF] Kleinhans | GOR-DIAN: VLSI placement by quadratic programming and slicing optimization[END_REF], GORDIAN-L [START_REF] Sigl | Analytical placement: A linear or a quadratic objective function?[END_REF], and BonnPlace [START_REF] Vygen | Algorithms for large-scale flat placement[END_REF] combine partitioning and analytic placement. Likewise, Dragon [START_REF] Wang | Dragon2000: Standardcell placement tool for large industry circuits[END_REF] combines partitioning and simulated annealing. These methods, however, have largely been employed for standard cell placement.

Several approaches have been proposed to address mixed-size placement. Very good results using a chiefly partitioning-based flow are reported in [START_REF] Adya | Unification of partitioning, placement and floorplanning[END_REF][START_REF] Khatkhate | Recursive bisection based mixed block placement[END_REF], while [START_REF] Kahng | Implementation and extensibility of an analytic placer[END_REF] reports good results using analytic methods. Force-directed techniques [START_REF] Eisenmann | Generic global placement and floorplanning[END_REF][START_REF] Vorwerk | Engineering details of a stable analytic placer[END_REF] are also of interest due to their seamless handling of macro cells, though run-times can be larger than partitioning-based strategies. Furthermore, the quality of placements obtained by force-directed methods falls short of recent work [START_REF] Adya | Unification of partitioning, placement and floorplanning[END_REF][START_REF] Khatkhate | Recursive bisection based mixed block placement[END_REF].

This paper addresses the issue of quality in forcedirected placement by describing three techniques to augment the open-source tool FDP [START_REF] Vorwerk | Engineering details of a stable analytic placer[END_REF]. Section 2 presents a brief overview of force-directed placement. In Section 3, we describe the implementation of a multi-level physical clustering strategy. Section 4 presents a novel unification of partitioning and force-directed methodologies which further improves quality. In Section 5, we discuss a ripple-move enhancement to the median improvement heuristic BoxPlace [START_REF] Vorwerk | Engineering details of a stable analytic placer[END_REF]. Finally, Section 6 presents numerical results and Section 7 concludes the work. 1

Background

x = (x 1 , x 2 , ••• , x n ) and y = (y 1 , y 2 , ••• , y n ).
Wire length minimization is accomplished by solving the quadratic optimization problem (x-direction only) given by min

x 1 2 x T Q x x + c T x x + f T x x + d x . (1)
The matrix Q x is the Hessian which encapsulates the hyperedge connectivities. The vector c x is a result of fixed cell-to-free cell connections, and the vector d x is a result of fixed cell-to-fixed cell connections. The vector f x represents the vector of spreading forces which is used to perturb the placement to remove overlap. This optimization problem is strictly convex and has a unique minimizer given by the solution of a single, positive-definite system of linear equations,

Q x x + c x + f x = 0.
In FDP, the BoxPlace heuristic is employed to (occasionally) move each cell to the median position of its connected nets, reducing wire length directly [START_REF] Vorwerk | Engineering details of a stable analytic placer[END_REF]. For each cell in the netlist, BoxPlace determines a range (or "box") into which a cell should be moved to minimize wire length. In FDP, only six passes of the netlist are made in any call to BoxPlace; consequently, the amount of overlap that is reintroduced is kept within reasonable bounds. Moreover, cell spreading is re-evaluated after each pass-if more than 2% overlap is reintroduced, the previous cell positions are restored, and the algorithm stops. 2 BoxPlace is also used to compute "wire length minimizing" forces which are combined (vectorally) with spreading forces to achieve a mix between cell spreading and wire length minimization.

Clustering and the Multi-Level Paradigm

Empirical evidence suggests that the quality of placements obtained by FDP relies heavily on cells' initial "left/right" (and "up/down") ordering, which is determined chiefly by the solution to the first (unperturbed) quadratic problem (QP). We have observed that most circuits begin with significant cell overlap-between 85% and 98%-after solving the first QP, with many thousands of cells being placed on top of each other. While advocates of QP-based placement contend that these methods benefit from more detailed cell positions (versus their partitioning-based counterparts), it is arguable whether or not a placement with 85%-98% overlap offers much reliability in terms of cell positions. With so many overlapping cells, the determination of which cell should be placed to the left or right of another is governed primarily by the spreading forces. Furthermore, when a cell is placed in-between two highly-connected cells, a "barrier" is created which generates spreading forces that push the connected cells apart, despite their connectivity. While Box-Place has been noted to improve this "left/right" ordering and to reduce the "damage" to wire length due to spreading forces [START_REF] Vorwerk | Engineering details of a stable analytic placer[END_REF], the ordering problem persists due to the extremely large number of initially-overlapping cells.

We have found that a multi-level clustering approach can significantly improve FDP's placement quality. Historically, multi-level clustering has been used with partitioning-and annealing-based methods [START_REF] Chang | Multi-level placement for large-scale IC designs[END_REF]. Force-directed techniques, on the other hand, are usually seen as working best on flat netlists [START_REF] Eisenmann | Generic global placement and floorplanning[END_REF] or when used to seed a top-down placement strategy [START_REF] Kleinhans | GOR-DIAN: VLSI placement by quadratic programming and slicing optimization[END_REF][START_REF] Sigl | Analytical placement: A linear or a quadratic objective function?[END_REF][START_REF] Vygen | Four-way partitioning of two-dimensional sets[END_REF]. However, we have found that multilevel clustering minimizes the negative impact of spreading forces by helping to keep together highly-connected cells.

Hybrid First Choice Clustering

We use the Hybrid First Choice [START_REF] Karypis | Multilevel Optimization and VLSICAD, chapter 3[END_REF] clustering method. In this approach, cells are initially placed onto a "free list" containing the set of cells which have not been clustered. The affinity for pairing a node i with a node j is calculated for all shared edges using

r i j = ∑ e∈E h | i, j∈e 1 |e| -1 . ( 2
)
The algorithm repeatedly removes the node with the highest affinity from the free list and pairs it with the node that (originally) yielded this high affinity, even if that node has already been paired. Once a node has been paired, it is said to form a "cluster". In First Choice Clustering, an unpaired node is always paired with either another unpaired node or a cluster. The term "hybrid" refers to the fact that this aggregation heuristic reorders cells in the free list to improve the likelihood of greedily forming the best-possible pairings as early as possible.

Limits are placed on both the number and area of clusters to ensure that netlists are not reduced in size too quickly. We have found that it suffices to not match a node i with a cluster j if the aggregate area of the pairing (the sum of the area of node i and all of the paired nodes contained within the cluster) would exceed a multiple of the average cell area of the netlist. In such a circumstance, i and j would not be matched, and node i would simply be paired with its next best affinity match which satisfies this area constraint. (We note that the affinity equation could alternatively be modified along the lines of [START_REF] Chan | An enhanced multilevel algorithm for circuit placement[END_REF] to encourage matchings between smaller cells.)

We augmented (2) to account for physical cell locations in the hopes of encouraging the formation of better clusters. That is, we use

r i j = λ × ∑ e∈E h | i, j∈e 1 1 + |x i -x j | + |y i -y j | -ζ + (1 -λ) × ∑ e∈E h | i, j∈e 1 |e| -1 (3)
to compute the affinity r between two connected cells i and j located at (x i , y i ) and (x j , y j ), respectively. The equation consists of two parts: the first assigns an affinity based on the distance between cells, and the second implements the edge-coarsening affinity of (2). In the physical clustering term of (3), the variable ζ represents the minimum Manhattan distance between any two cells on a shared net. This ensures that the best possible physical pairings (i.e., those which are formed between the closest cells) receive an affinity of 1, as would a 2-pin net in the edge-coarsening term. The parameter λ is used to control the preference between physical and edge-based clustering. We have found that physical clustering works best as a means of "breaking ties" between nets which share the same edge-coarsening affinity. In practice, λ ≈ 0.25 does a good job of implementing this "tie-breaking" mechanism.

Multi-Level Placement

Based on the aforementioned clustering strategy, we developed the multi-level flow presented in Figure 1. To our knowledge, this is the first paper to discuss the use of a multi-level scheme within the context of force-directed placement. (Only a small amount of non-multi-level clustering was previously employed in FDP.)

In our approach, a QP is solved to determine initial cell positions and the netlist is clustered to 5000 cells using the physical clustering technique. (In Section 4, we discuss how a QP augmented with cutlines derived from min-cut partitioning can further reduce the ambiguity in the initial cell positions.) At most 35% of cells are aggregated in one pass, so several "levels" of clustered netlists are created (forming a clustering "tree"), with the bottom-most netlist containing approximately 5000 cells. At each level, clusters are positioned at the average location of their contained cells. The most-clustered netlist is then placed to a stopping value of approximately 30% overlap, after which a small amount of greedy swapping is performed between clusters.

The netlist is subsequently declustered, with cells in the flat netlist placed at the centers of their former clusters. BoxPlace is called to move cells in the flat netlist to improve wire length. Subsequently, the entire circuit is reclustered up to a maximum of one less level than the number of levels required for the previous clustering tree. As before, force-directed placement is used to reduce overlap between the clusters to approximately 30% and the process repeats. The placer proceeds to legalization when there are no longer any clustered netlists remaining and overlap in the flat netlist has been reduced to approximately 30%.

Two points are worth noting about this approach. First, by repeatedly decrementing the maximum number of levels of clustering, FDP places increasingly larger netlists until it ultimately places the original (flat) netlist. Second, the use of BoxPlace and reclustering allow the physical affinity term in (3) to more accurately decide which cells should be paired in subsequent clusters, which, in turn, improves the quality of the clustering.

Commentary

Figure 2 illustrates the reduction in overlap versus iteration count in FDP for a subset of the circuits in the ISPD02 IBM-MS benchmark [START_REF] Adya | Combinatorial techniques for mixedsize placement[END_REF]. (Other designs are omitted for clarity, but exhibit similar characteristics.) Three distinct phases are apparent in FDP's multi-level flow. Placements begin with significant overlap and many iterations are required prior to any measurable cell spreading. As designs spread, a small amount of overlap is occasionally reintroduced due to the median improvement. Finally, overlap is re-introduced and removed as declustering and placement refinement on the declustered netlists are performed.

As mentioned in [START_REF] Hur | Force directed Mongrel with physical net constraints[END_REF][START_REF] Viswanathan | Fastplace: Efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model[END_REF], the run-time in force-directed techniques can be attributed, in part, to numerous iterations and the potentially large computational effort required per iteration. As suggested by Figure 2, there are a number of seemingly wasted iterations (during the first phase) prior to any significant overlap removal. This occurs because force weights are initially kept small and increased slowly to ensure that proper "left/right" ordering between cells is maintained [START_REF] Vorwerk | Engineering details of a stable analytic placer[END_REF]. With multi-level clustering, more iterations are typically required to purge overlap among the numerous clustered levels; however, the effort per iteration is reduced because of the smaller size of the clustered netlists.

Unified Partitioning and Force-Directed Placement

We have found that a small amount of min-cut partitioning-based placement can improve circuits' initial cell ordering, thereby leading to better results within FDP's primarily force-directed design flow. In our implementation, the netlist is bi-partitioned prior to force-directed placement, as shown in Figure 3.

At each min-cut layer, we solve a QP augmented with cutlines from the partitioned regions. Then, we use the Klee's measure technique [START_REF] Vorwerk | Engineering details of a stable analytic placer[END_REF] to assess the resultant amount of cell spreading in each partitioned region. We continue to recursively bi-partition the netlist to minimize cell overlap-based on empirical evidence, regions with macro cells are partitioned until they possess less than 20% overlap, while regions containing standard cells are partitioned to less than 90% overlap. These rules ensure that the largest macro cells are separated (allotted to different partition regions) prior to force-directed placement; in so doing, overlap is improved since macros are less likely to collapse on top of each other during the solution of the QP. After min-cut placement, FDP's multi-level force-directed placement is employed to reduce the remaining overlap to approximately 30%. Thus, the partitioning problem merely serves to enhance initial cell positions. We note that our criteria for handing off a partially generated min-cut placement to FDP are quite different-but complementary-to those criteria where a min-cut placer should hand off to a floorplanner [START_REF] Adya | Unification of partitioning, placement and floorplanning[END_REF].

In this approach, quadratic placement and Klee's measure technique are used in conjunction to assess overlap and identify potential candidate regions for partitioning. Likewise, min-cut partitioning helps the force-directed placer by providing better starting locations for cells. While this flow may seem similar to Capo Flow 2-A in [START_REF] Adya | Combinatorial techniques for mixedsize placement[END_REF] (which used Capo 8.8 and Kraftwerk-ECO), our approach applies partitioning to selective regions which are identified as highoverlap "problem zones". (We also note that FDP appears to offer superior results compared to Kraftwerk.) We have observed that partitioning deeply (i.e., doing a primarily min-cut placement) followed by FDP achieves worse results than selectively partitioning those regions with high overlap and handing off to FDP once the problem areas have been adequately spread. This is similar, conceptually, to Capo 9.0 [START_REF] Adya | Unification of partitioning, placement and floorplanning[END_REF] in which a min-cut partitioner situates cells globally and a floorplanner refines their positions.

Using a partitioner to seed the force-directed placer explicitly helps with the cell ordering problem and improves the accuracy of FDP's physical reclustering. Moreover, since cells are not constrained to partitioned regions during forcedirected placement, it is felt that FDP is better able to replace cells previously assigned to sub-optimal regions during min-cut placement. Furthermore, placements exhibit less initial overlap and therefore converge to a fairly nonoverlapping placement more quickly, effectively bypassing the first phase of placement illustrated in Figure 2.

Better Median Improvement

We have observed that BoxPlace works well early in placement, when there exists between 70% and 100% overlap. However, once a circuit possesses less than ≈ 70%, BoxPlace tends to reintroduce too much overlap, and cell positions are generally restored. Thus, BoxPlace is not as effective in mid-to-late placement.

We enhanced BoxPlace so that it does not reintroduce as much overlap into the placement. Our method consists, in part, of overlaying a fine grid (which tracks cell positions) to ensure that cells are placed into relatively under-occupied spots within their target ranges. However, this "occupancy grid" does not completely alleviate the reintroduction of overlap, as the ranges determined by BoxPlace for each cell may themselves be highly overlapping. So, in addition to the grid, we extend the range over which cells can move-that is, we extend the boxes such that any position between a cell's current location and its range's outer extremities are also included. This concept is illustrated in Figure 4 (a). Any movement of a cell in the x-or y-direction toward its minimizing "box" results in at least the same or better half-perimeter wire length (HPWL).

Using BoxPlace and the occupancy grid proposed here, we have developed a cell rippling strategy that can be employed in every iteration of force-directed placement. To accomplish this, we iterate through the netlist, using BoxPlace to compute a range for a given cell. However, we modify the range such that it emanates from the center of the cell up to, at most, three times the cell's height or width. This concept is illustrated in Figure 4 (b). The more passes over the netlist that are performed, the more cells are "rippled" in the direction of minimum HPWL-due to the occupancy grid, overlap is not reintroduced, as cells are placed within the least overlapping areas within their range. Often, and especially late in placement, the least overlapping spot within a cell's range is the same position in which the cell is presently located; thus, the algorithm usually does no worse, overlapwise, than the current placement.

Experimental Results

We use a simple strategy to legalize placements produced by FDP [START_REF] Vorwerk | Engineering details of a stable analytic placer[END_REF]. Macro cells are processed using sequence pair analysis along the lines of [START_REF] Adya | Fixed-outline floorplanning: Enabling hierarchical design[END_REF]. Based on the results of the sequence pair analysis, macro cells are shifted to align with rows to remove overlap in the y-direction, and shifted to the left and right to remove overlap in the x-direction. Standard cells are then snapped to their closest rows to minimize total cell movement. Greedy juggling of standard cells is per- formed between rows to meet width restrictions imposed by the fixed die. Finally, we apply greedy (same-size) swapping and single-row branch and bound on groups containing six or fewer standard cells. No attempt is currently made to optimize whitespace in the final placement.

Numerical Results

We compare FDP to mPG [START_REF] Chan | An enhanced multilevel algorithm for circuit placement[END_REF], Capo 9.0 (with feedback) [START_REF] Adya | Unification of partitioning, placement and floorplanning[END_REF] and Feng Shui 2.61-beta2 [START_REF] Khatkhate | Recursive bisection based mixed block placement[END_REF] on the IBM-MS mixed-size benchmark [START_REF] Adya | Combinatorial techniques for mixedsize placement[END_REF]. 3 Results are presented in Table 1. 4 Run-times for Capo, Feng Shui, and FDP are observed on a dual-processor 3.2 GHz Xeon, and are reported in minutes. Run-times for mPG are observed on a 750 MHz Sun Blade 1000. Wire lengths correspond to HPWL divided by 10 6 . The column "FDP C+P" includes all of the multi-level clustering, BoxPlace, and partitioning enhancements discussed in this paper; the configuration for "FDP C" is similar, but partitioning is disabled.

We observe that our placer produces results that are, on average, 15% better than mPG and 4% better than Capo 9.0. The majority of the improvement stems from our multilevel clustering strategy, with our min-cut partitioning enhancements accounting for approximately 3%. We make particular note of our results compared to mPG, as it is also a multi-level placer.

On the other hand, our tool produces results that are 5% worse than Feng Shui. While the wire lengths of Feng Shui are excellent, differences in whitespace allocation may account for some of the discrepancies in quality. In addition, Feng Shui excels on ibm14, ibm17, and ibm18these circuits possess the lowest ratios of macro cell-tostandard cell area in the benchmark suite (26.72%, 23.78%, and 11.97%, respectively). As a result, it is possible that Feng Shui's tighter packing and better detailed improvement contribute to some of the differences in these cases.

The average run-time for "FDP C+P" versus Capo and Feng Shui is 1.58 and 2.61, respectively. The average runtime ratio of "FDP C+P" versus "FDP C" is 0.94. While the min-cut partitioning decreases FDP's iteration count, its runtime advantage is mostly offset by the effort required to do the partitioning.

Although we present only mixed-size results in this paper, our modifications are by no means limited to such designs-they are equally admissible for standard cell circuits. Using the same standard cell benchmark as in [START_REF] Vorwerk | Engineering details of a stable analytic placer[END_REF], our average quality versus Capo for "FDP C+P" is 0.98,

Conclusions

This paper described a multi-level clustering strategy, a means of unifying partitioning and force-directed placement, and a rippling technique to further improve wire length. With all features combined, we produced results that were 4% better, on average, than Capo 9.0 (with feedback) and 15% better than mPG. We feel that there are still opportunities to improve the quality and performance of our flow, as well as to incorporate congestion minimization and timing within the infrastructure.

A

  circuit is modeled as a hypergraph G h (V h , E h ) with vertices V h = {v 1 , v 2 , ••• , v n }representing cells and hyperedges E h = {e 1 , e 2 , ••• , e m } corresponding to signal nets. Vertices are weighted by cell area while hyperedges are weighted according to criticalities or multiplicities. Vertices are either free or fixed. Circuit hypergraphs are typically transformed into graphs in which each hyperedge is represented by a set of equally-weighted edges. Cell placements in the x-and y-directions are captured by placement vectors

Procedure: MULTI-LEVEL PLACEMENT 1 begin 2 3 NumLevels ← ∞; 4 while NumLevels > 0 do 5 6 NumLevels 10 Delete the clustering tree; 11 Call 12 NumLevels ← NumLevels - 1 15 Figure 1 .

 1234561011121151 Figure 1. Pseudocode for our multi-level flow.

Figure 2 .

 2 Figure 2. Overlap versus iteration count in FDP for different mixed-size circuits.

Figure 3 .

 3 Figure 3. A small amount of min-cut partitioning employed prior to force-directed placement helps to improve cell ordering and reduce starting overlap.

Figure 4 .

 4 Figure 4. Illustration of the extended BoxPlace search range used (a) during individual calls to BoxPlace, and (b) when employed to ripple cells.

Table 1 . Mixed-size results comparing mPG, Capo, and Feng Shui to FDP with clustering ("C") and both clus- tering and initial partitioning ("C+P").

 1 with run-times being 2.85 times those of Capo, on average. (We do not compare explicitly to Feng Shui, as it crashed on four of the eighteen circuits.) This represents a ≈ 2% improvement in quality over FDP's previous standard-cell results[START_REF] Vorwerk | Engineering details of a stable analytic placer[END_REF].

	Circuit	mPG	Capo 9.0	FS 2.6 beta2	FDP C	FDP C+P		FDP C+P vs.
		WL	CPU	WL	CPU	WL	CPU	WL	CPU	WL	CPU	mPG	Capo	FS	FDP C
	ibm01	3.01	18	2.65	4	2.52	2	2.50	7	2.45	7	0.81	0.92	0.97	0.98
	ibm02	7.42	32	5.27	4	5.20	4	5.52	12	5.61	13	0.76	1.06	1.08	1.02
	ibm03	11.20	32	10.89	17	7.79	4	8.57	13	7.96	12	0.71	0.73	1.02	0.93
	ibm04	10.50	42	9.46	13	8.64	5	9.13	15	8.63	13	0.82	0.91	1.00	0.94
	ibm06	9.21	45	7.26	10	7.20	7	8.24	19	7.27	15	0.79	1.00	1.01	0.88
	ibm07	13.70	68	11.93	11	11.47	9	12.40	28	12.39	24	0.90	1.04	1.08	1.00
	ibm08	16.40	82	14.74	36	13.50	11	14.81	27	14.38	25	0.88	0.98	1.07	0.97
	ibm09	18.60	84	16.04	19	13.95	10	15.34	26	14.67	24	0.79	0.91	1.05	0.96
	ibm10	43.60	172	35.60	36	39.52	16	35.02	47	34.08	39	0.78	0.96	0.86	0.97
	ibm11	26.50	112	22.22	35	19.58	14	21.72	33	20.55	31	0.78	0.92	1.05	0.95
	ibm12	44.30	153	42.44	32	38.35	16	43.42	57	39.79	61	0.90	0.94	1.04	0.92
	ibm13	37.70	151	29.32	46	24.79	18	26.28	44	26.14	41	0.69	0.89	1.05	0.99
	ibm14	43.50	276	40.78	45	37.92	36	41.96	63	42.53	70	0.98	1.04	1.12	1.01
	ibm15	65.50	285	58.92	76	52.48	45	55.14	107	55.93	93	0.85	0.95	1.07	1.01
	ibm16	72.40	436	66.08	88	60.55	49	66.45	103	65.60	97	0.91	0.99	1.08	0.99
	ibm17	78.50	606	78.97	55	71.56	55	79.64	137	79.85	122	1.02	1.01	1.12	1.00
	ibm18	50.70	437	49.84	48	44.00	60	51.90	169	50.88	174	1.00	1.02	1.16	0.98
											Avg.	0.85	0.96	1.05	0.97

Our source code has been included in FDP, and is available for free download at http://gibbon.uwaterloo.ca. Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

In this paper, we measure cell overlap using Klee's technique[START_REF] Vorwerk | Engineering details of a stable analytic placer[END_REF].

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Currently, FDP does not optimize cell orientations; thus, we use the IBM-MS circuits without pins.

While FastPlace[START_REF] Viswanathan | Fastplace: Efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model[END_REF] purports excellent run times, the tool is not available for download, and is not yet capable of placing mixed-size problems.Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

* This work was supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant #203763-03, a grant from Altera Corporation, and a grant from CITO.


Hua Wang

Miguel Miranda
email: miranda@imec.be

Wim Dehaene
email: wim.dehaene@esat.kuleuven.ac.be

Francky Catthoor
email: catthoor@imec.be

Karen Maex
email: maex@imec.be

Variability is becoming a serious problem in process technology for nanometer technology nodes. The increasing difficulty in controlling the uniformity of critical process parameters (e.g. doping levels) in the smaller devices, makes the electrical properties of such scaled devices much less predictable than in the past. In this paper, we study how these technology effects influence the energy and delay of a SRAM module. Despite the implications in the correct operation of the module, in practically all cases the affected memory implementations become also slower while consuming on average more energy than nominally. This is partly counter-intuitive and no existing literature describes this in a systematic generic way for SRAMs. In this paper, we identify and illustrate the different mechanisms behind this unexpected behavior and quantify the impact of these effects for on-chip SRAMs at the 65nm technology node.

Introduction

Technology process variations introduced during the fabrication of CMOS wafers such as mismatch in doping levels and/or lack of uniformity of the gate oxide cause transistor electrical characteristics to drift from their nominal values. For nanometer technologies (e.g., below 90nm) this is reflected in a stochastic component of variability that becomes much more prominent than any other systematic effects [START_REF] Bastos | Mismatch characterization of submicron MOS transistors Analog Integrated Circuits and Signal Processing[END_REF]. Due to the extremely small dimensions of the transistors in nanometer technologies, the same variation in the number of dopant atoms have a much higher impact in the electrical properties of the device than in earlier technology nodes. This makes digital circuits and systems more difficult to predict and control.

The analysis of the impact that this intra-die stochastic component of variability has on the performance and energy consumption of common IP blocks such as ALUs and other arithmetic components is relatively new [START_REF] Chen | A low cost individual-well adaptive body bias (IWABB) scheme for leakage power reduction and performance enhancement in the presence of intra-die variations Prod[END_REF][START_REF] Visweswariah | First-order Incremental Block-Based Statistical Timing Analysis Prod[END_REF]. For SRAMs the focus has been mostly in functional yield and reliability issues [START_REF] Heald | Managing variability in SRAM designs[END_REF], where the sensitivity of the SRAM circuits, especially the SRAM cell stability (e.g. signal to noise margin) and the design rules to compensate that has gained most attention [START_REF] Burnett | Implications of fundamental threshold voltage variations for high-density SRAM and logic circuits Proc[END_REF][START_REF] Bhavnagarwala | The impact of intrinsic device fluctuations on CMOS SRAM cell stability[END_REF]. However, parametric yield which is related to meeting specific performance constraints for the memory library becomes even more critical than pure functional yield. Indeed embedded SRAMs are performance and energy critical components in modern SoCs, contributing to most of the delay and energy consumption of the system. Thus, understanding the performance and energy behavior of embedded SRAMs under the influence of process variation is key to achieving successful IP block and system design.

This paper investigates how the variability in the electrical properties of the transistors (e.g. Vt and β) makes the actual energy and delay per SRAM (read/write) operation to drift from the expected nominal value. Neighborhood transistors in the same die can make a simple circuit, such as an inverter, to become faster or slower or consume more or less energy hence leading to a "variability cloud" in the Energy/Delay (E/D) space with the nominal point centered in it. However, even when such effects are expected to manifest also in a similar way for more complex modules like SRAMs, this is not the case. As we show in this paper, these effects manifest at the SRAM level even more dramatic than at the inverter level, resulting also in variation clouds. However, in the case of SRAMs (and memories in general) all points become in practice slower and consume more energy in average than the memory not affected by variability (hereafter called the "nominal" memory).

Up to our knowledge, this is the first paper to analyze the different (global) interactions originating from intra-die stochastic variability effects inside and between the different blocks of an SRAM in a systematic way. We also quantify the impact that these effects have on both energy and delay at the 65nm technology node. Experimental results obtained from HSPICE simulations show that already for small size SRAMs, process variability increases the delay and energy consumption up to a 40% above their nominal values. This values are expected to grow both with the memory size and further scaled technology nodes.

Stochastic model for variability

Process variation impacts many technology parameters. In this paper, our focus is on the effects of the front-end devices (e.g., transistors). The effect of variability in the interconnect is neglected here since for SRAMs its impact in the back-end processing is expected to be less dramatic than in the front-end. This is true for the long interconnect lines such as bit-lines, word-lines or decoder busses that are typically long enough so as to average variability effects [START_REF] Pelgrom | Matching properties of MOS transistors[END_REF].

Impact of variability at transistor level can be reflected in a drift in the drain current (I D ) from its nominal value. A first order approximation shows that, variations in the drain current are linearly related to variations in the current factor (β) and the threshold voltage (V t ) [START_REF] Croon | An easy-to-use mismatch model for the MOS transistor[END_REF]. The current factor (β) depends on several physical parameters: β = C ox µW /L. A first order analysis shows that the variabilities of these two electrical parameters for MOSFETs are proportional to the device dimensions [START_REF] Pelgrom | Matching properties of MOS transistors[END_REF]. Furthermore, they both follow a Gaussian distribution with the following standard deviation:

σ V t = ∆ V t / √ W L, σ β = ∆ β / √ W L,
where W, L are the width and length of the MOSFET device.

At the 65 nm, characterizations of that technology node towards (intra-die) variability impact leads to the following estimated values for ∆ V t = 2.5mV µm and ∆ β /β = 0.7% [START_REF] Tavel | Thin oxynitride solution for digital and mixed-signal 65nm CMOS platform[END_REF]. Given these estimates, one-sigma variation for the smallest representative transistors of that technology leads to about 10% drift from their nominal value in both V t or β. These minimum sized transistors are very common in SRAMs in order to achieve maximum density, making these memories very vulnerable to the impact of process variability.

The transistor model used in our analysis is the BSIM4 model of Berkeley Predictive Technology Model [START_REF] Cao | New paradigm of predictive MOSFET and interconnect modeling for early circuit design[END_REF] and the interconnect parameters are taken from the ITRS roadmap [START_REF]International technology roadmap for semiconductors[END_REF]. Both models are intended to reflect technology parameter specifications at the 65nm technology node. As variabilities are uncorrelated between transistors (stochastic effect dominant), every transistor in the netlist is injected with an independent V t and β values generated according to a Gaussian distribution as described above.

In our experiments, we use HSPICE as transistor-level netlist simulation environment. The modeling of variation in V t is straightforward in HSPICE since it is a parameter in the model card and an offset to that value can be explicitly specified at the netlist level. However, β can only be modeled in HSPICE via parameters of the device model. The oxide capacitance (C ox ) and mobility (µ) cannot be modified since they are correlated with other transistor parame-ters like gate capacitance. Therefore we have opted to reflect changes in β by using the ratio of W /L given the proportionality of β to that ratio while keeping the gate area (W × L) constant. This ensures that the first order contribution of the extrinsic load driven by the transistor acting as driver does not become influenced by the variation in β.

SRAM architecture and model

The SRAM architecture we consider for analysis is the partitioned cell-array architecture [START_REF] Prince | Semiconductor Memories: A handbook of design, manufacture, and application[END_REF] typically used in industry with the cell-matrix partitioned into several subarrays. In this architecture, the row decoder is split into twostages, with a predecoder stage shared by all sub-arrays and a post-decoder locally placed in each sub-array. In our SRAM implementation, we use a set of three-input NAND gates for the predecoder and a set of three-input NOR gates for the postdecoder as illustrated in Figure 1.

The cell-array is made out of bitlines and wordlines with the cells implemented using a classical 6T SRAM cell structure. The memory cells and periphery circuits are dimensioned to perform stable operations at the 65 nm technology node, together with several timing interfaces present between the different blocks of the critical path of the SRAM. A very critical interface is the one devoted to activate the wordline once the decoding process is finished. That interfase is critical since the decoder is the first block in the critical path and variability has a large impact in its delay as shown in Section 5. That delay will be then propagated to the rest of the memory. To properly reflect the impact of this delay and specifically to the cell array, a self-timed style [START_REF] Furber | Asynchronous design for tolerance to timing variability[END_REF] is used when building up such interface. Such circuit style also enables memory to be read or written only when all the necessary blocks are ready so that the real variation in memory E/D can be reflected in the memory generated without affecting its functionality.

Clearly, the time consuming HSPICE simulations of the full SRAM are not directly practical for analysis of the process impact as many simulations are required to gather data with reasonable statistical significance. To speed up simulation time without sacrificing much accuracy, a lumped SRAM model is developed for this analysis. This model is composed out of a full row decoder plus a simplified cellarray where the number of wordlines is just a fraction of the ones present in the full memory and they are equally distributed along the height of the cell-array. The details of this model are left out since they are not the focus of this paper. Still, it is worth to mention that the results from HSPICE simulations indicate that this lumped model achieves more than 97% accuracy in average with a factor of 12 reduction in the simulation time compared to the full SRAM simulation.

Methodology for capturing worst-case delay and energy under process variability

This section describes a methodology to define the critical path of the memory and specifically that of the decoder under process variability. The critical path of the SRAM starts from the row decoder and ends at the output buffer in the array. The delay of this path under process variations can be obtained in the netlist by connecting the row decoder critical path with the array and finding the delay of the slowest output out of all parallel outputs of the array.

Row decoder characterization

The task of finding the worst case decoder delay (hence the critical path) under process variability is not trivial as the decoder critical path depends not only on the selected row but also on the transition from the previous address. The reason for this is that the activated transition will change the (dis)charge paths of the parasitic capacitances of the decoder gates [START_REF] Rabaey | Digital Integrated Circuits: a design perspective 2nd Edition Pearson Education international[END_REF]. Hence it will also affect the actual measured delay. In fact, for a nominal decoder, a worst case transition exists but that one will not depend on the activated row. Under variability this is clearly not the case. The reason is that many parallel decoding paths exist in the combinational decoder. Hence, the slowest decoding path that determines the decoded row will have a different delay depending on the variability. Finding this critical path for the slowest decoded row implies also finding a worst case delay transition that excites that row.

A first analysis on the number of possible combinations leading to worst case response would require 2 2N simulations for a N-input decoder and that for each netlist where variability has been injected. Even for small decoders, this characterization is unfeasible. Therefore a methodology is required to find the critical path with the smallest possible number of transition vectors.

For that purpose, we have developed a heuristic that is based on decoupling the search for worst delay output for a given address from that one for the worst delay transition, irrespective of the output being selected. Based on this, an experimental methodology is developed as follows:

Step1. Find the initial vector that activates a set of worst case delay transitions for the decoder under process variability independently of the decoded row.

Step2. Identify the worst case address vector that excites the slowest decoded row under variability.

Step3. Find the set of worst case delay transitions for the full decoder by combining the initial vector to activate the worst case transitions (Step1) with the worst case decoded row address vector (Step2).

Step1: The goal of this step is to find the initial vector that activates a set of worst case delay transitions for the decoder independent of the decoded row. A method has been developed for that by first finding the worst case transition set per building block of the decoder (e.g., address driver, predecoder and postdecoder) and then combining these transitions to find at the inputs of the decoder the worst delay transition for each decoded row. This analysis is possible since the transition only influences the intrinsic capacitance of the current block. The extrinsic load from the next block will not affect the relative ordering of each transition according to their associated delay.

For the two-stage decoder of the SRAM, the building blocks of the first stage is a set of three-input NAND gates and that of the second stage is a set of three-input NOR gates. According to the decoding feature of these gates (e.g., the input combination identifying one different output out of all possible ones in their Karnaugh map), the NAND and NOR gate will have only one decoding vector respectively (e.g., 111 for the NAND gate and 000 for the NOR gate). Hence, the set of transitions potentially leading to worst case delay are, for the NAND gate, the transitions of the type XXX → 111, while for the NOR gate these are of the type XXX → 000 (see Figure 1). To find out which of these transitions remain being the worst case under variability, a significant number of simulations (each under a random process variability scenario) has been performed. Figure 2 shows the results after simulations for the NAND gate. It is clearly visible that at the 65nm technology node, only the transition 000 → 111 remains worst case irrespective of the variability scenario for a NAND gate. While the critical transition for the NOR gate, obtained in similar way as that of the NAND, is the 011 → 000 one. Therefore, we can safely conclude that the influence of process variability in the internal (parasitic) loads of the netlist at 65nm is not yet dominant enough so as to change the impact of the "nominal" worst case transition.

To find the initial vector that exercises a worst case transition for any decoded output, we just have to backtrack the gate-level worst case transitions all the way, from the postdecoder (NOR gate) through the predecoder (NAND gate), to the inputs of the address driver in the full decoder netlist.

Step2: The goal of this step is to identify the worst case address vector that excites the slowest decoded row. For this we could simply excite all decoder outputs one by one and detect the slowest one. However, due to the CPU time inefficiency of HSPICE that would also be expensive as the number of combinations grows as 2 n , being n the number of address decoder inputs. To avoid an expensive search, a technique based on exciting all decoder outputs at the same time and finding the slowest of them by using only one address vector has been developed.

This can be done by modifying the decoder input driver circuitry under test mode such that all input address bits and their complemented bits (see Figure 1) are supplied with the same "0 → 1" transition simultaneously irrespectively on whether a particular input should be complemented. This functionality of the address driver will violate the decoding principle by applying under test mode a 1...1 combination to the predecoder gates, hence activating all the decoder rows simultaneously. By monitoring the difference in delay of all the rows, the slowest one can be easily identified. Based on this, the worst delay vector can be obtained to activate that row under normal decoding operation. The input address transition will not play a role in the determination of this vector since the same transition (0 → 1) is generated in all outputs.

NAND delay of different transitions under variation

0.00E+00 Step3: The goal of this step is to find the set of worst case delay transitions for the full decoder. For this we simply combine the initial vector activating the worst case transitions obtained in Step1 with the worst case decoded row address vector obtained in Step2. This will lead to a set of two-address vectors where first vector is the initial vector exercising the worst case transition irrespectively of the decoded output, followed by the vector selecting the worst case output.

To capture the worst case energy of the decoder, the set of vectors we select is different although still based on the set found for delay characterisation. Since energy is also proportional to the switched capacitances involved in the decoding process, the worst case decoder transition for energy can be also obtained by applying two vectors. In this case, the first vector should be the same as the one found for delay in order to activate the worst-case load conditions of the gate's parasitic capacitances. The second vector is obtained by complementing the the bits of the vector identifying the slowest row. That should lead to an opposite switching direction in the nodes of the netlist hence maximizing the activity of these nodes.

Full memory characterization

Similar to the decoder, finding the delay of the array under process variability using a full search of all the cells, Sense Amplifiers (SA), and other related periphery is impractical. Hence, there is no better alternative than using a local search where decoder and cell-array interactions are neglected. However, in practice given enough Monte-Carlo simulations are made, the worst case delay range of both decoder and the cell-array when simulating both together is still captured.

For that purpose, the delay of the SRAM is obtained as follows:

Step A: Generate the nominal netlist of the target memory row decoder (see Section 3) and inject stochastic variability on the transistors of that netlist, hence generating a netlist for a given variability scenario. Then characterise the row decoder worst case delay and energy following the methodology described in Section 4.1. As a result the worst-case activated wordline both for energy and delay is also identified.

Step B: Generate the full memory lumped netlist (see Section 3) by connecting the critical rows with one of the wordlines of the lumped cell-array netlist.

Step C: Simulate the netlist generated in the previous step and measure the worst-case energy and delay of the write and read operations. The write operation worst case delay is measured from the moment the input address is given to the moment when the last cell in the accessed bitlines becomes stable. The read operation is performed right after the write operation and its associated worst case delay is measured from the time the address is given to the time when the slowest data bit is read out among the all the parallel bitlines.

To capture the SRAM energy/delay with enough accuracy, 200 simulations have been performed by each time generating a different process variability scenario. Given Monte-Carlo analysis, this should bring a confidence factor above the 99% since that one is inversely proportional to the square root of the number of experiments.

Analysis of variability results

To evaluate the impact that process variability has at the SRAM level, a 1KB SRAM has been simulated following the methodology defined in Section 4. The circuits of this SRAM and especially the associated timing interfaces have been designed for nominal operation. Hence, no particular safety design margins have been taken when designing these circuits.

The experimental results shown in Figure 3 indicate that the decoder, under process variability tend to have larger delay than the nominal one. The large impact in decoder delay is due to the fact that the slowest path of the affected decoder will be slower than the nominal one for most of the cases. The energy increases also marginally and this is due to the existence of fanout paths initiated at the predecoder stage that reconverge at the input of the postdecoder gates. The delay of these paths are different depending on the actual variability scenario, hence leading to glitching activity at the input of the postdecoder gates. This is wasted energy that leads to a spread in decoder energy. The delay/energy cloud of the memory for read and write operation are shown in Figure 4 and Figure 5 respectively. These Figures clearly indicate that the delay of both operations tend to become slower in most of the simulations. This increase in delay mostly comes from longer decoder delay but, also from the cell array. This is the case for small size SRAMs, since the decoder contribution in the overall delay is significant [START_REF] Amrutur | Speed and power scaling of SRAM[END_REF]. Also, as Figure 3 shows this is significantly affected by variability.

In the read operation, apart from the decoder, the cell array also tends to have larger delay because in most cases the slowest bitline (incl. the SA) among the ones being read will become slower than nominally. The increase in delay is related to a larger time required by the sense amplifiers to amplify the smaller-than-nominal voltage swing on this particular bitline to a full-rail voltage. This smaller swing is due to several effects, even a combination between them. For in-

Figure 5. SRAM energy/delay for write operation under process variation

The energy variation of the read operation is dominated by the energy consumed on the bitlines, including the active ones (e.g., these being selected by the column muxes), the passive ones (e.g., these not being selected) and the SA. When bitlines have larger swing than nominal, they will also consume also more energy than in the nominal case due to the larger discharge current in the global bitline capacitance and this up to a level where the SA can amplify that swing up to a full rail. When the bitlines have less voltage swing, they will also consume less energy due to the smaller discharge in the associated bitline capacitances. In this case, even when the SA needs more time, hence more energy to amplify this smaller swing to full rail, that one is not yet big enough (in their global contribution) so as to compensate the decrease in energy obtained in the bitlines due to the smaller discharge current. This balance is illustrated in Table 1 for both a nominal memory and one affected by variability showing less overall energy. In the write operation, delay has the same trend as in the read operation for similar reasons. For instance, one end (e.g. n1 in Figure 6) of the cell being written is directly grounded by the write circuit in a very short time while in the other end (e.g. n2 in Figure 6) of the cell, the bit stored there has to be flipped by one of the inverters in that cell. That inverter may have under variability less driving capability than in the nominal case, which would result in a longer time for the cell to modify its state. Indeed, we would require all bitlines to react faster than the nominal bitline and that gain in delay to become larger than the excess in the decoder delay so as to have an overall memory with a faster reaction time than the nominal memory. That is in fact extremely unlikely to happen as simulation results confirm. The impact in energy in write operation is also similar to that in the read operation. Apart from the marginal energy increase in the decoder, the array consumes, in most cases, more energy due to the interaction between passive bitline and the active bitlines. Different from the array read delay which is mainly composed of bitline delay and SA delay, the array write delay is mainly determined by the bitline delay (the time the cell being written to become stable). When it becomes larger than nominal, the passive bitlines have more time to discharge through the pass transistors of the cells (see Figure 6). This will lead to a larger than nom-inal voltage swing on them which consequently increases their energy consumption. On the other hand, the active bitlines can also consume more energy due to larger swing on them and due to short circuit or leakage effects in the cells being activated. When the write operation becomes faster than the nominal case the energy associated becomes also smaller because of a similar mechanism.

Conclusion

SRAMs tend to be slower and consume more energy on average than their nominal implementation in most cases under variability. This is partly counter-intuitive so in this paper we have identified and illustrated the different mechanisms behind this unexpected behavior and quantify the impact of these effects for on-chip SRAMs at the 65nm technology node.

Figure 1 .

 1 Figure 1. Decoder structure and possible set of worst case transitions for the (pre/post)decoder blocks

Figure 2 .

 2 Figure 2. Impact of variability in delay for the set of potential worst case transitions for a NAND gate at the 65nm technology node.

Figure 3 .

 3 Figure 3. Decoder energy and delay under process variation

Figure 6 .

 6 Figure 6. Simplified passive bitline structure in the Write (1) operation

  stance, the bitline discharge current can be reduced due to the difference in time when the pass transistors start activating the selected cell. This time can become later than nominally e.g., due to an increase in the V t value of these transistors. Also, the inverters in the cell can have less driving capability due to the impact of variability in both V t and β. Statistically, it is very much likely to have one of the bitlines reacting slower than the nominal case, hence the delay of the read operation is also in most cases larger than nominal.

				E/D of read operation, 1KB SRAM
		1.2
			E/D under variation
		1
	Energy (relative)	0.4 0.6 0.8	E/D of nominal case		40%	42%
		0.2
		0
		0	0.2	0.4	0.6	0.8	1	1.2
				Delay (relative)
	Figure 4. SRAM energy/delay for read operation
	under process variation
				E/D of write operation, 1KB SRAM
		1.2
		1
	Energy (relative)	0.4 0.6 0.8	E/D of nominal case E/D under variation		30%	42%
		0.2
		0
		0	0.2	0.4	0.6	0.8	1	1.2
				Delay (relative)

Table 1 . Array read energy breakdown under variation where total energy is less than nominal

 1

	Relative Active Passive	SA	Total
	energy	bitlines bitlines
	nominal	0.163	0.6	0.237	1
	variation	0.07	0.51	0.26	0.84

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Acknowledgments

The authors gratefully acknowledge the fruitful discussion held with colleagues of IMEC's System Level Integration project as source of inspiration for the material presented here. In particular we thank to Antonis Papanikolaou and Jeroen Croon for their feedback.


Christophe Alexandre

Hugo Clément

Jean-Paul Chaput

Marek Sroka

Christian Masson

Rémy Escassut

TSUNAMI: An Integrated Timing-Driven Place And Route Research Platform

In this paper, we present an experimental integrated platform for the research, development and evaluation of new VLSI back-end algorithms and design flows. Interconnect scaling to nanometer processes presents many difficult challenges to CAD flows. Academic research on back-end mostly focuses on specific algorithmic issues separately. However one key issue to address also is the cooperation of multiple algorithmic tools. TSUNAMI, our platform, is based on an integrated C++ database around which all tools consistently interact and collaborate. Above this platform a fixed die standard cell timing-driven placement and global routing flow has been developed.

Introduction

The advent of nanometer silicon technologies has introduced new challenges in physical design CAD, introducing an almost intractable interdependence between the tasks of synthesis, placement, global and detailed routing, timing optimization and noise avoidance. Therefore new design flows are being worked out with major objectives : avoid iterations between levels of design, enable early assessment of chip area and performance, reduce design uncertainty on the feasibility of later design steps and provide scalable tools against complexity increase. The key issue is to let multiple algorithmic tools cooperate through an integrated database providing a unified view of the ongoing state of the design, in order to concurrently refine all interacting design facets. This issue has been addressed by proprietary solutions into CAD industry. Recently the OPEN-ACCESS initiative [START_REF] Mallis | OpenAccess: The Standard API for Rapid EDA Tool Integration[END_REF] has proposed an open-source standard with the intent to improve interoperability of CAD tools. The TSUNAMI project is one of the first academic attempts to develop a back-end platform where all algorithmic engines operate on an integrated C++ database (HURRI-CANE) around which they consistently interact and collaborate. This ongoing project currently addresses the timing-driven placement and global routing of fixed-die standard cell blocks. In the following sections, we will briefly present the HUR-RICANE database, the TSUNAMI flow currently implemented and the main features of its algorithmic engines.

HURRICANE: the C++ database

HURRICANE is a lightweight C++ object oriented database and programming platform which provides a unified and consistent modeling of hierarchical VLSI layouts through all the design steps from logic description down to detailed layout. It also consistently manages parasitic data (RC trees) and the timing graph. For that purpose :

• It provides a powerful API for fast access and incremental update which fully relieves the application programmer from memory management issues.

• It allows the seamless forward or backward transformation of net-list into a global routing or a detailed layout (or a mix of those states), ensuring built-in connectivity invariance.

• It represents a hierarchical layout as a "folded" memory data model (as usual), but provides a "virtually unfolded" view to the tools tracing, annotating or displaying its content. For that purpose it manages the concept of "occurrences" which virtually refer items anywhere within the "unfolded" design hierarchy.

• User defined properties and relations can be attached to any database object but also to occurrences (without the need to "unfold" or "flatten" the design hierarchy). This provides elegant ways to design algorithms for visiting, extracting and annotating hierarchical designs.

• It provides a rich (extensible) set of powerful query objects ("collections") for visiting database items or occurrence items.

• It embeds high performance 2D region query facilities, a high speed graphical display engine and a graphical "data structure inspector", significantly simplifying the development and debugging of layout algorithms, editors and user interfaces. HURRICANE was developed by BULL S.A. in close co-operation with UPMC/LIP6 and later with the support of SILVACO. It has been focused on the fast development of integrated RTL to silicon flows, full-custom layout generators and technology migration tools for highly hierarchical layouts (it has been used for the migration of a 40 M transistors CPU IC from 120 nanometer 6 M layers to 90 nanometer 9 M layers CMOS process).

The TSUNAMI platform and flow

Above HURRICANE, the TSUNAMI platform provides general services: input/output LEF/DEF interfaces, cell library timing data inputs and utilitarians for building GUIs above the Hurricane display engine. It also provides a interpretative PYTHON interface both as an extension language to HURRICANE API and as an encapsulation facility for the algorithmic engines in order to build and experiment different optimization flows and easily integrate new engines. Within this environment, each algorithmic tool is an engine (a C++ object with its PYTHON wrapper) whose task is to analyze or process the current state of the design. Are currently implemented:

• A space manager, which plays a central communication role. It manages the recursive division of the design area into bins, the fences separating them and the pseudo-pins for nets crossing fences.

• A global placer, based on the hmetis multi-level net-list quadri-partitioner [START_REF] Karypis | Multilevel k-way hypergraph partitioning[END_REF], which refines cell location into bins.

• A global router which refines or rebuilds the steinertree topology of nets. It can operate both within placement refinement steps and after placement finalization.

• A parasitics estimator which evaluates RC according to the level of precision of the routing and a delay evaluator which computes and stores Elmore delays.

• A static timing analyzer which, from interconnect delays and library cell delays, determines critical paths and valuates nets criticality to be fed back to placer and router.

• A detailed placer which finalizes and legalizes cell locations in each terminal bin. And those under development:

• A gate sizing and buffer placement tool.

• A detailed router driven by the global router directives.

The standard cell place and route flow developed and under experimentation (figure 1) is a top-down progressive refinement process which proceeds by a succession of interleaved phases of quadri-partitioning, global routing and net-list timing optimizations:

• The entry point of a refinement loop is the geometric quadri-partitioning of all bins with more than 100 instances. Then each net-list of those bins are quadri-partitioned (but • Then the global router (re)builds or refines the steiner-trees of all nets whose cells have changed location. It has multiple algorithmic tactics tailored for different net configuration and timing criticalities, and tries to minimize both wire length and congestion on fences.

• Then the RC trees are (re)evaluated and a new static timing analysis is processed in order to compute updated critical paths, slacks and criticality value on each arc of the timing graph [START_REF] Kong | A novel net weighting algorithm for timing-driven placement[END_REF].This provides tighter directives to the next placement and global routing step.

• At this step, data is available to proceed (in the future) to gate sizing and buffer planning (virtual insertion in the timing graph, not in the net-list).

At the end of the refinement loop (after buffers physical insertion) the simulated annealing detail placement of each bin is completed. Global routing is then refined, taking into account pin locations and obstructions. The resulting global routing directives and net criticalities will be fed to the detailed router under development.

Figure 1 .

 1 Figure 1. Overview of the place&route flow

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE


Amitava Bhaduri

Ranga Vemuri

Inductive and Capacitive Coupling Aware Routing Methodology Driven by a Higher Order RLCK Moment Metric

A new routing methodology, which accounts for inductive and capacitive coupling between neighboring wires is proposed. The inductive and capacitive coupling of the wires are introduced through a 'moment' based higher order RLCK cost function. The routing process guided by this costfunction ensures that the final solution has minimum ringing and delay.

Introduction

In the multi-GHz range, interconnect parasitics play crucial role in circuit performance. In traditional 'maze' routing it is difficult to introduce the effect of coupling parasitics. The maze router always finds the shortest path, which may lead to significant parallel runs between two neighboring wires giving rise to considerable amount of inductive and capacitive coupling. In this paper, we propose a routing methodology driven by a 'moment-based' cost function. This costfunction accounts for the higher order R,L,C,K parasitics between neighboring wires and converges to a routing solution that minimizes the overall delay of the nets and results in a better waveform response for all the nets.

Related Work

Crosstalk reduction (coupling capacitance) has been done in [START_REF] Smey | Crosstalk Reduction in Area Routing[END_REF]. The authors in [START_REF] Lillis | New Performance Driven Routing Techniques With Explicit Area/Delay Tradeoff and Simultaneous Wire Sizing[END_REF], developed various performance driven routing strategies using a simple Elmore (RC) delay model. Cong et al. [START_REF] Cong | Interconnect Layout Optimization Under Higher Order RLC Model for MCM Designs[END_REF], have used higher order RLC model in their MINOTAUR global router Though all of the above routing methodologies have their own merits, none of them considers complete R,L,C,K parasitics during routing.

Ringing and Central Moments

At high frequencies, the inductive effect of the interconnects gives rise to a T-line phenomenon called 'ringing', which can inadvertently cause the circuit to transit to a wrong state and cause logic failure. The repeated 'overshoots' and 'undershoots' also adversely affects the delay of the line as it increases the settling-time of the signal response. In addition to the rise time (t r ) of the signal, the settling time (t s ) has to be accounted to obtain the actual wire delay (t d ) [START_REF] Bakoglu | Circuits, Interconnections, and Packaging for VLSI[END_REF].

In order to account for the self and mutual inductive effects we resort to higher order moments of the impulse response. The concept of central moments is taken from probability theory and is used in delay characterization. The second and third central moments are as follows [START_REF] Gupta | Transmission Line Synthesis via Constrained Multivariable Optimization[END_REF].

µ 2 = 2m 2 - m 2 1 m 0 ( 1
)
µ 3 = -6m 3 + 6 m 1 m 2 m 0 -2 m 3 1 m 2 0 (2)
where, µ 2 is a measure of the spread and µ 3 the skewness of the impulse response. µ 3 = 0 gives rise to a "criticallydamped" signal response. On driving µ 3 closer to zero, 't s ' reduces to a negligible value. In addition to the minimum delay we also obtain a signal response that is less distorted and preserves signal quality. Hence, in our cost function we have chosen µ 3 minimization (closest to µ 3ideal = 0) as the primary objective.

Proposed Methodology

We propose a routing methodology that uses the concepts of Section 3 to find the best possible overall routing solution that has the least parasitic interactions and the best waveform response for all the nets. We describe each of the steps used in our approach below.

Transfer Function and Template Generation: A simple example in Figure 1(A) demonstrates the transfer function generation of two interacting wires. Likewise, we pregenerate the symbolic transfer function of coupled interconnects as per the templates devised. In order to capture the parasitic interactions between the aggressor and the victim wires we have generated a few templates that covers the various ways in which 1-bend and 2-bend interconnects can couple with each other. The L-shaped route is a subset of Z-shaped route, hence we generate the templates with only Z-shaped nets in mind.

Route Cost Function: Let us consider that there are 'n' nets and at a particular instance the 'i'th net needs to be routed. 1. For each of the 'k' candidates of net 'i' µ 3 is calculated.

2. The µ 3 's of all the affected nets (victims) that have already been routed are re-evaluated.

3. For each candidate of net 'i', we compute the overall standard deviation of the routed and the current net as:

Cost = ∑ i n=1 (µ n 3 -µ 3ideal ) 2 i 4.
Store the values of the cumulative cost function for each candidate route.

5. Select the candidate route having the least cumulative cost and add to the list of routed nets.

The cost funtion thus gives a snapshot of the cumulative performance in terms of third-order central moments (µ 3 ) of all the nets up to the current net 'i'. Figure 1(B) illustrates an example with k = 14. Out of the 14 candidates, the cost function chooses candidate 11 as the routing solution.

Moment-driven Routing Technique:

We have implemented the fundamental idea of a Mikami-Tabuchi line-search algorithm, which has been tailored to include our 'moment driven' cost function to sequentially route the nets. We have considered only 2-pin nets that can be connected using either a 1-bend or a 2-bend route. The inspiration of using L-shaped and Z-shaped technique find its origin in [START_REF] Smey | Crosstalk Reduction in Area Routing[END_REF], [START_REF] Kastner | Coupling Aware Routing[END_REF]. As we inspect 'k' possible candidates for each of the 'n' nets in our sequential algorithm, the routing complexity is Θ(kn), in contrast to Θ(k n ) complexity in the method described in [START_REF] Smey | Crosstalk Reduction in Area Routing[END_REF]. DRC violations are automatically eliminated by following the H-V routing technique. In addition, minimum spacing and width rules are accounted for during route generation.

Experimental Results

In our experiments we have randomly distributed pairs of pins and have routed the terminal pairs using our momentdriven line-search algorithm. We were able to find routes for each terminal pair such that the waveform response of the current net and the affected nets are best. As the individual signal response in terms of µ 3 is kept as close as possible to zero we find a routing solution that has a high signal quality and least settling time.

We compare our routing methodology to a standard linesearch algorithm. For the competing approach, we picked the first route found by the router. We measured the cumulative cost (standard deviation) of the routing solution obtained, in separate instances of routing 3, 5, 10, 20, 30, 40 and 50 nets respectively. We see that the cumulative cost obtained using our method is significantly better than the competing approach as shown in Figure 1(C).

Conclusion

Interconnect parasitic consideration cannot remain restricted to a simple RC or a RLC model in performance-driven routing at multi-GHz frequencies. We have proposed a routing methodology that takes into account the inductive and capacitive coupling parasitics between neighboring wires during the routing process. The proposed approach ensures a routing solution for a number of randomly distributed pin-pairs, which has the least ringing and less settling time.

(Figure 1 .

 1 Figure 1. (A)Transfer function of 2 coupled wires (B) Possible Candidate Routes (C) Cumulative Cost comparison

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE