Additional Foils Chapter 3 Parallel Programming Models 2005 David A Padua 1 of 20 There are many different parallel programming paradigms Most are of academic interest only We will present three paradigms that are popular with real application programmers Shared memory programming Message passing programming Array programming We will start by introducing the notion of task 2005 David A Padua 2 of 20 Tasks Tasks are a central concept in parallel programming A task is a sequential program under execution The programmer may assume that there is a processor devoted to each task There may not be a physical processor but the operating system will timeshare the real processors to give the illusion of one processor per task It is said that the operating system creates a virtual machine Parallel programs consist of two or more tasks Each task may contain private data local memory That is data that only the tasks can access There are two main programming approaches used frequently to generate tasks 1 Explicit spawning 2 Programming in the SPMD Single Program Multiple Data model The SPMD model will be discussed shortly We will illustrate the explicitly spawning strategy next in the context of shared memory parallel programming 2005 David A Padua 3 of 20 Shared Memory Parallel Programming To illustrate this model consider the following simple program read b c e g a f1 b c h f2 e d f3 h g q f4 d a print q end where f1 f2 f3 and f4 are very complex functions and a b c d e p and q are complex data structures 2005 David A Padua 4 of 20 A simple parallel program for this is read b c e g start task sub e g d a f1 b c wait for all tasks to complete q f4 d a print q end subroutine sub e g d local h h f2 e d f3 h g end sub 2005 David A Padua 5 of 20 The program starts as a single task program and then a second task is initiated The second task proceeds by executing subroutine sub The computations of variable a and variable d proceed in parallel The original task waits for the second task to complete before proceeding with the computation of q Waiting is necessary to guarantee that d has been computed before it is used In this program all variables except for h can be shared by the two tasks In fact only variables e g and d are accessed by both tasks 2005 David A Padua 6 of 20 Notice that because h is private to the task a new copy of h will be created every time start task sub is executed Consider the following program read b c e g start task sub b c a call sub e g d wait for all tasks to complete q f4 d a print q end subroutine sub e g d local h h f2 e d f3 h g end sub Two copies of sub will be executing simultaneously and each will have its own copy of h 2005 David A Padua 7 of 20 Channels and Message Passing In message passing programming all variables are private Variable are shared by explicitly writing and reading data to and from tasks The following code is equivalent to the first shared memory code presented above read b c e g start task sub send x e g a f1 b c receive y d q f4 d a print q end subroutine sub local m n r h receive x m n h f2 m r f3 h n send y r end sub 2005 David A Padua 8 of 20 Here x and y are communication channels The send operation is asynchronous it completes immediately The receive operation is synchronous it halts execution of the task until the necessary data is available Thus thanks to the send and receive operations the values of variables e and g are tranferred from the original task to the created task and the value of d is transferred in the opposite direction Notice that no wait operation is needed The receive y d operation does the necessary synchronization An alternative approach message passing uses the names of the destination tasks rather than channels for communication Usually message passing systems start one task per processor all executing the same code This is the SPMD model mentioned above It is the most popular model today The previous program in SPMD and message passing 2005 David A Padua 9 of 20 if my proc eq 0 then read b c e g send e g to 1 a f1 b c receive d from 1 q f4 d a print q else my proc 1 receive m n from 0 h f2 m r f3 h n send r to 0 end if Later in the semester we will study this approach in more detail 2005 David A Padua 10 of 20 Parallel loops One of the most popuar constructs for shared memory programming is the parallel loop Parallel loops are just like any usual iterative statement such as for or do except that it doesn t actually iterate Instead it says just get all these things done in any order using as many processors as possible The number of processors available to the job may be specified or limited in some way but that s usually outside the domain of the parallel loop construct An example of a parallel loop is c sin d parallel do i 1 to 30 a i b i c end parallel do e a 20 a 15 2005 David A Padua 11 of 20 Parallel loops are implemented using tasks For example the previous program could be translated by the compiler into something similar to the following program c sin d start task sub a b c 1 10 start task sub a b c 11 20 call sub a b c 21 30 wait for all tasks to complete e a 20 a 15 subroutine sub a b c k l for i k to l a i b i c end for end sub Notice that in this program arrays a and b are shared by the three processors cooperating in the execution of the loop 2005 David A Padua 12 of 20 This program assigns to each processor a fixed segment of the iteration space This is called static scheduling Scheduling also could be dynamic Thus the compiler could generate the following code instead c sin d start task sub a b c start task sub a b c call sub a b c wait for all tasks to complete e a 20 a 15 subroutine sub a b c logical empty call get another iteration empty i while not empty do a i b i c call get another iteration empty i end while end sub 2005 David A Padua 13 of 20 Here the get another iteration subroutine accesses a pool containing all n iteration numbers gets one of them and removes it from the pool When all iterations have been assigned …