為了簡化超大型積體電路高度複雜的設計流程，傳統的電腦輔助設計工具大多將晶片設計分成幾個獨立且互不相關的階段 – 諸如，高階合成、邏輯合成與實體電路佈局等。可惜的是，在現今深次微米的系統單晶片時代，由於繞線的延遲時間逐漸接近邏輯閘的延遲時間，因此，此種互相獨立，相關性薄弱的設計工具愈來愈無法處理高複雜的積體電路設計。有鑑於此，近幾年來，一種能同時考慮各階段設計特性的方法論逐漸抬頭。本論文旨在探討一個能用來提高組合電路績效的整合邏輯合成與實體電路佈局階段的方法，此方法的中心概念是一種稱為最大超級閘分割的技巧。
首先，在此種整合設計方法的邏輯層部份，我們利用最大超級閘分割將待設計電路轉換成一個巨觀的樹狀結構，此結構有別於傳統的微觀樹狀技術映成方法。擁有此一巨觀結構的好處之一是，我們可以充分運用動態規劃演算法來達到更佳的技術映成目標。在我們的方法中，我們利用延遲分析工具將所有的最大超級閘分成兩類，第一類最大超級閘位於電路的關鍵路徑上，而第二類最大超級閘則位於非關鍵路徑上。為了儘量地縮減整個電路的延遲時間，我們允陴臚@類最大超級閘的技術映成中出現電路複製，而在第二類最大超級閘中則不允章q路複製以減少付出的面積代價。另外，因為最大超級閘本身為一個圖狀電路，所以可在技術映成時採用圖狀匹配而非樹狀匹配，如此一來，可大大增加設計空間，提高最佳化的可能性，同時，電路分割本身也可減輕可能造成的計算複雜度問題。我們的實驗顯示，在ISCAS’85的標準電路中，可減少平均20.6%的延遲時間，卻只需付出約9.5%左右的面積代價。
其次，在我們整合方法的實體佈局層部份，最大超級閘電路分割具有兩項極有價值的特性：其一，最大超級閘本身即是一個電路叢集，此分割的目標正與實體層的分割演算法設定的目標一致，正可減輕電路置放演算法額外的負擔。其二，輸入到每一個最大超級閘的電路方塊之間不存在邏輯的相關性，此一特性可提高置放這些電路方塊時的自由度。我們在本論文中提出一個利用動態規劃機制的電路置放演算法，此一演算法乃是用來解決組合邏輯電路中標準細胞元的置放問題。此一動態規劃演算法分兩階段進行，在後位先行巡行時，我們將每一個最大超級閘的電路方塊視為一個軟性巨集細胞元，並呼叫一個設計空間探索演算法來產生各種可能的置放解。接下來，在前位先行巡行時，選擇每一個節點的最佳置放解，並與其親節點的置放解合併，最後完成整個電路的置放。

Traditionally, in order to simplify the highly complex design flow of VLSI chip, EDA tools often separated the flow of chip design into distinctive stages, such as high level synthesis, logic synthesis, and physical design, etc. However, those mutually un-related phases of design are increasingly incapable to handle the much complicated problems encountered in the deep submicron SOC era, in which the dominant factor affecting performance of the chip is mainly on the wire delays instead of the gate delays. As a result, a new design paradigm that simultaneously considers the properties of different design stages is popular in recent years. This dissertation investigates the integration of logic synthesis and physical design for performance improvement of combinational circuits. The pivot concept used in our approach for the logic-physical co-synthesis is a technique of circuit partitioning called maximal super-gates (MSGs).
In the logic aspect of co-synthesis, first, with the help of MSG partitioning, the circuit can be transformed to a globally trees locally non-trees structure, which contrasts with the locally trees globally non-trees structure in traditional tree-based technology mapping. This structure enables us to globally perform dynamic programming technology mapping on the circuit. Besides, by way of delay analysis, the nodes in circuit can be divided into two groups, the ones belonging to the timing critical MSGs and the others belonging to the timing non-critical MSGs. This separation of nodes allows the individual MSG to be manipulated in different way. In our approach, the nodes belonging to timing critical MSGs are matched in a way allowing gate duplication to reduce the circuit delay, while those belonging to the timing non-critical MSGs are matched without duplication to minimize the area penalty. In addition, to enrich the design space for the technology mapping, graph matching instead of tree matching can be applied in each MSG, while the partitions per se can largely alleviate the computational complexity problem imposed by the graph-matching algorithm. Experimental results on the ISCAS’85 benchmarks show that our approach delivers an average of 20.6% reduction on delay with only 9.5% increase on area.
In the physical design aspect of co-synthesis, two salient characteristics of MSG partitioning are especially valuable. First, the MSG forms a natural cluster of circuit, i.e., the strongly connected wires are confined in the MSGs. Second, the inputs to MSG are mutually logic independent. The former property relieves the burden of placement tools whose goal is set to place the close connected cells together and the latter property provides more degrees of freedom to place the input blocks of MSGs. In this dissertation, we propose a dynamic programming mechanism for placement algorithm, which solves the standard cell placement for the combinational circuit of random logic. During the post-order traversal of MSG trees, the MSG blocks are treated as soft macro-cells and a design space exploration algorithm is invoked to generate a variety of design alternatives for the MSGs. The final placement of the circuit is determined in the pre-order traversal process, which picks the best implementation of placements and runs a row-merging algorithm to merge the row placement with that of its parent MSG block. Although we have not yet finished the experiments, we believe that the proposed dynamic programming approach is very promising for the performance driven standard cell placement.

Contents


Abstract (Chinese)……………………………………………Ⅰ
Abstract (English)……………………………………………Ⅲ
Acknowledgement……………………………………………Ⅵ
Contents………………………………………………………Ⅶ
List of Figures………………………………………………...Ⅹ
List of Tables….……………………………………………XIII

Chapter 1 1
Motivation 1
1.1 Traditional Top-Down Design Flow 1
1.2 Logic-Physical Co-synthesis 4
Chapter 2 7
Introduction 7
2.1 Technology Mapping 7
2.2 The Targeted Physical Design Style 13
2.3 The Concepts of Maximal Super-Gate 17
2.4 Dissertation Overview 21
Chapter 3 22
Previous and Related Work 22
3.1 The Work for Algorithmic Structural Technology Mapping 22
3.2 The Work for Maximal Super Gate 23
3.3 The Work for Maximum Fanout-Free Cone 24
3.4 The Work for Logic-Physical Co-Synthesis 25
Chapter 4 28
The Logic Aspect of Co-Synthesis 28
4.1 Introduction 28
4.2 Technology Mapping Flow 33
4.3 Pruning of Unprofitable Duplications 43
4.4 Heuristic for General Circuits 46
4.5 Experimental Results 51
Chapter 5 55
The Physical Design Aspect of Co-Synthesis 55
5.1 Introduction 55
5.2 The Benefit of MSG Partitioning to Deep Submicron Physical Design 59
5.3 A Dynamic Programming Cell Placement Algorithm 62
5.3.1 Weakly integrated co-synthesis and strongly integrated co-synthesis 63
5.3.2 Post-order traversal of MSG trees 67
5.3.3 Pre-order traversal of MSG trees 71
Chapter 6 73
Conclusions and Future Work 73
6.1 Conclusions and Future Work for the Logic Side of Co-Synthesis 73
6.2 Conclusions and Future Work for the Physical Side of Co-Synthesis 75

Appendix A: The GenLib format in SIS package……………..…78
Appendix B: The CCU 0.35 micron library in GenLib format
……………………………………………………..………………82
Bibliography …………………………………..…………………….…………100

[1]Ali, Samia A, “A partitioning technique of general combinational circuit into a tree type circuit,” in Proceeding of the 24th Southeastern Symp., and the 3rd Annual Symp. On Communications, Signal Processing Expert Systems and ASIC VLSI Design, pp. 116-119, 1992.

[2]Bhattacharya, B. B., and Seth, S. C., “On the reconvergent structure of combinational circuits with applications to compact testing,” in Proceedings of the Fault-Tolerant Computing Symposium, pp. 264-269, 1987.

[3]Bhattacharya, B. B., and Seth, S. C., “Design of parity testable combinational circuits,” IEEE Transactions on Computers, Vol. 38, No. 11, pp. 1580-1584, 1989.

[4]Bhattacharya, U. K., Gupta, I. Sen, Nath, S. Shyama, and Dutta, P., “PLA based synthesis and testing of hazard free logic,” in Proceedings of the IEEE 8th International Conference on VLSI Design, pp. 121-124, 1995.

[5]Brasen, D. R., and Saucier, G., “Using cone structures for circuit partitioning into FPGA packages,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 17, No. 7, pp. 592-600, 1998.

[6]Breuer, M. A., Sarrafzadeh, M., and Somenzi, F., “Fundamental CAD algorithms,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 19, No. 12, pp. 1449-1475, 2000.

[7]Chakravarty, Sreejit, and Hunt III, Harry B., “On computing signal probability and detection probability of stuck-at faults,” IEEE Transactions on Computers, Vol. 39, No. 11, pp. 1369-1377, 1990.

[8]Chatterjee, S., Mishchenko, A., Brayton, R., Wang, X., and Kam, T., “Reducing structural bias in technology mapping,” In Proceedings of the IEEE ICCAD., pp. 518-525, 2005.

[9]Chaudhary, K., and Pedram, M., “A near-optimal algorithm for technology mapping minimizing area under delay constraints,” in Proceeding of the 29th ACM/IEEE Design Automation Conference, pp. 492-498, 1992.

[10]Chaudhary, K., and Pedram, M., “Computing the area versus delay trade-off curves in technology mapping,” IEEE Transactions On Computer-Aided Design of Integrated Circuits and Systems, Vol. 14, No. 12, pp. 1480-1489, 1995.

[11]Chen, Y., Tsai, W. K., and Kurdahi, F. J., “Layout-driven logic synthesis system,” IEE Proc.-Circuits, Devices and Systems, Vol. 142, No. 3, pp. 158-164, 1995.

[12]Cheng, D. I., Marek-sadowska, Malgorzata, and Cheng, K. T., “Speeding up power estimation by topological analysis,” in Proceedings of the IEEE International Conference on Custom Integrated Circuits, pp. 623-626, 1995.

[13]Chuang, W. and Hajj, I. N., “Delay and area optimization for compact placement by gate resizing and relocation,” in Proceedings of the IEEE ICCAD, pp. 145-148, 1994.

[14]Cong, J., and Ding, Y., “On Area/Depth Trade-off in LUT-Based FPGA Technology Mapping,” in Proceedings of the 30th ACM/IEEE Design Automation Conf., pp. 213-218, 1993.

[15]Cong, J., Li, Z., and Bagrodia, R., “Acyclic Multi-Way Partitioning of Boolean Networks,” in Proceedings of the 31th ACM/IEEE Design Automation Conf., pp. 670-675, 1994.

[16]Cong, J., and Xu, D., “Exploiting Signal Flow and Logic Dependency in Standard Cell Placement,” in Proceedings of ASP-DAC, pp. 399-404, 1995.

[17]Cong, J., and Xu, S., “Technological Mapping for FPGAs with Embedded Memory Block,” in Proceedings of the International Symposium on FPGA, pp. 179-188, 1998.

[18]Devadas, S., Ghosh, A., and Keutzer, K., “Logic synthesis,” McGraw-Hill, 1994.

[19]Gao, T., Vaidya, P. M., Liu, C. L., “A new performance driven placement algorithm,” in Proceedings of the IEEE ICCAD, pp. 44-47, 1991.

[20]Giovanni De Micheli, “Synthesis and optimization of digital circuits,” McGraw-Hill, 1994.

[21]Giovanni De Micheli, “Technology mapping of digital circuits,” in Proceedings of the 5th Annual European Computer Conference On Advanced Computer Technology, Reliable Systems and Applications, pp. 580-586, 1991.

[22]Gosti, W., Narayan, A., Brayton, R. K., and Sangiovanni-vincentelli, A., “Wireplanning in logic synthesis,” in Proceedings of the ACM/IEEE Design Automation Conf., pp. 26-33, 1998.

[23]Guruswamy, M., Maziasz, R. L., Dulitz, D., Raman, S., Chiluvuri, V., Fernandez, A., and Jones, L. G., “CELLERITY: A fully automatic layout synthesis system for standard cell libraries,” in Proceedings of the ACM/IEEE Design Automation Conf., pp. 327-332, 1997.

[24]Hachtel, G. D., and Somenzi, F., “Logic Synthesis and Verification Algorithm,” Kluwer Academic Publishers, Norwell, MA., 1996.

[25]He, J. A., and Kobayashi, H., “Simultaneous wire sizing and wire spacing for post-layout performance optimization,” in Proceedings of the ASP-DAC., pp. 373-378, 1998.

[26]Hu, Bo, Watanabe, Y., and Marek-sadowska, M., “Gain-based technology mapping for discrete-size cell libraries,” in Proceedings of the ACM/IEEE Design Automation Conf., pp. 574-579, 2003.

[27]Jiang, Y., Kristic, A., Cheng, K. T., and Marek-sadowska, M., “Post-layout logic restructuring for performance optimization,” in Proceedings of the ACM/IEEE Design Automation Conf., pp. 662-665, 1997.
[28]Jiang, Y., and Sapatnekar, S. S., “An integrated algorithm for combined placement and libraryless technology mapping,” in Proceedings of the IEEE ICCAD, pp. 102-105, 1999.

[29]Jiang, Y., Sapatnekar, S. S., Bamji, C., and Kim, J., “Interleaving buffer insertion and transistor sizing into a single optimization,” IEEE Transactions On VLSI Systems, Vol. 6, NO. 4, pp. 625-633, 1998.

[30]Kannan, L. N., Suaris, P. R., and Fang, H., “A methodology and algorithms for post-placement delay optimization,” in Proceedings of the ACM/IEEE Design Automation Conf., pp. 327-332, 1994.

[31]Keutzer, K., “DAGON: Technology binding and local optimization by DAG matching,” in Proceedings of the ACM/IEEE Design Automation Conf., pp. 341-347, 1987.

[32]Keutzer, K., Newton, A. R., and Shenoy, N., “The future of logic synthesis and physical design in deep-submicron process geometries,” In Proceedings of the ISPD., pp. 218-224, 1997.

[33]Kukimoto, Y., Brayton, R. K., and Sawkar, P., “Delay-optimal technology mapping by DAG covering,” in Proceedings of the ACM/IEEE Design Automation Conf., pp. 348-351, 1998.

[34]Lee, D. H., Choi, H., Park, L. J., Park, C. H., and Hwang, S. H., “A stochastic evolution algorithm for the graph covering problem and its application to the technology mapping,” in Proceedings of the IEEE International Conference on Evolutionary Computation, pp. 475-479, 1996.

[35]Lehman, E., Watanabe, Y., Grodstein, J., and Harkness, H., “Logic decomposition during technology mapping,” IEEE Transactions On Computer-Aided Design of Integrated Circuits and Systems, Vol. 16, No. 8, pp. 813-834, 1997.

[36]Lengauer, T., “Upper and lower bounds on the complexity of the min-cut linear arrangement problem on trees,” SIAM J. Algorithm Disc. Meth., Vol. 3, No. 1, pp. 99-113, 1982.

[37]Lian, Y. Y., and Lin, Y. L., “Layout-based logic decomposition for timing optimization,” in Proceedings of the ASP-DAC., pp. 229-232, 1999.

[38]Lou, J., Salek, A. H., and Pedram, M., “An exact solution to simultaneous technology mapping and linear placement problem,” in Proceedings of the IEEE ICCAD., pp. 671-675, 1997.

[39]Lu, A., Stenz, G., and Johannes, F. M., “Technology mapping for minimizing gate and routing area,” in Proceedings of the Design, Automation and Test in Europe, pp. 664-669, 1998.

[40]Lu, A., Stenz, G., Eisenmann, H., and Johannes, F. M., “Technology mapping for simultaneous gate and interconnect optimization,” IEE Proc.-Comput. Digit. Tech., Vol. 146, No. 1, pp. 21-31, 1999.

[41]Marek-Sadowska, M., and Lin, S. P., “Timing driven placement,” in Proceedings of the IEEE ICCAD, pp. 94-97, 1989.

[42]Marhoefer, Michael and McCluskey, E. J., “An experimental study of supergates,” CRC Technical Report. No. 88-6 Stanford University, 1988.

[43]Min, H. B., and Park, E. S., “Graph-theoretic algorithm for finding maximal supergates in combinational logic circuits,” IEE Proc.-Circuits Devices Syst., Vol. 143, No. 6, pp. 313-318, 1996.

[44]Pan, Yuqi, Li, Z., and Min, Y., “Structural analysis of large digital circuits,” in Proceedings of the Pacific Rim International Symp. on Fault Tolerant Systems, pp. 121-124, 1991.

[45]Pedram, M., and Bhat, N., “Layout driven technology mapping,” in Proceedings of the ACM/IEEE Design Automation Conf., pp. 99-105, 1991.

[46]Pedram, M., and Bhat, N., “Layout driven logic restructuring and decomposition,” in Proceedings of the IEEE ICCAD., pp. 134-137, 1991.


[47]Pedram, M., “Panel : Physical design and synthesis : merge or die,” in Proceedings of the ACM/IEEE Design Automation Conf., pp. 238-239, 1997.

[48]Pedram, M., “Logical-physical co-design for deep submicron circuits: challenges and solutions,” in Proceedings of the IEEE ICCAD., pp. 304-307, 1998.

[49]Preas, B. T., and Lorenzetti, M. J., Editors, “Physical design automation of VLSI systems,” The Benjamin/Cummings Publishing Company, Inc., 1988.

[50]Raj, R. V., Murty, N. S., Nagendra Rao, P. S., Patnaik, L. M., “Effective heuristics for timing driven constructive placement,” in Proceedings of the 10th International Conference On VLSI Design, pp. 38-43, 1997.

[51]Rudell, R., “Logic synthesis for VLSI design,” Memorandum UCB/ERL M89/49, Ph.D. Dissertation, University of California at Berkeley, 1989.

[52]Salek, A. H., Lou, J., and Pedram, M., “A DSM design flow: putting floorplanning, technology mapping, and gate-placement together,” in Proceedings of the ACM/IEEE Design Automation Conf., pp. 128-133, 1998.

[53]Salek, A. H., Lou, J., and Pedram, M., “An integrated logical and physical design flow for deep submicron circuits,” IEEE Transactions On Computer-Aided Design of Integrated Circuits and Systems, Vol. 18, No. 8, pp. 1305-1315, 1999.

[54]Sato, K., Kawarabayashi, M., Emura, H., and Maeda, N., “Post-layout optimization for deep submicron design,” in Proceedings of the ACM/IEEE Design Automation Conf., pp. 740-745, 1996.

[55]Sentovich, E. M., Singh, K. J., Lavagno, L., Moon, C., Murgai, R., Saldanha, A., Savoj, H., Stephan, P. R., Brayton, R. K., and Sangiovanni-vicentelli, A., “SIS: a system for sequential circuit synthesis,” Electron. Res. Lab., Dept. of Elect. Eng., Comput. Sci., Univ. California, Berkeley, Memo. UCB/ERL M92/41, 1992.



[56]Seth, S. C., Pan, L., and Agrawal V. D., “PREDICT – probabilistic estimation of digital circuit reliability,” in Proceedings of the Fault-Tolerant Comput. Symp., pp. 220-225, 1985.

[57]Seth, S. C., Bhattacharya, B. B., and Agrawal V. D., “An exact analysis for efficient computation of random pattern testability in combinational circuits,” in Proceedings of the Fault-Tolerant Comput. Symp., 1986.

[58]Sherwani, N., “Algorithms for VLSI physical design automation,” 2nd ed., The Netherlands: Kluwer Academic, 1995.

[59]Stok, L., Iyer, M. A., and Sullivan, A. J., “Wavefront technology mapping,” in Proceedings of DATE, pp. 531-536, 1999.

[60]Su, H. P., Wu, C. H., and Lin, Y. L., “A timing-driven soft-macro placement and resynthesis method in interaction with chip floorplanning,” IEEE Transactions On Computer-Aided Design of Integrated Circuits and Systems, Vol. 18, No. 4, pp. 475-483, 1999.

[61]Sutanthavibul, S., and Shragowitz, E., “An adaptive timing-driven layout for high speed VLSI,” in Proceedings of the ACM/IEEE Design Automation Conf., pp. 90-95, 1990.

[62]Togawa, N., Yanagisawa, M., and Ohtsuki, T., “Maple-opt: a performance-oriented simultaneous technology mapping, placement, and global routing algorithm for FPGAs,” IEEE Transactions On Computer-Aided Design of Integrated Circuits and Systems, Vol. 17, No. 9, pp. 803-818, 1998.

[63]Touati, H. J., Moon, C. W., Brayton, R. K., and Wang, A., “Performance oriented technology mapping,” in Proceedings of the Sixth MIT Conference Advanced Res. VLSI, pp. 79-97, 1990.

[64]Tsay, Y. W., Lin, Y. L., “A row-based cell placement method that utilizes circuit structural properties,” IEEE Transactions On Computer-Aided Design of Integrated Circuits and Systems, Vol. 14, No. 3, pp. 393-397, 1995.

[65]Vaishnav, H., and Pedram, M., “Logic extraction based on normalized netlengths,” in Proceedings of the IEEE ICCD., pp. 658-663, 1995.

[66]Vardanian, V. A., “Exact probabilistic analysis of error detection for parity checkers,” in Proceedings of the 15th IEEE VLSI Test Symposium, pp. 222-227, 1997.

[67]Zhao, M., and Sapatnekar, S. S., “A new structural pattern matching algorithm for technology mapping,” in Proceedings of the ACM/IEEE Design Automation Conf., pp. 348-351, 2001.