This paper addresses the challenges associated with standard cell synthesis for Nanosheet FET technology, particularly the constraints on M2 layer usage and the need to consider M0 and M1 layers in block-level routing. We propose a flexible synthesis flow that can dynamically switch between single-row and multi-row cell structures. To improve pin accessibility, we introduce a method for dynamic pin allocation on M0 and M1 layers, along with techniques to limit M0 pin length and mitigate vertical pin access conflicts. Experimental results demonstrate that, under 70% core utilization, our cell library achieves an average 3.2% reduction in chip area, an average 97.6% reduction in design rule violations, and an average 16.5% decrease in wirelength compared to NS3K. Under the same chip area, our cell library achieves 97.5% reduction in design rule violations and 15.1% decrease in total wirelength.

With increasingly complex design rules and pin density in advanced technology nodes, achieving a violation-free layout has become more challenging, also making rip-up and reroute (RUR) the most runtime-intensive component of detailed routing. We propose a novel reinforcement learning (RL)based approach to enhance the window-based RUR process. Our method features a dynamic window generation strategy that adjusts window size and position based on the distribution of design rule violations (DRV), enabling efficient targeting of congested areas. By leveraging the predictive capabilities of RL, our approach aims to minimize DRVs and achieve high-quality routing results. Experimental results demonstrate that our method outperforms the state-of-theart detailed routers, TritonRoute, achieving a DRV-free solution, averagely improving wirelength by 0.07%, via count by 2.42%, and consuming almost the same average runtime.

As technology nodes continue to shrink, Complementary FET (CFET) structures, which stack PMOS and NMOS together, have emerged as a promising candidate for next-generation technology. Due to the reduction in routing tracks, the insertion of dummy polys to increase routing resources and the use of M2 during the synthesis of CFET standard cells have become more inevitable. These two factors make block-level routing significantly more challenging. To address this, we introduce the methods to utilize the backside (BS) routing resources at the CFET standard cell synthesis stage and efficiently handle CFET transistor folding. To the best of our knowledge, this is the first work to consider BS routing resources at the cell synthesis stage and efficiently address transistor folding in the CFET stacked structure. In the transistor folding and placement stages, we utilize Euler paths to estimate the lower bound of contacted poly pitch (CPP) and apply dynamic programming (DP) to calculate the frontside minimum required tracks (FMRT) of BS-resource-aware placements. The subsequent satisfiability modulo theories (SMT) approach determines which tracks the devices occupy and completes cell routing. Experimental results show that compared to previous work [11], we achieve reductions of 1%, 45%, and 19% in #CPP, #M2 tracks, and runtime, respectively.

With the advent of CFET technology, which stacks P and N transistors together, the number of available tracks in a cell decreases. This poses a substantial challenge of hard-to-access pins during upper-level routing, which has been addressed in previous works by lengthening IO pins and increasing the spacing between adjacent IO pins. However, upper-level routing may generate DRC violations around IO pins in a cell, which compromises these efforts to improve pin accessibility. To overcome this challenge, we propose a scalable satisfiability modulo theories-based cell routing that establishes a DRC-aware scheme to enumerate potential DRC violations, enabling pin accessibility to be improved without producing DRC violations in upper-level routing. Our experimental results demonstrate that the proposed CFET cell generator is 100 times faster than previous work on average while delivering the same or better cell quality in terms of cell area. The scalability of the proposed method allows for the synthesis of large cells, including high-driving-strength cells and multi-bit flip flop (MBFF). Moreover, compared to previous work, the proposed method reduces DRC violations by an average of 99% in upper-level routing, and reduces both wire length and via usage effectively as well.

This paper presents a novel reinforcement-learning-trained router for building a multi-layer obstacle-avoiding rectilinear Steiner minimum tree (OARSMT). The router is trained by our proposed combinatorial Monte-Carlo tree search to select a proper set of Steiner points for OARSMT with only one inference. By using a Hanan-grid graph as the input and a 3D U-Net as the network architecture, the router can handle layouts with any dimensions and any routing costs between grids. The experiments on both random cases and public benchmarks demonstrate that our router can significantly outperform previous algorithmic routers and other RL routers using Alpha-Go-like or PPO-based training.

In recent years, the accessibility of pins has become a focal point for cell design and synthesis research. In this study, we propose a novel approach to improve routability in upper-level routing by eliminating one M1 track during cell synthesis. This creates space for accommodating upper-level routing, leading to improved routability. We achieve consolidated routability of transistor placement by integrating fast track assignment with dynamic programming-based transistor placement. Additionally, we introduce a hybrid routing algorithm that identifies an optimal cell routing territory for each net. This optimal territory facilitates subsequent Steiner Minimum Tree (SMT) solutions for mixed-integer linear programming (MILP) and constrains the routing region of MILP, resulting in accelerated execution. The proposed MILP approach enables concurrent routing planning and pin metal allocation, effectively resolving the chicken-or-egg causality dilemma. Experimental results demonstrate that, when using the routing-friendly synthesized cell library, the routing quality in various designs surpasses that achieved with a handcrafted cell library in ASAP7 PDK. This improvement is evident in metrics such as wirelength, number of vias, and design rule check (DRC) violations.

This paper presents a router, which tackles a classic algorithm problem in EDA, obstacle-avoiding rectilinear Steiner minimum tree (OARSMT), with the help of an agent trained by our proposed policy-based reinforcement-learning (RL) framework. The job of the policy agent is to select an optimal set of Steiner points that can lead to an optimal OARSMT based on a given layout. Our RL framework can iteratively upgrade the policy agent by applying Monte-Carlo tree search to explore and evaluate various choices of Steiner points on various unseen layouts. As a result, our policy agent can be viewed as a self-designed OARSMT algorithm that can iteratively evolves by itself. The initial version of the agent is a sequential one, which selects one Steiner point at a time. Based on the sequential agent, a concurrent agent can then be derived to predict all required Steiner points with only one model inference. The overall training time can be further reduced by applying geometrically symmetric samples for training. The experimental results on single-layer 15x15 and 30x30 layouts demonstrate that our trained concurrent agent can outperform a state-of-the-art OARSMT router on both wire length and runtime.

In this paper, we will first have a brief review of the ISPD 2018 and 2019 Initial Detailed Routing Contests. We will then visit a few important and interesting topics in VLSI routing that includes GPU accelerated routing, signal speed optimization in routing, PCB routing and AI-driven analog routing.

For the 7-nm technology node, cell placement with a drain-to-drain abutment (DDA) requires additional filler cells, increasing the placement area. This is the first work to fully automatically synthesize a DDA-aware cell library with the optimized number of drains on cell boundary based on ASAP 7-nm PDK. We propose a DDA-aware dynamic programming-based transistor placement. Previous works ignore the use of the M0 layer in cell routing. We first propose an ILP-based M0 routing planning. With M0 routing, the congestion of M1 routing can be reduced and the pin accessibility (PA) can be improved due to the diminished use of M2 routing. We also present a quadratic-programming based-coupling-capacitance-aware initial routing to optimize cell delay, cell area, and M2 usage. To improve the routing resource utilization, we propose an implicitly adjustable grid map, making the maze routing able to explore more routing solutions. The experimental results show that block placement using the DDA-aware cell library requires fewer filler cells than that using the traditional cell library by 25.1%, which achieves a block area reduction rate of 0.97%.

Trends in high pin density and an increasing number of routing layers complicate printed circuit board (PCB) routing, which is categorized as escape and area routing. Traditional escape routing research has focused on escape routing but has not considered the quality of area routing among chip components at the same time. In this work, we propose a complete PCB routing methodology, including simultaneous escape routing (SER), post-SER refinement, and gridless area routing. The SER completes the layer assignment of all nets and produces an escape order ensuring suitable escape and area routing on each layer. Length-matching constraints and differential pair routing are satisfied in each stage of the routing flow. The experiment results indicate that the proposed PCB routing method can complete routings for seven commercial PCB designs, whereas the commercial PCB tool cannot complete any of them.

This paper describes the latest release of the DATC Robust Design Flow (RDF), RDF-2021, which has several key additions to expand its horizons. The Chisel/FIRRTL compiler is now part of DATC RDF, enabling support of recent hardware generator designs written in Chisel. Logic locking through RTL obfuscation, an updated ABC synthesis flow, and DFT support are other notable updates to the RDF. A Bookshelf-LEF/DEF converter powered by OpenDB is also added into DATC RDF's inventory as an enabler of robust benchmark conversion. We also describe efforts toward open metrics standards and datasets for machine learning (ML) applications and smart tuning of the design flow, as well as expansion of public analysis calibration data. Our paper closes with future research directions related to DATC's efforts.

Fast and reliable communication plays a major role in the success of smart shopping applications. In a “Just Walk Out” shopping scenario, a video camera is installed on the cart to monitor shopping activities and transmit images to the cloud for processing so that items in the cart can be tracked and checked out. This paper proposes a prototype of a smart shopping cart based on image-based action recognition. Firstly, deep learning networks such as Faster R-CNN, YOLOv2, and YOLOv2-Tiny are utilized to analyze the content of each video frame. Frames are classified into three classes: No Hand, Empty Hand, and Holding Items. The classification accuracy based on Faster R-CNN, YOLOv2, or YOLOv2-Tiny is between 93.0% and 90.3%, and the processing speed of the three networks can be up to 5 fps, 39 fps, and 50 fps, respectively. Secondly, based on the sequence of frame classes, the timeline is divided into No Hand intervals, Empty Hand intervals, and Holding Items intervals. The accuracy of action recognition is 96%, and the time error is 0.119s on average. Finally, we categorize the events into four cases: No Change, placing, Removing, and Swapping. Even including the correctness of the item recognition, the accuracy of shopping event detection is 97.9%, which is higher than the minimal requirement to deploy such a system in a smart shopping environment. A demo of the system and a link to download the data set used in the paper are in Smart Shopping Cart Prototype or found at this URL: https://hackmd.io/abEiC83rQoqxz7zpL4Kh2w.

We describe the RDF-2020 release of the IEEE CEDA DATC Robust Design Flow (RDF). RDF-2020 extends the previous four years of DATC efforts to (i) preserve and integrate leading research codes, including from past academic contests, and (ii) provide a foundation and backplane for academic research in the RTL-to-GDS IC implementation arena. Implementation and analysis flows have been enhanced by the addition of steps including multi-bit flip-flop clustering, parasitic extraction and antenna checking, as well as a recent contest-winning global router. RDF-2020 also opens a new "Calibrations" direction to support academic research on key analyses such as extraction and timing. An open-source physical design database with Tcl/Python/C++ APIs, a flow integration into a single scriptable application, and support for the newly-opened SKY130 manufacturable PDK, are also new this year. Our paper closes with a discussion of potential future directions for the RDF effort.

Cell layout synthesis is a critical stage in modern digital IC design. In previous automatic synthesis solutions, algorithms always consider only cell area and routability. This is the first work to propose a method of delay-aware transistor placement for cell library synthesis at the sign-off level. We consider the delay and area of a cell in the transistor placement stage. Our methodology consists of three major steps. First, a search tree finds the candidate placement list that has the smallest area in a large search space. Then, a neural network filters out the unroutable candidates. Finally, a comparative convolutional neural network model, trained by sign-off level data, sorts the delays during the early placement stage. The experimental results show that the proposed CNN-based routable classifier can achieve up to 98% accuracy, and the proposed CNN-based delay ranker also can achieve up to 94.6% accuracy. The work obtains a 1.77% average sequential component delay improvement over the traditional cell synthesis method. Our method also has a 0.97% better delay performance than the human-level design.

Multi-row cell structure has become popular for modern designs, especially for the multi-bit flip-flop (MBFF) cells, but has not been under full investigation in previous cell library synthesis researches. In this work, we propose an entire placement and routing flow for synthesizing multi-row cell layouts. The proposed new A*-based multi-row transistor placement algorithm can optimize the intra-row and inter-row connections. We also present the first MAX-SAT based detailed router to optimize the cross-row connections that also conform to primitive design rules, but not only to obtain a legal routing result in previous SAT-based detailed router. Experimental results show that the quality of synthesized cells is similar to that of a state-of-the-art cell library in [6], and better aspect ratios of multi-row cells also offer more flexible capability in assembling block designs under some aspect ratio constraints as compared to single-row cell library.

Self-checkout systems enable retailers to reduce costs and customers to process their purchases quickly without waiting in queues. However, existing self-checkout systems suffer from design problems as they require large hardware consisting of a camera, sensors, RFID and other IoT technologies which increases the cost of such systems. Therefore, we propose a smart shopping cart with self-checkout, called iCart, to improve customer's experience at retail stores by enabling just walk out checkout and overcome the aforementioned problems. iCart is based on mobile cloud computing and deep learning cloud services. In iCart, a checkout event video is captured and sent to the cloud server for classification and segmentation where an item is identified and added to the shopping list. The Linux based cloud server contained the yolov2 deep learning network. iCart is a lightweight system of low cost solution which is suitable for the small-scale retail stores. The system is evaluated using real-world checkout video, and the accuracy of the shopping event detection and item recognition is about 97%. iCart demo can be found at URL: http://nol.cs.nctu.edu.tw/iCart/index.html.

For 7nm technology node, cell placement with drain-to-drain abutment (DDA) requires additional filler cells, increasing placement area. This is the first work to fully automatically synthesize a DDA-aware cell library with optimized number of drains on cell boundary based on ASAP 7nm PDK. We propose a DDA-aware dynamic programming based transistor placement. Previous works ignore the use of M0 layer in cell routing. We firstly propose an ILP-based M0 routing planning. With M0 routing, the congestion of M1 routing can be reduced and the pin accessibility can be improved due to the diminished use of M2 routing. To improve the routing resource utilization, we propose an implicitly adjustable grid map, making the maze routing able to explore more routing solutions. Experimental results show that block placement using the DDA-aware cell library requires less filler cells than that using traditional cell library by 70.9%, which achieves a block area reduction rate of 5.7%.

We describe a new RDF-2019 release of the IEEE CEDA DATC Robust Design Flow (RDF). RDF-2019 enhances the DATC RDF to span the entire RTL-to-GDS IC implementation flow, from logic synthesis to detailed routing. The new release represents a significant revision of the previously-reported RDF-2018 flow. Noteworthy vertical extensions include addition of logic synthesis starting from pure behavioral RTL Verilog RTL; floorplanning that includes initial DEF creation, I/O placement and PDN layout generation; and clock tree synthesis between placement legalization and global routing. A number of horizontal extensions to RDF are achieved by incorporating additional tool options at the static timing analysis, global placement, gate sizing, and detailed routing stages of the flow. Further, for the first time, multiple open-source realizations of the entire RDF tool chain are available. Last, RDF-2019 provides significantly enhanced support of and interoperability with industry-standard tools and design formats (LEF/DEF, SPEF, Liberty, SDC, etc.). We illustrate the configuration and use of RDF-2019, with example results on open as well as commercial design enablements.

Satisfying timing requirements is the most challenging phase of the modern complex system-on-chip (SOC) design. The timing closure of the static timing analysis (STA) is a necessary but time-consuming stage before tapeout. Physical design tools are normally ineffective in obtaining accurate timing estimates, so the accurate timing calculation must be conducted in the signoff level timer after each physical modification on designs. This paper proposes a way to reduce the number of iterations between the signoff timer and the physical implementation procedures. Approximate timing models for extracting the signoff timer information and the nonlinear library are used in the optimization of the timing-driven placement (TDP). The accurate estimation of net and cell delays is integrated into TDP, so the optimal positions of cell movement can be obtained. This post optimization algorithm was entered into the benchmark of the ICCAD15 incremental timing-driven contest, and the embodiments were obtained from the top three teams. Under the same design constraints, the proposed method yielded significant improvements in all kinds of default design chip.

As the VLSI technology scales down, 193nm optical lithography reaches the limit and one-dimensional (1D) unidirectional style lithography technique emerges as one of the most promising solutions for coming advanced technology nodes. The 1D process first generates unidirectional dense metal lines and then use line-end cutting to form the target patterns with cut masks. If cuts are too close, they will lead to conflicts. Line-end spacing rules become dynamic rather than static because of cut mask and also now need to be followed strictly. Line-end spacing check between two line-end pairs in the same mask has also been regarded as compulsory line-end spacing constraints that have not discussed in previous works yet. Complying with these rules during APR has become a new bottleneck. In this work, we propose to make the router aware of the dynamic line-end spacing rules, including end-end spacing and parity spacing constraints. Experimental results of our proposed router demonstrates that it can effectively expel all end-end spacing violations as well as 75% of parity spacing violations in a reasonable runtime increase of 14%.

In this paper, we present DATC Robust Design Flow (RDF) from logic synthesis to detailed routing. We further include detailed placement and detailed routing tools based on recent EDA research contests. We also demonstrate RDF in a scalable cloud infrastructure. Design methodology and cross-stage optimization research can be conducted via RDF.

Owing to existing intellectual properties, prerouted nets, and power/ground wires, the routing of a system on chip design demands to detour around multilayer obstacles. Traditional approaches for the multilayer obstacle-avoiding rectilinear Steiner tree (ML-OARST) problem are thus nonmaze routing-based approaches for runtime issues, yet they cannot be directly applied to deal with additional constraints such as variant edge weights on a routing layer. In this article, we propose the maze routing-based methodology with bounded exploration and path-assessed retracing to reduce runtime and routing cost for the constrained ML-OARST construction problem. The exploration of maze routing is bounded to reduce the runtime; the costs of connecting pins are computed to select Steiner points in the retracing phase. To further reduce the routing cost, we develop a Steiner point-based ripping-up and rebuilding scheme for altering tree topology. Experimental results on industrial and randomly generated benchmarks demonstrate that the proposed methodology can provide a solution with good quality in terms of routing cost and has a significant speedup compared to traditional maze routing. A commercial tool is also used to show the effectiveness of the proposed methodology.

The benefits of applying maze routing algorithm over non-maze routing based methods include the feasibility of imposing various additional constraints on routing graphs. However, the much higher complexity of a multi-layer routing graph than that of a single-layer routing graph significantly increases the required runtime of conducting maze routing to solve the multi-layer obstacle-avoiding rectilinear Steiner tree (ML-OARST) problem, making applying maze routing to this problem infeasible. In this paper, we present a maze routing-based algorithm with the proposed Steiner point pre-selection to guide the construction of a ML-OARST. This can achieve a favorable balance between quality and runtime. The quality of routing is determined by total cost, that is, the summation of wire-length and via cost. To improve the flexibility of routing tree generation, we also propose a rip-up and re-building strategy for altering Steiner points and tree topology. Compared with a multi-layer multi-terminal maze routing algorithm, our algorithm can reduce the total cost by 4.8% on average and achieve 45x runtime speed-up averagely; moreover, our algorithm outperforms the state-of-the-art ML-OARST method using computational geometry techniques in terms of wire-length. With additional costs on routing graph, the proposed maze routing-based method can be further enhanced to solve VLSI routing constraints, such as layer-specific costs, scenic control, and layer directive.

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.

Once vehicles start to be driven automatically, people expect the driving routing is automatically and optimally selected. Supposing all the vehicles are navigated by a single system in the future, the navigation system will be able to provide instructions to each vehicle based on the evaluated near-future traffic information while the current navigation system frequently updates the routing based on current traffic information. This paper proposes a navigation method that guides vehicles based on the evaluated near-future traffic information. Experimental results with actual city maps show the evaluated near-future traffic information is helpful to mitigate traffic jam and reduce driving time.

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.

As design-for-manufacturability techniques have become widely used to improve the yield of nano-scale semiconductor technology in recent years, hotspot detection methods have been investigated with a view to calibrating layout patterns that tend to reduce yield. In this paper, we propose two graph models, i.e., skeleton graph and space graph, to formulate polygon topology and spatial relationship among polygons. In addition, a Prüfer encoding-based method is presented to encode each skeleton graph. Single polygon matching problem is then equivalent to the verification of graph isomorphism, which is realized by checking the identity of two enhanced Prüfer codes associated with two skeleton graphs. A branch and bound-based pattern anchoring algorithm is presented to resolve the vertex ordering problem for isomorphism checking. The general exact pattern matching problem can then be accomplished by adopting the space graph to identify the similarity of spatial relationship among polygons. Vias are one of the most device components that attract much attention in monitoring manufacturing variation due to via alignment issue, but hotspot detection rarely takes vias into consideration. Multilayer hotspot detection can also be realized by extending the skeleton graph to maintain the relations between adjacent layers through vias. Experimental results show that we can achieve 5.6 × runtime speedup than design-rule-based methodology in average for single layer hotspot detection while the runtime for multilayer hotspot is roughly equal to the summation of that for individual single layer hotspot detection.

Placement consists of three stages: global placement, legalization, and detailed placement (DP). Recently, most research works have concentrated on improving global placement and legalization, but innovations in DP have been rarely seen. ICCAD13 held a DP contest that formulates the emerging placement issues into a bin-utilization metric and maximum cell displacement constraint. This paper presents a detailed placer that can effectively reduce both half-perimeter wirelength and the peak bin-utilization under the displacement constraint. The proposed lazy-update based incremental density profit function supports efficient cell swapping. Combination of lazy-update density profit function and Density-Driven Swap lets our placer achieve AOFP of 0 for the majority of the ICCAD13 test cases. The placer presented produces the best placement results among the top3 teams in the ICCAD13 contest.

The comparison of temperatures (temperature correlation) obtained by measuring instruments and by thermal simulation is commonly necessary. Currently the way in which thermal maps are obtained by infrared thermographer yields inaccurate results since the emissivity values of all elements in an IC are ignored and measurement method assumes a constant emissivity. Without the correct settings of emissivity in infrared thermographer, the temperature variation could reach up to as high as 300 %. Coating black paint on the IC surface is a widely used method to assume the IC with constant emissivity and simplify the measurement procedures. Coating a uniform black thin film on an IC is a highly skillful technique and the coated black paint is un-removable. In certain cases, it is not convenient or possible to do so - for example, as monitoring a working chip. This article proposes the first practical and feasible method for emissivity map measurement. Two reference plates are utilized to obtain an emissivity map, from which real emissivity value of each pixel of the infrared thermographer is obtained. Firstly the radiances of IC and two reference plates are measured by the infrared thermographer. After that, the emissivity map of the IC can be calculated by the radiances. According to the experimental results herein, the uncertainty in the emissivity measured using this method is very low, of the order of 0.01, consistent with the minimum resolution of all currently available infrared thermographic instruments. With the emissivity map, the high accuracy temperature map is then obtained. The comparison of the temperature maps simulated by the extend version of Noxim (Access Noxim) as well as measured by the thermographer with constant emissivity and with the accurate emissivity map are presented in this article. This work contributes to the field of thermal analysis and simulation. Accurate circuit characteristics can be obtained through accurate thermal map; on the other hand, the closeness between the thermal simulation result and the real thermal map can also be realized.

Traditional solutions to antenna effect, such as jumper insertion and diode insertion performed at post-route stage may produce extra vias and degrade circuit performance. Previous work suggests combining layer assignment, jumper insertion, and diode insertion together to achieve a better design quality with less additional cost. Based on our observations on global and local antenna violations, this paper proposes an antenna-safe single-net layer assignment (AS-SLA), which first enumerates all antenna-safe layer assignment solutions of a net, and then extracts the minimum-cost one for the net. AS-SLA can minimize via count and separators as well. In addition, an antenna avoidance layer assignment flow (AALA) adopting AS-SLA as its kernel not only avoids global antenna violations, but also eliminates local antenna violations. Experimental results reveal that, in 16 benchmarks, AALA can yield ten antenna-violation-free assignments, while the algorithms of other works yield no antenna-violation-free assignment. However, AALA performs about seven times slower than other antenna-aware layer assignment algorithm. Accordingly, two acceleration techniques are proposed to reduce the runtime of AALA by 57.6%.

Routability has become a critical issue in VLSI design flow. To avoid producing an unroutable design, many placers [4-7] invoke global routers to get a congestion map and then move cells to reduce congestion based on this map. However, as cells move, the accuracy of the congestion map degrades, thereby affecting the effectiveness of the placer in minimizing congestions. Moreover, most global routers [8-13] ignore local congestion. If placers are guided by these routers, it may produce hard-to-route placement solutions in terms of detailed routing. This work develops a routability optimizer, called Ropt, to reduce both global and local routing congestion levels of a given placement. Based on a local-routability-aware routing model, Ropt builds a global routing instance to obtain global and local congestion information for guiding global re-placement. In addition, this work presents a new legalization scheme to preserve the global routing instance after legalization. Finally, local detailed placement further minimizes the local congestion and wirelength. For the evaluation of Ropt, we use an academic global router and a commercial router to obtain both global and detailed routing results, respectively. Experimental results reveal that Ropt can improve the routing quality (in terms of congestion, wirelength, and violation) and routing runtime of a given placement solution.

To address the routability issue, routing congestion estimators (RCE) become essential in industrial design flow. Recently, several RCEs [1-4] based on global routing engines are developed, but they typically ignore the effects of routing on timing so that the identified routing paths may be overlong and thus impractical. To be aware of the timing issues, our proposed global-routing-based RCE obeys the layer directive and scenic constraints to respectively limit the routing layers and the maximum routing wirelength of the potentially timing-critical nets. To handle the scenic constrains, we propose a novel method based on a relaxation-legalization scheme. Also, because the work in [5] reveals that congestion ratio is a better indicator than overflow to evaluate routability, this work focuses on minimizing the congestion ratio rather than overflows. As will be shown, the problem of minimizing congestion ratio is more complicated than minimizing overflows, so we develop a new rip-up and rerouting scheme to reduce congestion and further to approach a target congestion ratio. Moreover, to fit the demands of practical uses, this work presents a control utility to trade off runtime and quality, which is an essential function to an industrial RCE tool. Experiments reveal that the proposed RCE is faster and more accurate than another industrial global-routing-based RCE.

Routability is a critical issue in VLSI design flow. To address this issue, the routability-driven placement contests [1, 2] held at ISPD11 and DAC12 promote the development of routability-driven placers such as those in [4-6]. ISPD11 and DAC12 contests adopt metrics that are based on global routing solutions to evaluate the routability of placement solutions. However, such global-routing-based metrics typically ignore local congestion, and they cannot evaluate the actual routability effectively. In this work, we develop a translator that allows us to feed the placement solutions of mPL [3], NTUplace [4], Ripple [5], and SimPLR [6] into a commercial router for detailed routing. We then analyze the detailed routing result of each placement solution to better understand the issues that may cause routing violations. Moreover, we examine the suitability of using the ISPD11 and DAC12 metrics in predicting routability. Our findings indicated that the metrics might not reliably predict actual routability, in terms of the number of (detailed) routing violations.

Modern global routers employ various routing methods to improve routing speed and quality. Maze routing is the most time-consuming process for existing global routing algorithms. This paper presents two bounded-length maze routing (BLMR) algorithms (optimal-BLMR and heuristic-BLMR) that perform much faster routing than traditional maze routing algorithms. In addition, a rectilinear Steiner minimum tree aware routing scheme is proposed to guide heuristic-BLMR and monotonic routing to build a routing tree with shorter wirelength. This paper also proposes a parallel multithreaded collision-aware global router based on a previous sequential global router (SGR). Unlike the partitioning-based strategy, the proposed parallel router uses a task-based concurrency strategy. Finally, a 3-D wirelength optimization technique is proposed to further refine the 3-D routing results. Experimental results reveal that the proposed SGR uses less wirelength and runs faster than most of other state-of-the-art global routers with a different set of parameters , , , . Compared to the proposed SGR, the proposed parallel router yields almost the same routing quality with average 2.71 and 3.12-fold speedup on overflow-free and hard-to-route cases, respectively, when running on a 4-core system.

Conventional buffer insertion in timing ECO involves only minimizing the arrival time of the most critical sink in one multi-pin net and neglects the obstacles and the topology of routed wire segments, which may worsen the arrival times of other sinks and burden subsequent timing ECO. This work develops a topology-aware ECO timing optimization (TOPO) flow that comprises three phases - buffering pair scoring, edge breaking and buffer connection, and topology restructuring. TOPO effectively improves the arrival times of violation sinks without worsening those of other sinks. Experimental results indicate that TOPO improves the worst negative slack (WNS) and total negative slack (TNS) of benchmarks by an average of 79.2% and 84.3%, respectively. The proposed algorithm improves the arrival time that is achieved using conventional two-pin net-based buffer insertion by an average of 40.4%, at the cost of consuming 19× runtime. To speed up routing and further improve sink slack, a highly scalable massively parallel maze routing on Graphics Processing Unit (GPU) platform is also developed to enable the proposed flow to explore more solution candidates. High scalability and parallelism are realized by block partitioning and staggering. Experiments reveal that the proposed GPU-based parallel maze routing can achieve near 12× runtime speedup for two-pin routings. With parallelized maze routing, WNS violations in four out of five cases can be resolved.

Contests and their benchmarks have become an important driving force to push our EDA domain forward in different areas lately, such as ISPD, TAU, DAC contests. To encourage better research development on timely and practical EDA problems across all domains, a new international CAD Contest is held this year under the joint sponsorship of the IEEE CEDA and Ministry of Education (MOE) of Taiwan. Three contest problems on functional ECO, placement, and litho hotspot identification are announced this year and run by industry experts from Cadence, IBM and Mentor Graphics.

TPL-friendly detailed routers require a systematic approach to detect TPL conflicts. However, the complexity of conflict graph (CG) impedes directly detecting TPL conflicts in CG. This work proposes a token graph-embedded conflict graph (TECG) to facilitate the TPL conflict detection while maintaining high coloring-flexibility. We then develop a TPL aware detailed router (TRIAD) by applying TECG to a gridless router with the TPL stitch generation. Compared to a greedy coloring approach, experimental results indicate that TRIAD generates no conflicts and few stitches with shorter wirelength at the cost of 2.41x of runtime.

Considering routability issue in the early stages of VLSI design flow can avoid generating an unroutable design. Several recent routablity-driven placers [8--11] adopt a built-in global router to estimate routing congestion. While the routability of the placement solution improves, the performance of these placers degrades. Many of these built-in global router and state-of-the-art academic global routers use maze routing to seek a detoured path. Although very effective, maze routing is relatively slower than other routing algorithms, such as pattern routing and monotonic routing algorithms. This work presents two efficient routing algorithms, called unilateral monotonic routing and hybrid unilateral monotonic routing, to replace maze routing and to realize a highly fast maze-free global router that is suited to act as a built-in routing congestion estimator for placers. Experimental results indicate that RCE achieves similar routing quality when compared with [20], as well as an over 20-fold runtime speedup in large benchmarks.

Traditional solutions to antenna effect, such as jumper insertion and diode insertion peformed at post-route stage may produce extra vias and degrade circuit performance. The work in [1] suggests combining layer assignment, jumper insertion and diode insertion together to achieve a better design quality with less additional cost. Based on our observations on global and local antenna violations, this work proposes a dynamic-programming based single-net layer assignment called NALAR, which first enumerates all antenna-violation-safe layer assignment solutions of a net, and then extracts the minimum-cost one for the net. NALAR can minimize via count and separators as well. In addition, an antenna avoidance layer assignment algorithm (ANLA) adopting NALAR as its kernel not only avoids global antenna violations, but also eliminates local antenna violations. Experimental results reveal that, in 11 benchmarks, ANLA can yield 5 violation-free assignments while the algorithms of other works yield no violation-free assignment. As for the total number of antenna violations in all benchmarks, this work and the works in [2], [3] and [4] yield 21, 43506, 41261 and 29671 antenna violations, respectively. However, ANLA performs about 7 times slower than other antenna-aware layer assignment [4].

The increasing complexity of interconnection designs has enhanced the importance of research into global routing when seeking high-routability (low overflow) results or rapid search paths that report wirelength estimations to a placer. This work presents two routing techniques, namely circular fixed-ordering monotonic routing and evolution-based rip-up and rerouting using a two-stage cost function in a high-performance congestion-driven 2-D global router. We also propose two efficient via-minimization methods, namely congestion relaxation by layer shifting and rip-up and reassignment, for a dynamic programming-based layer assignment. Experimental results demonstrate that our router achieves performance similar to the first two winning routers in ISPD 2008 Routing Contest in terms of both routability and wirelength at a 1.05 × and 18.47 × faster routing speed. Moreover, the proposed layer assignment achieves fewer vias and shorter wirelength than congestion-constrained layer assignment (COLA).

Layer assignment determines on which layer the wires or vias should be placed; and the assignment results influence the circuit's delay, crosstalk, and via counts. How to minimize via count and via overflow during layer assignment has received considerable attention in recent years. Traditional layer assignment to minimize via count tends to produce varying qualities of assignment results using different net orderings. This work develops a negotiation-based via count minimization algorithm (NVM) that can achieve lower via counts than in previous works, and experimental results indicate that net assignment ordering only slightly influences the quality of NVM's results. As for via overflow minimization, we observe via overflow can be well minimized if via overflow minimization is performed following stacked via minimization. The stacked via minimization adopts the proposed NVM, while via overflow minimization adopts a modified NVM by replacing via cost with via overflow cost. Experimental results reveal that the proposed NVM yields a lower additional via cost than and by 10.8%, 2.5%, respectively, in the via count minimization problem. As for via overflow minimization, the proposed two-stage algorithm improves via overflow by 11.5% and lowers the via cost by 6.5% than the one-stage algorithm.

The printed image of a layout that satisfies the double patterning lithograph (DPL) constraints may not have good fidelity if the layout neglects optical proximity correction (OPC). Simultaneously considering DPL and OPC becomes necessary when gene rating layouts, especially in routing stage. Moreover, one decomposed design with balanced mask density has a lower edge placement error (EPE)than an unbalance done[6]. This work proposes a compre-hensive conflict graph (CCG)to enable detailed routers to simultaneously consider DPL, OPC, and mask density to gene rate litho-friendly layouts. This work then develops an DPL-aware and OPC-friendly gridless detailed routing (DOPPLER) by applying CCG in a gridless routing model. A density variation threshold annealing-based routing flow is also proposed to prevent DOPPLER from falling into a sub-optimal mask density balance. Compared with existing DPL-aware detailed routing works, DOPPLER demon-stratesanaverage 73.84% of EPE hotspot reduction with a satisfactory mask density at the cost of an average increase of 0.08% wire-length, 15.14% number of stitches, and 77.28% runtime.

Multiple dynamic supply voltage (MDSV) provides an effective way to reduce dynamic power and is widely used in high-end or low-power designs. The challenge of routing MDSV designs is that the net in MDSV designs needs to be planned carefully to avoid electrical problems or functional failure as a long interconnect path pass through the shutdown power domains. As the first work to address the MDSV global routing problem, power domain-aware routing (PDR) problem is defined and the point-to-point PDR algorithm is also presented herein with look-ahead path selection method and look-up table acceleration approach. For multi-pin net routings, a novel constant-time table-lookup mechanism by invoking four enhanced monotonic routings to fast compute the least-cost monotonic path from every node to the target sub-tree is presented to speed up the query about routing cost (including driven-length slack) to target during multi-source multi-target PDR. Experimental results confirm that the proposed MDSV-based global router can efficiently identify legally optimized routing results for MDSV designs, and can effectively reduce overflow, wire length, inserted level shifters and runtime.

For modern designs, delay optimization significantly facilitates success in design closure owing to its more realistic metric than wirelength in routing. Obstacle-avoiding rectilinear Steiner tree (OARST) construction is an essential routing problem. With the trends toward Internet protocol-block-based system-on-chip designs, OARST with buffer insertion has been surveyed to diminish the delay of long wires. Previous works on performance-driven (PD) OARST without and with buffer insertion can only handle small circuits. This paper develops a novel routing algorithm in obstacle-avoiding spanning graph to construct OARST with optimized delay efficiently. The proposed multisource single-target maze routing is first employed to identify the critical trunks, and the critical-trunk-based tree growth mechanism connects the unconnected pins to critical trunks under delay constraints of every sink. We apply the proposed critical-trunk-based tree growth mechanism to solve PD and slack-driven (SD) OARST problems. The proposed algorithms are extended to consider buffer insertion during PD and SD OARST constructions. Experimental results demonstrate that the proposed algorithms achieve an average 25.84% improvement in the maximum delay over obstacle-avoiding rectilinear Steiner minimal tree in the PD OARST problem and successfully solve 66.67% worst negative slack violations in the SD OARST problem. Compared to the simultaneous routing and buffer insertion approach, the proposed buffer-aware (BA) algorithm generates satisfactory timing results with almost identical wire length (WL). Moreover, the proposed BA SD OARST algorithm utilizes less WL than the BA rectilinear Steiner tree construction does by 17.99% on average. The runtime comparison with previous works shows the efficiency and scalability of this paper.

Track assignment, which is an intermediate stage between global routing and detailed routing, provides a good platform for promoting performance, and for imposing additional constraints during routing, such as crosstalk. Gridless track assignment (GTA) has not been addressed in public literature. This work develops a gridless routing system integrating a congestion-driven global router, crosstalk-driven GTA and an enhanced implicit connection-graph-based router. Initial assignment is produced rapidly with a left-edge like algorithm. Crosstalk reduction on the assignment is then transformed to a restricted nonslicing floorplanning problem, and a deterministic O-Tree based algorithm is employed to reassign each net segment. Finally, each panel is partitioned into several subpanels, and the subpanels are reordered using branch and bound algorithm to decrease the crosstalk further. Before detailed routing, routing tree construction is undertaken for placed IRoutes and other pins; many original point-to-point routings are set to connect to IRoutes, and can be accomplished simply with pattern routing. For detailed routing, this work proposes a rapid extraction method for pseudomaximum stripped tiles to boost path propagation. Experimental results demonstrate that the proposed gridless routing system has over 2.02 times the runtime speedup in average for fixed- and variable-rule routings of an implicit connection-graph-based router, NEMO. As compared with a commercial routing tool, this work yields an average reduction rate of 13.8% in coupling capacitance calculated using its built-in coupling capacitance estimator.

While via failure significantly contributes to yield loss during manufacturing, post-routing redundant via insertion method is the conventional means of reducing the via failure rate, but only alive vias can be protected. As existing dead vias still lower manufacturing yield, identifying a routing result with fewer dead vias can increase the redundant via insertion rate, subsequently enhancing the yield of chips. This work presents, for the first time, a redundant-via-aware routing system to retain redundant via resources in track assignment, in which redundant vias are inserted in detailed routing. The proposed via prediction scheme performs trial route using L-shaped patterns to estimate via positions. Meanwhile, the proposed redundant-via-aware detailed router gradually relaxes the limitation on the number of generated dead vias during path searching to minimize the number of dead vias. Experimental results indicate that the proposed redundant-via-aware routing system is, to our knowledge, the first routing system that can achieve 100% redundant via insertion rate with all MCNC benchmark circuits.

Given the extensive study of clock skew minimization, in the ISPD 2009 Clock Network Synthesis (CNS) Contest, clock latency range (CLR) was initially minimized across multiple supply voltages under capacitance and slew constraints. CLR approximates the summation of the clock skew and the maximum source-to-sink delay variation for multiple supply voltages. This work develops an efficient three-stage clock tree synthesis flow for CLR minimization. Firstly, a balanced clock tree with small skew is generated. Secondly, buffer insertion and wire sizing minimizes delay variation without violating the slew constraint. Finally, skew is minimized by inserting snaking wires. Experimental results reveal that the proposed flow can complete all ISPD'09 benchmark circuits and yield less CLR than the top three winners of ISPD'09 CNS contest by 59%, 52.7% and 35.4% respectively. Besides, the proposed flow can also run 5.52, 1.86, and 7.54 times faster than the top three winners of ISPD'09 CNS contest respectively.

Double patterning lithography (DPL) is the most feasible solution for sub-32nm nodes owing to the recurrent delay in next generation lithography. DPL attempts to decompose a single layer of one layout into two masks in order to increase pitch size and improve depth of focus (DOF). Considering DPL at detailed routing stage can improve the flexibility of layout decomposition as compared to the post-routing layout decomposition. The conflict graph proposed in [8] provides a global view of all nets in a layout to obtain a highly decomposable layout with less yield loss. However, adopting conflict graph in routing process using grid-based model or gridless model both brings huge overhead. This work presents an innovative conflict graph (ICG) to realize adopting conflict graph in a routing process. Three routing-friendly characteristics of ICG are constant-time conflict cycle detection, lazy ICG update, and light-weight routing overhead. To efficiently utilize routing resources for a crowded region, gridless models provide a better solution space than grid-based models do. This work also develops, to our knowledge, the first DPL-aware gridless detailed routing with ICG to generate a highly decomposable routing result. Moreover, greedily assigning colors for routed nets may cause unnecessary stitches or even a coloring conflict. This work presents a deferred coloring assignment-based routing flow to escape local optimum of a greedy coloring approach. Experimental results indicate that DPL-aware routing results contain no coloring conflicts, and the stitches produced by the proposed router are less than those produced by a greedy coloring approach by 41% on average with only 0.22% and 30% increment in wirelength and runtime, respectively.

Modern global routers use various routing methods to improve routing speed and the quality. Maze routing is the most time-consuming process for existing global routing algorithms. This paper presents two bounded-length maze routing (BLMR) algorithms (optimal-BLMR and heuristic-BLMR) to perform much faster routing than traditional maze routing algorithms. The proposed sequential global router, which adopts a heuristic-BLMR, identifies less-wirelength routing results with less runtime than state-of-the-art global routers. This study also proposes a parallel multi-threaded collision-aware global router based on a previous sequential global router. Unlike the conventional partition-based concurrency strategy, the proposed algorithm uses a task-based concurrency strategy. Experimental results reveal that the proposed sequential global router uses less wirelength and runs about 1.9X to 18.67X faster than other state-of-the-art global routers. Compared to the proposed sequential global router, the proposed parallel global router yields almost the same routing quality with average 2.71 and 3.12-fold speedup on overflow-free and hard-to-route benchmarks, respectively, when running on an Intel quad-core system.

The increasing complexity of interconnection designs has enhanced the importance of research into global routing when seeking high-routability (low overflow) results or rapid search paths that report wire-length estimations to a placer. This work presents two routing techniques, namely adaptive pseudorandom net-ordering routing and evolution-based rip-up and reroute using a two-stage cost function in a high-performance congestion-driven 2-D global router. We also propose two efficient via-minimization methods, namely congestion relaxation by layer shifting and rip-up and re-assignment, for a dynamic programming-based layer assignment. Experimental results demonstrate that our router achieves performance similar to the first two winning routers in ISPD 2008 Routing Contest in terms of both routability and wire length at a 1.42X and 25.84X faster routing speed. Besides, our layer assignment yields 3.5% to 5.6% fewer vias, 2.2% to 3.3% shorter wirelength and 13% to 27% less runtime than COLA.

Placement profoundly impacts physical design owing to its role in determining the lower bound of a circuit wirelength, as well as the circuit routability. To close the gap between placement and routing, this study integrates global routing and placement to improve the wirelength estimation accuracy of placement. Two methods, called wirelength-reduced cell shifting and cell rearrangement by bipartite matching, are applied to minimize wirelength. Cell sorting based congestion reduction and pattern-prerouting based congestion-avoided cell shifting are proposed to reduce congestion. Experimental results demonstrate that the proposed placer improves total routed wirelength by 2% to ROOSTER on IBMv2 benchmarks. Moreover, the proposed GRPlacer resolves the original congested regions of the placements generated by ROOSTER. Compare with the detailed placer in ROOSTER, our work can reduce more routed wire length and remove more overflows.

Traditional layout migration focuses on area minimization, thus suffered wire distortion, which caused loss of layout topology. A migrated layout inheriting original topology owns original design intention and predictable property, such as wire length which determines the path delay importantly. This work presents a new rectangular topological layout to preserve layout topology and combine its flexibility of handling wires with traditional scan-line based compaction algorithm for area minimization. The proposed migration flow contains devices and wires extraction, topological layout construction, unidirectional compression combining scan-line algorithm with collinear equation solver, and wire restoration. Experimental results show that cell topology is well preserved, and a several times runtime speedup is achieved as compared with recent migration research based on ILP (integer linear programming) formulation.

Obstacle-avoiding rectilinear Steiner tree (OARST) construction is a fundamental problem associated with the trend toward IP-block-based System-on-Chip designs. The objective of previous studies on obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) has been to minimize the total wirelength of the constructed Steiner tree. Studies of performance-driven Steiner trees have demonstrated that the minimization of wirelength may worsen the performance of the Steiner tree. This work is the first to construct OARST while considering the Elmore delay. A critical-trunk-based tree growth mechanism is proposed. The critical trunks are constructed by extended single-source single-target maze routing called multi-source single-target maze routing. The unconnected pins are connected to critical trunks under the delay constraints of every sink. The proposed critical trunk can be applied to solve performance-driven and slack-driven OARST problems. Experimental results demonstrate that the proposed algorithms achieve an average 24.12% improvement in the maximum delay over OARSMT in performance-driven OARST problem and successfully solve 66.67% worst negative slack (WNS) violations in slack-driven OARST problem while running faster than previous OARSMT algorithms.

Track assignment, which is an intermediate stage between global routing and detailed routing, provides a good platform for promoting performance, and for imposing additional constraints during routing, such as crosstalk. Gridless track assignment (GTA) has not been addressed in public literature. This work develops a gridless routing system integrating a congestion-driven global router, crosstalk-driven GTA and an enhanced implicit connection graph-based router. Initial assignment is produced rapidly with a left-edge like algorithm. Crosstalk reduction on the assignment is then transformed to a restricted non-slicing floorplanning problem, and a deterministic O-tree based algorithm is employed to re-assign each net segment. Finally, each panel is partitioned into several sub-panels, and the sub-panels are reordered using branch and bound algorithm to decrease the crosstalk further. Before detailed routing, routing tree construction is undertook for placed IRoutes and other pins; many original point-to-point routings are set to connect to IRoutes, and can be accomplished simply with pattern routing. For detailed routing, this work proposes a rapid extraction method for pseudo-maximum stripped tiles to boost path propagation. Experimental results demonstrate that the proposed gridless routing system has over 2.66 times the runtime speedup for fixed- and variable-rule routings of an implicit connection-graph-based router, NEMO. As compared with a commercial routing tool, this work yields an average reduction rate of 15% in coupling capacitance calculated using its built-in coupling capacitance estimator

The implicit-connection-graph-based router is superior to the tile-based router in terms of routing graph construction and point querying. However, the implicit connection graph has a higher degree of routing graph complexity. In this paper, a new multilayer implicit-connection-graph-based gridless router called NEMO is developed. Unlike the first implicit-connection-graph-based router that embeds all routing layers onto a routing plane, NEMO constructs a routing plane for each routing layer. Additionally, each routing plane comprises tiles, not an array of grid points with their connecting edges, and consequently, the complexity of the routing problem decreases. Each grid point then represents exactly one tile or its left-bottom corner such that a tile query is equivalent to any point query inside the queried tile, and a grid maze becomes tile propagation. Furthermore, to accelerate path search, continuous space tiles are combined as a pseudo maximum horizontally or vertically stripped tile. Experimental results reveal that NEMO conducts a point-to-point path search around ten times faster than the implicit-connection-graph-based router. General-purpose routing by NEMO also improves routing performance by approximately 1.69times-55.82 times, as compared to previously published works based on a set of commonly used MCNC benchmark circuits

Engineering change order (ECO) routing is frequently requested in the later design stage for the purpose of delay and noise optimization. ECO routing is complicated as a result of huge existing obstacles and the requests for various design rules. The tile-based routing model results in fewer nodes of the routing graph than grid and connection-based routers; however, the number of nodes of the tile-based routing graph has grown to over a billion for system-on-chip designs, while no notable progress has been achieved in the routing speed of the tile-based router since it was proposed. This paper first proposes a novel routing graph reduction (RGR) method for promoting tile propagation speed and then depicts a new ECO routing design flow with RGR and enhanced global routing flow (EGRF). RGR can be used to remove redundant tiles as well as align and merge neighboring tiles in order to diminish tile fragmentation such that the tile-based ECO router can run twice as fast while still producing an optimal path. Compared with a commercial placement and routing tool, the proposed tile-based router with RGR obtains better routing performance and routing quality for three ECO routings. EGRF incorporates ECO global routing considering via-resource congestion metric with extended routing and global cell (GCell) restructuring to prevent routing failure in routable designs. The ECO router with the proposed design flow can perform up to 20 times faster than the original tile-based router at the cost of only a slight decline in routing quality. Experimental results also demonstrate that a more congested layout tends to have higher graph reduction rate. Also discussed herein are further refinements by dynamic weighting of via and wire resources based on the vacancy density of the routed design and further application of RGR to multiple-net routing

Engineering Change Order (ECO) routing is frequently requested in the later design stage for the purpose of delay and noise optimization. ECO routing is complicated by huge existing obstacles and the requests for various design rules. Tile-based routers have work with fewer nodes of the routing graph than grid and connection-based routers; however, the number of nodes of the tile-based routing graph has grown to over a thousand millions for SOC designs. This work depicts a new ECO routing design flow with routing graph reduction and enhanced global routing flow. Routing graph reduction reduces the complexity of nodes by removing redundant tiles and aligning neighboring tiles to merge adjacent block tiles. Routing graph reduction reduces tile fragmentation such that the ECO router can run twice as fast without sacrificing routing quality. Enhanced global routing flow incorporates ECO global routing with extended routing and GCell restructuring to prevent routing failure in a routable routing. The ECO router with new design flow can perform up to 20 times faster than the original tile-based router, at the cost of only a very small decline in routing quality.

We present a unilateral 2D cellular automata (CA) model and pipelining technique to parallelize logic and fault simulation. We show that given an acyclic digraph describing the Boolean function of a combinational circuit at the gate level, whose nodes are the logic gates of the circuit and whose directed edges stand for the propagating directions of signals, we can map this digraph onto a 2D CA to simulate the signal propagation of the circuit on the CA. This mapping preserves not only the electrical connectivity of the circuit but also the massive parallelism inherited from the CA. Experimental results on ISCAS-85 benchmark circuits are obtained. Compared with previous fault simulation results, the time required for simulating one test pattern on an average is shorter by three to four orders of magnitude. As to pure logic simulation, our CA performs up to 9.24 billion gate evaluations per second using a 20 MHz clock and 8-b words. Scalability and extension to sequential circuits are discussed.>