Exploiting Net Connectivity in Legalization and Detailed Placement Scenarios

Abstract

Standard-cell placement is the fundamental step in a typical VLSI/ASIC design flow. Its result, paired with the outcome of the routing procedure can be the decisive factor in rendering a design manufacturable. Global placement generates an optimized instance of the design targeting a set of metrics, while ignoring rules pertaining its feasibility. Legalization and detailed placement rectify this situation, attempting to attain minimum quality loss by often disregarding the connectivity between cells and making runtime the focal point of these steps. In this article, we present a set of variations on a connectivity-based legalization scheme that can either be applied as a legalizer or a detailed placer. The variations can be applied in the entirety of the chip area or in the confinement of a user-specified bin while they are guided by various optimization goals, e.g., total wire length, displacement and density. We analytically describe our variations and evaluate them through extensive simulations on commonly used benchmarks.

1. Introduction

The constant change in chip design requirements, has led to the creation of custom design methodologies based on the available vendor-related tool flows and the expected quality of result. Nevertheless, there is a mature and proven backbone process which can be seen in Figure 1 and includes the following steps:

• Functional Specification: Architecture, features and functionalities specification in terms of power consumption, area and delay.
• HDL Design and Simulation: Design implementation using a Hardware Description Language (HDL) (primarily VHDL or Verilog) followed by a functional simulation that verifies the logical and/or algorithmic behavior of the design.
• Synthesis: Conversion of the HDL design into an optimal technology-dependent gate-level netlist, based on a set of constraints.
• Floorplanning: Design partitioning that generates the shape and size of blocks, followed by block, macros and pin placement, and chip area estimation.
• Placement: Designation of standard cells’ positions in pre-defined rows as to minimize total interconnect wire length, power dissipation and delay. Placement can be further divided into three distinct steps: global placement, legalization and detailed placement. During global placement, the coordinates of each standard cell are computed as the outcome of an overall optimization procedure that focuses on minimizing key metrics in addition to interconnect wire length. The result at hand might, and most certainly will, contain overlapping cells and/or cells that are not properly embedded in the design’s predefined rows, a situation which certifies the infeasibility of the manufacturing procedure. The aforementioned issues can be resolved by distancing and fitting the cells throughout legalization. Moreover, the deterioration caused by the preceding step is leveled by minor and swift modifications that are performed in detailed placement.
• Routing: Implementation of the connections between cells, blocks and pins.
• Verification and Signoff: Succeeding routing, the design process undergoes three steps of physical verification (commonly referred as signoff):

  −

  Layout versus schematic (LVS), certifying that the layout matches the schematic.

  −

  Design rule check (DRC), affirming that the geometry follows the foundry rules.

  −

  Logical equivalence check(LVC), checking the equivalence between pre and post design layout.

The following list reports on the contribution of our work:

• We propose six variations on the legalization scheme described at [1] that can be easily applied on top of any modern standard cell design.
• Each variation can be applied either as a legalizer or as a detailed placer.
• Proposed approaches managed to reduce the total interconnect wire length up to 81% upon the original legalization scheme [1], without significantly affecting the execution time.
• Extensive simulations are conducted to analyze the performance of proposed variations against state-of-the-art algorithms using 22 real-world benchmark circuits

The rest of the article is organized as follows. Section 2 presents related approaches considering legalization and detailed placement, Section 3 introduces a list of variations on a previously published legalization scheme [1], that can be applied either as a legalizer or as a detailed placer, while Section 4 accommodates the experimental results for the selected benchmark suites, followed by a discussion and the conclusions in Section 5.

2. Related Work

Tetris [2] and Abacus [3] have laid the foundation for most modern legalizers. A mutual and beneficial feature displayed by both algorithms is their overall execution time, and the ability to minimize total displacement considering the initial locations of the cells. However, both algorithms can be characterised as wire length agnostic, since the minimization of the total interconnect wire length is ignored in placement decisions. Due to their straightforward approach and swift manner, these algorithms provide a good baseline solution, that can be further enhanced with additional optimization approaches and heuristics that mitigate their disadvantages.

In [4], a collection of Tetris-based heuristics, that improve upon major placement-related metrics is presented. Tempering with the directionality regarding each cell’s movement and the construction of the chip area grid, restricts abrupt cell movements, thus avoiding a sharp increase in interconnection wire length. A two-step overlap elimination procedure is presented in [5]. Initially, the cells are redeployed vertically, until the row capacity constraints are satisfied, while at later stage, the overlaps within rows are eliminated by modelling the procedure as a topological shortest path calculation problem.

OAL [6] and Domocus [7] can be considered as Abacus-adjacent. OAL presumes upon a linear wire length model and can be applied successfully in designs containing obstacles, while Domocus utilises parallelisation techniques in order to mitigate the high execution time and memory consumption of Abacus. To do that, authors proposed the partition of the entire circuit area into equally-sized vertical zones. Then, the Abacus algorithm is applied in parallel to each zone over the cells contained in the zone. In this way, the need for extra synchronization overhead is avoided (e.g., semaphores) as each zone is processed independently. In addition, in [8] a history-based legalizer is proposed. During each iteration of the algorithm, feasible solutions to the legalization problem at hand are automatically applied, while non-feasible solutions are registered in an appropriate record, forming a sequence of possible moves that should be discouraged in future iterations.

Additionally, in [9], a legalization algorithm targeting mixed-height cell designs that takes into consideration custom region constraints is presented in [10], a swift optimization method for quadratic cell movement that can manage designs containing cells with height equal to that of two standard rows is deployed to tackle the legalization problem, while in [11] the legalization scheme qualifies the minimization of displacement as its target metric.

Finally, in [1], an approach that incorporates the connectivity between cells throughout each iteration of a typical legalization algorithm is presented. Cells are dealt with in an ascending order, according to their lower left corner x-coordinate. For each cell the insertion cost in each row is calculated based on its displacement, and the most cost-effective row is selected to accommodate the cell in question. Upon the completion of the aforementioned move, all cells belonging to the same nets as the preceding cell, are moved by the exactly same amount in the same direction. The only cells excluded from the previous move are those that have been relocated in previous iterations or those that, based on the calculated displacement, are going to be placed outside the boundaries of the core area. The process concludes when all cells have once taken the role of the leader.

Furthermore, considering detailed placement, various approaches have been proposed in academia. We should bear in mind, that these approaches should ideally have minor execution time compared to global placement and yield moderate gains in terms of total half perimeter wire length (HPWL), thus they fall under at least one of the following categories:

• Single Row Optimization: [12,13,14,15,16].
• Cell-to-Slot Matching: [14,17,18,19,20,21,22].
• Cell Swapping: [14,15,16,20,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37].

Single row optimization approaches commonly assume a fixed cell ordering, generated by a previous legalization step and capitalize on the principle of dynamic programming. Unfolding from a pre-computed solution combined with a minimum cost constraint assigned to each cell and related to their current position, an iterative process commences that leads to the computation of the final coordinates.

As for cell-to-slot matching, a subgroup of exchangeable cells is initially identified in a pre-defined bin. A matching problem is subsequently formulated, where cells are to be matched with unoccupied slots inside the aforementioned bin. The legality of the solution might be taken into account (selecting cells with widths less or equal to the slot’s at hand) or otherwise a supplementary legalization step is required.

Lastly, cell swapping although the most “simplistic” approach, encompasses a vast amount of possible variations considering the selection of inter-exchangeable cells, the most straightforward approach being taking into account only same size cells therefore retaining the legality of the design. Moreover, the search space can either be expanded by including different size cells or consider empty spaces as void cells, or be restricted in a specific window/bin/row.

3. Approaches

There is a plethora of algorithms and heuristics that can be applied throughout physical design [38,39,40,41] that achieve feasible solutions upon each of the distinct steps of the placement procedure. Since standard cell placement can be perceived as an NP problem [42,43], constant research and experimentation is required in order to achieve near optimal solutions without sacrificing execution time.

The most common performance metrics for algorithms belonging in this area are total HPWL and total displacement, both measured in distance units. HPWL is directly related with the routability and the timing behavior of the final outcome, while displacement can be interpreted as a metric showcasing how much we have diverged from an optimal, although illegal, initial solution. A good approximation considering the interconnection wire length of a net, can be calculated based on the half perimeter of the minimum bounding box enclosing its components. Thus, total half perimeter wire length is the summation of each net’s wire length. Displacement is calculated as the Manhattan distance between a cell’s initial position (after the global placement phase) and the one obtained after any of the subsequent phases (legalization and/or detailed placement). It should be noted that a chip’s row density is calculated as the the total area of the cells embedded in the row divided by the row’s area.

The work in [1], is used as the yardstick in the proposed methods and as such its functionality requires further analysis. The aforementioned algorithm can be applied either as a legalizer or as a detailed placer in a typical placement flow.

It receives a globally placed design as its input, and proceeds in eliminating overlap and overflow phenomena, meaning overlapping core elements or cells that that extend further than the die area. In the beginning, all core elements are sorted in an ascending order based on their leftmost-x coordinate. Following that, each leading cell is iteratively placed in the die area at the leftmost available position, at a minimum distance from their original position. In an intermediate step, every cell that is directly connected to the leading cell and is a part of the same net, duplicate the movement of its leader, aiming at the deceleration of the deterioration of the total half perimeter wire length.

While this approach succeeds in eradicating manufacturability issues and produces a legal design, it exhibits some drawbacks. Firstly, by stacking all cells to the leftmost available position, congested (highly dense areas) are formed in the left side of the chip and secondly, only half of the available options are considered while checking for the optimal leftmost available positions. Amending these handicaps is the focal point of the variations presented in this work.

The first set of variations focuses on the legalization capabilities of the algorithm:

• unbounded_bidirectional (ub): The main difference from its original counterpart is the utilization of both sides of the chip while considering the position with minimum displacement where the leading cell will be placed. The interconnected cells are relocated in the exact same manner. By considering additional placement slots, cells that are going to be placed in future iterations, will have increased chances of being placed in an optimal position. Moreover, the left-right arrangement reduces the overall density of the chip. Figure 2 depicts an execution example of $ub$, followed by Algorithm 1 describing its functionality.
• bounded_bidirectional_dens_limit (bd): This variation follows the previous bidirectional arrangement but applies a density threshold, in addition, for each row. Upon reaching this threshold, the row at hand is viewed as a macro that cannot be tampered with. The goal is to decongest the globally placed design while simultaneously correcting any illegalities, functioning as a legalizer and a detailed placer at the same time.
• unbounded_bidirectional_div (ubd): Practically, a modified version of $ub$ that differentiates in the intermediate step of moving interconnected cells, by recalculating their displacement following the formula:

  $$total\_disp=\sum _0^{n-1}\frac{orig\_disp}{2^n},$$

  (1)

  where n is the number of common nets and $orig\_disp$ is the displacement of the leading cell. The goal is to minimize total displacement by limiting the number of moves a cell has to make.
• bounded_bidirectional_div_dens_limit (bdd): An amalgamation of the two previous methods, applying a density threshold on every row of the design while applying the same formula for relocating the interconnected cells.

Algorithm 1 Unbounded Bidirectional

1: Sort cells in ascending order based on their x-coordinate 2: for$cell=cells[0,1,\dots ,N-1]$do 3:       Find minimum displacement cell position searching in both directions 4:       Place cell in new position AND render this cell immovable 5:       for $net=cell.nets[0,1,\dots ,N-1]$ do 6:             for $cell\_inter=net.cells[0,1,\dots ,N-1]$ do 7:                    Move cell_inter the same way as cell 8:             end for 9:       end for 10: end for

Additional adaptations were explored utilizing the option of dividing the overall chip area in an even number of bins, thus creating a grid, where the aforementioned variations could be applied separately. The number of bins is initially defined based on the user’s input leading to the grid formation (i.e., if the given size is equal to 4, the grid will contain 16 bins). This grid can be considered static, since it remains stable throughout the execution of each approach. The minimum and maximum value of the grid size cannot be strictly defined as it depends upon the design’s overall area and core elements.

• unbounded_bidirectional_grid (ubg): The core functionality is implemented, unmodified, and applied upon each bin of the design. Every cell within a bin is placed into an optimal positions following the bidirectional search pattern, generating a layout similar to the one presented in Figure 3. Further displacement reduction is attained, That way we can achieve further reduction upon displacement of every core element and also achieve decongestion of more areas within the design.
• unbounded_bidirectional_div_grid (ubdg): Similar to the corresponding legalization scheme where the minimization of interconnected cells’ displacement is taken into account. The generated grid restricts considerably the available search areas.

It should be noted that grid-based versions of the density-driven approaches were also implemented, but as the results demonstrate, there may exist certain cases where grid-based approaches exhibit performance degradation. Finally, a subset of the variations was applied as a detailed placement scheme, in randomly placed designs containing macros to test their effectiveness in a different context.

The proposed variations have an $\mathcal{O}\left(C(R+C_N{C}_X)\right)$ time complexity for C cells, R rows. $C_N$ and $C_X$ denote the number of nets where cell C is a part of and the number of cells connected via the net with C, respectively.

4. Experimental Results

4.1. Simulation Setup

Standard Cell Designs

We report on the experimental evaluation of the proposed variation relying on eighteen (18) standard cell designs (benchmarks) as depicted by [44] and on four (4) benchmarks from [45]. These benchmarks are derived from industrial ASIC designs. The number of cells is ranging from 12,506 to 210,341 and from 211,447 to 496,045, respectively. The total number of nets varies from 14,111 to 201,920 and from 221,142 to 515,951, accordingly. The detailed characteristics of ISPD’98 and ISPD’05 benchmarks are presented in

Table 1. ISPD’98 benchmark characteristics.

Design	#Cells	#I/O Pads	#Nets	#Pins	#Rows
ibm01	12,506	246	14,111	50,566	96
ibm02	19,342	259	19,584	81,199	109
ibm03	22,853	283	27,401	93,573	121
ibm04	27,220	287	31,970	105,859	136
ibm05	28,146	1201	28,446	126,308	139
ibm06	32,332	166	34,826	128,182	126
ibm07	45,639	287	48,117	175,639	166
ibm08	51,023	286	50,513	204,890	170
ibm09	53,110	285	60,902	222,088	183
ibm10	68,685	744	75,196	297,567	234
ibm11	70,152	406	81,454	280,786	208
ibm12	70,439	637	77,240	317,760	242
ibm13	83,709	490	99,666	357,075	224
ibm14	147,088	517	152,772	546,816	305
ibm15	161,187	383	186,608	715,823	303
ibm16	182,980	504	190,048	778,823	347
ibm17	184,752	743	189,581	860,036	379
ibm18	210,341	272	201,920	819,697	361

and

Table 2. ISPD’05 benchmark characteristics.

Design	#Objects	#Movable Objects	#Fixed Objects	#Nets	#Pins	#Rows
adaptec1	211,447	210,904	543	221,142	944,053	890
adaptec2	255,023	254,457	566	266,009	1,069,482	1170
adaptec3	451,650	450,927	723	466,758	1,875,039	1944
adaptec4	496,045	494,716	1329	515,951	1,912,420	1944

, respectively. Regarding [45], in order to produce a feasible all non-movable objects must to placed inside the placement region. The designs were globally placed using mPL6 [46] and ePlace [47,48], and were subsequently legalized by applying the baseline legalizer and the variations described in the previous section.

Performance Metrics

To evaluate the performance of the proposed variations we adopt the following set of metrics: (i) total HPWL, (ii) total displacement and (iii) the overall execution time. For each design, all metrics were measured as the percentage of performance improvement of each approach (A) over the connectivity-based legalization scheme (B) as follows:

$$improvement=\frac{performance\left(B\right)-performance\left(A\right)}{performance\left(B\right)}$$

(2)

All algorithms were implemented in Python, and experiments were performed on a Linux-based server, with two 6-core Intel Xeon E5-2630 CPUs running 2.2 GHz, using the benchmark suit of [44,45].

4.2. Performance Assessment

Firstly, we perform a set of experiments using mPL6 as a global placer over the ISPD’98 benchmarks, whose characteristics are presented in Table 1. Each figure is divided into four sub figures each oh which presents a different proposed variation. In Figure 4, we present the percentage improvement in terms of HPWL. In total all of our variations are performing good in case of HPWL improvement, which is quite encouraging for our variations. In case of $ub,bd,ubd$ and $bdd$, the improvement is proportional to the size of the design as well as the methodology that each approach is following. This can be justified by the fact that the latter approaches are performing changes to the entire design. To be more precise, $ub$ (Figure 4a), is the first and most similar variation to the original algorithm. Introducing a novel methodology to identify the best position to place a cell clearly achieves significant results in terms of HPWL. Density threshold approaches ($bd$ and $bdd$) are presented in Figure 4c,d. A notable reduction in HWPL (up to 70%) is achieved when we set the threshold down to 95% of the original row density. We have to mention that lower threshold values will result into non-feasible solutions. This is due to the nature of our benchmarks under testing, as they are smaller in scale and already densely populated. In all the aforementioned cases, we can notice a performance degradation in terms of displacement and execution time. This is expected, as in our approaches, by minimizing HPWL we need to re-place interconnected cells as close as possible in an iterative manner. Regarding the grid based approaches ($ubg$ and $ubdg$) our variations demonstrate the best performance. Furthermore, in Figure 6a,b it is shown how the techniques that divide the designs into grid can decrease significantly the execution time. The above performance is reasonable since the best position of each cell can be found by exploring a much smaller-in-scale area compared to the rest of the variations. Additionally, this impacts the HWPL metric as well, because the displacement of each cell from its initial position is far smaller in range (Figure 5a,b).

Subsequently, the same set of designs, now globally placed by ePlace, are utilized to enhance our understanding upon the efficiency of the proposed approaches. The results are quite similar and follow the same patterns as those of the first set, thus proving that all approaches are performing better than the original algorithm, as a legalization method, regardless of the global placement algorithms applied in previous steps. The results in their entirety are depicted in Figure 7, Figure 8 and Figure 9. As can be seen in

Table 3. Average improvement in core placement metrics.

Approach	Avg. HPWL Improvement (mPL6)	Avg. HPWL Improvement (ePlace)	Avg. Displacement Improvement (mPL6)	Avg. Displacement Improvement (ePlace)	Avg. Runtime Improvement (mPL6)	Avg. Runtime Improvement (ePlace)
ub	18.13%	17.01%	36.18%	32.72%	0.53%	0.86%
bd99	17.48%	16.52%	34.858%	31.17%	−2.02%	−29.56%
bd95	15.31%	14.61%	27.15%	24.52%	−21.76%	2.78%
ubd	40.36%	38.57%	−80.25%	−86.99%	−105.06%	−102.99%
bdd99	40.32%	38.50%	−82.35%	−88.83%	−147.22%	−161.25%
bdd95	38.74%	36.95%	−91.09%	−96.33%	−203.66%	−215.67%
ub(2 × 2)	43.87%	46.13%	57.05%	57.88%	99.22%	99.12%
ubd(2 × 2)	59.94%	62.36%	18.57%	24.71%	99.20%	99.03%
ub(4 × 4)	61.78%	64.06%	73.26%	74.12%	99.54%	99.45%
ubd(4 × 4)	71.21%	73.50%	63.39%	65.26%	99.50%	99.38%
ub(8 × 8)	72.12%	74.07%	83.95%	84.76%	99.72%	99.89%
ubd(8 × 8)	76.84%	78.78%	83.97%	85.28%	99.67%	99.60%
ub(16 × 16)	77.41%	79.09%	91.08%	91.56%	99.81%	99.78%
ubd(16 × 16)	79.31%	81.04%	92.98%	93.65%	99.78%	99.73%

, considering the grid-based approaches, whose effectiveness is explained in detail in the previous paragraph, remarkable maximum average improvement can be observed in key metrics (81% for HPWL, 93% for displacement and 99% in execution time) in comparison to the baseline legalizer. Analytic results considering HPWL are depicted in

Table 4. Detailed results considering HPWL of the dominant legalization variations.

Design	GP (mPL6)	Baseline [1]	ub 8 × 8	ubd 8 × 8	ub 16 × 16	ubd 16 × 16
ibm01	2,073,720	8,578,749	2,687,459	2,268,377	2,232,947	2,127,129
ibm02	4,115,535	17,088,957	5,104,443	4,348,663	4,328,567	4,176,168
ibm03	5,618,096	22,618,146	6,934,248	6,196,641	5,970,270	5,764,097
ibm04	6,959,972	23,732,424	8,328,121	7,522,072	7,262,231	7,030,794
ibm05	10,058,599	36,390,124	11,862,607	10,530,664	10,582,865	10,163,971
ibm06	5,735,064	22,289,668	7,360,543	6,551,592	6,250,799	5,973,455
ibm07	9,403,115	47,913,647	12,863,250	11,069,734	10,653,858	9,894,014
ibm08	10,188,507	54,872,802	14,751,303	11,639,903	11,703,331	1,0572,367
ibm09	11,095,230	54,440,500	16,567,562	13,836,911	13,147,719	11,938,413
ibm10	19,841,489	98,718,698	30,091,176	24,160,180	23,733,083	21,170,214
ibm11	16,349,962	89,133,528	23,991,183	20,617,189	19,454,785	17,756,809
ibm12	24,204,836	139,103,758	35,747,744	28,500,840	28,719,277	25,676,673
ibm13	19,099,801	141,639,550	31,222,644	25,607,769	24,010,729	21,529,955
ibm14	34,804,692	234,332,753	57,311,946	47,511,227	44,773,614	39,711,435
ibm15	42,097,139	309,725,895	74,604,463	58,926,602	56,302,260	48,779,650
ibm16	45,342,902	353,949,149	87,668,119	66,058,790	64,848,164	5,4053,562
ibm17	62,242,741	483,965,502	116,968,604	82,558,553	86,069,785	71,817,907
ibm18	44,084,573	386,787,994	86,903,950	64,359,380	63,517,563	5,2543,606
adaptec1	103,334,844	491,406,304	19,1049,903	141,001,589	148,124,392	121,840,413
adaptec2	121,481,139	684,333,764	251,113,848	185,450,686	178,073,983	143,689,629
adaptec3	256,734,372	1,314,853,028	695,749,638	472,768,557	466,814,791	355,400,251
adaptec4	230,334,408	126,638,919	652,205,290	457,445,662	434,328,800	338,347,283

.

The last set of experiments targeted the application of the aforementioned approaches as detailed placement methods over legalized designs. The benchmarks from [45] were globally placed in a random manner and legalized by the original algorithm. It should be noted that these designs contain immovable core elements that cannot partake in any placement-related procedure and cannot be moved/re-placed in any way. The size of these elements, compared to the available spaces in the die area, render the density-driven approaches presented, impractical, and as a consequence no further experiments were performed.

The non-grid versions of $ub$ and $ubd$ improve HPWL, as expected. As for their counterpart, although the 2 × 2 grid version seems unable to generate sustainable results (mainly due to the “crude” partitioning of the overall area), the remainder of the approaches outperform this version in an incremental way as the partitioning scale rises to create greater grids, as depicted in Figure 10, Figure 11 and Figure 12 display the results concerning displacement and execution time, respectively. In both cases, improvements are inversely proportional to the size of the design and the grid constructed.

5. Discussion and Conclusions

In this article, we introduced new approaches to tackle the VLSI placement problem. We presented legalization and detailed placement variations that consider the entire chip design as well as grid based approaches whereby the entire design area is divided into a variable sized grid. We provide the outcome of an extensive experimentation using 22 real-world benchmark circuits (fixed macro blocks were included) and compared the proposed variations with a sophisticated legalizer/detailed placer and two global placers. Our evaluation exhibits that the proposed variations can outperform the performance of the solutions provided in the respective literature in terms of both HPWL and execution time. Viewing the results in a retrospect we can state that the variations that utilize the grid formation achieve the best performance in all three optimization criteria, i.e., HPWL, displacement and execution time. Generally, in grid variations the total number of cells’ moves are fewer compared to the rest approaches as the grid creation generates small areas of unused space, i.e., smaller number of candidate positions to allocate an unplaced cell. The above holds true regarding the type of global placer being used as an initial step. Thus, the proposed variations can be applied after any global placer encountered without jeopardising the anticipated performance.