跳到主要內容

臺灣博碩士論文加值系統

(3.231.230.177) 您好!臺灣時間:2021/08/02 10:34
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林庭瑜
研究生(外文):Lin, Ting-Yu
論文名稱:能源複雜度在平行演算法之評估模型及分析
論文名稱(外文):Investigation on the Energy Complexity of Parallel Algorithms
指導教授:王小璠王小璠引用關係
指導教授(外文):Wang, Hsiao-Fan
學位類別:碩士
校院名稱:國立清華大學
系所名稱:工業工程與工程管理學系
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
論文頁數:73
中文關鍵詞:能源複雜度時間複雜度複雜度平行演算法能量消耗
外文關鍵詞:Energy complexityTime complexityParallel algorithmEnergy consumption
相關次數:
  • 被引用被引用:0
  • 點閱點閱:151
  • 評分評分:
  • 下載下載:21
  • 收藏至我的研究室書目清單書目收藏:0
基於節約能源日益重要之趨勢,及各種攜帶型電子產品日漸普及卻始終受限於電池容量不足之需求,本研究提出了一個有系統且可行的能源複雜度估算模型,以期在一般熟知的時間及空間複雜度等評估演算法效率之基準外,提供一個可以針對演算法的能源消耗進行評估之模組。目的在於提供程式設計或演算法開發人員一個可以分析並比較演算法耗能的估算模型,進而選擇最適合且可達到最低能源消耗的決策,甚至可依循本模組進行程式之最低能量消耗設計,以因應環保議題逐被重視的未來,同時解決消費性電子產品使用時限不足之市場需求。本研究主要專注於執行平行演算法時的能量消耗探討,因其可利用處理器多工之特性,在不影響時間消耗的前提下得到最低能量消耗的需求,進而提供我們比較不同演算法能耗之依據。演算法執行時能源消耗主要來自四個層面:分別為處理器執行指令能耗、處理器傳遞訊息能耗、指令讀取記憶體能耗以及資料讀取記憶體能耗。透過有系統的計算,我們可以利用Big-O的表現方式求出在最佳數量的處理器下,演算法執行時所需的最少能量消耗。本研究分別以六個經典的演算法為例,實際示範並說明模型的可適性。最後,本研究也提出了驗證的方法,並透過此方法,證明本能源複雜度模型,在計算機處理器可負荷的工作範圍內,確實具有相當的準確度以評估演算法之能源消耗。
Due to the energy crisis, energy consumption from software computation has become an issue. This study investigates the factors affecting energy consumed from a parallel algorithm, and then provides the general measure of each factor together with a comparison with time complexity as normally adopted for measuring the complexity of an algorithm. With several experiments conducted, the proposed method is shown to be systematic, practical, and able to assist a system designer or software developer in estimating the energy consumption upon execution. Finally, we establish an approach to verifying the accuracy of the model. The results show that with the upper bound of the input size that a parallel processor can normally handle, the accuracy of the energy complexity model is ensured.
In this study, due to the reason that energy and time complexities will be indistinguishable in the case of sequential algorithms, we shall focus on the measure of energy complexity for parallel algorithms. Based on the proposed model, energy consumption upon execution mainly originates from four sources: (1) consumption by the processor during the execution of instructions, (2) consumption by the processor for data communication, (3) consumption by the memory storage while accessing instructions, and (4) consumption by the memory storage for data accessing. By progressive calculations, we can capitalize on the performance of the Big-O to obtain the lowest possible energy consumption subject to the optimal number of processors employed as a prerequisite. This research is based on six classical calculation models, and the feasibility of the models is affirmed by substantial practical experiments.

中文摘要 I
ABSTRACT II
ACKNOWLEDGEMENT III
TABLE CAPTIONS IV
FIGURE CAPTIONS VI
LIST OF NOTATIONS IX
CHAPTER 1 INTRODUCTION 1
1.1 Background and Motivation 1
1.2 Problem Statement 1
1.3 Organization of the Thesis 3
CHAPTER 2 LITERATURE REVIEW 4
2.1 Energy Complexity Models 4
2.2 Factors of Energy Consumption in Computation 7
2.2.1 Consumption from a Processor on Execution of the Instructions 7
2.2.2 Consumption from Processor on Data Communication 8
2.2.3 Consumption on Memory Storage on Instructions Accessing 8
2.2.4 Consumption on Memory Storage for Data Accessing 8
2.3 Relation Between Energy and Time Consumption- Time-Energy Cost Models 8
2.4 Summary and Conclusion 10
CHAPTER 3 ENERGY COMPLEXITY MEASURING MODEL 11
3.1 Problem Statement 11
3.2 Basic Assumptions 14
3.3 The Proposed General Energy Complexity Model 15
3.4 Discussion and Conclusion 19
CHAPTER 4 NUMERICAL EXAMPLES AND ANALYSIS 21
4.1 Numerical Examples of Classical Algorithms 21
4.1.1 LU Factorization 21
4.1.2 Simplex Method 25
4.1.3 Nelder–Mead Simplex Method 30
4.1.4 Interior Point Method 34
4.1.5 Quick Sort 39
4.1.6 Merge Sort 43
4.1.7 Summary of Energy Complexity of the Main Algorithms 47
4.2 Evaluation and Verification of the Model 49
4.2.1 Methodology of Verification 49
4.2.2 Results of Verification 51
4.2.2.1 LU Factorization 51
4.2.2.2 Simplex Method 56
4.2.2.3 Quick Sort 59
4.2.2.4 Merge Sort 61
4.3 Comparison with Time Complexity 63
4.3.1 Evidence of the Differences 64
4.3.2 Condition of the Same Order 64
4.4 Discussion and Conclusion 66
CHAPTER 5 CONCLUSION AND FURTHER STUDIES 67
REFERENCES 71

[1]. Bingham B. D. and M. R. Greenstreet, “Computation with energy-time trade-offs: Models, algorithms and lower-bounds,” in ISPA, p.143-152 (2008).
[2]. Chandrakasan A., R. Brodersen, “Low power digital CMOS design,” Kluwer Academic Publishers, Boston (1995).
[3]. Curtis-Maury M., A. Shah, F. Blagojevic, D. Nikolopoulos, B. de Supinski, and M. Schulz, “Prediction Models for Multi-dimensional Power-Performance Optimization on Many Cores,” in PACT, pp. 250-259 (2008).
[4]. Geist G. and C. Romine, “ LU Factorization Algorithms on Distributed- Memory Multiprocessor Architectures,” SIAM Journal on Scientific and Statistical Computing, vol. 9, p. 639 (1988).
[5]. Gondzio, J. and R. Sarkissian, “Parallel Interior Point Solver for Structured Linear Programs,” Mathematical Programming, 96(3), 561-584 (2003).
[6]. Gonzalez R. and M. A. Horowitz, “Energy dissipation in general purpose microprocessors,” IEEE Journal of Solid-State Circuits, vol. 31, p.1277-1284 (1995).
[7]. Henessy J.L., D.A.Patterson, “Computer architecture: A quantitative approach, ” Morgan Kaufman, San Mateo, CA (1990).
[8]. Jain R., D. Molnar, and Z. Ramzan, “Towards a model of energy complexity for algorithms,” In Wireless Communications and Networking Conference, vol. 3, pp. 1884-1890 (2005).
[9]. Klabjan, D., E. Johnson, G.L. Nemhauser, “A Parallel Primal-Dual Simplex Algorithm,” Operations Research Letters 27, 47-55 (2000).
[10]. Knuth D., The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, ISBN 0-201-89685-0. Pages 106–110 of section 5.2.2: Sorting by Exchanging. (1997).
[11]. Korthikanti V. A. and G. Agha, “Analysis of parallel algorithms for energy conservation in scalable multicore architectures,” in ICPP, pp. 212-219 (2009).
[12]. Korthikanti V. A. and G. Agha, “On the energy complexity of parallel algorithms,” International Conference on Parallel Processing (2011).
[13]. Martin A. J., “Towards an energy complexity of computation,” Information Processing Letters, vol. 39, p. 181-187 (2001).
[14]. Petersen, J. A. M., Bodson, M., “Constrained Quadratic Programming Techniques for Control Allocation,” IEEE Transactions on Control Systems Technology, Vol. 14, No. 1, pp. 91-98 (2006).
[15]. Potra F. A., R. Sheng, “A modified O(nL) infeasible-interior-point algorithm for LCP with quadratic convergence,” Reports on Computational Mathematics 54, Department of Mathematics, The University of Iowa, Iowa City, IA 52242, USA (1994).
[16]. Singer, S., and Singer, S, “Complexity analysis of nelder-mead search iterations,” Applied Mathematics and Computation, 185-196 (1999).
[17]. Tierno J.A., “An energy-complexity model for VLSI computations,” Ph.D. Thesis, California Institute of Technology (1995).
[18]. Tiwari V., S. Malik, A. Wolfe, “Power analysis of embedded software: A first step towards software power minimization,” IEEE Transactions on VLSI Systems, Vol. 2, pp. 437-445 (1994).
[19]. Wolfe P., “The simplex method for quadratic programming,” Econometrica, 27, p.382-398 (1959).
[20]. Zhao C. Y., “Parallel Quick sort algorithm With PVM optimization,” Parallel & Distributed Processing, pp.18-27 (1998).
[21]. Zotos K., A. Litke, A. Chatzigeorgiou, S. Nikolaidis, and G. Stephanides,“Energy complexity of software in embedded systems,” in Proc. IASTED Int. Conf. Autom., Control Appl. (ACIT-ACA), Novosibirsk, Russia,
Jun. 20-24 (2005).
[22]. Design and Analysis of Algorithm. (2012, March). Merge Sort [Web blog message].Retrieved from http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/mergeSort.htm
[23]. Wikipedia. (2012, April 2). Quick Sort [Online encyclopedia].Retrieved from http://en.wikipedia.org/wiki/Quick_sort
[24]. Wikipedia. (2012, April 6). Merge Sort [Online encyclopedia].Retrieved from http://en.wikipedia.org/wiki/Mergesort
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top