Browsing by Author "Li, Yih-Lang"

Now showing 1 - 20 of 57

A Fast Maze-Free Routing Congestion Estimator With Hybrid Unilateral Monotonic Routing
(2012)
Liu, Wen-Hao
;
Li, Yih-Lang
;
Koh, Cheng-Kok
;
資訊工程學系
;
Department of Computer Science
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.
A Gridless Routing System with Nonslicing Floorplanning-Based Crosstalk Reduction on Gridless Track Assignment
(2011-03-01)
Li, Yih-Lang
;
Chang, Yu-Ning
;
Cheng, Wen-Nai
;
資訊工程學系
;
Department of Computer Science
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.
A Maze Routing-Based Algorithm for ML-OARST with Pre-Selecting and Re-Building Steiner Points
(2017-01-01)
Lin, Kuen-Wey
;
Lin, Yeh-Sheng
;
Li, Yih-Lang
;
Lin, Rung-Bin
;
資訊工程學系
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.
A Maze Routing-Based Methodology With Bounded Exploration and Path-Assessed Retracing for Constrained Multilayer Obstacle-Avoiding Rectilinear Steiner Tree Construction
(2018-07-01)
Lin, Kuen-Wey
;
Lin, Yeh-Sheng
;
Li, Yih-Lang
;
Lin, Rung-Bin
;
資訊工程學系
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.
A Novel Fast Layout Encoding Method for Exact Multilayer Pattern Matching With Prufer Encoding
(2015-01-01)
Su, Hong-Yan
;
Chen, Chieh-Chu
;
Li, Yih-Lang
;
Tu, An-Chun
;
Wu, Chuh-Jen
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 Prufer 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 Prfer codes associated with two skeleton grap. 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.6x 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.
A simulation-based hybrid optimization technique for low noise amplifier design automation
(2007)
Li, Yiming
;
Yu, Shao-Ming
;
Li, Yih-Lang
;
電信工程研究所
;
Institute of Communications Engineering
In this paper, a simulation-based optimization technique for integrated circuit (IC) design automation is presented. Based on a genetic algorithm (GA), Levenberg-Marquardt (LM) method, and circuit simulator, a window-interfaced prototype of computer-aided design (CAD) is developed for IC design. Considering low noise amplifier (LNA) IC, we simultaneously evaluate specifications including S parameters, K factor, noise figure, and input third-order intercept point in the optimization process. If the simulated results meet the aforementioned constraints, the prototype outputs the optimized parameters. Otherwise, CAD activates GA for global optimization; simultaneously, LM method searches solutions with the results of GA. The prototype then calls a circuit simulator to compute and evaluate newer results until all specifications are matched. More than fifteen parameters including device sizes, passive components, and biasing conditions are optimized for the aforementioned constraints. For LNA IC with 0.18 mu m metal-oxide-silicon filed effect transistors, benchmark results confirm the functionality of the implemented prototype.
An efficient tile-based ECO router using routing graph reduction and enhanced global routing flow
(2007-02-01)
Li, Yih-Lang
;
Li, Jin-Yih
;
Chen, Wen-Bin
;
資訊工程學系
;
Department of Computer Science
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.
Cellular Automata Based Hardware Accelerator for Parallel Maze Routing
(2016-01-01)
Saurabh, Shashank
;
Lin, Kuen-Wey
;
Li, Yih-Lang
;
資訊工程學系
;
Department of Computer Science
This paper introduces a scalable hardware design to accelerate the maze algorithm for VLSI routing on Cellular automata (CA). The time-complexities of wave-propagation and back-tracing on CA are both O(n) while constant time for label clearing. Innately high parallelism of CA largely reduces the runtime in wave propagation and label clearing. The RTL implementation for this design has been developed in Verilog and a cell lattice of 35. 35 cells has been implemented on FPGA. The runtime of the proposed CA is shorter than that on a sequential computer by about four to five orders of magnitude.
Clock Tree Aware Post-Global Placement Optimization
(2017-01-01)
Su, Hong-Yan
;
Chiang, Po-Ting
;
Samanta, Radhamanjari
;
Li, Yih-Lang
;
資訊工程學系
Power consumption is one of the key optimization objectives for modern integrated circuit designs. More than 40% of the total power consumption is contributed by clock trees due to their high frequency of switching and high capacitance. In the traditional physical design flow, placement is done before clock tree synthesis (CTS). CTS constructs a tree to connect the clock source with all the registers. Therefore, optimization of clock trees is limited by the quality of register placement. This paper proposes a post-global placement optimization procedure that integrates a fast three stage CTS method based on modified k-means clustering technique into a global placer. The fast three stage CTS constructs a virtual clock tree to guide global placement to favor CTS. Then a multi-level clock net contractive force according to the virtual clock tree is inserted to optimize register locations for reducing the clock tree wirelength. The experimental results show that the proposed optimization approach can reduce both the clock tree wirelength and clock net switching power at the cost of slight increase in half perimeter wirelength (HPWL).
Critical-Trunk Based Obstacle-Avoiding Rectilinear Steiner Tree Routings for Delay and Slack Optimization
(2009)
Lin, Yen-Hung
;
Chang, Shu-Hsin
;
Li, Yih-Lang
;
資訊工程學系
;
Department of Computer Science
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.
Critical-Trunk-Based Obstacle-Avoiding Rectilinear Steiner Tree Routings and Buffer Insertion for Delay and Slack Optimization
(2011-09-01)
Lin, Yen-Hung
;
Chang, Shu-Hsin
;
Li, Yih-Lang
;
交大名義發表
;
National Chiao Tung University
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.
DATC RDF-2019: Towards a Complete Academic Reference Design Flow
(2019-01-01)
Chen, Jianli
;
Jiang, Iris Hui-Ru
;
Jung, Jinwook
;
Kahng, Andrew B.
;
Kravets, Victor N.
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.
DATC RDF: An Academic Flow from Logic Synthesis to Detailed Routing
(2018-01-01)
Jung, Jinwook
;
Jiang, Iris Hui-Ru
;
Chen, Jianli
;
Lin, Shih-Ting
;
Li, Yih-Lang
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.
DATC RDF: Robust Design Flow Database
(2017-01-01)
Jung, Jinwook
;
Lee, Pei-Yu
;
Wu, Yan-Shiun
;
Darav, Nima Karimpour
;
Jiang, Iris Hui-Ru
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.
Dead Via Minimization by Simultaneous Routing and Redundant Via Insertion
(2010)
Lin, Chih-Ta
;
Lin, Yen-Hung
;
Su, Guan-Chan
;
Li, Yih-Lang
;
資訊工程學系
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.
Design optimization of a current mirror amplifier integrated circuit using a computational statistics technique
(2008-12-15)
Li, Yiming
;
Li, Yih-Lang
;
Yu, Shao-Ming
;
資訊工程學系
;
電信工程研究所
In this work, we implement a Computational statistics technique for design optimization of integrated circuits (ICs). Integration of a well-known circuit simulation software and central composite design method enables us to construct a second-order response surface model (RSM) for each concerned constraint. After Construction of RSMs. we verify the adequacy and accuracy using the normal residual plots and their residual of squares. The constructed models are further employed for design optimization of current mirror amplifier ICs with 0.18 mu m CMOS devices. By considering the voltage gain, cut-off frequency, phase margin, common-mode rejection ratio and slew-rate, six designing parameters including the width and length of different transistors are selected and optimized to fit the targets. (C) 2007 IMACS. Published by Elsevier B.V. All rights reserved.
DOPPLER: DPL-aware and OPC-friendly Gridless Detailed Routing with Mask Density Balancing
(2011)
Lin, Yen-Hung
;
Ban, Yong-Chan
;
Pan, David Z.
;
Li, Yih-Lang
;
資訊工程學系
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 generating layouts, especially in routing stage. Moreover, one decomposed design with balanced mask density has a lower edge placement error (EPE) than an unbalanced one [6]. This work proposes a comprehensive conflict graph (CCG) to enable detailed routers to simultaneously consider DPL, OPC, and mask density to generate 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 demonstrates an average 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.
Double Patterning Lithography Aware Gridless Detailed Routing with Innovative Conflict Graph
(2010-01-01)
Lin, Yen-Hung
;
Li, Yih-Lang
;
資訊工程學系
;
Department of Computer Science
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.
Efficient Simulated Evolution Based Rerouting and Congestion-Relaxed Layer Assignment on 3-D Global Routing
(2009)
Dai, Ke-Ren
;
Liu, Wen-Hao
;
Li, Yih-Lang
;
資訊工程學系
;
Department of Computer Science
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 pseudo-random 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 wire-length and 13% to 27% less runtime than COLA.
Electronic design automation using a unified optimization framework
(2008-12-15)
Li, Yiming
;
Yu, Shao-Ming
;
Li, Yih-Lang
;
資訊工程學系
;
電信工程研究所
This work proposes an object-oriented unified optimization framework (UOF) for general problem optimization. Based on biological inspired techniques, numerical deterministic methods, and C++ objective design, the UOF itself has significant potential to perform optimization operations on various problems. The UOF provides basic interlaces to define a general problem and generic solver, enabling these two different research fields to be bridged. The components of the UOF can be separated into problem and solver components. These two parts work independently allowing high-level code to be reused, and rapidly adapted to new problems and solvers. The UOF is customized to deal with several optimization problems. The first experiment involves a well-known discrete combinational problem, wihle the second one studies the robustness for the reverse modeling problem, which is in high demanded by device manufacturing companies. Additionally, experiments are undertaken to determine the capability of the proposed methods in both analog and digital circuit design automation. The final experiment designs antenna for rapidly growing wireless communication. Most experiments are categorized as simulation-based optimization tasks in the microelectronics industry. The results confirm that UOF has excellent flexibility and extensibility to solve these problems successfully. The developed open-source project is publicly available. (C) 2007 IMACS. Published by Elsevier B.V. All rights reserved.