Browsing by Author "Lin, Rung-Bin"

Now showing 1 - 4 of 4

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.
Logic Block and Design Methodology for Via-Configurable Structured ASIC Using Dual Supply Voltages
(2014)
Lin, Ta-Kai
;
Lin, Kuen-Wey
;
Chiu, Chang-Hao
;
Lin, Rung-Bin
;
資訊工程學系
This paper presents a via-configurable logic block and a design methodology for realizing fine-grained dual-supply-voltage structured ASIC. Experiments with a 90nm process technology show that, given various timing budgets, our approach can achieve up to 44% energy reduction with 1.6% area overhead on level converters. Compared with GECVS, our approach converts up to 39% more high-supply voltage gates into low-supply voltage gates.
Multiple-Patterning Lithography-Aware Routing for Standard Cell Layout Synthesis
(2016)
Lin, Kuen-Wey
;
Li, Yih-Lang
;
Lin, Rung-Bin
;
資訊工程學系
;
Department of Computer Science
As features in semiconductor technology become extremely scaled down, manufacturability is becoming a great challenge. Owing to the delayed adoption of new lithographic techniques, such as extreme ultraviolet (EUV), e-beam direct write (EBDW), and directed self-assembly (DSA), in IC volume production, double patterning lithography (DPL) or multiple patterning lithography (MPL) is used to print critical features in advanced technology nodes. DPL/MPL imposes many restrictive design rules on the mask layout and most of previous works discuss their impact on the design of interconnection, especially on block and chip level routing. The layout decomposition problem and multiple-patterning lithography aware routing problem have been widely studied in relation to DPL/MPL for resolving the manufacturing problem at the stages of post routing and routing respectively. The same challenges also happen in standard cell layout synthesis problem that has another limited area constraint and transistor design rules to lower the feasibility of synthesis algorithms. This paper provides an overview of issues in DPL/MPL and focus on the gridless routing model, which is suitable for accommodating the restrictive design rules that are imposed by DPL/MPL. The routability problem of the standard cell layout synthesis under conditional design rules in advanced nodes will also be addressed.