To better utilize space and reduce wirelength within a fixed-outline with preplaced modules, modern floorplanning is desired to be able to handle rectilinear soft modules. Nevertheless, the induced special shape constraints have not been fully explored in the literature. In this paper, we propose a novel analytical-based approach to address the challenges of fixed-outline, preplaced modules, and rectilinear soft modules. Unlike most previous work, which abstracts modules as circles during global floorplanning, we treat modules as shape-adjustable rectangles and propose a differentiable shape mechanism to capture the impact of shaping on the floorplan quality. For legalization, we first construct an overlap graph to extract the neighborhood of overlaps, modules, and whitespaces. Then, a shortest-path based algorithm effectively migrates area from overlaps through a chain of modules to whitespaces while carefully considering the shape constraints. Finally, we iteratively expand and shrink the bounding boxes of modules to further refine the wirelength by improving area utilization. Our legalization and refinement allows rectilinear shapes to form naturally. Based on the experiments conducted on the GSRC, MCNC, and CAD contest benchmark suites, our results show that our approach achieves superior wirelength and runtime to the state-of-the-art works and the contest winning team, demonstrating its effectiveness and efficiency.

Recently, successful applications of reinforcement learning to chip placement have emerged. Pretrained models are necessary to improve efficiency and effectiveness. Currently, the weights of objective metrics (e.g., wirelength, congestion, and timing) are fixed during pretraining. However, fixed-weighed models cannot generate the diversity of placements required for engineers to accommodate changing requirements as they arise. This paper proposes flexible multiple-objective reinforcement learning (MORL) to support objective functions with inference-time variable weights using just a single pretrained model. Our macro placement results show that MORL can generate the Pareto frontier of multiple objectives effectively.

To observe internal signals, physical probing is an important step in post-silicon debug. Focused ion beam (FIB) is one of most popular probing technologies. However, an unsuitable layout significantly decreases the percentage of nets which can be observed through FIB probing for advanced process technologies. This paper presents the first design-for-debug routing to increase the FIB observable rate. The proposed algorithm, which adopts three FIB states and costs to enhance the maze routing, keeps at least one FIB candidate for each net while routing. Experimental results demonstrate that the proposed method can significantly increase the FIB observable rate under 100% routability.

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. The annual CAD Contest in Taiwan has been held for 14 consecutive years and has successfully boosted the EDA research momentum in Taiwan. To encourage better research development on timely and practical EDA problems across all domains, CAD Contest is internationalized since 2012 under the joint sponsorship of the IEEE CEDA and Ministry of Education (MOE) of Taiwan. 2012 CAD Contest attracted 56 teams from 7 regions, while 2013 CAD contest attracted 87 teams from 9 regions. Continuing its great success in 2012 and 2013, 2014 CAD contest attracts 93 teams from 9 regions, including Taiwan, Mainland China, Hong Kong, India, Singapore, US, Canada, Brazil, and Russian Federation. Three contest problems on verification, placement, and mask optimization are announced this year and run by industry experts from Cadence and IBM. Topic chair Chih-Jen Hsu of Cadence Design Systems manages the first contest problem, concentrating on efficiently solving the combinational single-output netlists. The efficiency of solving a single-output function highly depends on the CNF encoding and the SAT solving. For the first problem, contestants are required to explore the best CNF encoding and SAT solver setting to solve the most tests within the shortest runtime. Topic chair Myung-Chul Kim of IBM manages the second problem, focusing on incremental timing-driven placement. Placement, which determines locations of circuit elements, is one of the most crucial steps in the modern IC design flow. For the second problem, contestants are required to perform local refinements on a legal design such that the total slack and worst slack are optimized. Topic chair Rasit O. Topaloglu of IBM manages the third problem, exploring lithography mask optimization. In a circuit layout, densities of polygons within windows of interest may have a large variation across such windows in the rest of the layout. To balance the density of polygons, fills are inserted to make the density of several windows uniform. For the third problem, contestants are required to minimize the density variation with least fills. This session will include three presentations from the contest organizers for these contest problems and an award ceremony. Each contest organizer (topic chair) will present detailed information about the corresponding contest problem, including problem description, benchmarks, and evaluation. Along with the contest, a new set of industrial benchmarks for each contest problem will be released and facilitate scientific evaluations of related research results. We expect that the benchmark suites will further play a key driving force to push the advancement of related research. Moreover, we also expect that the participants will submit their works to the subsequent top conferences to boost related research and also extend the impacts of this contest.

In modern technology, layout effects have more and more impacts on circuit performance. However, most of the existing analog automation tools consider the circuit sizing and layout generation in two separate steps, which often result in time-consuming sizing-layout iterations. In this paper, a layout-aware analog synthesis tool is presented to generate the required designs from specifications to layout through a user-friendly GUI. In order to provide a strong link between sizing and layout steps, a parasitic-aware circuit sizing flow is proposed based on a flexible layout template to prevent the performance from failing to meet the specifications after layout. Routability-aware analog placement is then performed with a simple routing algorithm to generate the corresponding layout with minimized cost. As demonstrated in the experimental results, this analog synthesis tool is able to generate the required circuits in seconds with high quality layouts and effectively guarantees the post-layout performance with less over-design.

The routing quality on RDLs in 3D ICs is affected by the micro-bump location seriously. In this paper, we propose a micro-bump assignment method using order relation to minimize the crossing problem and reduce the detours in RDLs. Experimental results show that our approach can obtain an assignment result with 100% routability and minimal wirelength in global routing.

The escape routing problem for PCB designs has been extensively studied in literature. Although industrial tools and few studies have worked on the escape routing of differentials pairs, the routing solutions are not good enough by previous methods. In this paper, we propose an escape routing approach of differential pairs considering length matching. The approach includes two stages. The first stage is to find min-cost median points which connect two pins by shortest and equal wire lengths while the second stage is adopted a network-flow approach with min-cost max-flow to simultaneously route all differential pairs. Experimental results show that our approach can efficiently and effectively obtain length-matching differential pairs with significant reduction in maximum and average differential-pair skews.

The 3D IC is an emerging technology. The primary emphasis on 3D-IC routing is the interface issues across dies. To handle the interface issue of connections, the inter-die routing, which uses micro bumps and two single-layer RDLs (Re-Distribution Layers) to achieve the connection between adjacent dies, is adopted. In this paper, we present an inter-die routing algorithm for 3D ICs with a pre-defined netlist. Our algorithm is based on integer linear programming (ILP) and adopts a two-stage technique of micro-bump assignment followed by non-regular RDL routing. First, the micro-bump assignment selects suitable micro-bumps for the pre-defined netlist such that no crossing problem exists inside the bounding boxes of each net. After the micro-bump assignment, the netlist is divided into two sub-netlists, one is for the upper RDL and the other is for the lower RDL. Second, the non-regular RDL routing determines minimum and non-crossing global paths for sub-netlists in the upper and lower RDLs individually. Experimental results show that our approach can obtain optimal wirelength and achieve 100% routability under reasonable CPU times.

Due to the subwavelength lithography, manufacturing sub-90-nm feature sizes require intensive use of resolution-enhancement techniques, among which optical proximity correction (OPC) is the most popular technique in industry. Considering the OPC effects during routing can significantly alleviate the cost of postlayout OPC operations. In this paper, we present an efficient, accurate, and economical analytical formula for intensity computation and develop the first modeling of postlayout OPC based on a quasi-inverse lithography technique. The technique provides key insights into a new direction for postlayout OPC modeling during routing. Extensive simulations with SPLAT, the golden lithography simulator in academia and industry, show that our intensity formula has high fidelity. Incorporating the OPC costs computed by the quasi-inverse lithography technique for our postlayout OPC modeling into a router, the router can be guided to maximize the effects of the correction. Compared with a rule-based OPC method, the experimental results show that our approach can achieve 15% and 16% reductions in the maximum and average layout distortions, respectively.

Due to the sub-wavelength lithography, manufacturing sub-90 nm feature sizes require intensive use of resolution-enhancement techniques, among which optical proximity correction (OPC) is the most popular technique in industry. Considering the OPC effects during routing can significantly alleviate the cost of post-layout OPC operations. In this paper, we present an efficient, accurate, and economical analytical formula for intensity computation and develop the first modeling of post-layout OPC based on a quasi-inverse lithography technique. Extensive simulations with SPLAT, the golden lithography simulator in academia and industry, show that our intensity formula has high fidelity. Incorporating the OPC costs computed by the quasi-inverse lithography technique for our post-layout OPC modeling into a router, the router can be guided to maximize the effects of the correction. Compared with a rule-based OPC method, the experimental results show that our approach can achieve 14% and 16% reductions in the maximum and average layout distortions, respectively.

As IC process geometries scale down to the nanometer territory, the industry faces severe challenges of manufacturing limitations. To guarantee yield and reliability, physical design for manufacturability and reliability has played a pivotal role in resolution and thus yield enhancement for the imperfect manufacturing process. In this paper, we introduce major challenges arising from nanometer process technology, survey key existing techniques for handling the challenges, and provide some future research directions in physical design for manufacturability and reliability.

To handle modern routing with nanometer effects, we need to consider designs with variable wire/via widths and spacings, for which gridless-routing approaches are desirable due to its great flexibility. In this paper, we introduce a gridless-routing model that can obtain design-rule-correct paths and avoid redundant wires. Besides, we propose an enhanced model for the gridless-routing model to reduce the solution space and the runtime. Based on the enhanced gridless-routing model, we present the first multilevel full-chip gridless detailed router (called MGR). The router integrates global routing, detailed routing, and congestion estimation together at each level of multilevel routing. It can handle designs with nonuniform wire/via widths and spacings and consider routability and optical-proximity correction. Experimental results show that MGR achieves the best routing solutions in smaller running times than previous works, based on a set of commonly used benchmarks (with uniform and nonuniform wire widths) and a set of real industrial benchmarks (with a versatile set of design rules)

Due to its great flexibility, gridless routing is desirable for nanometer circuit designs that use variable wire widths and spacings. Nevertheless, it is much more difficult than grid-based routing because of its larger solution space. In this paper, we present a novel "V-shaped" multilevel framework (called VMF) for full-chip gridless routing. Unlike the traditional "A-shaped" multilevel framework (inaccurately called the "Vcycle" framework in the literature), our VMF works in the V-shaped manner: top-down uncoarsening followed by bottom-up coarsening. Based on the novel framework, we develop a multilevel full-chip gridless router (called VMGR) for large-scale circuit designs. The top-down uncoarsening stage of VMGR starts from the coarsest regions and then processes down to finest ones level by level; at each level, it performs global pattern routing and detailed routing for local nets and then estimate the routing resource for the next level. Then, the bottom-up coarsening stage performs global maze routing and detailed routing to reroute failed connections and refine the solution level by level from the finest level to the coarsest one. We employ a dynamic congestion map to guide the global routing at all stages and propose a new cost function for congestion control. Experimental results show that VMGR achieves the best routability among all published gridless routers based on a set of commonly used MCNC benchmarks. Besides, VMGR can obtain significantly less wire-length, smaller critical path delay, and smaller average net delay than the previous works. In particular, VMF is general and thus can readily apply to other problems.

To handle modern routing with nanometer effects, we need to consider designs of variable wire widths and spacings, for which gridless routers are desirable due to their great flexibility. The gridless routing is much more difficult than the grid-based one because the solution space of gridless routing is significantly larger than that of grid-based one. In this paper, we present the first multilevel, full-chip gridless detailed router. The router integrates global routing, detailed routing, and congestion estimation together at each level of the multilevel routing. It can handle non-uniform wire widths and consider routability and optical proximity correction (OPC). Experimental results show that our approach obtains significantly better routing solutions than previous works. For example, for a set of 11 commonly used benchmark circuits, our approach achieves 100% routing completion for all circuits while the famous state-of-the-art three-level routing and multilevel routing (multilevel global routing + flat detailed routing) cannot complete routing for any of the circuits. Besides, experimental results show that our multilevel gridless router can handle non-uniform wire widths efficiently and effectively (still maintain 100% routing completion for all circuits). In particular, our OPC-aware multilevel gridless router archives an average reduction of 11.3% pattern features and still maintains 100% routability for the 11 benchmark circuits.

As the operating frequency increases to gigahertz and the rise time of a signal is less than or comparable to the time-of-flight delay of a wire, it is necessary to consider the transmission line behavior for delay computation. We present in this paper, an analytical formula for the delay computation under the transmission line model. Extensive simulations with SPICE show the high fidelity of the formula. Compared with previous works, our model leads to smaller average errors in delay estimation. Based on this formula, we show the property that the minimum delay for a transmission line with reflection occurs when the number of round trips is minimized (i.e., equals one). Besides, we show that the delay of a circuit path is a posynomial function in wire and buffer sizes, implying that a local optimum is equal to the global optimum. Thus, we can apply any efficient search algorithm such as the well-known gradient search procedure to compute the globally optimal solution. Experimental results show that simultaneous wire and buffer sizing is very effective for performance optimization under the transmission line model.

As the operating frequency increases to giga hertz and the rise time of a signal is less than or comparable to the time-of-flight delay of a line, it is necessary to consider the transmission line behavior for delay computation. We present an analytical formula for the delay computation under the transmission line model. Extensive simulations with SPICE show the high fidelity of the formula. Compared with previous works of Elmore (1948) and Ismaul et al. (2000), our model leads to smaller average errors in delay estimation. Based on this formula, we show the property that the minimum delay for a transmission line with reflection occurs when the number of round trips is minimized. Besides, we show that the delay of a circuit path is a posynomial function in wire and buffer sizes, implying that a local optimum is equal to the global optimum. Thus, we can apply any efficient search algorithm such as the well-known gradient search procedure to compute the globally optimal solution. Experimental results show that simultaneous wire and buffer sizing is very effective for performance optimization under the transmission line model.