CS420 CSE 402 ECE 492 Introduction to Parallel Programming for Scientists and Engineers Spring 2006 2006 David A Padua 1 of 28 Additional Foils 0 i Course organization 2006 David A Padua 2 of 28 Instructor Office Hours David Padua 4227 SC padua uiuc edu 3 4223 By appointment T A Predrag Tosic XXXX Siebel Center p tosic uiuc edu X XXXX Office Hours 2006 David A Padua 3 of 28 Textbook 2006 David A Padua 4 of 28 Lectures Some lecture foils will be required reading These will be posted at http www courses cs uiuc edu cs420 Grading 6 9 Machine Problems MPs Homeworks 50 Midterm Friday Mar 3 25 Final Comprehensive 25 Graduate students registered for 1 unit 4 credits must complete additional work associated with each MP Homework 2006 David A Padua 5 of 28 Additional Foils 0 ii Topics 2006 David A Padua 6 of 28 Machine models Parallel programming models Language extensions to express parallelism OpenMP Fortran and MPI Fortran or C If time allows High Performance Fortran Linda pC SplitC UPC Unified Parallel C CAF Co array Fortran HTA Hierarchically Tiled Aarrays Issues in algorithm design Parallelism Load balancing Communication Locality 2006 David A Padua 7 of 28 Algorithms Linear algebra algorithms such as matrix multiplication and equation solvers Symbolic algorithms such as sorting N body Random number generators Asynchronous algorithms Program analysis and transformation Dependence analysis Race conditions Deadlock detection Parallel program development and maintenance Modularity Performance analysis and tuning Debugging 2006 David A Padua 8 of 28 Additional Foils Chapter 1 Introduction 2006 David A Padua 9 of 28 Parallelism The idea is simple improve performance by performing two or more operations at the same time Has been an important computer design strategy since the very first computers It takes many complementary forms within conventional systems such as uniprocessor PCs and UNIX workstations At the circuit level Adders and multipliers do not handle one digit at a time but operate on several digits at the same time This design strategy was used even by Charles Babbage in his mechanical computer design of the 19th century At the processor design level The execution of instructions and floatingpoint operations is usually pipelined Several instructions can execute simultaneously At the system level Computation and I O can proceed simultaneously This is why multiprogramming increases throughput 2006 David A Padua 10 of 28 However the design strategy of interest to us is to attain parallelism by using several processors or even several complete computers Future PCs will be built with multicore chips Reading assignment http www intel com business bss products server resource center multicore htm ppc cid ggl multicore resrc ctr k46EE s Multicore are made possible by Moore s Law named after a 1964 observation by Gordon E Moore of Intel It holds that The number of elements in advanced integrated circuits doubles every year Another important reason for the development of parallel systems of the multicomputer variety is availability Having a computer shrivel up into an expensive doorstop can be a whole lot less traumatic if it s not unique but rather one of a herd The herd should be able to accomodate spares which can potentially be used to keep the work going or if one chooses to configure sparelessly the work that was done by the dear departed sibling can potentially be redistributed among the others In search of clusters G Pfister Prentice Hall 2006 David A Padua 11 of 28 12 of 28 Applications Traditionally highly parallel computers have been used for numerical simulations of complex systems such as the weather mechanical devices electronic circuits manufacturing processes chemical reactions etc In part because of HPCC technologies simulation has become recognized as the third paradigm of science the first two being experimentation and theory In some cases it is the only approach available for further advancing knowledge experiments may not be possible due to size very big or very small speed very fast or very slow distance very far away dangers to health and safety toxic or explosive or the economics of conducting the experiments In simulations mathematical models of physical phenomena are translated into computer software that specifies how calculations are performed using input data that may include both experimental data and estimated values of unknown parameters in the mathematical models By repeatedly running the software using different data and different parameter values an understanding of the phenomenon of interest emerges The realism of these simulations and the speed with which they are produced affect the accuracy of this understanding and its usefulness in predicting change From an old document entitled High Performance Computing and Communications Foundation for America s Information Future 2006 David A Padua 13 of 28 Perhaps the most important government program in parallel computing today is the Advanced Simulation and Computing Program ASC Reading assignment http www llnl gov asc overview overview html http www llnl gov asci platforms bluegenel images BGLbrocure pdf Its main objective is to accurately simulate nuclear weapons in order to verify safety reliability and performance of the US nuclear stockpile Several highly parallel computers 1000s of processors from Intel IBM and SGI are now being used to develop these simulations Commercial applications are also important today Examples include transaction processing systems web servers data mining etc These applications will probably become the main driving force behind parallel computing in the future In this course we will focus on numerical simulations due to their importance for scientists and engineers 2006 David A Padua 14 of 28 As mentioned above computer simulation is considered today as a third mode of scientific research It complements experimentation and theoretical analysis Furthermore simulation is an important engineering tool that provides fast feedback on the quality and feasibility of new designs 2006 David A Padua 15 of 28 Additional Foils Chapter 2 Machine models 2006 David A Padua 16 of 28 2 1 The Von Neumann computational model Discussion taken from Almasi and Gottlieb Highly Parallel Computing Benjamin Cummings 1988 Designed by John Von Neumann about fifty years ago All widely used conventional machines follow this model It is represented next PROCESSOR ARITHMETIC UNIT registers logic CONTROL