Detailed routing is one of the most challenging aspects of the physical design process. Many of the violations that occur during the detailed routing stage stem from the placement of the cells. In this paper, we propose a deep learning framework to identify short violations that can occur during detailed routing from a placed netlist. One of the advantages of our technique is that by using the proposed deep learning-based predictor, global routing is no longer required as frequently and hence the total runtime for place and route can be significantly reduced. In this paper, we discuss the proposed framework and the methodology for analyzing the extracted features. The experimental results show that the average sensitivity, specificity, and accuracy of Eh?Predictor is above 90%. In addition, we show that Eh?Predictor is up to 14 times faster than NCTUgr for smaller designs and up to 96 times faster for larger designs.

Modern analytic placement tools are commonly built around the idea of iterative Lower Bound (LB) and Upper Bound (UB) placement. The LB step optimizes wirelength and timing while ignoring overlap and cell-type constraints, whereas the UB step attempts to spread cells and satisfy constraints without harming design quality. Top-down geometric partitioning techniques have traditionally been used to spread cells during UB placement. We propose a new, network flow-based approach for UB placement which does a better job of preserving quality by optimizing the displacement of cells from their LB positions. Our approach not only addresses cell overlap, but also accommodates complex region constraints and simultaneously spreads unit-sized logic, carry chains, and blocks like RAMs and DSPs. Our technique is scalable, does not require geometric partitioning, and is suitable for both flat and clustered placement flows.We deployed our algorithm in a commercial FPGA CAD flow, and show that it reduces HPWL by 6.4% on average (up to 22.8% in the best case) while improving worst-slack timing in over 90% of designs, compared to a state-of-the-art alternative.

Detecting and preventing routing violations has become a critical issue in physical design, especially in the early stages. Lack of correlation between global and detailed routing congestion estimations and the long runtime required to frequently consult a global router adds to the problem. In this paper, we propose a machine learning framework to predict detailed routing short violations from a placed netlist. Factors contributing to routing violations are determined and a supervised neural network model is implemented to detect these violations. Experimental results show that the proposed method is able to predict on average 90% of the shorts with only 7% false alarms and considerably reduced computational time.

The legalization step is performed after global placement where wire length and routability are optimized or during timing optimization where buffer insertion or gate sizing are applied to meet timing requirements. Therefore, an ideal legalization approach must preserve the quality of the input placement in terms of routability, wire length, and timing constraints. These requirements indirectly impose maximum and average cell movement constraints during legalization. In addition, the legalization step should effectively manage white space availability with a highly efficient runtime in order to be used in an iterative process such as timing optimization. In this article, a robust and fast legalization method called Eh?Legalizer for standard-cell placement is presented. Eh?Legalizer legalizes input placements while minimizing the maximum and average cell movements using a highly efficient novel network flow-based approach. In contrast to the traditional network flow-based legalizers, areas with high cell utilizations are effectively legalized by finding several candidate paths and there is no need for a post-process step. The experimental results conducted on several benchmarks show that Eh?Legalizer results in 2.5 times and 3.3 times less the maximum and average cell movement, respectively, while its runtime is significantly (18×) lower compared to traditional legalizers. In addition, the experimental results illustrate the scalability and robustness of Eh?Legalizer with respect to the floorplan complexity. Finally, the detailed-routing results show detailed-routing violations are reduced on average by 23% when Eh?Legalizer is used to generate legal solutions.

An increasing number of multi-deck cells occupying multiple rows (e.g. multi-bit registers) are used in advanced node technologies to achieve low power and high performance. The multi-deck standard cell legalization not only should remove all overlaps between cells but also should satisfy delicate and complicated design rules with preserving the quality of the given placement by applying the minimal perturbation. In addition, the process must be fast and robust to handle the sheer number of cells in the state-of-the-art designs. For this purpose, we have defined an evaluation metric based on maximum, average cell movements, and Half Perimeter Wire Length (HPWL) as well as runtime of the legalization algorithm. In addition, we have introduced a set of benchmarks that include multi-deck cells with a range of heights (1-4 row heights).

In this paper, we present DATC Robust Design Flow Database covering the stages from logic synthesis to physical design [1]. Based on this database, design flow and cross-stage optimization research can be conducted via various EDA tools developed from academia.

The standard-cell placement legalization problem has become critical due to increasing design rule complexity and design utilization at 16nm and lower technology nodes. An ideal legalization approach should preserve the quality of the input placement in terms of routability and timing, as well as effectively manage white space availability and have low runtime. In this work, we present a robust legalization algorithm for standard cell placement that minimizes maximum cell movements fast and effectively based on a novel network-flow approach. The idea is inspired by path augmentation but with important differences. In contrast to the classical path augmentation approaches, we resolve bin overflows by finding several candidate paths that guarantee realizable (legal) flow solutions. In addition, we show how the proposed algorithm can be seamlessly extended to handle relevant cell edge spacing design rules. Our experimental results on the ISPD 2014 benchmarks illustrate that our proposed method yields 2.5x and 3.3x less maximum and average cell movement, respectively, and the runtime is significantly (18x) lower compared to best-in-class academic legalizers.

The placement problem has become more complex and challenging due to a wide variety of complicated constraints imposed by modern process technologies. Some of the most challenging constraints and objectives were highlighted during the most recent ACM/IEEE International Symposium on Physical Design (ISPD) contests. In this article, the framework of Eh?Placer and its developed algorithms are elaborated, with the main focus on modern technology constraints and runtime. The technology constraints considered as part of Eh?Placer are fence region, target density, and detailed routability constraints. We present a complete description on how these constraints are considered in different stages of Eh?Placer. The results obtained from the contests indicate that Eh?Placer is able to efficiently handle modern technology constraints and ranks highly among top academic placement tools.

The placement problem has become challenging due to a variety of complicated constraints imposed by modern process technologies. Some of the most challenging constraints were highlighted during the ISPD 2015 placement contest and include fence region and target density constraints; these constraints are in addition to those issues that affect detailed routability such as pin shorts, pin access problems and cell spacing issues. These constraints not only make cell placement more difficult, but can impact the placement objectives such as wire length, routability and so forth. In this paper, we present a comprehensive technique to address fence region constraints in global placement and legalization while still considering detailed-routing issues. We combine concepts from image processing such as region coloring with parallel programming to efficiently deal with fence regions. We also introduce a heuristic method to adjust target densities while avoiding adverse effects on the quality of global routability. Numerical results using both the released and hidden benchmarks from the ISPD 2015 placement contest demonstrate the efficacy of our proposed techniques.

Circuit placement involves the arrangement of a large number of cells which must be aligned to sites in rows without overlap. Placement is done via a sequence of optimization steps which include global placement, legalization and detailed placement. Global placement determines a rough position for each cell throughout the chip while optimizing objectives such as wirelength and routability. The rough placement is legalized and cells are aligned to sites in rows without overlap. Detailed placement attempts to further improve the placement while keeping the placement feasible. In reality, the placement of cells is more complicated than aligning cells to sites without overlap; detailed routability issues compound the placement problem by introducing issues such as pin shorts, pin access problems, and other spacing requirements. The importance of addressing these issues were highlighted during the recent ISPD2014 placement contest [1]. In many cases, detailed routability issues can be addressed during placement to avoid later problems. We describe our ISPD2014 contest legalizer and detailed placer (plus additional extensions) that can address many detailed routing issues without negatively impacting the quality of the final placement. Numerical results are presented to demonstrate the effectiveness of our techniques.