請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/22663
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 郭斯彥 | |
dc.contributor.author | Jung-Hung Weng | en |
dc.contributor.author | 翁榮鴻 | zh_TW |
dc.date.accessioned | 2021-06-08T04:23:53Z | - |
dc.date.copyright | 2010-07-21 | |
dc.date.issued | 2010 | |
dc.date.submitted | 2010-06-24 | |
dc.identifier.citation | [1] P. Gronowski, W. j. Bowhill, R. P. Preston, M. K. Gowan, R. L. Allmon, “High-Performance Microprocessor Design”, IEEE Journal of Solid-State Circuits, Vol. 33, No. 5, pp. 676-686, May 1998.
[2] D. R Gonzales, “Micro-RISC Architecture for the Wireless Market”, IEEE Micro, Vol. 19, No. 4 pp. 30-37, July 1999. [3] F. Anderson, S. Wells, and E. Berta, “The core clock system on the next generation Itanium microprocessor”, ISSCC Dig. Tech. Papers, pp. 146-147, February 2002. [4] D. Duarte, V. Narayanan, M. J. Irwin, “Impact of Technology Scaling in the Clock system Power”, IEEE Computer Society Annual Symposium on VLSI, pp. 52-57, Pittsburgh, PA, April 2002. [5] Faraday Technology Corporation, http:://www.faraday-tech.com/index.html. [6] Balas E, Padberg M, “Set partitioning: a survey”, SIAM Review, vol. 18, No.4, pp.710-760, October 1976. [7] I. Gershkoff, “Optimizing flight crew schedules”, Interface, vol. 19, pp. 29-43, 1989. [8] R. Marsten and F. Shepardson, “Exact solutions of crew scheduling problems using the set partitioning model: recent successful applications”, Networks, 11, 1981. [9] Marsten R, Shepardon F., “Exact solution of crew Scheduling Problem using the set partitioning model: recent successful applications”, Networks, vol. 11, pp.165-77, 1981. [10] Hoffman K, Padberg M. Solving, “Solving airline crew scheduling problems by branch and cut”, Management Science, vol. 39, No. 6, pp. 657-682, 1993. [11] Elhallaoui ID, Villeneuve, Soumis F, Desaulniers G, “Dynamic aggregation of set-partitioning constraints in column generation”, Operations Research, vol. 53, no.4, pp. 632-645, July 2005. [12] F. Harche and G.L. Thompson, “The column subtraction algorithm: an exact method for solving weighted set covering, packing and partitioning problems”, Computers & Operations Research, vol. 21, issue 6, pp. 689-705, July 1994. [13] PC Chu, JE Beasley, “Constraint handling in genetic algorithms: the set partitioning problem”, Journal of Heuristics, vol. 4, no. 4, pp. 323-357, November, 1998. [14] Jiah-Shing Chen, Yao-Tang Lin, and Liang-Yu Chen, “A relation-base genetic algorithm for partitioning problems with applications”, Lecture Notes in Artificial Intelligence (IEA/AIE 2007), 4570, pp. 217-226, 2007. [15] James P. Kelly, Jiefeng Xu, “A set-partitioning-based heuristic for the vehicle routing problem”, INFORMS journal on Computing archive, vol. 11, no. 2, pp. 161-172, 1999. [16] Broderick Crawford, and Carlos Castro, “Integration lookahead and post processing procedures with ACO for solving set partitioning and covering problems,” ICAISC 2006. LNCS (LNAI), vol. 4029, pp.1082-1090, 2006. [17] Uriel Feige, “A threshold of ln n for approximating set cover,” Journal fo the ACM (JACM), vol. 45, issue 4, pp. 634-652, July 1998. [18] M. Pan, N. Viswanathan, and C. Chu, “An Efficient and Effective Detailed Placement Algorith,” in Proc. IEEE/ACM Int. Conf. on Computer-Aided Design, pp. 48-55, 2005. [19] Niklaus Wirth, Algorithms + Data structures = Programs, Prentice Hall PTR Upper Saddle River, pp. 84, 1978. [20] Mentor Graphics, “Low-Power Physical Design with Olympus-Soc”, http://www.mentor.com/. [21] Y. Cheon, P.-H. Ho, A.B. Kahng, S. Reda and Q. Wang, “Power-aware placement,” In Proc. ACM/IEEE DAC, pp. 795-800, 2005. [22] Joseph O’Rourke, Computational Geometry in C, Cambridge University, pp 166, 1994. [23] Jason Cong, Andrew B. Kahng, Cheng-Kok Koh, C.-w. Albert Tsao, “Bounded-skew clock and Steiner routing”, ACM Transactions on Design Automation of Electronic System (TODAES), vol. 3, issue 3, pp. 341-388, July 1998. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/22663 | - |
dc.description.abstract | 近年來便攜式設備的興起,低功率電路設計成為現今設計中最被注目的問題。由先前的設計經驗得知,時鐘樹為整體電路中最為消耗功率的元件之一,降低時鐘樹的消耗功率可以有效的降低整體的消耗功率。因此,許多關於低功率時鐘樹的設計一一被提出。
另外,隨著製程的日益先進,最小的反相器已不止能驅動一個單一位元正反器。因此,多個單一位元正反器分享同一驅動,也就是使用多位元正反器,將可有效的減少反相器的使用,進而減少整體使用在其上的功率及面積。另一方面,亦可有效的縮小時鐘樹的總線長,進而亦降低時鐘樹的消耗功率。 本論文所提出之演算法,可使設計功率有效降低。其中包含正反器功率節省平均約23%,時鐘樹功率節省平均約48%。另外,本演算法用於合併兩百萬個正反器最快不到一個小時就能完成,整體實驗時間複雜度為Θ(n1.052),比Θ(nlogn)的實驗時間複雜度Θ(n1.09)較為小。因此為一有效率之演算法。 | zh_TW |
dc.description.abstract | In the recent years, low-power circuit design has become the most concerned issue in today’s design problems due to the popularity of the portable devices. From the previous design experience, the clock tree is one of the most power consumption components of the whole design. Reducing the power consumption of the clock tree can effectively reduce the overall power consumption. Therefore, many techniques on low-power clock tree design have been proposed.
In addition, with increasingly sophisticated manufacturing process, the smallest inverter usually can drive more than a 1-bit flip-flop. Therefore, several 1-bit flip-flops can share the same drive, that is, the multi-bit flip-flops. It will effectively reduce the use of inverter, thereby reducing the overall power consumption and chip area. On the other hand, it can also effectively reduce the clock tree wire length, and thus also reduce the clock tree power consumption. The algorithm in this work can effectively reduce the total power of the designs. The power saving includes the flip-flops power saving, about 23%, and clock tree power saving, about 48%. On the other hand, merging 2,000,000 flip-flops with this algorithm can be achieved in least than 1 hour. The empirical time complexity of the algorithm is Θ(n1.052) which is less than the empirical time complexity of Θ(nlogn) time complexity algorithm. | en |
dc.description.provenance | Made available in DSpace on 2021-06-08T04:23:53Z (GMT). No. of bitstreams: 1 ntu-99-R97943148-1.pdf: 3335566 bytes, checksum: b59ba5ed84f2a55c237ddc431f4a6872 (MD5) Previous issue date: 2010 | en |
dc.description.tableofcontents | 口試委員會審定書 #
誌謝 ii 中文摘要 iii ABSTRACT iv CONTENTS v LIST OF FIGURES vii LIST OF TABLES ix Chapter 1 Introduction 1 1.1 Clock Tree 3 1.2 Low-Power Clock Tree Synthesis 5 1.2.1 Multi-Voltage Design 5 1.2.2 Clock Gating 7 1.2.3 Register Clumping 8 1.3 Contribution 9 1.4 Thesis Organization 9 Chapter 2 Problem Formulation 10 2.1 Problem Definition 10 2.2 Problem Constraints 11 2.3 Problem Assumptions 13 2.4 Example 14 Chapter 3 Algorithm 16 3.1 Minimizing Total Power Consumption 17 3.1.1 Flip-Flop Location Region 17 3.1.2 Flip-Flop Location Region Intersections 19 3.1.3 Flip-Flop Merge Selection 20 3.1.4 Set Partitioning Problem 22 3.1.5 Flip-Flop Merge Selection Algorithm 23 3.1.6 Reorder Original Flip-Flops 25 3.2 Minimizing Total Signal Wire Length 27 3.2.1 Minimum Wire Cost Location 27 3.2.2 Exchanging the Component Flip-Flops 29 3.3 Removing Density Constraint Violations 35 Chapter 4 Experimental Results 37 Chapter 5 Conclusion and Future Works 46 REFERENCES 47 | |
dc.language.iso | en | |
dc.title | 使用多位元正反器以節省時脈功率 | zh_TW |
dc.title | Using Multi-Bit Flip-Flops for Clock Power Saving | en |
dc.type | Thesis | |
dc.date.schoolyear | 98-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 雷欽隆,顏嗣鈞,呂學坤,袁世一 | |
dc.subject.keyword | 低功率設計,時鐘樹,正反器, | zh_TW |
dc.subject.keyword | Low-Power Design,clock-tree,flip-flop, | en |
dc.relation.page | 50 | |
dc.rights.note | 未授權 | |
dc.date.accepted | 2010-06-25 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf 目前未授權公開取用 | 3.26 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。