過去，使用者假如想要遞交一個平行工作到超級電腦中心去執行，就必須要指定一個特定數量的處理器，然後工作排程系統才能據以安排每個工作的處理器使用量。不過，當所指定的資源數量與目前可用的資源數目無法吻合時，這樣的配置方式往往就會導致低落的系統使用率與拉長的工作完成時間。由於現今多數平行應用程式皆具有可調式的平行度，因此，可以在開始執行前才決定實際使用的處理器數量。此性可以被利用來發展出新的可調式工作排程方法，以進一步改善系統的整體效能與資源使用效率。最近，高效能運算即服務模式被提出的其中一項目標就是讓使用者可以更方便地使用高效能運算工具以及應用程式。我們認為免除使用者必須指定處理器使用數量的麻煩是邁向此一目標的重要一步，因為大部分高效能運算即服務的使用者並不清楚底下的應用程式架構與特性，因此很難恰當地指定一個最適合的處理器數目來提升應用程式的執行效能。為了達成此一目標，我們在此篇論文中提出了三個新的可調式工作排程方法，這些方法不僅可免除使用者指定處理器使用數量的麻煩，同時還能進一步提升系統的整體執行效能。我們所執行的實驗結果顯示這三個方法比起現有的方法而言，分別可以有效提升系統執行效能達 83%、 78%、及 89%之多。

Traditionally, users who submit parallel jobs to supercomputing centers need to specify the amount of processors that each job requires. Job schedulers then allocate resources to each job according to the processor requirement. However, this kind of allocation has been shown leading to degraded system utilization and job turnaround time when mismatch between requirement and available resources occurs. System performance could be improved through the moldable property which most current parallel application programs have. With moldable property, parallel programs can exploit different parallelisms for execution at runtime. Previous research has shown potential performance improvement achieved by adaptive processor allocation based on the moldable property. Recently, the concept of HPC as a Service (HPCaaS) was proposed to bring the traditional high performance computing field into the era of cloud computing. One of its goals aims to allow users to get easier access to HPC facilities and applications. This thesis deals with related job submission and scheduling issues to achieve such goal. Traditional HPC users in supercomputing centers are required to specify the amount of processors to use upon job submission. However, we think this requirement might not be necessary for HPCaaS users since most modern parallel jobs are moldable and they usually could not know how to choose an appropriate amount of processors to allow their jobs to finish earlier. Therefore, we propose three moldable job scheduling approaches which not only relieve HPC users’ burden of selecting an appropriate number of processors and but also achieve even better system performance than existing methods. The experimental results indicate that the three approaches can achieve up to 83%, 78%, and 89% performance improvement in terms of average turnaround time.

Table of Contents
誌謝 I
摘要 II
Abstract III
Table of Contents IV
List of Figures V
Chapter 1. Introduction 1
Chapter 2. Related Work 5
Chapter 3. Moldable Job Scheduling Without Runtime Information 8
3.1 Auxiliary Moldable Job Scheduling 9
3.2 Moldable Job Scheduling for HPCaaS 17
Chapter 4. Moldable Job Scheduling with Runtime Information 25
4.1 Previous Moldable Job Scheduling with Runtime Information 25
4.2 Our Moldable Job Scheduling with Runtime Information for HPCaaS 27
Chapter 5. Experiments and Performance Evaluation 31
Chapter 6. Conclusions 37
References 40
 

[1]D. G. Feitelson, “A Survey of Scheduling in Multiprogrammed Parallel Systems”, Proc. Research Report RC 19790 (87657), IBM T. J. Watson Research Center, Oct. 1994.
[2]R. Gibbons, “A Historical Application Profiler for Use by Parallel Schedulers”, Proc. Job Scheduling Strategies for Parallel Processing, pp. 58-77, Springer-Verlag, 1997.
[3]D. Lifka, “The ANL/IBM SP Scheduling System”, Proc. Job Scheduling Strategies for Parallel Processing, pp. 295-303, Springer-Verlag, 1995.
[4]D. G. Feitelson, L. Rudolph, U. Schweigelshohn, K. Sevcik, and P. Wong, “Theory and Practice in Parallel Job Scheduling”. Proc. Job Scheduling Strategies for Parallel Processing, D. G. Feitelson and L. Rudolph (Eds.), pp. 1-34, Springer-Verlag, 1997. Lecture Notes in Computer Science Vol. 1291.
[5]The Message Passing Interface standard, http://www.mcs.anl.gov/research/projects/mpi/ (June 2013)
[6]Load sharing facility, http://www-03.ibm.com/systems/technicalcomputing/platformcomputing/products/lsf/ (June 2013)
[7]M. AbdelBaky,M.Parashar, H. Kim,E. J.JordanKirk,V.Sachdeva, J. Sexton, H. Jamjoom, Z.Y. Shae, G. Pencheva, R. Tavakoli and M. F. Wheeler, “Enabling High Performance Computing as a Service”, Proc. IEEE Computer, Vol. 45, pp. 72-80. IEEE Press, Oct. (2012).
[8]Cloud computing, http://www.infoworld.com/d/cloud-computing/what-cloud-computing-really-means-031 (Mar 2012)
[9]S. Srinivasan, S. Krishnamoorthy and P. Sadayappan, “A Robust Scheduling Strategy for Moldable Scheduling of Parallel Jobs”, Proc. 5th IEEE International Conference on Cluster Computing, pp. 92-99, 2003.
[10]S. Srinivasan, V. Subramani, R. Kettimuthu, P. Holenarsipur and P. Sadayappan, “Effective Selection of Partition Sizes for Moldable Scheduling of Parallel Jobs”, Proc. 9th International Conference on High Performance Computing, Springer, Lecture Notes in Computer Science, Bangalore, India, Vol. 2552, pp.174-183, 2002.
[11]K. C. Huang, “Performance Evaluation of Adaptive Processor Allocation Policies for Moldable Parallel Batch Jobs”, Proc. 3th Workshop on Grid Technologies and Applications, Dec 2006.
[12]D. L. Eager, J. Zahorjan, E. D. Lozowska,“Speedup versus efficiency in parallel systems”. IEEE Transactions on Computers archive Vol.38, Issue 3, pp. 408-423, March 1989.
[13]L. Kleinrock, J.H. Huang: On parallel processing systems, “Amdahl’s law generalized and some results on optimal design”, Proc. IEEE Transactions Softw. Eng. 18(5) (1992)
[14]A. B. Downey, “A Model for Speedup of Parallel Programs”, Proc. UC Berkeley EECS Technical Report, No. UCB/CSD-97-933, January 1997.
[15]A. B. Downey, “A Parallel Workload Model and Its Implications for Processor Allocation”, Proc. the 6th International Symposium on High Performance Distributed Computing, 1997.
[16]NAS parallel benchmarks, http://www.nas.nasa.gov/publications/npb.html (Jan 2012)
[17]Parallel Workloads Archive, http://www.cs.huji.ac.il/labs/parallel/workload/ (Jan 2012)
[18]M. W. Hall and M. Martonosi, “Adaptive parallelism in compiler-parallelized code. Concurrency: Practice and Experience”, 10(14):1235–1250, 1998.
[19]D. G. Feitelson and A. M. Weil, “Utilization and Predictability in Scheduling the IBM SP2 with Backfilling”, Proc. 12th Int’l Parallel Processing Symp., pp. 542-546, Apr. 1998
[20]A. W. Mu’alem and D. G. Feitelson, “Utilization, Predictability, Workloads, and User Runtime Estimate in Scheduling the IBM SP2 with Backfilling”, IEEE Transactions on Parallel and Distributed Systems, Vol. 12, Issue 6, pp. 529-543, June 2001.
[21]H. Sun, Y. Cao and W. J. Hsu, “Efficient Adaptive Scheduling of Multiprocessors with Stable Parallelism Feedback”, Proc. IEEE Transactions on Parallel and Distributed System, Vol. 22, No. 4, April 2011.
[22]S. Ioannidis, U. Rencuzogullari, R. Stets, and S. Dwarkadas, “CRAUL: Compiler and run-time integration for adaptation under load”, Journal of Scientific Programming, Aug. 1999.
[23]J. Pruyne and M. Livny. Parallel Processing on Dynamic Resources with CARMI. In D. G. Feitelson and L.Rudolph, editors, Proc. Job Scheduling Strategies for Parallel Processing, Vol 949, pp. 259–278. Springer, 1995.
[24]W. Cirne and F. Berman, “Using Moldability to Improve the Performance of Supercomputer Jobs”, Journal of Parallel and Distributed Computing, Vol. 62, pp. 1571-1601, Oct 2002
[25]W. Cirne and F. Berman, “Adaptive Selection of Partition Size for Supercomputer Requests”, Proc. Job Scheduling Strategies for Parallel Processing Lecture Notes in Computer Science, Vol. 1911, pp. 187-207 , 2000
[26]G. Sabin, M. Lang and P Sadayappan, “Moldable Parallel Job Scheduling Using Job Efficiency: An Iterative Approach”, Proc. Job Scheduling Strategies for Parallel Processing, Saint Malo, France, June 2006.
[27]T. G. Lewis and H. E. Rewini, Introduction to Parallel Computing, Prentice-Hall International, 1992.