跳到主要內容

臺灣博碩士論文加值系統

(44.222.64.76) 您好!臺灣時間:2024/06/14 07:44
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張華宇
研究生(外文):Hua-Yu Chang
論文名稱:作用於金屬層之積體電路設計變更最佳化
論文名稱(外文):Metal-Only Engineering Change Order Optimization for Integrated Circuit Design
指導教授:張耀文張耀文引用關係
指導教授(外文):Yao-Wen Chang
口試委員:張世杰李毅郎王廷基黃鐘揚郭斯彥
口試委員(外文):Shih-Chieh ChangYih-Lang LiTing-Chi WangChung-Yang HuangSy-Yen Kuo
口試日期:2014-07-16
學位類別:博士
校院名稱:國立臺灣大學
系所名稱:電子工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:英文
論文頁數:146
中文關鍵詞:實體設計設計變更時序修正技術映射陣列元件
外文關鍵詞:Physical designEngineering change orderTiming fixingTechnology mappingGate array
相關次數:
  • 被引用被引用:0
  • 點閱點閱:231
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
隨著積體電路晶片設計複雜度的急劇增加,某些重要的規格變更或極難偵測 的設計缺陷幾乎是不可避免的在設計階段的晚期才被提出或發現。因此只需修訂 金屬層光罩之電路設計變更在工業界的設計流程中被廣泛的使用。這些設計變更 可以是修正設計缺陷或是更改產品規格的功能性設計變更或者是收斂時序與最 佳化的時序設計變更。另外,為了讓此作用於金屬層的設計變更可以實行,會在 擺置與繞線階段的前期便事先將備用元件事先散置在整個設計中。傳統上利用標 準元件作為備用元件。然而,這些標準備用元件會被它們事先決定好的數量、擺 放位置以及功能所限制。於是,一種名為可配置金屬層陣列之備用元件被發展出 來以克服標準備用元件先天的限制,並使得作用於金屬層的設計變更的實用性更 加增強。為了在很短的週轉時間內補救晚期所發現的設計缺陷並且減輕產品上市 時機的壓力,作用於金屬層的設計變更已經在當代電路晶片設計流程中變成一個 相當流行並普遍的步驟。
本篇論文中,我們針對作用於金屬層之設計變更提出了一個完整的解決方 法。首先,針對使用標準備用元件的設計變更:一、我們提出了一個以穩定配對 為基礎的功能性金屬層設計變更合成器。此合成器可在不犧牲時序與可繞度的狀 況下解決備用元件的資源競爭問題。二、在時序設計變更上,和前人使用元件延遲和負鬆弛為量測基礎不同,我們提出藉由考慮路徑平滑度來量測時序關鍵性, 並使用貝茲曲線當作量測的黃金曲線。我們進一步將違反時序路徑分割成各自獨 立的線段,並導出了傳播性質使得可以同時間修正多條違反時序路徑。三、我們 發現將功能性設計變更與時序設計變更分別處理可能會導致無法修正所有違反 的時序。因此,我們提出了文獻中第一個同時考慮功能性與時序的設計變更方 法。我們提出增廣的二分圖來作為兩種設計變更的模型。
另一方面,我們提出了一個新的設計變更問題—利用可配置金屬層陣列備用 元件之設計變更。首先,我們探討這個新問題的特性,並提出了一個新的量測此 陣列備用元件的功能彈性的度量—活躍度。接著我們發展了兩個新的設計變更最 佳化的演算法。一、在時序設計變更方面,為了完全利用此陣列備用元件的特性, 我們同時考慮活躍度、可繞度以及滿足時序要求。之後,我們利用反覆的混合型 整數線性規劃來解決此時序變更的問題。二、針對功能性設計變更,我們發現這 個新的功能性設計變更問題在選擇備用元件上有著在邏輯上與實體上動態變化 花費的天性。與現有的功能性設計變更的研究不同,我們從陣列備用元件往設計 變更補釘方向實行反向的技術映射。之後,我們設計了備用元件關係圖來記錄陣 列備用元件在幾何上的相鄰關係,並且在此關係圖與設計變更補釘所形成的邏輯 網路交互切換以控管動態花費並完成設計變更最佳化。

As the design complexity grows dramatically, late design changes are nearly in- evitable to handle specification modifications and/or rectify design errors. Metal- only engineering change order (ECO), which revises only metal layers to realize incremental design changes, is widely used in the industrial design flow. These in- cremental changes can be functional ECO, dedicated for functional rectification or specification modification, or timing ECO, dedicated for timing closure and opti- mization. In addition, to facilitate metal-only ECO, (redundant) spare cells are inserted at the early placement and routing stage. Conventionally, standard cells are regarded as spare cells. Nevertheless, these pre-inserted standard spare cells are limited by their pre-determined quantity, functionality, and locations. To overcome the inflexibility of standard cells, metal-configurable gate-array spare cells are de- veloped, and thus further enhance the practicality of metal-only ECO. To sum up, metal-only ECO becomes prevalent in the modern IC design flow to remedy late- found failures in a short turn-around time and reduce the time-to-market pressure.
In this dissertation, we propose a comprehensive solution for metal-only ECO. First, for metal-only ECO using standard spare cells: 1) We propose a stable match- ing based functional metal-only ECO synthesizer that can resolve spare cell com- petition and does not sacrifice timing and routability. 2) Different from 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, and using the B &;#769;ezier curve as the golden path to measure the smoothness of a path. Furthermore, in order to concurrently fix timing violations, we derive a propagation property to divide violating paths into independent segments. 3) We observe that separating functional and timing ECO may fail to fix all timing violations. Con- sequently, we present the first work to perform simultaneous functional and timing ECO. We use an augmented bipartite graph to model both types of ECO.
Second, we address a new problem of ECO optimization using metal-configurable gate-array spare cells. We first study the properties of this new ECO problem, pro- pose a new cost metric, aliveness, to model the capability of a spare gate array, and then develop two ECO optimization algorithms—functional ECO and timing ECO using metal-configurable gate-array spare cells. 1) For the new timing ECO, we con- sider aliveness, routability, and timing satisfaction in our framework to fully utilize the capability of spare arrays. Then, we resort to iterative mixed integer linear pro- gramming (MILP) in our timing ECO framework, where a set of independent and small MILPs are computed. 2) For the new functional ECO, we observe that this functional ECO problem has the nature of dynamic logical and physical costs for selecting spare gate arrays. Unlike existing functional ECO works, which perform technology mapping based on ECO patches, we perform reverse mapping from spare gate arrays to handle these dynamic costs. Then, we devise a spare array relation graph to record geometrical adjacency among spare gate arrays and interleave with the AIG network of ECO patches.

Table of Contents
Acknowledgements vii
Abstract (Chinese) ix
Abstract xi
List of Tables xvii
List of Figures xix
Chapter 1. Introduction 1
1.1 RecentResearchDevelopmentonMetal-OnlyECO . . . . . . . . . . . . 3
1.1.1 FunctionalECO ............................ 3
1.1.2 TimingECO.............................. 5
1.2 Metal-OnlyECOChallenges......................... 6
1.2.1 ResourceCompetition......................... 7
1.2.2 TimingCriticalityIdentification ................... 7
1.2.3 Spare Cell Flexibility: Metal-Configurable Gate Array Spare Cells 7
1.2.4 DynamicCost ............................. 8
1.3 OverviewoftheDissertation......................... 10
1.3.1 Stable Matching Based Functional ECO Optimization . . . . . . . 11
1.3.2 Timing ECO Optimization via B &;#769;ezier Curve Smoothing and Fix- abilityIdentification.......................... 12
1.3.3 SimultaneousFunctionalandTimingECO . . . . . . . . . . . . . 12
1.3.4 Timing ECO Optimization Using Metal-Configurable Gate-Array SpareCells............................... 13
1.3.5 Functional ECO Using Metal-Configurable Gate-Array Spare Cells 14
1.4 OrganizationoftheDissertation....................... 14
Chapter 2. Stable Matching Based Functional ECO Optimization 17
2.1 Problem Formulation and Traditional ECO Synthesis Flow . . . . . . . . 18
2.1.1 ProblemFormulation ......................... 18
2.1.2 TraditionalECOSynthesisFlow ................... 20
2.1.3 Terminology .............................. 21
2.2 StableMatchingBasedFunctionalECOSynthesis . . . . . . . . . . . . . 24
2.2.1 TechnologyMapping:GuidedABC ................. 24
2.2.2 SpareCellSelection:StableMatching ................ 27
2.2.3 TheComplexityofSpareCellSelection . . . . . . . . . . . . . . . 31
2.3 ExtensiontoCongestion-DrivenFunctionalECO. . . . . . . . . . . . . . 32
2.3.1 CongestionEstimation......................... 32
2.3.2 Congestion-DrivenStableMatching ................. 34
2.4 ExperimentalResults............................. 36
2.4.1 ExperimentalSettings......................... 36
2.4.2 ComparisonBetweenECOSynthesisFlows . . . . . . . . . . . . . 37
2.4.3 Wirelength-Driven Functional ECO Results . . . . . . . . . . . . . 38
2.4.4 Congestion-Driven Functional ECO Results . . . . . . . . . . . . . 42
Chapter 3. Timing ECO Optimization via B &;#769;ezier Curve Smoothing and Fixability Identification 45
3.1 PreliminariesandProblemFormulation................... 49
3.1.1 TimingLibraryandTimingModel.................. 49
3.1.2 ProblemFormulation ......................... 50
3.2 SlackProperties................................ 50
3.3 OurAlgorithm................................. 55
3.3.1 Overview................................ 55
3.3.2 FixabilityComputation ........................ 56
3.3.3 SpareCellSelection .......................... 59
3.3.4 ViolatingPathSegmentComposition ................ 62
3.3.5 ComplexityAnalysis.......................... 64
3.4 ExperimentalResults............................. 65
3.4.1 ExperimentalSettings......................... 65
3.4.2 Comparison with State-of-the-Art Timing ECO Approaches . . . . 66
3.4.3 Effectiveness of Resource-Aware Fixability and Multiple Gate Ex- traction................................. 68
Chapter 4. Simultaneous Functional and Timing ECO 71
4.1 Preliminaries.................................. 73
4.1.1 TimingModel ............................. 74
4.1.2 ProblemFormulation ......................... 74
4.2 Simultaneous Functional and Timing ECO Synthesis . . . . . . . . . . . 75
4.2.1 Overview................................ 75
4.2.2 ConstantInsertionandBridging ................... 75
4.2.3 ECORemappingandConversion................... 77
4.2.4 SpareCellselection .......................... 79
4.3 ExperimentalResults............................. 83
4.3.1 ExperimentalSettings......................... 83
4.3.2 TimingECOResults ......................... 84
4.3.3 FunctionalECOResults........................ 85
4.3.4 Simultaneous Functional and Timing ECO Results . . . . . . . . . 86
Chapter 5. Timing ECO Optimization Using Metal-Configurable Gate- Array Spare Cells 89
5.1 ProblemFormulationandCostMetrics ................... 92
5.1.1 SpareArrays.............................. 93
5.1.2 Aliveness ................................ 94
5.1.3 Routability............................... 95
5.1.4 ProblemFormulation ......................... 96
5.2 SingleMILPFormulationforTimingECO ................. 96
5.2.1 GenericSingleMILP ......................... 96
5.2.2 ReducedSingleMILP .........................100
5.3 OurTimingECOOptimizationFramework. . . . . . . . . . . . . . . . .101
5.3.1 Overview................................101
5.3.2 FixableandCriticalGateExtraction. . . . . . . . . . . . . . . . .103
5.3.3 SpareArrayAssignment........................103
5.3.4 SpareArrayPacking..........................106
5.3.5 Extension to Mixed Standard Spare Cells and Spare Arrays . . . . 108
5.4 ExperimentalResults.............................109
5.4.1 ExperimentalSettings.........................109
5.4.2 Complexity Comparison Between Different MILP Formulations . . 111
5.4.3 ResultsofOurFramework ......................111
Chapter 6. Functional ECO Using Metal-Configurable Gate-Array Spare Cells 115
6.1 ProblemFormulationandCostMetrics ...................118
6.1.1 ProblemFormulation .........................118
6.1.2 TheLogicalCost............................118
6.1.3 ThePhysicalCost ...........................119
6.2 OurFunctionalECOFramework.......................120
6.2.1 Overview................................120
6.2.2 BoundingBoxCalculation ......................121
6.2.3 RelationGraphGeneration ......................121
6.2.4 ResourceBudgeting ..........................123
6.2.5 LogicalandPhysicalMapping ....................124
6.2.6 AdjustmentandNegotiation .....................128
6.3 ExperimentalResults.............................128
6.3.1 ExperimentalSettings.........................128
6.3.2 ResultsofOurFramework ......................129
Chapter 7. Concluding Remarks and Future Work 133
7.1 ConcludingRemarks .............................133
7.1.1 Metal-onlyECObyUsingStandardSpareCells. . . . . . . . . . .133
7.1.2 Metal-onlyECObyUsingSpareArrays . . . . . . . . . . . . . . .134
7.2 FutureWork..................................135
Bibliography 137
Vita 143
Publication List 145

[1] ABC: A System for Sequential Synthesis and Verification, Release 70930, 2012. http://www.eecs.berkeley.edu/a &;#771;lanmi/abc/.
[2] ARM Artisan ECO Kit. Available at http://www.arm/products/physical-ip/logic-ip/eco-kit.php.
[3] IBM ILOG CPLEX Optimizer. http://www.ilog.com/products/cplex/.
[4] International Technology Roadmap for Semiconductors (ITRS) 2013. http://www.itrs.net/.
[5] LEDA package. http://www.algorithmic-solutions.com/.
[6] LEF/DEF Exchange Format: Reference Documentation Plus Parser. http://www.si2.org/openeda.si2.org/projects/lefdef.
[7] Liberty: The EDA library modeling standard. http://www.opensourceliberty.org/.
[8] A. Balasinkski. Optimization of sub-100-nm designs for mask cost reduction. J. Microlithogr., Microfab., Microsyst., 3(2):322–331, Apr 2004.
[9] R. H. Bartels, J. C. Beatty, and B. A. Barsky. An Introduction to Splines for Use in Computer Graphics and Geometric Modeling. Morgan Kaufmann, 1998.
[10] L. Benini and G. D. Micheli. A survey of boolean matching techniques for library binding. ACM Transactions on Design Automation of Electronic Sys- tems, 2(3):193–226, Jul 1997.
[11] R. E. Bryant. Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Computing Surveys, 24(3):293–318, Sep 1992.
[12] H.-Y. Chang, I. H.-R. Jiang, and Y.-W. Chang. Simultaneous functional and timing ECO. In Proceedings of ACM/IEEE Design Automation Conference, pages 140–145, 2011.
[13] H.-Y. Chang, I. H.-R. Jiang, and Y.-W. Chang. Timing ECO optimization using metal-configurable gate-array spare cells. In Proceedings of ACM/IEEE Design Automation Conference, pages 802–807, 2012.
[14] H.-Y. Chang, I. H.-R. Jiang, and Y.-W. Chang. Timing ECO optimization via b &;#769;ezier curve smoothing and fixability identification. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 31(12):1857–1866, Dec 2012.
[15] K.-H. Chang, I. L. Markov, and V. Bertacco. Reap what you sow: Spare cells for post-silicon metal fix. In Proceedings of ACM International Symposium on Physical Design, pages 103–110, 2008.
[16] H.-T. Chen, C.-C. Chang, and T.-T. Hwang. Reconfigurable ECO cells for timing closure and IR drop minimization. IEEE Transactions on Very Large Scale Integration Systems, 18(12):1686–1695, Dec 2010.
[17] C. Chu and Y.-C. Wong. FLUTE: Fast lookup table-based rectilinear steiner minimal tree algorithm for VLSI design. IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, 27(1):77–83, Jan 2008.
[18] L. Ciccarelli. US patent 7965107: Base cell for engineering change order ECO implementation. June 2011.
[19] L. Ciccarelli. US patent 8390330: Base cell for implementating an engineering change order ECO. Mar 2013.
[20] S.-Y. Fang, T.-F. Jian, and Y.-W. Chang. Redundant-wires-aware ECO timing and mask-cost optimization. In Proceedings of IEEE/ACM International Con- ference on Computer-Aided Design, pages 381–386, 2010.
[21] A. Frank. On Kuhn’s Hungarian method - a tribute from hungary. In Technical Report No. 2004-14, Egervary Research Group, Oct 2004.
[22] D. Gale and L. S. Shapley. College admissions and the stability of marriage. Amer. Math. Monthly, 69:9–14, 1962.
[23] S. Golson. The human eco compiler. In Synopsys Users Group (SNUG), pages 1–57, 2004.
[24] A. Guttman. R-trees: A dynamic index structure for spatial searching. In Proceedings of International Conference on Management of Data, pages 47–57, Jun 1984.
[25] P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the heuristic deter- mination of minimum cost paths. IEEE Transactions on Services Computing, 4(2):100–107, July 1968.
[26] K.-H. Ho, Y.-P. Chen, J.-W. Fang, and Y.-W. Chang. ECO timing optimization using spare cells and technology remapping. IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, 29(5):697–710, May 2010.
[27] K.-H. Ho, J.-H. R. Jiang, and Y.-W. Chang. TRECO: dynamic technol- ogy remapping for timing engineering change orders. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 31(11):1723–1733, Nov 2012.
[28] M.-K. Hsu, S. Chou, T.-H. Lin, and Y.-W. Chang. Routability-driven ana- lytical placement for mixed-size circuit designs. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 80–84, Nov 2011.
[29]S.-L.Huang,C.-A.Wu,K.-F.Tang,C.-H.Hsu,and C.-Y.R.Huang. A robust ECO engine by resource-constraint-aware technology mapping and in- cremental routing optimization. In ACM/IEEE Asia and South Pacific Design Automation Conference, pages 382–387, 2011.
[30] I. H.-R. Jiang and H.-Y. Chang. ECOS: Stable matching based metal-only ECO synthesis. IEEE Transactions on Very Large Scale Integration Systems, 20(3):485–497, Mar 2012.
[31] Z.-W. Jiang, M.-K. Hsu, Y.-W. Chang, and K.-Y. Chao. Spare-cell-aware mul- tilevel analytical placement. In Proceedings of ACM/IEEE Design Automation Conference, pages 430–435, 2009.
[32] Z.-W. Jiang, B.-Y. Su, and Y.-W. Chang. Routability-driven analytical place- ment by net overlapping removal for large-scale mixed-size designs. In Proceed- ings of ACM/IEEE Design Automation Conference, pages 167–172, 2008.
[33] S. Krishnaswamy, H. Ren, N. Modi, and R. Puri. Deltasyn: An efficient logic difference optimizer for ECO synthesis. In Proceedings of IEEE/ACM Interna- tional Conference on Computer-Aided Design, pages 789–796, 2009.
[34] H. W. Kuhn. The hungarian method for the assignment problem. Naval Res. Logist. Quar., 2(1–2):83–97, Mar 1995.
[35] Y.-M. Kuo, Y.-T. Chang, S.-C. Chang, and M. Marek-Sadowska. Spare cells with constant insertion for engineering change. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 28(3):456–460, Mar 2009.
[36] Y.-L. Li, J.-Y. Li, and W.-B. Chen. An efficient tile-based ECO router using routing graph reduction and enhanced global routing flow. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 26(2):345–358, Feb 2007.
[37] C.-P. Lu, M. C.-T. Chao, C.-H. Lo, and C.-W. Chang. A metal-only-ECO solver for input-slew and output-loading violations. IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems, 29(2):240–245, Feb 2010.
[38] N. Modi and M. Marek-Sadowska. ECO-map: Technology remapping for post- mask ECO using simulated annealing. In IEEE International Conference on Computer Design, pages 652–657, 2008.
[39] T. Petit and STMicroelectronics. Important ECOs implementation using gate- array-like mask configurable cells. In Cadence CDNLive!, May 2011.
[40] F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer, 1985.
[41] P. Spindler and F. M. Johannes. Fast and accurate routing demand estimation for efficient routability-driven placement. In Proceedings of Design, Automation and Test in Europe, pages 1226–1231, 2007.
[42] L.-C. Tien. US patent 7137094: Method for reducing layers revision in engi- neering change order. Nov 2006.
[43] G. S. Tsapepas. US patent 7676776: Spare gate array cell distribution analysis. Mar 2010.
[44] G. F. Voronoi. Nouvelles applications des parametres continus a la theorie des formes quadratiques, volume 134. J. Reine Angew. Math., 1908.
[45] L.-T. Wang, Y.-W. Chang, and K.-T. Cheng. Electronic Design Automation: Synthesis, Verification, and Testing. Elsevier/Morgan Kaufmann, 2009.
[46] X. Wei, W.-C. Tang, Y. Diao, and Y.-L. Wu. ECO timing optimization with negotiation-based re-routing and logic re-structuring using spare cells. In Pro- ceedings of Asia and South Pacific Design Automation Conference, pages 511– 516, Jan 2012.
[47] K.-C. Wu and Y.-W. Tsai. Structured ASIC, evolution or revolution? In Proceedings of ACM International Symposium on Physical Design, pages 103– 106, 2004.
[48] J. Yang. US patent 8446176: Reconfigurable engineering change order base cell. Mar 2013.
[49] Y. Zhang and C. Chu. Crop: Fast and effective congestion refinement of place- ment. In Proceedings of IEEE/ACM International Conference on Computer- Aided Design, pages 344–350, 2009.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top