With the development of semiconductor technology nodes, the sizes of standard cells become smaller and the number of standard cells is dramatically increased to bring into more functionality in integrated circuits (ICs). However, the shrinking of standard cell sizes causes many problems of ICs such as timing, power, and electromigration (EM). To tackle these problems, a new style structural pre-route (SPR) is proposed. Such type of pre-route is composed of redundant parallel metals and vias so that the low resistance and the redundant sub-structures can improve timing and yield. But the large area overhead becomes the major problem of inserting such pre-routes all over a design. In this paper, we propose a machine learning-based approach to predict the insertability of SPRs for placed designs. In addition, we apply a pattern visualization method by using a guided backpropagation technique to see in depth of our model and identify the problematic layout features causing SPR insertion failures. The experimental results not only show the excellent performance of our model, but also show that avoiding generating the identified critical features during legalization can improve SPR insertability compared to a commercial SPR-aware placement tool.

Power management, which can be effectively realized by dynamically turning on/off power domains, is a key concern for modern mobile devices. Leakage power in multiple power domain design is usually dominated by nets passing through different power domains because prior work allocates always-on buffers for these feedthrough nets. Unlike prior work, which uses always-on buffers, we create specific power islands with normal buffers in this paper; these power islands gather buffers on feedthrough nets together to share the power and area overhead. The buffer allocation is performed by a wave-propagation based algorithm, named GasStation. Compared with the conventional always-on buffer approach, experimental results show that GasStation can reduce 75% buffer area, 34% buffer count, 80% leakage power, and 8% wirelength on feedthrough nets in eight industrial smart phone designs.

Double patterning technology (DPT) and layout migration (LM) are two closely related problems on design for manufacturability in the nanometer era. DPT decomposes a layout into two masks and applies double exposure patterning to increase pitch size and, thus, printability. In this paper, we present the first algorithm in the literature for the simultaneous layout migration and decomposition (SMD) problem. Our algorithm first constructs a potential conflict graph and DPT-aware constraint graphs, and then applies integer linear programming (ILP) corresponding to the graphs to obtain a decomposed and migrated layout. We further present an effective graph-based reduction technique to prune the ILP solution space, which maintains the same DPT conflicts. We also present a new DPT-aware objective for the SMD problem to minimize the difference between the original and migrated layouts while considering the DPT effects. In addition, we present an approach to generate DPT-aware standard cells by considering the DPT effects on the cell boundaries; this technique improves the layout printability and facilitates electronic design automation tools to consider DPT. Experimental results show that our algorithms can effectively generate conflict-free migrated layouts with 11% smaller layout areas and 21% smaller layout changes, compared with the traditional method of layout decomposition followed by LM. In particular, our reduction technique reduces the ILP variables by 45.7%, the ILP constraints by 58.5%, and the DPT edges by 79.9% over the basic ILP formulation, leading to a substantial speedup. For example, it can reduce the runtimes for the test cases from more than one day to only seconds.

Double patterning technology (DPT) has recently gained much attention and is viewed as the most promising solution for the sub-32-nm node process. DPT decomposes a layout into two masks and applies double exposure patterning to increase the pitch size and thus printability. This paper proposes the first mask-sharing methodology for DPT, which can share masks among different designs, to reduce the number of costly masks for double patterning. The design methodology consists of two tasks: template-mask design and template-mask-aware routing. A graph matching-based algorithm is developed to design a flexible template mask that tries to accommodate as many design patterns as possible. We also present a template-mask-aware routing (TMR) algorithm, focusing on DPT-related issues to generate routing solutions that satisfy the constraints induced from double patterning and template masks. Experimental results show that our designed template mask is mask-saving, and our TMR can achieve conflict-free routing with 100% routability and save at least two masks for each circuit with reasonable wirelength and runtime overheads.

Global routing for modern large-scale circuit designs has attracted much attention in the recent literature. Most of the state-of-the-art academic global routers just work on a simplified routing congestion model that ignores the essential via capacity for routing through multiple metal layers. Such a simplified model would easily cause fatal routability problems in subsequent detailed routing. To remedy this deficiency, a more effective congestion metric that considers both the in-tile nets and the residual via capacity for global routing is presented. Experimental results show that our global router can achieve very high-quality routing solutions with more reasonable via usage.

Global routing is an important step for physical design. In this paper, we develop a new global router, NTUgr, that contains three major steps: prerouting, initial routing, and enhanced iterative negotiation-based rip-up/rerouting (INR). The prerouting employs a two-stage technique of congestion-hotspot historical cost pre-increment followed by small bounding-box area routing. The initial routing is based on efficient iterative monotonic routing. For traditional INR, it has evolved as the main stream for the state-of-the-art global routers, which reveals its great ability to reduce the congestion and overflow. As pointed out by recent works, however, traditional INR may get stuck at local optima as the number of iterations increases. To remedy this deficiency, we replace INR by enhanced iterative forbidden-region rip-up/rerouting (IFR) which features three new techniques of (1) multiple forbidden regions expansion, (2) critical subnet rerouting selection, and (3) look-ahead historical cost increment. Experimental results show that NTUgr achieves high-quality results for the ISPD'07 and ISPD'08 benchmarks for both overflow and runtime.

Double patterning technology (DPT) and layout migration are two closely related problems on design for manufacturability in the nanometer era. DPT decomposes a layout into two masks and applies double exposure patterning to increase the pitch size and thus printability. In this paper, we present the first algorithm in the literature for the simultaneous layout migration and decomposition (SMD) problem. Our algorithm first constructs a conflict graph and DPT-aware constraint graphs, and then applies integer linear programming (ILP) corresponding to the graphs to obtain a decomposed and migrated layout. We further present an effective graph-based reduction technique to prune the ILP solution space, which maintains the same DPT conflicts. We also present a new DPT-aware objective for the SMD problem to minimize the difference between the original and migrated layouts while considering the DPT effects. In addition, we present an approach to generate DPT-aware standard cells by considering the DPT effects on the cell boundaries; this technique improves the layout printability and facilitates EDA tools to consider DPT. Experimental results show that our algorithms can effectively generate conflict-free migrated layouts with 14% smaller layout areas and 28% smaller layout changes, compared with the traditional method of layout decomposition followed by layout migration. In particular, our reduction technique can reduce the runtimes for the test cases from more than one day for the basic ILP formulation to only seconds. can reduce the runtimes for the test cases from more than one day to only seconds.

The flip-chip package provides a high chip-density solution to the demand for more input-output pads of very large scale integration designs. In this paper, we present the first routing algorithm in the literature for the preassignment flip-chip routing problem with a predefined netlist among pads and wire-width and signal-skew considerations. Our algorithm is based on integer linear programming (ILP) and guarantees to find an optimal solution for the addressed problem. It adopts a two-stage technique of global routing followed by detailed routing. In global routing, it first uses three reduction techniques to prune redundant solutions and create a global-routing path for each net. Without loss of the solution optimality, our reduction techniques can further prune the ILP variables (constraints) by 85.5% (98.0%) on average over a recent reduction technique. The detailed routing applies passing-point assignment, net-ordering determination, and X-based gridless routing to complete the routing. Experimental results based on five real industry designs show that our router can achieve 100% routability and the optimal global-routing wirelength, and satisfy all signal-skew constraints, under reasonable central-processing-unit times, whereas recent related work has resulted in much inferior solution quality.

Global routing for modern large-scale circuit designs has attracted much attention in the recent literature. Most of the state-of-the-art academic global routers just work on a simplified routing congestion model that ignores the essential via capacity for routing through multiple metal layers. Such a simplified model would easily cause fatal routability problems in subsequent detailed routing. To remedy this deficiency, we present in this paper a more effective congestion metric that considers both the in-tile nets and the residual via capacity for global routing. With this congestion metric, we develop a new global router that features two novel routing algorithms for congestion optimization, namely least-flexibility-first routing and multi-source multi-sink escaping-point routing. The least-flexibility-first routing processes the nets with the least flexibility first, facilitating a quick prediction of congestion hot spots for the subsequent nets. Enjoying lower time complexity than traditional maze and A*-search routing, in particular, the linear-time escaping-point routing guarantees to find the optimal solution and achieves the theoretical lower-bound time complexity. Experimental results show that our global router can achieve very high-quality routing solutions with more reasonable via usage, which can benefit and correctly guide subsequent detailed routing.

The flip-chip package provides a high chip-density solution to the demand for more I/O pads of VLSI designs. In this paper, we present the first routing algorithm in the literature for the pre-assignment flip-chip routing problem with a pre-defined netlist among pads and wire-width and signal-skew considerations. Our algorithm is based on integer linear programming (ILP) and guarantees to find an optimal solution for the addressed problem. It adopts a two-stage technique of global routing followed by detailed routing. In global routing, it first uses two reduction techniques to prune redundant solutions and create a global-routing path for each net. Without loss of the solution optimality, our reduction techniques can further prune the ILP variables (constraints) by 85.5% (98.0%) on average over a recent reduction technique. The detailed routing applies X-based grid-less routing to complete the routing. Experimental results based on five real industry designs show that our router can achieve 100% routability and the optimal global-routing wirelength and satisfy all signal-skew constraints, under reasonable CPU times, while recent related work results in much inferior solution quality.

Treatment for bone deformities secondary to malunited fractures usually require corrective osteotomies, and high incidence of surgical failure rates have been reported. Inaccurate corrections and loss of reductions are among the most common causes, and these technical errors ought to be improved. A new measuring fixator for humeral supracondylar corrective osteotomies in children was designed and used in clinical application. Two boys who had sustained cubitus varus following malunited humeral supracondylar fracture were performed using proposed measuring fixator. The results of the clinical trial show that the angle of correction was accurate, and the procedure could be carried out by the surgeon himself without additional help, with an average of 1.3 penetration of the physis per each fixating Kirschner wire (8 times in 6 K-wires). The surgical time was reduced, as well as the radiation exposure.