作用於金屬層之積體電路設計變更最佳化

Metal-Only Engineering Change Order Optimization for Integrated Circuit Design

10.6342/NTU.2014.01210

張華宇

實體設計 ； 設計變更 ； 時序修正 ； 技術映射 ； 陣列元件 ； Physical design ； Engineering change order ； Timing fixing ； Technology mapping ； Gate array

臺灣大學電子工程學研究所學位論文

2014年

博士

張耀文

英文

隨著積體電路晶片設計複雜度的急劇增加,某些重要的規格變更或極難偵測 的設計缺陷幾乎是不可避免的在設計階段的晚期才被提出或發現。因此只需修訂 金屬層光罩之電路設計變更在工業界的設計流程中被廣泛的使用。這些設計變更 可以是修正設計缺陷或是更改產品規格的功能性設計變更或者是收斂時序與最 佳化的時序設計變更。另外,為了讓此作用於金屬層的設計變更可以實行,會在 擺置與繞線階段的前期便事先將備用元件事先散置在整個設計中。傳統上利用標 準元件作為備用元件。然而,這些標準備用元件會被它們事先決定好的數量、擺 放位置以及功能所限制。於是,一種名為可配置金屬層陣列之備用元件被發展出 來以克服標準備用元件先天的限制,並使得作用於金屬層的設計變更的實用性更 加增強。為了在很短的週轉時間內補救晚期所發現的設計缺陷並且減輕產品上市 時機的壓力,作用於金屬層的設計變更已經在當代電路晶片設計流程中變成一個 相當流行並普遍的步驟。 本篇論文中,我們針對作用於金屬層之設計變更提出了一個完整的解決方 法。首先,針對使用標準備用元件的設計變更:一、我們提出了一個以穩定配對 為基礎的功能性金屬層設計變更合成器。此合成器可在不犧牲時序與可繞度的狀 況下解決備用元件的資源競爭問題。二、在時序設計變更上,和前人使用元件延遲和負鬆弛為量測基礎不同,我們提出藉由考慮路徑平滑度來量測時序關鍵性, 並使用貝茲曲線當作量測的黃金曲線。我們進一步將違反時序路徑分割成各自獨 立的線段,並導出了傳播性質使得可以同時間修正多條違反時序路徑。三、我們 發現將功能性設計變更與時序設計變更分別處理可能會導致無法修正所有違反 的時序。因此,我們提出了文獻中第一個同時考慮功能性與時序的設計變更方 法。我們提出增廣的二分圖來作為兩種設計變更的模型。 另一方面,我們提出了一個新的設計變更問題—利用可配置金屬層陣列備用 元件之設計變更。首先,我們探討這個新問題的特性,並提出了一個新的量測此 陣列備用元件的功能彈性的度量—活躍度。接著我們發展了兩個新的設計變更最 佳化的演算法。一、在時序設計變更方面,為了完全利用此陣列備用元件的特性, 我們同時考慮活躍度、可繞度以及滿足時序要求。之後,我們利用反覆的混合型 整數線性規劃來解決此時序變更的問題。二、針對功能性設計變更,我們發現這 個新的功能性設計變更問題在選擇備用元件上有著在邏輯上與實體上動態變化 花費的天性。與現有的功能性設計變更的研究不同,我們從陣列備用元件往設計 變更補釘方向實行反向的技術映射。之後,我們設計了備用元件關係圖來記錄陣 列備用元件在幾何上的相鄰關係,並且在此關係圖與設計變更補釘所形成的邏輯 網路交互切換以控管動態花費並完成設計變更最佳化。

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 ́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.

1. [1] ABC: A System for Sequential Synthesis and Verification, Release 70930, 2012. http://www.eecs.berkeley.edu/a ̃lanmi/abc/.
   連結：
2. [4] International Technology Roadmap for Semiconductors (ITRS) 2013. http://www.itrs.net/.
   連結：
3. [6] LEF/DEF Exchange Format: Reference Documentation Plus Parser. http://www.si2.org/openeda.si2.org/projects/lefdef.
   連結：
4. [8] A. Balasinkski. Optimization of sub-100-nm designs for mask cost reduction. J. Microlithogr., Microfab., Microsyst., 3(2):322–331, Apr 2004.
   連結：
5. [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.
   連結：
6. [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.
   連結：
7. [11] R. E. Bryant. Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Computing Surveys, 24(3):293–318, Sep 1992.
   連結：
8. [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.
   連結：
9. [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.
   連結：
10. [14] H. Y. Chang, I. H. R. Jiang, and Y. W. Chang. Timing ECO optimization via b ́ezier curve smoothing and fixability identification. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 31(12):1857–1866, Dec 2012.
    連結：
11. [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.
    連結：
12. [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.
    連結：
13. [21] A. Frank. On Kuhn’s Hungarian method - a tribute from hungary. In Technical Report No. 2004-14, Egervary Research Group, Oct 2004.
    連結：
14. [22] D. Gale and L. S. Shapley. College admissions and the stability of marriage. Amer. Math. Monthly, 69:9–14, 1962.
    連結：
15. [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.
    連結：
16. [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.
    連結：
17. [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.
    連結：
18. [29]S.L.Huang,C.A.Wu,K.F.Tang,C.H.Hsu,andC.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.
    連結：
19. [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.
    連結：
20. [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.
    連結：
21. [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.
    連結：
22. [34] H. W. Kuhn. The hungarian method for the assignment problem. Naval Res. Logist. Quar., 2(1–2):83–97, Mar 1995.
    連結：
23. [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.
    連結：
24. [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.
    連結：
25. [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.
    連結：
26. [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.
    連結：
27. [40] F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer, 1985.
    連結：
28. [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.
    連結：
29. [44] G. F. Voronoi. Nouvelles applications des parametres continus a la theorie des formes quadratiques, volume 134. J. Reine Angew. Math., 1908.
    連結：
30. [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.
    連結：
31. [2] ARM Artisan ECO Kit. Available at http://www.arm/products/physical-ip/logic-ip/eco-kit.php.
32. [3] IBM ILOG CPLEX Optimizer. http://www.ilog.com/products/cplex/.
33. [5] LEDA package. http://www.algorithmic-solutions.com/.
34. [7] Liberty: The EDA library modeling standard. http://www.opensourceliberty.org/.
35. [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.
36. [18] L. Ciccarelli. US patent 7965107: Base cell for engineering change order ECO implementation. June 2011.
37. [19] L. Ciccarelli. US patent 8390330: Base cell for implementating an engineering change order ECO. Mar 2013.
38. [20] S. 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.
39. [23] S. Golson. The human eco compiler. In Synopsys Users Group (SNUG), pages 1–57, 2004.
40. [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.
41. [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.
42. [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.
43. [39] T. Petit and STMicroelectronics. Important ECOs implementation using gate- array-like mask configurable cells. In Cadence CDNLive!, May 2011.
44. [42] L. C. Tien. US patent 7137094: Method for reducing layers revision in engi- neering change order. Nov 2006.
45. [43] G. S. Tsapepas. US patent 7676776: Spare gate array cell distribution analysis. Mar 2010.
46. [45] L. T. Wang, Y. W. Chang, and K. T. Cheng. Electronic Design Automation: Synthesis, Verification, and Testing. Elsevier/Morgan Kaufmann, 2009.
47. [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. [48] J. Yang. US patent 8446176: Reconfigurable engineering change order base cell. Mar 2013.
49. [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.