UNIVERSITY OF CALIFORNIA, IRVINE Predictive Adaptive Parallelism DISSERTATION submitted in partial satisfaction of the requirements for the degree of DOCTOR OF PHILOSOPHY in Information and Computer Science by David L. Wangerin Dissertation Committee: Professor Isaac D. Scherson, Chair Professor Alex Nicolau Professor Alex Veidenbaum 2006 UMI Number: 3243277 INFORMATION TO USERS The quality of this reproduction is dependent upon the quality of the copy submitted. Broken or indistinct print, colored or poor quality illustrations and photographs, print bleed-through, substandard margins, and improper alignment can adversely affect reproduction.
In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted. Also, if unauthorized copyright material had to be removed, a note will indicate the deletion. ® UMI UMI Microform 3243277 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved.
This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 © 2006 David L. Wangerin The dissertation of David L.
Wangerin is approved and is acceptable in quality and form for publication on microfilm: Ts lao =e = mmfftee Chair University of California, Irvine 2006 ii TABLE OF CONTENTS LIST OF FIGURES Vv LIST OF TABLES VII ACKNOWLEDGMENTS VIII CURRICULUM VITAE IX ABSTRACT OF THE DISSERTATION xX 1 FOREWORD 1 2 INTRODUCTION 3 2. Q Q Q Q Q Quy và va 10 3 SOLUTION OUTLINE 12 3. vn v VN cv VN va 14 3.4 Example of the System. cv v g k v v k k v k Và 29 43 Loop Level Parallelism.4 Multiple Program Segments .41 Nested Parallel Segments.2 Adjacent Parallel Segments .3 Concurrent Parallel Segments.5 Sensitivity of Performance Vectors.6 Task Level Parallelism.
eee eee ee 56 5 ANALYSIS OF SOLUTION 60 5.3 Jacobi Relaxation Algorithm. 0000000004 90 iil 6 PREVIOUS WORK 91 6.2 Parallelizing Compiler Techniques .3 Full Dynamic Runtime Optimizing Systems. 101 7 CONCLUSIONS AND FUTURE WORK 104 7. ee 105 BIBLIOGRAPHY 114 APPENDICES A Instruction Classes.v và xà B Parallel Python.
ee C Benchmark Set. ee v2 iv LIST OF FIGURES 2.1 Irregularity from data set size.2 Irregularity from data values.3 Choice of how to divide a parallel program.1 Program cost and time translations.2 Jacobi relaxation algorithm in HPE.3 Visual representation of two iterations of the Jacobi relaxation algorithm.4 Division of the data set for the parallel Jacobi relaxation algorithm.5 Structure of a generic thread in the parallel Jacobi relaxation algorithm.6 Pseudocode for a parallel Jacobi relaxation algorithm.7 The load vectors for each section of the parallel Jacobi relaxation al- gorithm. ng cv kg k NV kia 22 3.8 Time profile of the parallel Jacobi relaxation algorithm.1 Visualization of a performance vector with two instruction classes.2 Example of the load vector created from a single basic block.3 Basic block structure of a while loop and repeat loop.4 The load vector from a loop with a regular loop variant.5 The load vector from an irregular loop with an identifiable and pre- dictable loop variant.6 The load vector from a base metric loop.7 Basic block structure of a conditional if-then-else statement.8 Structure of an embarrassingly parallel program.9 Typical timing curve of equation (4.10 Two adjacent parallel sections with communications in the transition between sections. HQ HH ng và Tà xa 42 4.11 Time plot of two adjacent program segments.12 Two parallel sections that execute concurrently.13 Time profile of two program segments under case (1).14 Time profile of two program segments under case (2).15 Time profile of two program segments under case (3).16 Time profile to execute two program segments simultaneously while minimizing the total processing time.17 Time profile of executing three program segments simultaneously.18 Structure of a program using pipeline parallelism.1 Time plot on a fast system.
ee ee ee 61 5.2 Time plot on a medium system.3 Time plot on a slow system.4 Time plot of the same program on three different systems.9 The kernel of the 1-dimensional Jacobi relaxation algorithm.6 The client code for parallel Jacobi relaxation.7 Timing of network packet transmissions.8 Closeup of the low range of packet sizes and timing.9 Timing results for A= 32.10 Timing results for A=64.11 Timing results for A= 128.12 Timing results for A= 256.13 Timing results for A=512, 2.14 Timing results for Á = 1024.15 Timing results for A = 32, 2 iterations.16 Timing results for A = 64, 2 iterations.17 Timing results for A= 128, 2 iterations.18 Timing results for A = 256, 2iterations.19 Timing results for A = 512, 2iterations.20 Timing results for A = 1024, 2 iterations.1 Data decomposition of a matrix for a heterogeneous system. 106 vi LIST OF ‘TABLES 3.1 Machine and program cost characteristics.1 Comparison between scheduling methods for two program segments.1 Performance vectors for the three machines.2 Sensitivity of the performance vector memory value.3 Sensitivity with large memory values.4 Configuration of the test cluster.5 Instruction counts and timing results from the benchmark set.6 Performance vectors using memory-only and least squares models.7 Load vectors for the parallel Jacobi relaxation algorithm.8 Optimal number of threads for Jacobi relaxation algorithm.9 Optimal number of threads for Jacobi relaxation algorithm with 2 it- erations. vii ACKNOWLEDGEMENTS First and foremost, I would like to thank Issac Scherson for being a wonderful adviser, a great friend, and a constant source of inspiration. I first met Isaac in my under- graduate career, and it was by his suggestion that I became involved in research.
If it were not for Isaac, I would never have pursued a graduate degree. I am, and always will be, in debt to him for all of his great advice and help. I am also very grateful for the help and advice of my committee members Alex Nicolau and Alex Veidenbaum. Their feedback and critiques have been both invalu- able and through-provoking, and they have greatly increased the quality of my work.
I would like to thank everyone in my family (and soon to be family) for their constant love and support. I can’t express how much it has meant to me. I would also like to thank everyone from my research group, whose comments, insights, and help have been invaluable. In particular I would like to thank Shean McMahon and John Duselis for their hours of help with working on frustrating math- ematical problems, proof-reading papers, discussing difficult problems, and providing encouragement when I got stuck.
My education and research endeavors have been enriched by my experiences work- ing with NASA Goddard, NASA JPL, Unisys, the UC-MEXUS program, and of course UCI. In particular, I would like to thank John Dorband, Raphael Some, Mike Haken, and the great faculty of UCI. Last but not least, I would like to thank Rob Kolstad who has always given me great advice and pushed me to pursue hard and interesting problems. Vili CURRICULUM VITAE David L.
in Information and Computer Science, University of California, Irvine. 2005-2006 Software Developer, TMT Laboratories, Huntington Beach, California. 2005 Summer Researcher Fellowship, University of California, Irvine. in Information and Computer Science, University of California, Irvine.
2003-2004 Teaching Assistant, Information and Computer Science, University of California, Irvine. 2001 Internship, NASA Goddard Space Flight Center, VSEP Program, Greenbelt, Maryland. in Information and Computer Science, University of California, Irvine. 1998-2002 Co-op, Unisys Corporation, Systems Analysis, Modeling and Measurement Group, Mission Viejo, California.
Publications e David Wangerin and Isaac D. Using Predictive Adaptive Parallelism to Address Portability and Irregularity. In Proceedings of the 2005 Interna- tional Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN 2005), Las Vegas, Nevada, USA, December 2005. e David Wangerin and Isaac D.
Automatic Resource Management using an Adaptive Parallelism Environment. In Proceedings of the 2003 IEEE Inter- national Parallel and Distributed Processing Symposium (IPDPS) Workshop on Massively Parallel Processing, Nice, France, April 2003. A Modular Client-Server Discrete Event Simulator for Networked Computers. In Proceedings of the 35th Annual Simulation Symposium 2002, San Diego, California, USA, April 2002.
ix ABSTRACT OF THE DISSERTATION Predictive Adaptive Parallelism By David L. Wangerin Doctor of Philosophy in Information and Computer Science University of California, Irvine, 2006 Professor Isaac D. Scherson, Chair Parallel processing is used to increase the execution rate of programs. Since pro- cessing resources are the bottleneck for processing speed, increasing the processing rate is accomplished by adding more processing resources to the system.
However, using extra resources adds extra overhead, and the more resources that are used, the more overhead that is incurred. Optimal performance for parallel programs is achieved by finding the correct balance between computational speedup and overhead of using parallel resources. The current method of optimizing parallel programs is through extensive profiling and manual tuning of programs. This is not ideal since it is both time consuming in terms of programmer and machine time, and does not work for all programs, such as irregular programs and sequential programs executed in dynamic parallel systems.
A novel method, called predictive adaptive parallelism, is presented for automat- ically calculating the optimal number of threads for parallel programs at runtime. The method uses a combination of compile-time and run-time information to gauge the program resource requirements and target machine capabilities. Programs are x described in platform-independent load vectors, which describe the cost of executing a section of a program, and cost functions, which describe the number of times each section will be executed. When the programs are loaded onto a machine, the load vectors are translated into time costs.
As runtime metrics become known, the cost functions can be solved to give a time profile of executing the program as a function of the number of threads assigned to the program. Minimizing the cost function yields the minimal execution time of the program and thus the optimal number of threads. The method is applied to loop-level parallelism and task-level parallelism, and the techniques are shown to be effective and accurate on a cluster system. In addition, the sensitivity of the method to inaccuracy in measuring the machine capabilities is explored.
xi CHAPTER Í FOREWORD A personal anecdote: when I first entered college, I bought a dual-processor computer system. I was extremely excited about it, not the least because I had purchased the system piecemeal over the span of a year with all the money I earned from my job. I had the expectation that with a second processor, all the programs on my system would run about twice as fast. However, after I completed the system and got it running, it seemed that everything ran at about the same speed as when I only had a single processor.
In fact, after running some tests with game frame rates and other simple benchmarking tools available to me, it turned out that all the programs really were running at the same speed as with a single processor. This was both very frustrating and confusing!. The experience was not all bad, as it led me to wonder why the second processor did not add to the execution speed of typical programs. After some investigation, I found out that writing programs to use more than one processor is difficult— difficult enough that for the most part it is only done when programs require it.
This is both because the programming tools for parallel processing are somewhat primitive and because of the fact that using extra processors does not always give a speedup as expected, i., there is more to the problem than just throwing resources at it. Parallel programs need to use different data structures and figure out how to partition the data among the processors, need to use communications between processors to share data, and need to coordinate the activities of all processors to avoid problems like race conditions, deadlocks, and using old data. In addition, debugging parallel programs 1To make the experience even worse, the motherboard had a faulty capacitor that literally burned up and destroyed the motherboard a few months after I added the second processor. Needless to say, the replacement was a single processor system.