Browsing by Author "Lin, Yen-Hung"

Now showing 1 - 13 of 13

A High-Performance Triple Patterning Layout Decomposer with Balanced Density
(2013)
Yu, Bei
;
Lin, Yen-Hung
;
Luk-Pat, Gerard
;
Ding, Duo
;
Lucas, Kevin
Triple patterning lithography (TPL) has received more and more attentions from industry as one of the leading candidate for 14nm/11nm nodes. In this paper, we propose a high performance layout decomposer for TPL. Density balancing is seamlessly integrated into all key steps in our TPL layout decomposition, including density-balanced semi-definite programming (SDP), density-based mapping, and density-balanced graph simplification. Our new TPL decomposer can obtain high performance even compared to previous state-of-the-art layout decomposers which are not balanced-density aware, e. g., by Yu et al. (ICCAD\'11), Fang et al. (DAC\'12), and Kuang et al. (DAC\'13). Furthermore, the balanced-density version of our decomposer can provide more balanced density which leads to less edge placement error (EPE), while the conflict and stitch numbers are still very comparable to our non-balanced-density baseline.
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.
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.
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.
Extension of C-elegans lifespan using the center dot NO-delivery dinitrosyl iron complexes
(2018-07-01)
Huang, Hsiao-Wen
;
Lin, Yen-Hung
;
Lin, Min-Hsuan
;
Huang, Ya-Rong
;
Chou, Chih-Hung
The ubiquitous and emerging physiology function of endogenous nitric oxide in vascular, myocardial, immune, and neuronal systems prompts chemists to develop a prodrug for the controlled delivery of center dot NO in vivo and for the translational biomedical application. Inspired by the discovery of natural [Fe(NO)(2)] motif, herein, we develop the synthetic dinitrosyl iron complexes (DNICs) [Fe-2(mu-SR)(2)(NO)(4)] (1) as a universal platform for the O-2-triggered release of center dot NO, for the regulation of center dot NO-release kinetics (half-life = 0.6-27.4 h), and for the activation of physiological function of center dot NO. Using C. elegans as a model organism, the center dot NO-delivery DNIC 1 regulates IIS signaling pathway, AMPK signaling pathway, and mitochondrial function pathway to extend the lifespan and to delay the aging process based on the lifespan analysis, SA-beta gal activity assay, and next-generation RNA sequencing analysis. This study unveils the anti-aging effect of center dot NO and develops DNICs as a chemical biology probe for the continued discovery of unprecedented NO physiology. [GRAPHICS] .
Gridless Wire Ordering, Sizing and Spacing with Critical Area Minimization
(2011)
Lee, Yu-Wei
;
Lin, Yen-Hung
;
Li, Yih-Lang
;
資訊工程學系
;
Department of Computer Science
Designs for yield (DFY) problems have received increasing attention. Of particular concern in DFY problems is how to formulate and reduce a critical area for random defects. Arranging interconnections is recognized as an effective means of improving the sensitivity towards random defects. Previous works have demonstrated that random defects significantly influence interconnections and the effectiveness of layer assignment and track routing to enhance routing quality and performance. This work proposes a random defect aware layer assignment and gridless track routing (RAAT) to eliminate the effect of random defects. Gridless track routing comprises wire ordering, wire sizing and spacing in this work. Exposure ratio metric is proposed to assign each iroute to a specific layer efficiently. RAAT utilizes min-cut partitioning, a conventionally adopted method for placement and floorplanning, to place interconnections. Slicing tree-based structure improves the efficiency of wire ordering in lowering overlapped length between adjacent partitions. Finally, a second-order cone programming refined by considering an extra random-defect effect determines the position and width of each iroute. Experimental results demonstrate the necessity of the integration of layer assignment and track routing. Results further demonstrate the effectiveness of the gridless track routing methods proposed by RAAT. In addition to finishing each case more rapidly with higher completion rate than previous works do, RAAT reduces up to 20% of the number of failures in the Monte Carlo simulation as compared to previous works.
Minimizing Critical Area on Grid less Wire Ordering, Sizing and Spacing
(2014-01-01)
Lee, Yu-Wei
;
Lin, Yen-Hung
;
Li, Yih-Lang
;
資訊工程學系
;
Department of Computer Science
Design for yield (DFY) problems have received increasing attention. Of particular concern in DFY problems is how to formulate and reduce a critical area for random defects. Arranging interconnects is recognized as an effective means of improving the sensitivity towards random defects. Previous works have demonstrated that random defects significantly influence interconnections and the effectiveness of layer assignment and track routing to enhance routing quality and performance. This work proposes a random defect aware layer assignment and gridless track routing (RAAT) to eliminate the effect of random defects. Gridless track routing comprises wire ordering, wire sizing and spacing in this work. Exposure ratio metric is proposed to assign well each iroute to a specific layer. RAAT utilizes min-cut partitioning, a conventionally adopted method for placement and floorplanning, to place and size interconnections. Slicing tree-based structure improves the efficiency of wire ordering in lowering overlapped length between adjacent partitions. Finally, a second-order corn programming refined by considering an extra random-defect effect determines the position and width of each iroute. Experimental results demonstrate the necessity of the integration of layer assignment and track routing. Results further demonstrate the effectiveness of the gridless track routing methods proposed by RAAT. In addition to finishing each case more rapidly with higher completion rate than previous works do, RAAT reduces up to 20% of the number of failures in the Monte Carlo simulation as compared to previous works.
Model checking safety-critical systems using safecharts
(2007-05-01)
Hsiung, Pao-Ann
;
Chen, Yean-Ru
;
Lin, Yen-Hung
;
交大名義發表
;
National Chiao Tung University
With rapid developments in science and technology, we now see the ubiquitous use of different types of safety-critical systems in our daily lives such as in avionics, consumer electronics, and medical systems. In such systems, unintentional design faults might result in injury or even death to human beings. To make sure that safety-critical systems are really safe, there is a need to verify them formally. However, the verification of such systems is getting more and more difficult because designs are becoming very complex. To cope with high design complexity, currently, model-driven architecture design is becoming a well-accepted trend. However, existing methods of testing and standards conformance are restricted to implementation code, so they do not fit very well with model-based approaches. To bridge this gap, we propose a model-based formal verification technique for safety-critical systems. In this work, the model-checking paradigm is applied to the Safecharts model, which was used for modeling but not yet used for verification. Our contributions listed are as follows: First, the safety constraints in Safecharts are mapped to semantic equivalents in timed automata for verification. Second, the theory for safety constraint verification is proven and implemented in a compositional model checker (that is, the State-Graph Manipulator (SGM)). Third, prioritized and urgent transitions are implemented in SGM to model the risk semantics in Safecharts. Finally, it is shown that the priority-based approach to mutual exclusion of resource usage in the original Safecharts is unsafe and corresponding solutions are proposed here. Application examples show the feasibility and benefits of the proposed model-driven verification of safety-critical systems.
Topology-Aware Buffer Insertion and GPU-Based Massively Parallel Rerouting for ECO Timing Optimization
(2012)
Lin, Yen-Hung
;
Lo, Yun-Jian
;
Tong, Hian-Syun
;
Liu, Wen-Hao
;
Li, Yih-Lang
Conventional buffer insertion in timing ECO involves only minimizing the arrival time of the most critical sink in one multi-pin net and neglects the obstacles and the topology of routed wire segments, which may worsen the arrival times of other sinks and burden subsequent timing ECO. This work develops a topology-aware ECO timing optimization (TOPO) flow that comprises three phases - buffering pair scoring, edge breaking and buffer connection, and topology restructuring. TOPO effectively improves the arrival times of violation sinks without worsening those of other sinks. Experimental results indicate that TOPO improves the worst negative slack (WNS) and total negative slack (TNS) of benchmarks by an average of 79.2% and 84.3%, respectively. The proposed algorithm improves the arrival time that is achieved using conventional two-pin net-based buffer insertion by an average of 40.4%, at the cost of consuming 19x runtime. To speed up routing and further improve sink slack, a highly scalable massively parallel maze routing on Graphics Processing Unit (GPU) platform is also developed to enable the proposed flow to explore more solution candidates. High scalability and parallelism are realized by block partitioning and staggering. Experiments reveal that the proposed GPU-based parallel maze routing can achieve near 12x runtime speedup for two-pin routings. With parallelized maze routing, WNS violations in four out of five cases can be resolved.
Topology-Driven Cell Layout Migration with Collinear Constraints
(2009)
Fu, De-Shiun
;
Chaung, Ying-Zhih
;
Lin, Yen-Hung
;
Li, Yih-Lang
;
資訊工程學系
Traditional layout migration focuses on area minimization, thus suffered wire distortion, which caused loss of layout topology. A migrated layout inheriting original topology owns original design intention and predictable property, such as wire length which determines the path delay importantly. This work presents a new rectangular topological layout to preserve layout topology and combine its flexibility of handling wires with traditional scan-line based compaction algorithm for area minimization. The proposed migration flow contains devices and wires extraction, topological layout construction, unidirectional compression combining scan-line algorithm with collinear equation solver, and wire restoration. Experimental results show that cell topology is well preserved, and a several times runtime speedup is achieved as compared with recent migration research based on ILP (integer linear programming) formulation.
TRIAD: A Triple Patterning Lithography Aware Detailed Router
(2012)
Lin, Yen-Hung
;
Yu, Bei
;
Pan, David Z.
;
Li, Yih-Lang
;
資訊工程學系
TPL-friendly detailed routers require a systematic approach to detect TPL conflicts. However, the complexity of conflict graph (CG) impedes directly detecting TPL conflicts in CG. This work proposes a token graph-embedded conflict graph (TECG) to facilitate the TPL conflict detection while maintaining high coloring-flexibility. We then develop a TPL aware detailed router (TRIAD) by applying TECG to a gridless router with the TPL stitch generation. Compared to a greedy coloring approach, experimental results indicate that TRIAD generates no conflicts and few stitches with shorter wirelength at the cost of 2.41 x of runtime.