CS420 CSE 402 ECE 492 Introduction to Parallel Programming for Scientists and Engineers Spring 2005 2005 David A Padua 1 of 30 Additional Foils 0 i Course organization 2005 David A Padua 2 of 30 Instructor Office Hours David Padua 4227 SC padua uiuc edu 3 4223 By appointment T A Nick Hurley XXXX Siebel Center nhurley2 uiuc edu X XXXX Office Hours M 3 4 pm Tu 2 30 3 30 pm 2005 David A Padua 3 of 30 Textbook 2005 David A Padua 4 of 30 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 4 25 Final Comprehensive 25 Graduate students registered for 1 unit 4 credits must complete additional work associated with each MP Homework 2005 David A Padua 5 of 30 Additional Foils 0 ii Topics 2005 David A Padua 6 of 30 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 Issues in algorithm design Parallelism Load balancing Communication Locality 2005 David A Padua 7 of 30 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 2005 David A Padua 8 of 30 Additional Foils Chapter 1 Introduction 2005 David A Padua 9 of 30 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 2005 David A Padua 10 of 30 However the design strategy of interest to us is to attain parallelism by using several processors or even several complete computers It has also been claimed that parallel computing is necessary for continuing performance gains given that clock times are decreasing slowly and appear to be approaching physical limits Assuming that nothing basic in manufacturing or physics breaks in the next couple of years there is no reason the historical trend in microprocessor performance will slow Robert Colwell Computer January 1998 However despite all the advances in semiconductor technology parallelism is becoming increasingly popular It is an important strategy to increase performance over what is possible by hardware technology alone EPIC Itanium 2 and Symmetric Multithreading SMT processors Future PCs will be built with multicore chips 2005 David A Padua 11 of 30 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 2005 David A Padua 12 of 30 13 of 30 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 Some claim that the era of this law is coming to an end at some point for several reasons The cost of chip factories will increase enormously The small number of electrons moved at these new small feature sizes may not be enough for reliable computing The feature sizes will be so small that quantum effects will start having an impact 2005 David A Padua 14 of 30 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 2005 David A Padua 15 of 30 Perhaps the most important government program in parallel computing today is the Accelerated Strategic Computing Initiative ASCI Reading assignment http www llnl gov asci 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