臺灣博碩士論文加值系統

　　在本論文中提出一個暫存器轉移級的分割演算法，以及探討其對於在資料導向電路設計上，硬體線路功率消耗的影響程度。此分割演算法將資料流程圖內的功能運算子節點劃分成幾個群集，且使得群集之間的訊號傳輸數量較少，以達成資料傳輸區域化目標。然而，硬體資源共享分配可能會造成群集之間的訊號傳輸數量增加，破壞了資料傳輸區域化的目標。我們所提出的分割演算法名稱叫RS-Partitioning，可以同時執行硬體資源共享和高階層運算分割，並把資料區域化考量進來。我們的高階層分割演算法把硬體資源共享納入可以去避免破壞資料區域化。經過分割和硬體資源分配後的資料路徑電路設計，將保有資料區域化，可以降低會消耗大量功率之廣域硬體線路的使用率。此外，分割演算法將使得分割過的資料流程圖較容易抓取規則性，也就能造成硬體線路上的簡化。因此，分割演算法使資料路徑電路保有資料區域性可以降低硬體線路上的功率消耗。而從經驗結果得知，使用我們所提出的方法可以分別在2分割和4分割方式上，達到平均28.5 %和34.2 %的硬體線路功率消耗。

　In this thesis, we present a register transfer level partitioning algorithm and discuss the impact of interconnect power consumption in a data-dominated design. The partitioning divides the functional operation nodes of data flow graph into several groups that have less inter-cluster communication for preserving data locality. However, resource sharing may increase inter-cluster communication and destroy data locality on the physical level. The proposed partitioning algorithm called RS-Partitioning performs resource sharing and high-level partitioning simultaneously under consideration of data locality. Our high-level partitioning takes resource sharing into account to avoid destroying data locality. Partitioned and allocated datapath design that preserves data locality can reduce the number of access of power hungry global wires. Besides, partitioning makes the partitioned data flow graph easier to get regularity that results in simplifying the structure of interconnects. Therefore, partitioning with data locality can reduce interconnect power consumption, and from experimental results our approach can achieve 28.5% and 34.2% interconnect power reduction on average for 2-way and 4-way partitions, respectively.

TABLES OF CONTENTS
Chapter 1 Introduction.......................1
1.1 Introduction.............................1
Chapter 2 Background.........................9
2.1 Background...............................9
Chapter 3 Interconnect Power................17
3.1 Interconnect Power......................17
3.2 Literature Survey.......................17
3.3 Interconnect Power Model................20
3.3.1 Local Interconnect Power Modeling.....20
3.3.1.1 Steering Logics.....................21
3.3.1.2 Local Wires.........................22
3.3.2 Global Interconnect Power Modeling....23
3.3.2.1 Global Wires........................24
3.3.2.2 Repeaters...........................26
Chapter 4 Proposed Partitioning Algorithm...28
4.1 RS-Partitioning Algorithm...............28
4.2 Preliminary.............................28
4.3 Procedures..............................36
4.3.1 ASAP/ALAP.............................37
4.3.2 RS-Scheduling Algorithm...............39
4.3.3 RS-Partitioning Algorithm.............44
4.3.3.1 First Phase – Clustering...........46
4.3.3.2 Second Phase – Partitioning........59
4.3.3.3 Register Allocation/Assignment......62
Chapter 5 Experimental Results..............64
5.1 Test Cases..............................64
5.2 Results.................................64
Chapter 6 Conclusions and Future Work.......72
6.1 Conclusions.............................72
6.2 Future Work.............................73
References...................................74

References

[1] Jan M. Rabaey, “Digital integrated circuits: a design perspective,” Prentice-Hall, Inc., Upper Saddle River, NJ, 1996

[2] G. Chandra, P. Kapur, and K. C. Saraswat, “Scaling trends for the on chip power dissipation,” Proceedings of the IEEE 2002 International Interconnect Technology Conference, pp. 170-172, June 2002.

[3] K. Banerjee and A. Mehrotra, “Power dissipation issues in interconnect performance optimization for sub-180 nm designs,” Symposium on VLSI Circuits Digest of Technical Papers, pp. 12-15, June 2002.

[4] N. Magen, A. Kolodny, U. Weiser, and N. Shamir, “Interconnect-power dissipation in a microprocessor,” Proceedings of the 2004 international workshop on System level interconnect prediction, session: Interconnect analysis for SoCs and microprocessors, pp. 7-13, February 2004.

[5] Z. Hui and J. Rabaey, “Low-swing interconnect interface circuits,” Proceedings of the 1998 international symposium on Low power electronics and design, pp. 161-166, August 1998.

[6] H. Yamauchi, H. Akamatsu, and T. Fujita, “An asymptotically zero power charge-recycling bus architecture for battery-operated ultrahigh data rate ULSI's,” IEEE J. Solid-State Circuits, vol. 30 , issue 4, pp. 423-431, April 1995.

[7] P. P. Sotiriadis, T. Konstantakopoulos, and A. Chandrakasan, “Analysis and implementation of charge recycling for deep sub-micron buses,” International Symposium on Low Power Electronics and Design, pp. 364-369, August 2001.

[8] M. R. Stan and W. P. Burleson, “Bus-invert coding for low-power I/O,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol 3, issue 1, pp. 49 – 58, March 1995.

[9] M. R. Stan and W. P. Burleson, “Low-power encodings for global communication in CMOS VLSI,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 5, issue 4, pp. 444-455, December 1997.

[10] U. Narayanan, H.W. Leong, K. S. Chung, and C. L. Liu, “Low power multiplexer decomposition,” Proceedings of Low Power Electronics and Design on 1997 International Symposium, pp. 269-274, August 1997.

[11] J. Pangjun and S. S. Sapatnekar, “Low-power clock distribution using multiple voltages and reduced swings,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 10, issue 3, pp. 309-318, June 2002.

[12] J. M. Rabaey, L. Guerra, and R. Mehra, “Design guidance in the power dimension,” Proceedings of. International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2837- 2840, May 1995.

[13] R. Mehra, L. Guerra, and J. M. Rabaey, “Low-power architectural synthesis and the impact of exploiting locality,” J. VLSI Signal Processing Syst., vol. 13, no. 2/3, pp. 239-258, Aug.–Sept. 1996.

[14] R. Mehra, L. M. Guerra, J. M. Rabaey, “A partitioning scheme for optimizing interconnect power,” Solid-State Circuits, IEEE Journal of, vol. 32, issue 3, pp. 433 – 443, March 1997.

[15] Giovanni De Micheli, “Synthesis and optimization of digital circuits,” McGraw Hill, New York, 1994.

[16] K. Roy and S. Prasad, “Low-Power CMOS VLSI Circuit Design,” John Wiley & Sons, Inc., 2000.

[17] Charles J. Alpert and Andrew B. Kahng, “Recent directions in netlist partitioning: a survey,” Integration, the VLSI Journal, vol. 19, issue 1-2, pp. 1-81, August 1995.

[18] Frank M. Johnnes, “Partitioning of VLSI circuits and systems,” Proceedings of the 33st ACM/IEEE Design Automation Conference, pp. 83–87, June 1996.

[19] Jason Cong, Sung Kyu Lim, “Performance driven multi-level and multi-way partitioning with retiming,” Proc. 2000 Design Automation Conference, pp. 274-279, June 2000.

[20] Ling Wang and Henry Selvaraj, “Performance driven circuit clustering and partitioning,” Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC), pp. 352-254, April 2002.

[21] Hirendu Vaishnav and Massoud Pedram, “Delay optimal partitioning targeting low power VLSI circuits,” In International Conference on Computer Aided Design (ICCAD), pp. 216-222, November 1995.

[22] S. Govindarajan, V. Srinivasan, P. Lakshmikanthan, and R. Vemuri, “A technique for dynamic high-level exploration during behavioral-partitioning for multi-device architectures,” Proceedings of the 13th International Conference on VLSI Design, pp. 212-219, January 2000.

[23] Y. Fei and N. K. Jha, “Functional partitioning for low power distributed systems of system-on-a-chip,” Proceedings of ASP-DAC 2002, pp. 274-281, Jan. 2002.

[24] E. D. Lagnese and D. E. Thomas, “Architectural partitioning for system level synthesis of integrated circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 10, issue 7, pp. 847-860, July 1991.

[25] Y. Chen, Y. Hsu, and C. King, “MULTIPAR: behavioral partition for synthesizing multiprocessor architectures,” IEEE Trans. VLSI Systems, vol. 2, no. 1, pp. 21-32, Mar. 1994.

[26] B. W. Kernighan and S. Lin, “An efficient heuristic procedure for partitioning graphs,” Bell Systems Technology J., vol. 49, no. 2, pp. 292-370, February 1970.

[27] C. M. Fiduccia and R. M. Mattheyses, “A linear-time heuristic for improving network partitions,” Proceedings of 19th Design Automation Conference, pp. 175-181, June 1982.

[28] B. Krishnamurthy, "An improved min-cut algorithm for partitioning VLSI networks," IEEE Transactions on Computers, Vol. C-33, No. 5, pp. 438-446, May 1984.

[29] S. Kirkpatrick, C. D. Gelatt, Jr., and M. P. Vecchi, “Optimization by simulated annealing,” Science 220, pp. 671-680, May 1983.

[30] K. M. Hall, “An r-dimensional quadratic placement algorithm,” Management Science, vol. 17, pp. 219-229, November 1970.

[31] M. Stoer and F. Wagner, “A simple min-cut algorithm,” Journal of the ACM, vol. 44, issue 4, pp. 585-591, July 1997.

[32] G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, “Multilevel hypergraph partitioning: applications in VLSI domain,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 7, issue 1, pp. 69-79, March 1999.

[33] E. Hwang, F. Vahid, and Y. C. Hsu, “FSMD functional partitioning for low power,” Proceedings of the conference on Design, automation and test in Europe, pp. 22-28, January 1999.

[34] L. Wang, Y. Jiang, H. Selvaraj, “A synthesis scheme for low power designs with multiple voltages under timing constraints,” Proc. NASA 11th VLSI Symp., 2003.

[35] L. Wang, Y. Jiang, H. Selvaraj, “Synthesis scheme for low power designs with multiple supply voltages by heuristic algorithms,” proceedings of International Conference on Information Technology: Coding and Computing, ITCC 2004, vol. 2, pp. 826-830, 2004.

[36] L. Wang, Y. Jiang, H. Selvaraj, “Synthesis scheme for low power designs with multiple supply voltages by tabu search,” proceedings of the 2004 International Symposium on Circuits and Systems, ISCAS '04, vol. 5, pp. 261-264, May 2004.

[37] K. M. Büyükşahin and F. N. Najm, “High-level power estimation with interconnect effects,” Proceedings of the 2000 international symposium on Low power electronics and design, pp. 197-202, July 2000.

[38] D. Stroobandt, H. V. Marck, and J. V. Campenhout, “An accurate interconnection length estimation for computer logic,” In Proc. IEEE 6th Great Lakes Symposium on VLSI, pp. 50-55, March 1996.

[39] J. A. Davis, V. K. De, and J. D. Meindl, “A stochastic wire-length distribution for gigascale integration (GSI)- Part I: derivation and validation,” IEEE trans. Electron Devices, vol. 45, no. 3, pp. 580-589, Mar.1998.

[40] J. A. Davis, V. K. De, and J. D. Meindl, “A stochastic wire-length distribution for gigascale integration (GSI)- Part II: applications to clock frequency, power dissipation, and chip size estimation,” IEEE trans. Electron Devices, vol. 45, no. 3, pp. 590-597, Mar.1998.

[41] P. Gupta, L. Zhong, and N. K. Jha, “A high-level interconnect power model for design space exploration,” in Proc. IEEE/ACM Int. Conf. on Computer-Aided Design (ICCAD), pp. 551-559, Nov. 2003.

[42] P. Christie and D. Stroobandt, “The interpretation and application of Rent’s rule,” IEEE trans. On VLSI Systems, Special Issue on System-Level Interconnect Prediction, pp. 639-648, December 2000.

[43] P. Zarkesh-Ha, J. A. Davis, and J. D. Meindl, “Prediction of net-length distribution for global interconnects in a heterogeneous system-on-a-chip,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 8, no. 6, pp. 649-659, December 2000.

[44] P. Zarkech-Ha, J. A. Davis, W. Loh, and J. D. Meindl, “On a pin versus gate relationship for heterogeneous systems: heterogeneous Rent’s rule,” in IEEE Custom Integrated Circuit Conf., pp. 93-96, May 1998.

[45] R. Mehra and J. M. Rabaey, “Behavioral level power estimation and exploration,” Proceedings of the International Workshop on Low-Power Design, pp. 187-202, April 1994.

[46] P. Kapur, G. Chandra, and K. C. Saraswat, “Power estimation in global interconnects and its reduction using a novel repeater optimization methodology,” in Proc. Design Automation Conf., pp. 461-466, June 2002.

[47] H. B. Bakoglu, “Circuits, interconnections and packaging for VLSI,” Addison-Wesley, 1990.

[48] C. J. Tseng and D. Siewiorek, “Automation synthesis of data paths in digital systems,” IEEE transaction on CAD/ICAS, vol. CAD-5, No. 3, pp. 379-395, July 1986.

[49] F. J. Kurdahi and A. C. Parker, “REAL: a program for Register Allocation,” proceedings of the 24th ACM/IEEE conference on Design Automation, pp. 210-215, July 1987.