The placement and routing steps directly impact the circuit performance, area, power consumption, and reliability. To handle the high complexity of modern circuits, these steps are tackled separately by applying a divide-and-conquer approach. Unfortunately, due to the continuous increase of design rules complexity, the convergence of solutions can suffer from misalignment, and the effects of an unsatisfactory placement will be noticed only during routing when the placement is considered fixed. In this work, we propose the ILPGRC, an integer linear programming (ILP)-based technique that simultaneously moves cells and routes nets to optimize Global Routing. ILPGRC enables the relocation of cells that can lead to routing issues without compromising the quality concerning the number of VIAs, wirelength, and design rule violations (DRVs). We also propose a partitioning strategy named Checkered paneling, which reduces the input size of the ILP model, making this approach scalable. The Checkered paneling strategy enables the execution of multiple ILP models in parallel, providing a speedup for large circuits. Additionally, we propose a GCell cluster-based approach to legalize the solution with minimum disturbance and displacement. We evaluated our technique for the ISPD 2018 and ISPD 2019 Contests circuits within a physical synthesis flow composed of state-of-the-art place and route academic tools. The results after the detailed routing show that ILPGRC can reduce, on average, the number of VIAs by 4.69% with less than 1% impact on wirelength. Additionally, ILPGRC reduces the number of DRVs in most cases with no open nets left.

Traditionally, the placement and routing stages of a physical design are performed separately. Because of the additional complexities arising in advanced technology nodes, they have become more interdependent. Therefore, creating efficient cooperation between the routing and placement steps has become an important topic in Electronic Design Automation (EDA). In this article, a framework that allows cooperation between routing and placement is proposed. The main objective of the proposed framework is to improve the detailed routing solution by combining routing and placement. The core of this framework is the Cooperation between Routing and Placement (CRP2.0) 1 engine including techniques to combine routing and placement. The key contributions of CRP2.0 include an Integer Linear Programming (ILP)-based Detailed Placement (ILP-DP), net classification, and two Cost and Net Caching techniques. The efficacy of the proposed framework is evaluated on the official ACM/IEEE International Symposium on Physical Design (ISPD) 2018 and 2019 contest benchmarks. In this article, we show that by using the Cost Caching technique, the global routing runtime compared with state-of-the-art algorithms was reduced by 28.56%, on average. Moreover, numerical results show that when working with advanced technology nodes, the proposed framework can improve the detailed routing score by an average of 0.3% while only moving 0.7% of the cells, on average. The proposed engine can be employed as an add-on to the physical design flow between the global routing and detailed routing steps.

Placement and Routing (P&R) are two main steps of the physical design flow implementation. Traditionally, because of their complexity, these two steps are performed separately. But the implementation of the physical design in advanced technology nodes shows that the performance of these two steps is tied to each other. Therefore, creating efficient co-operation between the routing and placement steps has become a hot topic in Electronic Design Automation (EDA). In this work, to achieve an efficient collaboration between the routing and placement engines, an iterative replacement and rerouting framework facilitated with an Integer Linear Programming (ILP)-based legalizer is proposed and tested on the ACM/IEEE International Symposium on Physical Design (ISPD) 2018 contest's benchmarks. Numerical results show that the proposed framework can improve detailed routing vias and wirelength by 2.06% and 0.14% on average in a reasonable runtime without adding new Design Rule Violations (DRVs). The proposed framework can be considered as an add-on to the physical design flow between global routing and detailed routing.

Technology advancements have enabled us to manufacture integrated circuits composed of a sheer number of gates onto a single chip. However, these enhancements have also introduced new challenges. In physical synthesis, the placement and routing steps have to satisfy even more complex design rules while optimizing the solution quality. However, the search for wirelength optimization may lead the placement engine to produce an infeasible routing solution, making it necessary to repeat previous steps and increase the overall project cost. Traditionally, placement algorithms estimate routability using pin density because of its low computational cost. Nonetheless, in advanced technology nodes, this has become inefficient due to more restrictive manufacturing constraints and complex standard cell layouts. Although many placement techniques propose to address routability, the problem is that these models rely on specific heuristics or designer experience. Therefore, we propose a machine learning-based framework for addressing routability during the placement step.

Machine learning (ML) models have been used to improve the quality of different physical design steps, such as timing analysis, clock tree synthesis, and routing. However, so far very few works have addressed the problem of algorithm selection during physical design, which can drastically reduce the computational effort of some steps. This work proposes a legalization algorithm selection framework using deep convolutional neural networks (CNNs). To extract features, we used snapshots of circuit placements and used transfer learning to train the models using pretrained weights of the Squeezenet architecture. By doing so, we can greatly reduce the training time and required data even though the pretrained weights come from a different problem. We performed extensive experimental analysis of ML models, providing details on how we chose the parameters of our model, such as CNN architecture, learning rate, and number of epochs. We evaluated the proposed framework by training a model to select between different legalization algorithms according to cell displacement and wirelength variation. The trained models achieved an average$F$-score of 0.98 when predicting cell displacement and 0.83 when predicting wirelength variation. When integrated into the physical design flow, the cell displacement model achieved the best results on 15 out of 16 designs, while the wirelength variation model achieved that for 10 out of 16 designs, being better than any individual legalization algorithm. Finally, using the proposed ML model for algorithm selection resulted in a speedup of up to$10\times $compared to running all the algorithms separately.

Machine learning has been used to improve the predictability of different physical design problems, such as timing, clock tree synthesis and routing, but not for legalization. Predicting the outcome of legalization can be helpful to guide incremental placement and circuit partitioning, speeding up those algorithms. In this work we extract histograms of features and snapshots of the circuit from several regions in a way that the model can be trained independently from region size. Then, we evaluate how traditional and convolutional deep learning models use this set of features to predict the quality of a legalization algorithm without having to executing it. When evaluating the models with holdout cross validation, the best model achieves an accuracy of 80% and an F-score of at least 0.7. Finally, we used the best model to prune partitions with large displacement in a circuit partitioning strategy. Experimental results in circuits (with up to millions of cells) showed that the pruning strategy improved the maximum displacement of the legalized solution by 5% to 94%. In addition, using the machine learning model avoided from 22% to 99% of the calls to the legalization algorithm, which speeds up the pruning process by up to 3x.

Similarly to game engines, physical design tools must handle huge amounts of data. Although the game industry has been employing modern software development concepts such as data-oriented design, most physical design tools still relies on object-oriented design. Differently from object-oriented design, data-oriented design focuses on how data is organized in memory and can be used to solve typical object-oriented design problems. However, its adoption is not trivial because most software developers are used to think about objects' relationships rather than data organization. The entity-component design pattern can be used as an efficient alternative. It consists in decomposing a problem into a set of entities and their components (properties). This paper discusses the main data-oriented design concepts, how they improve software quality and how they can be used in the context of physical design problems. In order to evaluate this programming model, we implemented an entity-component system using the open-source library Ophidian. Experimental results for two physical design tasks show that data-oriented design is much faster than object-oriented design for problems with good data locality, while been only sightly slower for other kinds of problems.