臺灣博碩士論文加值系統

新興的異質多核心系統提供良好的計算能力，並且在近年來已成為主流的計算系統之一。但是我們發現到，在這種異質多核心系統中存在一種資源競爭的問題。為了解決這個問題，我們利用全域資源的管理方法來管理異質多核心系統上所有可用來計算的資源。
而資源管理則需要一個有效的演算法來管理計算資源。因此我們在這篇論文中研究並比較了三種演算法。我們發現，min-min演算法是這三種演算法中可以提供最短的系統完成時間，但min-min演算法在平均往返時間上很高。
為了解決這個問題，我們以min-min演算法為基礎，同時加入老齡化技術，提出了一種新方法稱為MMA演算法，MMA演算法是被設計用來減少平均往返時間。我們實作了一個模擬器來評估四種演算法的表現，其中包括了MMA算法，min-min演算法，max-min演算法和MET演算法。從實驗的結果顯示，min-min演算法仍具有最短的系統完成時間，但MMA算法只分別在第一種類型的測試中落後min-min演算法約1.5％，在第二種類型的測試案例中所落後的比例介於0.4％和6.6％。但MMA演算法提供的平均往返時間則是最短的，在所有類型的測試案例中勝過其他三種算法約20％。
 

Emerging heterogeneous multi-core systems provide good computing power and have
become the mainstream of computing systems. However, we notice that there is a resource contention problem in the heterogeneous multi-core systems. To solve this problem, we exploited a global resource management method to manage the heterogeneous computing resources in a system. The resource manager needs an efficient algorithm to manage the resources. We compared three algorithms in this Thesis and we found out that the min-min algorithm gives the shortest makespan among these algorithms but the average turnaround time is high. To solve this problem, we proposed a new method called MMA based on the idea of the min-min algorithm, while adding an aging technique, which is used to decrease the average turnaround time. We implemented a simulator to evaluate the performance of four algorithms, including the MMA algorithm, the Min-min algorithm, the Max-min algorithm, and the MET algorithm. Experiments show that the Min-min algorithm still has the shortest makespan, but the MMA algorithm is only left behind by about 1.5% in the first type of test cases and by the range between 0.4% and 6.6% in the second type of test cases. The MMA algorithm gives the shortest average turnaround time in all test cases and supercedes other three algorithms by 20%.

1 Introduction 2
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 RelatedWork 8
2.1 Open Computing Language . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.1 OpenCL Platform Model . . . . . . . . . . . . . . . . . . . . . . . 9
2.1.2 OpenCL Execution Model . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Heterogeneous Computing Framework . . . . . . . . . . . . . . . . . . . . 12
2.3 Heterogeneous Task Scheduling and Mapping Algorithms . . . . . . . . . 14
3 Preliminaries 17
3.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.1.1 Target Heterogeneous Multi-core Systems . . . . . . . . . . . . . . 17
3.1.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1.3 Centralized Task Scheduler . . . . . . . . . . . . . . . . . . . . . . 19
3.2 The Age of an Application . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3 Problem Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4 Dynamic Application Scheduling on Heterogeneous Multi-Core Systems 24
4.1 The Scheduling Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2 Scenarios of the Proposed Approach . . . . . . . . . . . . . . . . . . . . . 26
5 Experiments 36
5.1 Experimenting Environment . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.2 Comparative Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.3 Test Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.4 Experiment Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.4.1 The Test Cases with Different Ranges of Arrival Time . . . . . . . 41
5.4.2 The Test Cases with Different Numbers of Compute Devices . . . . 44
5.5 Conclusions on the Experiment Results . . . . . . . . . . . . . . . . . . . 47
6 Conclusions and Future Work 51
Bibliography 53

[1] NVIDIA Corporation. OpenCL Programming Guide for the CUDA Architecture, 3.2
edition, Auguest 2010.
[2] Aaftab Munshi. The OpenCL Specification. Khronos OpenCL Working Group, 1.1
edition, September 2010.
[3] Advanced Micro Devices, Inc. AMD Accelerated Parallel Processing (APP) SDK
OpenCLTMProgramming Guide, 1.2c edition, April 2011.
[4] V´ıctor J. Jim´enez, Llu´ıs Vilanova, Isaac Gelado, Marisa Gil, Grigori Fursin, and Nacho
Navarro. Predictive runtime code scheduling for heterogeneous architectures.
In Proceedings of the 4th International Conference on High Performance Embedded
Architectures and Compilers, HiPEAC ’09, pages 19–33, Berlin, Heidelberg, 2009.
Springer-Verlag.
[5] C´edric Augonnet, Samuel Thibault, Raymond Namyst, and Pierre-Andr´e Wacrenier.
”starpu: A unified platform for task scheduling on heterogeneous multicore architectures.
In Henk Sips, Dick Epema, and Hai-Xiang Lin, editors, Euro-Par 2009 Parallel
Processing, volume 5704 of Lecture Notes in Computer Science, pages 863–874.
Springer Berlin / Heidelberg, 2009.
[6] Tomoaki Hamano, Toshio Endo, and Matsuoka Satoshi. Power-aware dynamic task
scheduling for heterogeneous accelerated clusters. In Proceedings of the 2009 IEEE
International Symposium on Parallel&Distributed Processing, pages 1–8, Washington,
DC, USA, 2009. IEEE Computer Society.
[7] A.P.D. Binotto, B.M.V. Pedras, M. Gotz, A. Kuijper, C.E. Pereira, A. Stork, and D.W.
Fellner. Effective dynamic scheduling on heterogeneous multi/manycore desktop
platforms. In Computer Architecture and High Performance Computing Workshops
(SBAC-PADW), 2010 22nd International Symposium on, pages 37 –42, oct. 2010.
[8] Kyle Spafford, Jeremy Meredith, and Jeffrey Vetter. Maestro: data orchestration and
tuning for opencl devices. In Proceedings of the 16th international Euro-Par conference
on Parallel processing: Part II, Euro-Par’10, pages 275–286, Berlin, Heidelberg,
2010. Springer-Verlag.
[9] A. Bahga and V.K. Madisetti. A dynamic resource management and scheduling environment
for embedded multimedia and communications platforms. Embedded Systems
Letters, IEEE, 3(1):24 –27, march 2011.
[10] Mario Kicherer, Rainer Buchty, and Wolfgang Karl. Cost-aware function migration
in heterogeneous systems. In Proceedings of the 6th International Conference on
High Performance and Embedded Architectures and Compilers, HiPEAC ’11, pages
137–145, New York, NY, USA, 2011. ACM.
[11] J. D. Ullman. Np-complete scheduling problems. J. Comput. Syst. Sci., 10:384–393,
June 1975.
[12] Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to
the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1990.
[13] Howard Jay Siegel and Shoukat Ali. Techniques for mapping tasks to machines in
heterogeneous computing systems. J. Syst. Archit., 46:627–639, June 2000.
[14] Tracy D. Braun, Howard Jay Siegel, Noah Beck, Lasislau L. B¨ol¨oni, Muthucumara
Maheswaran, Albert I. Reuther, James P. Robertson, Mitchell D. Theys, Bin Yao,
Debra Hensgen, and Richard F. Freund. A comparison of eleven static heuristics
for mapping a class of independent tasks onto heterogeneous distributed computing
systems. J. Parallel Distrib. Comput., 61:810–837, June 2001.
[15] Oscar H. Ibarra and Chul E. Kim. Heuristic algorithms for scheduling independent
tasks on nonidentical processors. J. ACM, 24:280–289, April 1977.
[16] R F Freund, T Kidd, D Hensgen, and L Moore. Smartnet: A scheduling framework
for metacomputing. In 2nd International Symposium on Parallel Architectures, Algorithms,
and Networks (ISPAN ’96, pages 514–521, 1996.
[17] Muthucumaru Maheswaran, Shoukat Ali, Howard Jay Siegel, Debra Hensgen, and
Richard F. Freund. Dynamic mapping of a class of independent tasks onto heterogeneous
computing systems. J. Parallel Distrib. Comput., 59:107–131, November
1999.
[18] Sunpyo Hong and Hyesoon Kim. An integrated gpu power and performancemodel. In
Proceedings of the 37th annual international symposium on Computer architecture,
ISCA ’10, pages 280–289, New York, NY, USA, 2010. ACM.
[19] C. Augonnet, J. Clet-Ortega, S. Thibault, and R. Namyst. Data-aware task scheduling
on multi-accelerator based platforms. In Parallel and Distributed Systems (ICPADS),
2010 IEEE 16th International Conference on, pages 291 –298, dec. 2010.
[20] Andre R. Brodtkorb, Christopher Dyken, Trond R. Hagen, Jon M. Hjelmervik, and
Olaf O. Storaasli. State-of-the-art in heterogeneous computing. Sci. Program., 18:1–
33, January 2010.
[21] Michael D. Linderman, James Balfour, Teresa H. Meng, and William J. Dally. Embracing
heterogeneity: parallel programming for changing hardware. In Proceedings
of the First USENIX conference on Hot topics in parallelism, HotPar’09, pages 3–3,
Berkeley, CA, USA, 2009. USENIX Association.
[22] Dominik Grewe and Michael OBoyle. A static task partitioning approach for heterogeneous
systems using opencl. In Jens Knoop, editor, Compiler Construction,
volume 6601 of Lecture Notes in Computer Science, pages 286–305. Springer Berlin
/ Heidelberg, 2011.
[23] H. Topcuoglu, S. Hariri, and Min-You Wu. Performance-effective and lowcomplexity
task scheduling for heterogeneous computing. Parallel and Distributed
Systems, IEEE Transactions on, 13(3):260 –274, mar 2002.
[24] Richard F. Freund and Howard Jay Siegel. Guest editor’s introduction: Heterogeneous
processing. Computer, 26:13–17, 1993.
[25] Ashfaq A. Khokhar, Viktor K. Prasanna, Muhammad E. Shaaban, and Cho-Li Wang.
Heterogeneous computing: Challenges and opportunities. Computer, 26:18–27,
1993.
[26] Howard Jay Siegel, Seth Abraham, William L. Bain, Kenneth E. Batcher, Thomas L.
Casavant, Doug DeGroot, Jack B. Dennis, David C. Douglas, Tse-Yun Feng, James R.
Goodman, Alan Huang, Harry F. Jordan, J. Robert Jamp, Yale N. Patt, Alan Jay Smith,
James E. Smith, Lawrence Snyder, Harold S. Stone, Russ Tuck, and Benjamin W.
Wah. Report of the purdue workshop on grand challenges in computer architecture for
the support of high performance computing. J. Parallel Distrib. Comput., 16(3):199–
211, 1992.
[27] I. Ekmecic, I. Tartalja, and V. Milutinovic. A survey of heterogeneous computing:
concepts and systems. Proceedings of the IEEE, 84(8):1127 –1144, aug 1996.
[28] I. Ekmecic, I. Tartalja, and V. Milutinovic. Em3: a taxonomy of heterogeneous computing
systems. Computer, 28(12):68 –70, dec 1995.
[29] Michael J. Flynn. Some computer organizations and their effectiveness. Computers,
IEEE Transactions on, C-21(9):948 –960, sept. 1972.