跳到主要內容

臺灣博碩士論文加值系統

(54.224.133.198) 您好!臺灣時間:2022/01/29 21:54
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:張雁翔
研究生(外文):Yen Hsiang Chang
論文名稱:在即時的多處理器SOC系統中考慮以基因的工作排程法來達到電量的最佳使用
論文名稱(外文):An Effective Task Scheduling Genetic Method of Power Aware Consideration for Real-Time Embedded Multiprocessor SOC Design
指導教授:陳正陳正引用關係
指導教授(外文):Cheng Chen
學位類別:碩士
校院名稱:國立交通大學
系所名稱:資訊工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
中文關鍵詞:工作排程基因演算法電量
外文關鍵詞:task schedulinggenetic algorithmpower awareSystem-on-Chip
相關次數:
  • 被引用被引用:0
  • 點閱點閱:207
  • 評分評分:
  • 下載下載:45
  • 收藏至我的研究室書目清單書目收藏:1
隨著深次微米技術快速的進展和個人攜帶式應用產品的普及,多處理器System-on-Chip(SOC)的架構將會是未來趨勢。因此,如何減少電量的消耗和資料的即時性成了一個重要的課題。而工作的排程在整個過程中是一個很關鍵的步驟。在本論文中,我們以基因演算法為基礎在不違反時間限制的狀況下找出消耗最少電量的工作排程。然而基因演算法需要大量的計算時間,因此我們在基因演算法上加入一些限制來建構我們的Constrained Genetic Method。除此之外,我們還應用了Divided-and-Conquer的技巧將整個工作流程,切成數個小流程使得Constrained Genetic Method可以單獨的處理這些被分割的工作流程以達到減少計算時間的效果。但是這樣的步驟卻會增加電量的消耗,因此我們在合併這些小的工作流程後,將會使用Power Minimization Method來減少合併後的電量消耗。我們會在接下來的本文中介紹我們演算法的詳細內容。

With the rapid evolution of submicron technology and the popularization of portable devices, embedded multiprocessor System-On-Chip (SOC) architecture will be one of the most attractive trends. How to decrease power consumption and process data in real-time is one of the most interesting topics to be investigated. The task scheduling is an important step through the whole process. In this thesis, we schedule tasks to obtain the minimal power consumption under time constraint, which is based on Genetic Algorithm. However, Genetic Algorithm needs huge computation time and therefore we propose an effective algorithm, named Constrained Genetic Method (CGM), by adding some constraints to Genetic Algorithm. Moreover, we partition the whole tasks graphs into several subgraphs to decrease computation time. But the total power consumption will increase after mergence process. Thus, we proposed a Power Minimization Method to decrease the total power consumption. The detail descriptions of our algorithm will be given in the contents.

Chapter 1 Introduction
Chapter 2 Fundamental Background and Related Works
2.1 System-on-Chip Overview
2.2 Related Work
2.3 Basic Principle of Genetic Algorithm
Chapter 3 Constraint Genetic Method
3.1 Problem Definition
3.2 Basic Terminology
3.3 Constrained Genetic Method
Chapter 4 Decrease Power Partition
4.1 Deadline Partition Technique
4.2 Subgraphs Mergence
4.3 Power Minimization Method
Chapter 5 Implementation of Our Simulation and Performance Evaluations
5.1 Implementation of Our Simulation
5.2 Performance Evaluations
Chapter 6. Conclusions and Future Work
6.1 Conclusions
6.2 Future Work
Bibliography
Appendix Ⅰ

[1] C. L, Liu and J. Layland, “Scheduling algorithm for multiprogramming in a hard-real-time enviroment” JACM, vol. 20, no. 1, Jan. 1973.
[2] D.E. Goldberg, “ Genetic Algorithms in Search, Optimization, and Distributed Systems ” , vol. 5 , 1994.
[3] J.J. Holland , “Adaptation in Natural and Artificial Systems .” Amm Arbor , Micj. : Univ. of Michigan Press , 1975.
[4] T.M. Nabhan and A.Y. Zomaya , “ A Parallel Computing Engine for a Class of Time Critical Processes ” IEEE Trans. Systems , Man , and Cybernetics , part B , vol. 27 , no. 25, pp. 774-786 , 1997.
[5] P. Hansen and B. Jaumard , “ Lipschitz Optimization ” Handbook of Global Optimization , R. Horst and P.M. Pardalos, eds., pp.407-493. The Netherlands: Kluwer Academic Publishers , 1995.
[6] R. Henn , “Antwortzeitgesteuerte prozessorzuteilung unter strengen zeitbedingungen” Computing , vol. 19, 1978, pp.209-220.
[7] M. Garey and D. Johnsom , “Two-processor scheduling with start-time and deadlines” SIAM J. Comput. ,vol. 6 1977 , pp.416-426.
[8] M. L. Dertouzos and A. K. Mok , “Multiprocessor On-Line Scheduling of Hard-Real-Time Tasks” IEEE Transactions on Software Engineering , vol. 15 , no.12, Dec. 1989.
[9] M. Coli and P. Palazzari , “A New Method for Optimization of Allocation and Scheduling in Real Time Applications” 7th Euromicro Workshop on Real-Time Systems , 1995.
[10] J. Aguilar , and E. Gelenbe , “Task Assignment and Transaction Clustering Heuristics for Distributed Systems” Information Sciences , Vol. 97 , March 1997 , pp. 199-219.
[11] C. A. Coello , “An Empirical study Of Evolutionary Techniques For Multiobjective Optimization In Engineering Design” , Ph. D. Thesis , Tulane University , 1996.
[12] Oh, J.; Bahn, H.; Wu, C.; Koh, K. “Pareto-based soft real-time task scheduling in multiprocessor systems” Software Engineering Conference, 2000. APSEC 2000. Proceedings. Seventh Asia-Pacific , 2000 pp.24 —28.
[13] Dick, R.P.; Jha, N.K. “MOGAC: a multiobjective genetic algorithm for hardware-software cosynthesis of distributed embedded systems” Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on , Vol. 17 1998 pp. 920 —935.
[14] D.E Goldberg, “Genetic Algorithm in Search, Optimization, and Machine Learning. Reading”, Mass: Addison-Wesley, 1989.
[15] White, N.R. “Moore's law: implications for ion implant equipment an equipment designer's perspective” Ion Implantation Technology. Proceedings of the 11th International Conference on , 1997 Page(s): 355 —359.
[16] Lyonnard, D.; Yoo, S.; Baghdadi, A.; Jerraya, A.A. “Automatic generation of application-specific architectures for heterogeneous multiprocessor system-on-chip” Design Automation Conference, 2001. Proceedings, 2001 Page(s): 518 —523.
[17] Kreutz, M.E.; Carro, L.; Zeferino, C.A.; Susin, A.A. “Communication architectures for system-on-chip” Ingegrated Circuits and Systems Design, 2001, 14th Symposium on. , 2001 Page(s): 14 —19.
[18] Salvini, A.; Fulginei, F.R. “Genetic algorithms and neural networks generalizing the Jiles-Atherton model of static hysteresis for dynamic loops” Magnetics, IEEE Transactions on , Volume: 38 Issue: 2 Part: 1 , Mar. 2002 Page(s): 873 —876.
[19] Chen, C.-C.; Wong, C.-C. “Self-generating rule-mapping fuzzy controller design using a genetic algorithm” Control Theory and Applications, IEE Proceedings- , Volume: 149 Issue: 2 , Mar 2002 Page(s): 143 —148.
[20] Yen-Wei Chen; Mendoza, N.; Uehara, S.; Nakao, Z.; Adachi, T.; Masuda, Y. “Estimating wind speed in lower atmosphere wind profiler based on genetic algorithms” Instrumentation and Measurement Technology Conference, 2001. IMTC 2001. Proceedings of the 18th IEEE , Volume: 2 , 2001 Page(s): 1258 -1263 vol.2.
[21] C.M. Fonseca and P.J. Fleming, “Multiobjective genetic algorithms mad easy: Selection, sharing and mating restrictions” in Proc. Genetic Algorithms in Engineering Systems: Innovations and Applications, Sept. 1995, pp. 45-52.
[22] Carlos M. Fonseca and Peter J. Fleming “Genetic algorithms for multiobjective optimization: Formulation, discussion and generalization” in Proc. Int. Conf. Genetic Algorithm, July 1993, pp. 416-423.
[23] D. Culler, J. P. Singh, and A. Gupta. “Parallel Computer Architecture: A Hardware/Software Approach.” Morgan Kaufmann Publishers, Aug. 1998.
[24] Hyunok Oh; Soonhoi Ha “A Hardware-Software Cosynthesis Technique Based on Heterogeneous Multiprocessor Scheduling” Hardware/Software Codesign, 1999. (CODES '99) Proceedings of the Seventh International Workshop on , 1999 Page(s): 183 —187.
[25] R.P. Dick, D.L. Rhodes, and W.Wolf, “TGFF: Task Graphs for Free” Proc. Int’l Workshop Hardware/Software Codesign, IEEE CS Press, Los Alamitos, Calif., 1998, pp. 97-101.
[26] T.Y. Yen, “Hardware-software cosynthesis of distributed embedded systems” Ph.D dissertation, Dept. Electrical Engineering, Princeton Univ., Princeton, NJ, June 1996.
[27] J. Hou and W. Wolf, “Process partitioning for distributed embedded systems” in Proc. Int. Workshop Hardware-Software Codesign, Mar. 1996, pp288-294.
[28] Silcott, G.; Wilson, J.; Peterson, N.; Peisel, W.; Kroekar, K.L. “SOCs drive new product development “ Computer , Volume: 32 Issue: 6 , June 1999
Page(s): 61 —66.
[29] De Man, H. “System-on-chip design: impact on education and research” IEEE Design & Test of Computers , Volume: 16 Issue: 3 , July-Sept. 1999
Page(s): 11 —19.
[30] Edwin S. H. Hou, Nirwan Ansari, and Hong Ren. “A Genetic Algorithm for Multiprocessors Scheduling” IEEE Transactions On Parallel And Distributed Systems. Vol. 5. Feb 1994.
[31] Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest., Introduction to Algorihtms, McGraw-Hill Book Company Twentieth printing 1998.
[32] T. C. Hu, “Parallel sequencing and assembly line problems” Operations Research, no. 9, pp. 841-848, 1961.
[33] Albert Y. Zomaya “Genetic Scheduling for Parallel Processor Systems: Comparative Studies and Performance Issues” IEEE Transactions on Parallel And Distrubuted Systems, Vol. 10. No. 8, Aug 1999.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 張群昌,「多角化經營─面對台灣變動紛擾的醫療環境醫療院所生存與發展之心力器(下)」,醫院,1995年10月,Vol.28,No.5,p32-38。
2. 張群昌,「多角化經營─面對台灣變動紛擾的醫療環境醫療院所生存與發展之心力器(下)」,醫院,1995年10月,Vol.28,No.5,p32-38。
3. 楊萬發、黃錦明,「醫療廢棄物處理現況與問題探討」,厚生雜誌發行,2000年,12月第12期。
4. 楊萬發、黃錦明,「醫療廢棄物處理現況與問題探討」,厚生雜誌發行,2000年,12月第12期。
5. 潘大永、陳金亮,「台灣地區醫院事業廢棄物之處理現況調查」,嘉南學報,1997年,Vol.23.p96-107。
6. 潘大永、陳金亮,「台灣地區醫院事業廢棄物之處理現況調查」,嘉南學報,1997年,Vol.23.p96-107。
7. 林敏雄,「醫療廢棄物處理與合作社」,合作發展,1998年1月,p26-32。
8. 林敏雄,「醫療廢棄物處理與合作社」,合作發展,1998年1月,p26-32。
9. 黃明聖、鄭惠中,「感染性醫療廢棄物清除處理機構費率訂定之言議」,經社法制論叢,第21期,1998年,p311-346。
10. 黃明聖、鄭惠中,「感染性醫療廢棄物清除處理機構費率訂定之言議」,經社法制論叢,第21期,1998年,p311-346。
11. 符樹強,醫療廢棄物管理,研考雙月刊,1998年10月,Vol.22,No.5,p100-104。
12. 符樹強,醫療廢棄物管理,研考雙月刊,1998年10月,Vol.22,No.5,p100-104。
13. 劉美芳、許雅汶、蔡春梅、劉有增、施智源,「醫療廢棄物管理」,院內感染控制雜誌,2000年12月,Vol.10,No.6,p381-392。
14. 劉美芳、許雅汶、蔡春梅、劉有增、施智源,「醫療廢棄物管理」,院內感染控制雜誌,2000年12月,Vol.10,No.6,p381-392。