The design automation research community has driven the evolution of integrated circuits from a handful of transistors in the 1960s to billions today. The International Symposium on Physical Design (ISPD) has been instrumental in tackling challenges like scaling complexities, hardware security, and the exponential growth in transistor counts. This study conducts a comprehensive bibliometric analysis of ISPD publications using Natural Language Processing, machine learning, and network analysis. It explores research themes, collaboration dynamics, and global contributions through citation networks, co-authorship graphs, geographical and spatial mapping, and topic modeling. Key areas of focus include Physical Design Optimization, Power Efficiency, and Emerging Technologies, with prominent topics such as placement, routing, clock skew, lithography, machine learning, and hardware security. The analysis highlights the evolution of foundational techniques like placement and routing while identifying emerging trends such as AI-driven design automation. These insights provide a roadmap for sustaining innovation in physical design over the next 25 years.

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.

Physical designers typically employ heuristics to solve challenging problems in global routing. However, these heuristic solutions are not adaptable to the ever-changing fabrication demands, and the experience and creativity of designers can limit their effectiveness. Reinforcement learning (RL) is an effective method to tackle sequential optimization problems due to its ability to adapt and learn through trial and error. Hence, RL can create policies that can handle complex tasks. This work presents an RL framework for global routing that incorporates a self-learning model called RL-Ripper. The primary function of RL-Ripper is to identify the best nets that need to be ripped and rerouted in order to decrease the number of total short violations. In this work, we show that the proposed RL-Ripper framework’s approach can reduce the number of short violations for ISPD 2018 benchmarks when compared to the state-of-the-art global router CUGR. Moreover, RL-Ripper reduced the total number of short violations after the first iteration of detailed routing over the baseline while being on par with the wirelength, VIA, and runtime. The proposed framework’s major impact is providing a novel learning-based approach to global routing that can be replicated for newer technologies.

Physical designers have been using heuristics to solve challenging problems in routing. However, these heuristic solutions are not adaptable to the ever-changing fabrication demands and their effectiveness is limited by the experience and creativity of the designer. Reinforcement learning is an effective method to tackle sequential optimization problems due to its ability to adapt and learn through trial and error, creating policies that can handle complex tasks. This study presents an RL framework for global routing that incorporates a self-learning model called RL-Ripper. The primary function of RL-Ripper is to identify the best nets to rip to decrease the number of total short violations. In this work, the final global routing results are evaluated against CUGR, a state-of-the-art global router, using the ISPD 2018 benchmarks. The proposed RL-Ripper framework's approach can reduce the short violations compared to CUGR. Moreover, the RL-Ripper reduced the total number of short violations after the first iteration of detailed routing over the baseline while being on par with the wirelength, VIA, and runtime. The major impact of the proposed framework is to provide a novel learning-based approach to global routing that can be replicated for newer technologies.

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.

This is a research work-in progress paper. The hidden curriculum is the invisible norms, ideals, and values in engineering education that are not part of the formal curriculum. At the University of Calgary, a first-year program in mental wellbeing aims to counteract some of the hidden curriculum narratives by providing students with humanizing support and reflections throughout their curriculum. As part of this, the program delivered a module on hidden curriculum, where students were required to answer three reflective open-ended questions. This paper provides a preliminary qualitative content analysis of the student responses to a specific question: what are some of these hidden lessons taught about engineering? The results found three main themes: engineering is difficult, engineering requires teamwork and collaboration, and engineering should be independent. These early results provide a unique insight into the student perspective on the hidden curriculum of engineering.

This Research Full Paper presents the implementation of a hybrid Project-Based Learning (PBL) model in a Software Engineering (SE) course to balance the focus on teaching fundamental knowledge and fostering of applied software development skills through a real-world project, accompanied by contextualized learning and Just-In-Time (JIT) teaching to develop students' scalable knowledge of how to intelligently design with respect to SE best practices. The data is collected from 2 semesters spanning over 2019 and 2020. Based on quantitative and qualitative analysis, this study examines the effectiveness of using the hybrid PBL approach in conveying to students the importance of SE best practices such as the SOLID principles which are deemed as timeless. Results support the claim that JIT lectures help students better evaluate their design decisions and ensure they're on the right track for following optimal design patterns and best practices, and that contextualized learning may be used to develop a notion of why design decisions matter outside of the classroom. Although incorporating these pedagogies in hybrid PBL allows for students' conviction of the significance of SE best practices in academic projects, there still exists room to better convey their significance in industry.

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.

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.

Placement is an important and challenging step in VLSI physical design. The placement solution can significantly impact timing and routability. In sub-nanometric technology nodes, several restrictions have been imposed on the placement solutions. These restrictions make designing an optimized and legal solution very hard. Achieving optimized placement solutions is especially challenging in regions with high-density utilization. The quality of placement solution can significantly impact the final circuit implementation. In this work, we present a cell spreading algorithm to move cells out from high-density utilization regions. Our algorithm opens up new spaces in regions with high cell concentration. These spaces can then be exploited by detailed placement algorithms to further optimize the placement solution. The objective of our technique is to reduce area density utilization while considering cell displacement and circuit delay. The outcome of the proposed algorithm is to obtain a uniform distribution of cells in the placement area while having minimal effects on the delay. To achieve this goal, our proposed algorithm uses branch and cut, and network flow techniques. Experimental results on industrial and academic circuits illustrate that our proposed algorithm can minimize circuit delay (up to 25%), cell displacement (up to 17μ m ), dynamic power consumption (up to 5.3%), and leakage power (up to 15%).

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.

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.

Within technical engineering courses, students may struggle with difficult concepts, overwhelming workloads, loss of motivation and a lack of classroom engagement. Studies have shown that students who are engaged and creative in their education have improved learning outcomes in technical understanding and application. This work proposes the use of gamification for the development of both creative and technical understanding. Gamification is the application of game mechanics and typical elements of game playing (e.g. point scoring, competition with others, rules of play, etc.) to technical education as a method of encouraging student engagement with course material in a compelling and familiar way. This paper describes the development and implementation of a creative design project within an electronic design automation course, as well as a further teaching and learning research evaluation by general public focus groups.

The Exploring Electrical Engineering program will electrify your understanding of engineering! Developed as part of a larger K-6 engineering education research initiative, this workshop paper details two activities for exploring electrical and computer engineering concepts for grade 3-5 students through the use of cross-disciplinary concepts in physical education and movement. Activity 1: Going with the Flow uses human electrons and circuit components to demonstrate electron behaviour in parallel and series circuits. Activity 2: Programming Puzzles introduces code design through life-size maze creation and completion. These creative activities have been tested as part of on-going research work in several classrooms, with over 350 elementary school students participating, and have resulted in an increased interest in electrical engineering as a future career.

Recently, there have been a slew of design automation contests and released benchmarks. ISPD place & route contests, DAC placement contests, timing analysis contests at TAU and CAD contests at ICCAD are good examples in the past and more of new contests are planned in the upcoming conferences. These are interesting and important events that stimulate the research of the target problems and advance the cutting edge technologies. Nevertheless, most contests focus only on the point tool problems instead of addressing the design flow or co-optimization among design tools. OpenDesign Flow Database platform is developed to direct attentions to the overall design flow from logic synthesis to physical design optimization [1]. The goals are to provide an academic reference design flow based on past CAD contest results, the database for design benchmarks and point tool libraries, and standard design input/output formats to build a customized design flow by composing point tool libraries.

In this paper, an augmented crossover memory polynomial model (A-COMPM) is proposed and developed which can be used for characterizing and linearizing multiple-input multiple-output (MIMO) transmitters in the presence of linear and nonlinear crosstalk. The proposed model significantly improves the performance of the crossover memory polynomial model (CO-MPM) by more accurately incorporating the effect of crosstalk. The proposed model performs comparably to the 2 x 2 parallel Hammerstein (2 x 2 PH) model, while requiring the same number of coefficients as CO-MPM and a lower number of coefficients than the 2 x 2 PH. The model was tested for forward modeling and digital predistortion (DPD) applications in the presence of both linear and nonlinear crosstalk. Experimental results show that the model outperforms the CO-MPM and 2 x 2 PH DPDs, at a lower number of coefficients compared to both models. Furthermore, the issue of numerical stability of the DPD

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.

In this paper, we present and analyze four efficient models that produce significantly improved results by optimizing conflicting power and skew objectives in the clock network buffer sizing problem. Each model is in geometric programming format and has certain advantages, such as maximum reduction in power, robustness to process variation, and striking a balance between skew and power optimization. The buffer sizing problem is formulated as a geometric programming problem to provide globally optimal solutions to the four models. We also show that a geometric programming multiobjective model can be used to optimize both power and skew without requiring any tuning from a designer. The presented self-tuning multiobjective formulation not only provides optimal solutions for buffer sizes, but also finds the tuning parameters that result in overall combined reduction in power and skew without loss of convexity. The effectiveness of the models are illustrated on several publicly available benchmarks. The models provide on average 40% to 60% improvement in power while reducing skew in several cases. We have also proposed a smart heuristic for discretization of the continuous geometric programming solution that preserves skew and power. Finally, we provide a guideline for designers to decide which one of the proposed models is the most appropriate for their needs.

Most engineering problems involve optimizing different and competing objectives. To solve multi-objective problems, normally a weighted sum of the objectives is optimized. However, how the weights are assigned can greatly affect the outcome. Therefore, many designers have to resort to producing the Pareto surface - a time-consuming procedure. In this paper, we propose a framework for solving multi-objective geometric programming problems where weights in the objective are optimally calculated during the optimization problem without having to produce the Pareto surface. It is shown that the proposed self-tuning multi-objective framework can be applied to geometric programming gate sizing problems. Then, the efficacy of the proposed framework is proven using the clock network buffer sizing problem as an application. The problem is first formulated as a geometric programming (GP) problem with the objectives of reducing power, skew, and slew. The problem is solved using ISPD09 circuits. The power, skew and slew of the optimized networks are calculated using ngspice. The results show on average 52% reduction in power and 28% reduction in skew compared to the original networks. The self-tuning multi-objective solution is shown superior to any single objective solution with no impact on runtime.

Minimizing power and skew for clock networks are critical and difficult tasks which can be greatly affected by buffer sizing. However, buffer sizing is a non-linear problem and most existing algorithms are heuristics that fail to obtain a global minimum. In addition, existing buffer sizing solutions do not usually consider manufacturing variations. Any design made without considering variation can fail to meet design constraints after manufacturing. In this paper, first we proposed an efficient optimization scheme based on geometric programming (GP) for buffer sizing of clock networks. Then, we extended the GP formulation to consider process variations in the buffer sizes using robust optimization (RO). The resultant variation-aware network is examined with SPICE and shown to be superior in terms of robustness to variations while decreasing area, power and average skew.

We have newly introduced the expert designer/user session (EDS) to ISPD in 2013, which is tailor-made for designers and users of physical design (PD) tools. Since ISPD is the premium PD-centric symposium, it is a great opportunity for designers, tools developers and PD researchers to interact and learn from each other. The benefit of including EDS in ISPD's program is twofold.

We describe an efficient, top-down strategy for overlap removal and floorplan repair which repairs overlaps in floorplans produced by placement algorithms or rough floorplanning methodologies. The algorithmic framework that we propose incorporates a novel geometric shifting technique within a top-down flow. The effect of our algorithm is quantified across a broad range of floorplans produced by multiple tools. Our method succeeds in producing valid placements in almost all cases; moreover, compared to leading methods, it requires only one fifth the run-time and produces placements with 4 to 13% less HPWL and up to 43% less cell movement.

In this paper, two effective preprocessing techniques for clustering large-scale circuits are presented. These techniques can be performed before the general multilevel clustering to enhance the speed of the partitioning technique while preserving the solution quality. A "wrapped" version of hMETIS is implemented, in which the proposed techniques are applied as the preprocessing step. The empirical results on standard benchmark circuits show that the application of the proposed techniques improves the over all runtime by 30% and the partitioning results by 2%.

Placement is a crucial step for the VLSI circuit physical design and it has a deep impact on the overall circuit performance. Numerous clustering techniques have been proposed and applied to placement to deal with the increasing circuit sizes and complexity. In this paper, an effective clustering algorithm for mixed-size placement is presented. This technique uses local cell connectivity information to identify all potential clusters, but finalizes clusters globally. The effectiveness of the proposed clustering technique is verified by empirical tests on ICCAD04 and ISPD05 benchmark circuits. Specifically, 4 major academic placers, including Capo10.1, FengShui5.1, mPL6 and NTUPlace3-LE, are tested by using the proposed clustering technique as a preprocessing step. The overall experimental results show that for ICCAD04 benchmarks, the proposed clustering technique consistently improves all of the placers' performance by 2% to 5% on average in term of the pin-to-pin half perimeter wire length, with comparable or lower runtime. For ISPD05 benchmarks, the proposed clustering technique shows promising results.

The complexity and size of digital circuits have grown exponentially, and today's circuits can contain millions of logic elements. Clustering algorithms have become popular due to their ability to reduce circuit sizes, so that the circuit layout can be performed faster and with higher quality. This paper presents a deterministic net-reduction-based clustering algorithm called Net Cluster. The basic idea of the proposed technique is to put the emphasis on reducing the number of nets versus the number of cells, thereby capturing the natural clusters of a circuit. The proposed algorithm has proven a linear-time complexity of O(p), where p is the number of pins in a circuit. To demonstrate the effectiveness of the proposed clustering technique, it has been applied to multilevel partitioning and wire length-driven placement. The numerical experiments on the ISPD98 benchmark suite for partitioning and the ICCAD 2004 benchmark suite for placement demonstrate that by applying Net Cluster as a preprocessing step, the performance of state-of-the-art multilevel partitioners and placers can be further improved

The complexity and size of digital circuits has grown exponentially and today's circuits can contain millions of logic elements. Clustering algorithms have become popular due to their ability to reduce the circuit sizes so that circuit layout can be performed faster and with higher quality. This paper presents a deterministic, net-reduction based clustering algorithm, called Net Cluster. The basic idea of the proposed technique is to put the emphasis of clustering on reducing the number of nets versus the number of cells. The proposed algorithm has proven linear time complexity of O(p), where p is the number of pins in a circuit. To demonstrate the effectiveness of the proposed clustering technique, it has been applied to multilevel partitioning process. The numerical experiments on ISPD98 benchmark suite demonstrate that by applying Net Cluster, the performance of state-of-the-art multilevel partitioners can be further improved.

Modern integrated circuit design involves the layout of circuits consisting of millions of switching elements or transistors. Due to the sheer complexity of the problem, optimizing the connectivity between transistors is very difficult. The circuit interconnection is the single most important factor in performance criteria such as signal delay, power dissipation, circuit size, and cost. These factors dictate that interconnections, i.e., wires, be made as short as possible. The wire-minimization problem is generally formulated as a sequence of discrete optimization subproblems that are known to be NP-hard. Hence, they can only be solved approximately using meta-heuristics. These methods are computationally expensive and the quality of the solution depends to a great extent on an appropriate choice of starting configuration and modeling techniques. In this paper, new modeling techniques are used to solve the routing problem formulated as an integer programming problem. The main contribution of this paper is a proposed global routing heuristic that combines the wire length, channel congestion, and number of pins in routes to find the best wiring layout of a circuit. By adding information such as channel congestion and the number of pins in each route as well as the wire length, the quality of the solution is improved. In addition, the solutions of the large relaxed linear programming problems are skewed towards a zero-one solution, resulting in faster convergence. The developed LP models in this paper are useful when solving the global routing problem for two reasons; first, the new interior-point algorithms to solve the LP problem are polynomial in time. Second, “near optimal wiring” is obtained in polynomial time without performing randomized rounding.