臺灣博碩士論文加值系統

隨著深次微米技術快速的進展和個人攜帶式應用產品的普及，多處理器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.