Browsing by Author "Lin, Kuen-Wey"

Now showing 1 - 7 of 7

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.
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.
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.
Near-Future Traffic Evaluation based Navigation for Automated Driving Vehicles
(2017-01-01)
Lin, Kuen-Wey
;
Li, Yih-Lang
;
Hashimoto, Masanori
;
資訊工程學系
;
Department of Computer Science
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.
Near-Future Traffic Evaluation based Navigation for Automated Driving Vehicles Considering Traffic Uncertainties
(2018-01-01)
Lin, Kuen-Wey
;
Hashimoto, Masanori
;
Li, Yih-Lang
;
資訊工程學系
;
Department of Computer Science
Because it is difficult to find empty space in a developed city to accommodate more transportation infrastructures, the development of an effective navigation system is a low cost option for mitigating traffic jam. Regarding a future world where automated driving technologies have become mature and most vehicles follow the pre-scheduled route suggested by a navigation system, it is likely to predict the traffic jam accurately if the navigation system can know the pre-scheduled route of each vehicle. Recently, a navigation algorithm is presented for automated driving vehicles with the assumption that all the navigating query requests are processed by a single system. However, the aforementioned algorithm does not consider any kind of uncertainty originating from accidents and destination change. To get close to the real world, we propose a navigation algorithm with near-future evaluation capability that also allows some kinds of uncertainties. We compare our algorithm with a dynamic-update based conventional navigation algorithm without near-future evaluation capability. We download some metropolitan maps from OpenStreetMap and utilize the data of traffic flow from official statistics to randomly generate many sets queries. Experimental results show that the total cruising time is improved for each case.