Browsing by Author "Chang, Hua-Yu"

Now showing 1 - 12 of 12

ECO Optimization Using Metal-Configurable Gate-Array Spare Cells
(2013-11-01)
Chang, Hua-Yu
;
Hui-Ru, Iris
;
Chang, Yao-Wen
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
Due to the rapidly increasing design complexity in modern IC designs, metal-only engineering change order (ECO) becomes inevitable to achieve design closure with a low respin cost. Traditionally, preplaced redundant standard cells are regarded as spare cells. However, these cells are limited by predefined functionalities and locations, and they always consume leakage power despite their inputs being tied off. To overcome the inflexibility and power overhead, a new type of spare cells, called metal-configurable gate-array spare cells, are introduced. In this paper, we address a new ECO problem, which performs design changes using metal-configurable gate-array spare cells. We first study the properties of this new ECO problem and propose a new cost metric, aliveness, to model the capability of a spare gate array. Based on aliveness and routability, we then develop two ECO optimization frameworks, one for timing ECO and the other for functional ECO. Experimental results show that our approach delivers superior efficiency and effectiveness.
ECOS: Stable Matching Based Metal-Only ECO Synthesis
(2012-03-01)
Jiang, Iris Hui-Ru
;
Chang, Hua-Yu
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
To ease the time-to-market pressure and save the photomask cost, metal-only ECO realizes the last-minute design changes by revising the photomasks of metal layers only. This task is challenging because the pre-injected spare cells are limited in number and in cell types. Metal-only ECO has to implement these functional and/or timing changes using available spare cells. In this paper, we propose a stable matching based metal-only ECO synthesizer, named ECOS, that can implement the incremental design changes correctly without sacrificing timing and routability. The experiments are conducted on nine industrial testcases. These testcases reflect the real difficulties faced by designers and our results show that ECOS is promising for all of them.
Functional ECO Using Metal-Configurable Gate-Array Spare Cells
(2014)
Chang, Hua-Yu
;
Jiang, Iris Hui-Ru
;
Chang, Yao-Wen
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
Metal-configarable gate-array spare cells, which have versatile functionality, are developed to overcome the inflexibility of standard spare cells used in conventional metal-only engineering change order (ECO). In this paper, we focus on functional ECO optimization using the new type of spare cells to fully exploit its strength. We observe that this functional LCD problem has the nature of dynamic logical and physical costs for at spare gate arrays. Unlike existing functional E0 works, which perform technology snapping based on ECO patches, we perform reverse mapping from spare gate arrays to handle these dynamic costs. We devise a spare array relation graph to record geometrical adjacency among spare gate arrays and interleave with the and-inverter network of ECO patches. To avoid redundant traversal and monitor the dynamic costs, we adopt A* search to simultaneously traverse and imp between the logical LCD network and the physical spare array relation graph.
Live Demo: ECOS 1.0: A Metal-Only ECO Synthesizer
(2010)
Jiang, Iris Hui-Ru
;
Chang, Hua-Yu
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
To ease the time-to-market pressure and save the photomask cost, metal-only ECO realizes the last-minute design changes by revising the photomasks of metal layers only. This task is challenging because the pre-injected spare cells are limited in number and in cell types. We develop a metal-only ECO synthesizer, named ECOS, that automates the incremental design changes without sacrificing timing and routability. Via the live demonstration, visitors can experience the superior performance of ECOS.
Matching-Based Minimum-Cost Spare Cell Selection for Design Changes
(2009)
Jiang, Iris Hui-Ru
;
Chang, Hua-Yu
;
Chang, Liang-Gi
;
Hung, Huang-Bi
;
電子工程學系及電子研究所
Metal-only ECO realizes the last-minute design changes by revising the photomasks of metal layers only. This task is challenging because the pre-injected spare cells are limited both in number and in cell types. This paper proposes a matching-based EGO synthesizer, named EGOS, that correctly implements the incremental design changes using the available spare cells as well as tries to reduce the prohibitive photomask cost at the same time. The experiments are conducted on five industrial testcases. ECOS uses less photomask costs to complete design changes for all cases than the direct method that transforms the widely-used hand-editing procedure into an automatic one.
Multiple Patterning Layout Decomposition Considering Complex Coloring Rules
(2016)
Chang, Hua-Yu
;
Jiang, Iris Hui-Ru
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
Multiple patterning lithography has been recognized as one of the most promising solutions, in addition to extreme ultraviolet lithography, directed self-assembly, nanoimprint lithography, and electron beam lithography, for advancing the resolution limit of conventional optical lithography. Multiple patterning layout decomposition (MPLD) becomes more challenging as advanced technology introduces complex coloring rules. Existing works model MPLD as a graph coloring problem; nevertheless, when complex coloring rules are considered, layout decomposition can no longer be modeled accurately by graph coloring. Therefore, in this paper, for capturing the essence of layout decomposition with complex coloring rules, we model the MPLD problem as an exact cover problem. We then propose a fast and exact MPLD framework based on augmented dancing links. Our method is flexible and general: It can consider the basic and complex coloring rules simultaneously, and it can handle quadruple patterning and beyond. Experimental results show that our approach outperforms state-of-the-art works on reported conflicts and stitches and is promising for handling complex coloring rules as well.
Multiple Patterning Layout Decomposition Considering Complex Coloring Rules
(2016)
Chang, Hua-Yu
;
Jiang, Iris Hui-Ru
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
Multiple patterning lithography has been recognized as one of the most promising solutions, in addition to extreme ultraviolet lithography, directed self-assembly, nanoimprint lithography, and electron beam lithography, for advancing the resolution limit of conventional optical lithography. Multiple patterning layout decomposition (MPLD) becomes more challenging as advanced technology introduces complex coloring rules. Existing works model MPLD as a graph coloring problem; nevertheless, when complex coloring rules are considered, layout decomposition can no longer be modeled accurately by graph coloring. Therefore, in this paper, for capturing the essence of layout decomposition with complex coloring rules, we model the MPLD problem as an exact cover problem. We then propose a fast and exact MPLD framework based on augmented dancing links. Our method is flexible and general: It can consider the basic and complex coloring rules simultaneously, and it can handle quadruple patterning and beyond. Experimental results show that our approach outperforms state-of-the-art works on reported conflicts and stitches and is promising for handling complex coloring rules as well.
Simultaneous Functional and Timing ECO
(2011-01-01)
Chang, Hua-Yu
;
Jiang, Iris Hui-Ru
;
Chang, Yao-Wen
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
Metal-only ECO is prevalent at design houses to perform incremental design changes to resolve last found functional and/or timing failures. However, it is hard to perform mixed functional and timing changes manually. Prior endeavors focus on functional or timing ECO alone, but we observe that separating them may fail to fix all timing violations. Consequently, this paper presents the first work to perform simultaneous functional and timing ECO. We use an augmented bipartite graph to model both types of ECO. In addition, through comprehensive constant insertion and bridging, the functional capability of each spare cell is enhanced, thus facilitating spare cell selection. Experimental results show that our simultaneous functional and timing ECO engine can successfully resolve mixed functional and timing ECO that is unsolvable by the sequential scheme. Moreover, our engine outperforms the state-of-the-art works for timing ECO with a 117X speedup, and for functional ECO with 6-15% wirelength reductions.
Smart Grid Load Balancing Techniques via Simultaneous Switch/Tie-line/Wire Configurations
(2014)
Jiang, Iris Hui-Ru
;
Nam, Gi-Joon
;
Chang, Hua-Yu
;
Nassif, Sani R.
;
Hayes, Jerry
Fast changing power distribution systems request a dynamic system configuration capability of reacting to volatile consumption demands in an economical way. Load balancing in power distribution systems is an essential technique for smart grid that enables reliable electricity delivery to end customers. This paper is the first work focusing on load balancing using switch reconfiguration, tie-line addition, and wire upgrade simultaneously, while existing works adopt only one of the three techniques to configure the power distribution system. We observe that the new load balancing problem induces a new challenge, dynamic topology rotation, which cannot be handled by existing solutions. To overcome this challenge, we first consider bidirectional power flows and formulate the load balancing problem as a mixed-integer quadratically constrained quadratic program (MIQCQP). To reduce the computational complexity, it is further transformed into a mixed-integer linear program (MILP) without loss of optimality. Experimental results show that, on real power distribution networks, our approach produces optimal solutions that arc unlikely to be found in ad-hoc heuristics methods.
Timing ECO Optimization Via Bezier Curve Smoothing and Fixability Identification
(2012-12-01)
Chang, Hua-Yu
;
Jiang, Iris Hui-Ru
;
Chang, Yao-Wen
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
Due to the rapidly increasing design complexity in modern integrated circuit design, more and more timing failures are detected at late stages. Without deferring time-to-market, metal-only engineering change order (ECO) is an economical technique to correct these late-found failures. Typically, a design might need to undergo many ECO runs in design houses; consequently, the usage of spare cells for ECO is of significant importance. In this paper, we aim at timing ECO by using as few spare cells as possible. We observe that a path with good timing is desired to be geometrically smooth. Unlike negative slack and gate delay used in most prior work, we propose a new metric of timing criticality, fixability, by considering the smoothness of timing violating paths. To measure the smoothness of a path, we use the Bezier curve as the golden path. Furthermore, in order to concurrently fix timing violations, we derive a propagation property to divide violating paths into independent segments. Based on Bezier curve smoothing, fixability identification, and the propagation property, we develop an efficient algorithm to fix timing violations. Experimental results show that we can effectively resolve all timing violations with significant speedups over the state-of-the-art works.
Timing ECO Optimization via Bezier Curve Smoothing and Fixability Identification
(2011)
Chang, Hua-Yu
;
Jiang, Iris Hui-Ru
;
Chang, Yao-Wen
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
Due to the rapidly increasing design complexity in modern IC design, more and more timing failures are detected at late stages. Without deferring time-to-market, metal-only ECO is an economical technique to correct these late-found failures. Typically, a design undergoes many ECO runs in design houses; the usage of spare cells is of significant importance. Hence, in this paper, we aim at timing ECO using the least number of spare cells. We observe that a path with good timing is desired to be geometrically smooth. Different from negative slack and gate delay used in most of prior work, we propose a new metric of timing criticality-fixability-considering the smoothness of critical paths. To measure the smoothness of a path, we use Bezier curve as the golden path. Furthermore, in order to concurrently fix timing violations, we derive the dominance property to divide violated paths into independent segments. Based on Bezier curve smoothing, fixability identification, and the dominance property, we develop an efficient algorithm to fix violations. Compared with the state-of-the-art works, experimental results show that our algorithm not only effectively resolves all timing violations with few spare cells but also achieves 22.8X and 42.6X speedups.
WiT: Optimal Wiring Topology for Electromigration Avoidance
(2012-04-01)
Jiang, Iris Hui-Ru
;
Chang, Hua-Yu
;
Chang, Chih-Long
;
電子工程學系及電子研究所
;
Department of Electronics Engineering and Institute of Electronics
Due to excessive current densities, electromigration (EM) may trigger a permanent open- or short-circuit failure in signal wires or power networks in analog or mixed-signal circuits. As the feature size keeps shrinking, this effect becomes a key reliability concern. Hence, in this paper, we focus on wiring topology generation for avoiding EM at the routing stage. Prior works tended towards heuristics; on the contrary, we first claim this problem belongs to class P instead of class NP-hard. Our breakthrough is, via the proof of the greedy-choice property, we successfully model this problem on a multi-source multi-sink flow network and then solve it by a strongly polynomial time algorithm. Experimental results prove the effectiveness and efficiency of our algorithm.