Parallel Programming PDF

Parallel Programming Attila Kertesz [email protected] Software Engineering Department University of Szeged 1/188  Contents Parallel Programming Introduction Parallel computer systems...

Parallel Programming Attila Kertesz [email protected] Software Engineering Department University of Szeged 1/188  Contents Parallel Programming Introduction Parallel computer systems Parallel hardware Parallel software Shared memory Semaphore Interaction schemes Monitor Java features Distributed memory Message passing Occam MPI Design methods 2/188  Parallel computer systems Parallel Programming System concepts Parallel computer systems Components – integrated Parallel programming Connections, interactions Boundary, environment, subsystem Parallel: “Occurring or existing at the same time or in a similar way” Related terms Distributed: components are separated in space Concurrent: components share and contend for resources 3/188  Parallel computer systems (cont.) Parallel Programming Advantages of parallelism Parallel computer systems Parallel hardware: n processors can be n times faster programming software: programs can have clearer structure 4/188  Parallel hardware Parallel Programming Component types Parallel computer systems C I P D M Memory Parallel programming Processor Conventional Neumann architecture Controller Flynn’s classification scheme Number of data streams (Single/Multiple) Number of instruction streams (Single/Multiple) Classes: SISD, MISD, SIMD, MIMD 5/188  Parallel hardware MISD Parallel Programming C I P Parallel computer systems Parallel programming C I P Very special architecture, suitable for fault tolerance.... D M.. C I P 6/188  Parallel hardware SIMD – Array processors Parallel Programming P D P D Parallel computer systems M Communication Parallel programming P D P D M C I.. M C I....... P D M P D Distributed memory Shared memory 7/188  Parallel hardware MIMD – General purpose architectures Parallel Programming C I P D C I P D M Parallel computer systems Parallel C I P D C I P D M Communication programming.... M........... C I P D C I P D M Shared memory Distributed memory (e.g. multicore machines) (e.g. network of workstations) 8/188  Parallel software Parallel Programming Component types Parallel computer systems Memory (variables) Parallel Process (thread, task) – NOT processor! programming Shared memory Distributed memory P1 P1 M1... M Communication... Pn Pn Mn 9/188  Hardware and software Parallel Programming Hardware shared distributed Parallel computer systems shared 3 7 Software Parallel programming distributed 3 3 Hibrid approaches are possible NUMA: Non-uniform memory access Distributed shared memory 10/188  Parallel programming aspects Design Parallel Programming Extended sequential core language Parallel computer systems C + Linux system calls Parallel PVM: C + library for process creation & communication programming MPI,... Parallel language by design Linda (tuple space) Occam SR (Synchronizing Resources) Java(?),... 11/188  Linux IPC Parallel Programming Linux process model: distributed memory by default, but shared memory segments can be created Parallel computer systems process creation: int fork() Parallel programming if ( fork()) statement_1; else statement_2; basic process interaction: wait() – special synchronisation IPC components: shared memory segment semaphore message queue 12/188  Parallel programming aspects Parallel Programming Parallel computer Fundamental design patterns systems Parallel programming Functional decomposition Data decomposition Load balancing Static – decomposition in advance Dynamic – decomposition during run-time 13/188  Efficiency of parallel programs Parallel Programming Execution times Parallel computer systems T1 : execution time on 1 processor (which input?) Parallel programming Tn : execution time on n processors (same algorithm?) Speedup: Sn = T1 /Tn , 1 ≤ Sn ≤ n How much faster does the program run on n processors than on 1? Efficiency: En = Sn /n, 0 ≤ En ≤ 1 How efficiently does the program use the available n processors? 14/188  Processes Lifetime Parallel Programming Process operations Parallel computer systems Parallel Creation/destruction programming Control: priority, suspension, queries,... Process granularity: relative lifetime fine: many short-lived processes, frequent creation/destruction medium coarse: few long-lived processes 15/188  Processes Asynchronous execution Parallel Programming sequence Parallel computer systems Parallel parallel/independent programming A B A B C C 16/188  Processes Interleaving Parallel Programming Parallel computer systems Parallel programming A B1 B1 B1 ⇒ B1... A... B2 A B2 C B2 B2 C C C A 17/188  Processes Interactions Parallel Programming Process interleaving Parallel computer Events of a sequential process have to retain their relative order systems Parallel Events of independent processes can occur in any order programming Process interactions We do not always want all possible interleavings to be possible ⇒ sometimes processes have to wait Process waiting modes Busy waiting (spin lock): exit condition testing in a loop Passive waiting: on a queue 18/188  Processes Execution & Interactions Parallel Programming P Parallel computer systems Parallel programming Q 19/188  Processes (cont.) Execution & Interactions Parallel Programming P Parallel computer systems Parallel n programming wait R R Q 20/188  Processes (cont.) Execution & Interactions Parallel Programming P Parallel computer systems Parallel n programming wait R S R S Q 21/188  Processes (cont.) Execution & Interactions Parallel Programming P Parallel computer systems Parallel n programming wait R S deadlock R S Q 22/188  Legacy code vs. processor architecture Parallel Programming Parallel computer Task: initialize a vector with 0s systems Parallel Each vector element can be set independently programming Independent execution cannot be expressed in most languages Vector initialization is expressed as a sequence int v[ n]; for ( int i= 0; i < n; ++i) v[ i]= 0; 23/188  Legacy code vs. processor architecture (cont.) Parallel Programming Sequence is not enough Parallel computer systems Processor technology advancements in 20th century Parallel programming method: decreasing circuit size, increasing clock frequencies effect: (sequential) programs automatically take advantage Processor technology advancements in 21st century method: multiple processor cores effect: (sequential) programs run on 1 core ⇒ no gain 24/188  Fundamental process interactions Parallel Programming Mutual exclusion - shared memory only Parallel computer Resource – anything a process needs, its capacity is limited systems Parallel Critical section – a block of code that handles a resource programming At most one process in its critical section at any given moment Synchronization - shared or distributed memory Wait-signal relationship between two processes Deadlock - shared or distributed memory Circle of 2 or more waiting processes Livelock (starvation): a process may be postponed indefinitely 25/188  Parallel Programming Semaphore Interaction schemes Monitor Shared Memory 26/188  Race condition Indeterminate result due to unpredictable interleaving Parallel Programming Semaphore Race condition Definition Application Implementation b=X a=X Possible outcomes: Interaction schemes X increases by 1 Monitor b =b+1 a=a+1 X increases by 2 X =b X =a 27/188  Semaphore A device for process interaction Parallel Programming A semaphore is an object Semaphore Race condition Definition Private data Application Implementation integer counter Interaction values ∈ {0, 1}: binary semaphore schemes any integer: counting semaphore Monitor waiting queue for processes Public operations Constructor wait() signal() 28/188  Semaphore Definition Parallel Programming public: void wait() { Semaphore Race condition if ( 0 == value) Definition queue.add(); Application class Semaphore { else Implementation int value; --_value; Interaction ProcessQueue queue; schemes }; Monitor public: public: Semaphore( int v) { void signal() { value= v; if ( NOT _queue.empty()) queue.empty(); _queue.release(); }; else ++_value; }; }; 29/188  Semaphore application Mutual exclusion Parallel Programming Semaphore Race condition Definition Application Implementation Interaction schemes Monitor 30/188  Semaphore application Synchronization Parallel Programming Semaphore Race condition Definition Application Implementation Interaction schemes Monitor 31/188  Semaphore implementation Atomic operations Parallel Programming void lock( int& lockvar) { // incorrect !!! Semaphore while ( 0 == lockvar) Race condition ; Definition Application lockvar= 0; Implementation } Interaction schemes void lock( int& lockvar) { Monitor while ( 0 == test and set( lockvar, 0)) ; } void unlock( int& lockvar) { lockvar= 1; } 32/188  Semaphore implementation Parallel Programming void wait() { lock( _lock); Semaphore if ( 0 == _value) Race condition _queue.add_unlock( _lock); Definition class Semaphore { Application else { int _value; Implementation --_value; ProcessQueue _queue; Interaction unlock( _lock); schemes } int _lock; Monitor }; void signal() { public: lock( _lock); Semaphore( int v) { if ( NOT _queue.empty()) _value= v; _queue.release_unlock( _lock); _queue.empty(); else { _lock= 1; ++_value; }; unlock( _lock); } 33/188 };  Interaction schemes Abstract problems to be solved using one of the interaction devices Parallel Programming Scenarios expressed involving active and passive components Semaphore active components: processes Interaction schemes passive components: resources Monitor scenario: rules of interaction Examples Mutual exclusion (race condition) Producer-consumer problem Readers-writers problem Dining philosophers problem 34/188  Producer-Consumer problem Structure Parallel Programming P1 C1 Semaphore Interaction... Bounded buffer... schemes Monitor Pn Cm Problems to be solved Mutual exclusion on bounded buffer Synchronisation to avoid data handling problems Producer to consumer Consumer to producer 35/188  Producer-Consumer problem Behaviours Parallel Programming public void Producer( Queue queue) { boolean going= true; Semaphore while ( going) { ITEM x= produce(); Interaction schemes queue.deposit( x); Monitor... } } public void Consumer( Queue queue) { boolean going= true; while ( going) { ITEM x= queue.extract(); consume( x);... } } 36/188  P-C for 1 item 2 binary semaphores for synchronizaion Parallel Programming Semaphore Interaction schemes Monitor 37/188  P-C for N items 1 binary semaphore for mutual exclusion 2 semaphores for synchronizaion Parallel Programming Semaphore Interaction schemes Monitor 38/188  Producer-Consumer problem Semaphore solution - mutual exclusion Parallel Programming class Queue { private ITEM data[ N]=...; Semaphore private Semaphore mutex( 1); Interaction schemes public void deposit( ITEM x) { Monitor mutex.wait(); // x -> data mutex.signal(); } public ITEM extract() { mutex.wait(); // x data // x -> data mutex.signal(); mutex.signal(); used.signal(); free.signal(); } } 40/188  Monitor A(nother) device for process interaction Parallel Programming Mutual exclusion with semaphores is not structured Semaphore Interaction Programmer errors may lead to improper resource use or schemes deadlock Monitor Definition Application A monitor is an object Java Private data A resource An implicit lock to ensure mutual exclusion among operations Initialization (constructor) Public monitor procedures (implicitly atomic) 41/188  Producer-Consumer problem Monitor solution - mutual exclusion Parallel Programming monitor Queue { private ITEM data[ N]=...; Semaphore Interaction public void deposit( ITEM x) { schemes // x -> data Monitor } Definition Application Java public ITEM extract() { // x data Java nonempty.csignal(); } public ITEM extract() { if ( empty()) nonempty.cwait(); // x PVM CHAN INT c: -- for sending integers Design methods MPI Varying number of elements Design methods v2 JPVM CHAN INT :: [] < type > DistSys CHAN INT::[]BYTE c: -- for strings c ! 3 :: "abc" c ! 5 :: "efghj" 98/188  Occam Scope Parallel Programming Message passing Occam PVM CHAN INT c: c PAR Design methods -- process P MPI P Q c ! 5 Design methods v2 -- process Q JPVM INT x: DistSys c ? x 99/188  Occam Protocols with custom name Parallel Programming Message passing Occam PVM Pair type Design methods MPI PROTOCOL PAIR IS INT; BYTE: -- protocol definition Design methods v2 CHAN PAIR c: -- a channel with PAIR type c ! 3; ’a’ JPVM DistSys 100/188  Occam Variant protocols - for sending different types (e.g. records) Parallel Programming Person type Message passing Occam PROTOCOL PERSON -- protocol definition PVM CASE Design methods name; INT::[]BYTE age; INT MPI quit Design methods v2 : JPVM DistSys CHAN PERSON p: -- a channel with PERSON type p ! name; 3 :: "joe" p ! age; 20 p ! quit 101/188  Occam Sequential execution Parallel Programming Message passing Occam PVM SEQ SEQ Design methods SEQ P x := 1 MPI x := 1 Q SEQ y := x+2 Design methods v2... y := x+2 z := y-1 JPVM R z := y-1 DistSys 102/188  Occam Selection Parallel Programming IF IF IF c1 x < 0 x < 0 Message passing P1 z := -1 z := -1 Occam c2 IF x = 0 P2 x = 0 PVM z := 0... z := 0 Design methods x > 0 cn x > 0 MPI z := 1 Pn z := 1 Design methods v2 JPVM DistSys CASE e l1,... CASE c P1 ’a’,’e’,’i’,’o’,’u’ l2,... vowel := TRUE P2 ELSE... vowel := FALSE ELSE P 103/188  Occam Iteration Parallel Programming Message passing Occam PVM INT x, y: SEQ Design methods x, y := 0 MPI WHILE c WHILE x < 10 Design methods v2 P SEQ JPVM x := x+1 DistSys y := y+x 104/188  Occam Replication Parallel Programming XXX v=start FOR count Message passing P(v) Occam PVM IF i=0 FOR 3 Design methods x[ i] > w MPI SEQ i=1 FOR 3 z := i Design methods v2 x[ i-1] := i JPVM IF DistSys SEQ x[ 0] > w x[ 0] := 1 z := 0 x[ 1] := 2 x[ 1] > w x[ 2] := 3 z := 1 x[ 2] > w z := 2 105/188  Occam Parallel execution Parallel Programming Message passing PAR Occam P PAR PVM Q x := 1 VAL INT s IS 5:... y := 2 Design methods [s]INT v: R z := 3 MPI SEQ Design methods v2 PAR i=0 FOR s CHAN INT c: JPVM v[ i] := 0 PAR SEQ i=0 FOR s DistSys P Q... R c ! 5 c ! v[ i] INT x: c ? x 106/188  Occam “Shared” variables in parallel processes Parallel Programming INT x: Message passing CHAN INT c, d: Occam PAR INT x: SEQ --------------- PVM PAR c ! x Design methods P1 -- no x INT x: d ! x MPI PAR P1 -- x readonly... Design methods v2 Pi−1 -- no x P1 -- x readonly INT x: JPVM x := x + 1 P2 -- x readonly SEQ --------------- DistSys Pi+1 -- no x P3 -- x readonly c ? x... P2 -- x readonly Pn -- no x INT x: SEQ --------------- d ? x P3 -- x readonly 107/188  Occam Multiple assignment Parallel Programming Message passing Rules for variables in PARs Occam If a process assigns to a variable, then it cannot appear in any PVM other process Design methods MPI Otherwise any process can read the variable Design methods v2 JPVM Multiple assigment x, y := y, x DistSys The same variable can occur on both sides Results should be predictable 108/188  Occam (cont.) Multiple assignment Parallel Programming v1 , v2 ,..., vn := e1 , e2 ,..., en Message passing T1 t1 : Occam T2 t2 : PVM... Design methods Tn tn : SEQ MPI PAR Invalid assigments Design methods v2 t1 := e1 JPVM t2 := e2 x, x := 1, 2 DistSys... i, x[ i] := 1, 2 tn := en PAR v1 := t1 v2 := t2... vn := tn 109/188  Occam Named processes – procedures Parallel Programming Message passing PROC p( VAL INT a, INT b, CHAN INT c) Occam process PVM : -- p Design methods PROC q( VAL []INT v, []INT w, []CHAN INT x) MPI INT s: Design methods v2 SEQ JPVM... DistSys s := SIZE w... : -- q 110/188  Occam Pipeline - Functional decomposition Parallel Programming Message passing Occam PVM Design methods MPI Design methods v2 JPVM DistSys 111/188  Occam Pipeline processing Parallel Programming Message passing P Q R Occam PVM Design methods MPI PROC pipeline( CHAN INT inp, out) PROC pipe.element( CHAN INT inp, out) VAL INT size IS 5: Design methods v2 WHILE going [size-1]CHAN BYTE ch: JPVM SEQ PAR DistSys inp ? data pipe.element( inp, ch[ 0])... PAR i=1 FOR size-2 out ! data pipe.element( ch[ i-1], ch[ i]) : -- pipe.element pipe.element( ch[ size-2], out) : -- pipeline 112/188  Occam Pipeline processing - sorting Parallel Programming Message passing Occam PVM Sorting elements with pipelined processes Design methods All processes execute the same MAX function MPI Design methods v2 JPVM DistSys 113/188  Occam Pipeline processing - Sorting elements Parallel Programming Message passing Occam PVM Design methods MPI Design methods v2 JPVM DistSys 114/188  Occam Functions Parallel Programming Function properties Message passing Multiple return values Occam Value (constant) parameters only, no communication PVM Design methods INT, INT FUNCTION max2( VAL INT a, b) MPI INT x, y: Design methods v2 VALOF JPVM IF DistSys a > b x, y := b, a TRUE x, y := a, b RESULT x, y : -- max2 115/188  Occam Pipeline sort Parallel Programming Message passing PROC sortelement( CHAN INT inp, out) Occam INT max, x: PVM max SEQ Design methods inp ? max MPI x SEQ i= 1 FOR N-1 Design methods v2 SEQ JPVM inp ? x x, max := max2( x, max) DistSys out ! x out ! max : -- sortelement 116/188  Occam Structure clash Parallel Programming Message passing Occam PVM Transforming one record to another Design methods MPI Design methods v2 JPVM DistSys 117/188  Occam Structure clash Parallel Programming Message passing Occam PVM Design methods MPI CHAN BYTE R2T, T2W: PAR Design methods v2 Reader(inp, R2T) JPVM Transfrom(R2T, T2W) DistSys Writer(T2W, out) 118/188  Occam Structure clash Parallel Programming Message passing Occam PVM Design methods MPI Design methods v2 JPVM DistSys 119/188  Occam Asynchronous communication Parallel Programming Message passing A pipeline can be used to create buffered channels with fixed Occam capacity PVM Design methods Each component stores a data item MPI Sender does not have to wait if pipeline is not full Design methods v2 JPVM DistSys Sender Receiver 120/188  Occam (cont.) Asynchronous communication Parallel Programming Message passing Occam PROC async( CHAN INT inp, out) PVM WHILE TRUE -- does not terminate :( Design methods INT x: MPI SEQ inp ? x Design methods v2 out ! x JPVM : -- async DistSys 121/188  Occam Alternation Parallel Programming ALT ALT Message passing g1 c ? x Occam ALT P1 y := y+x c ? x PVM g2 ALT y := y+x Design methods P2 d ? x d ? x MPI... z := z+x z := z+x gn e ? x Design methods v2 Pn w := w+x JPVM DistSys c P d 122/188  Occam Alternation Parallel Programming Guard forms - gi Message passing e & c ? v P Occam PVM c ? v ⇒ TRUE & c ? v Design methods TRUE & SKIP MPI Design methods v2 ALT life cycle JPVM DistSys 1 Initialize guards – filtering on condition 2 Wait until at least one guard becomes enabled 3 Select one guard – nondeterministic 4 Input data, execute process 123/188  Occam Replicated alternation Parallel Programming Message passing Replication does NOT mean iteration Occam Replicated ALT executes only once PVM Design methods MPI ALT c1 ? v Design methods v2 P1 JPVM ALT i=1 FOR n c2 ? v DistSys c(i) ? v P2 P(i)... cn ? v Pn 124/188  Occam Multiplexer – demultiplexer Parallel Programming Message passing Multiplexer Demultiplexer Occam PVM Design methods MPI Design methods v2 JPVM PROC mplex( []CHAN INT inp, DistSys CHAN INT out) PROC mplex.demplex( []CHAN INT inp, out)... CHAN INT ch: : -- mplex PAR mplex( inp, ch) PROC demplex( CHAN INT inp, demplex( ch, out) []CHAN INT out) : -- mplex.demplex... : -- demplex 125/188  Occam (cont.) Multiplexer – demultiplexer Parallel Programming Message passing Occam PROC mplex( []CHAN INT inp, PVM CHAN INT out) PROC demplex( CHAN INT inp, Design methods WHILE TRUE []CHAN INT out) MPI ALT i=0 FOR ( SIZE inp) WHILE TRUE INT d: INT d, i: Design methods v2 inp[ i] ? d SEQ JPVM SEQ inp ? d DistSys out ! d inp ? i out ! i out[ i] ! d : -- mplex : -- demplex 126/188  Occam Asynchronous communication v2 Parallel Programming Message passing Occam PVM Design methods MPI Design methods v2 JPVM DistSys 127/188  Occam Asynchronous communication v2 Parallel Programming Message passing Occam PVM Design methods MPI Design methods v2 JPVM DistSys 128/188  Occam Parallel Programming Examples Message passing Structure clash Occam PVM Asynchronous communication pipeline Design methods Asynchronous communication other MPI Design methods v2 Protocols JPVM DistSys Simple Sequential Iterated array Variant 129/188  Occam Processor farm - Load balancing Parallel Programming Message passing Occam PVM Design methods MPI Design methods v2 JPVM DistSys 130/188  Occam Processor farm - Farmer-Worker method Parallel Programming Message passing Occam PVM Design methods MPI Design methods v2 JPVM DistSys 131/188  Occam Processor farm - Farmer-Worker method Parallel Programming Message passing Occam PVM Design methods MPI Design methods v2 JPVM DistSys 132/188  Occam Processor farm - Farmer Parallel Programming Message passing Occam PVM Design methods MPI Design methods v2 JPVM DistSys 133/188  Occam Processor farm - Worker Parallel Programming Message passing Occam PVM Design methods MPI Design methods v2 JPVM DistSys 134/188  Occam Processor farm - Worker Parallel Programming Message passing Occam PVM Design methods MPI Design methods v2 JPVM DistSys 135/188  PVM – Parallel Virtual Machine Parallel Programming PVM properties Message passing Occam Operating system + C language + parallel library PVM Parallelism is not integrated into the language Design methods Components: variables, tasks (processes), message buffers MPI Design methods v2 Parallel applications on heterogenous computer networks JPVM DistSys PVM design decisions addressing: direct ⇒ Task IDs (TIDs) transfer mode: asynchronous ⇒ mailboxes (buffers) 136/188  PVM Tasks Parallel Programming PVM architecture Message passing Occam Hosts – machines on LAN PVM PVM daemons – manage interactions with other daemons Design methods A task interacts with their local daemon MPI Design methods v2 JPVM PVM monitor DistSys $ pvm – starts monitor (and daemon) PVM/host maintenance Task control commands 137/188  PVM (cont.) Tasks Parallel Programming PVM programs Message passing Tasks should be written as standalone C programs Occam Build with cc -o prog prog.c -lpvm3 PVM Design methods #include MPI #include "pvm3.h" Design methods v2 main() JPVM { DistSys int mytid; mytid= pvm mytid();... // other PVM calls pvm exit(); exit( EXIT SUCCESS); } 138/188  PVM (cont.) Tasks Parallel Programming Message passing Task life cycle Occam PVM 1 (Linux) process starts Design methods 2 Process calls pvm mytid() – registers as a PVM task MPI Design methods v2 3 Task interacts with other tasks JPVM 4 Task calls pvm exit() – leaves the virtual machine DistSys 5 Process exits 139/188  PVM Library functions – tasks Parallel Programming Basic task handling Message passing Occam int pvm mytid( void) PVM int pvm parent( void) Design methods int pvm exit( void) MPI Design methods v2 int pvm kill( int tid) JPVM DistSys Task groups int pvm joingroup( char *group) int pvm lvgroup( char* group) 140/188  PVM (cont.) Library functions – tasks Parallel Programming Task creation Message passing int pvm spawn( char* task, char** argv, int flag, Occam char* where, int ntask, int* tids) PVM char* task program path Design methods char** argv command line arguments MPI int flag options to interpret where Design methods v2 PvmTaskDefault JPVM PvmTaskHost DistSys PvmTaskArch char* where a host or architecture for created tasks int ntask number of instances to create int* tids points to allocated task ID vector 141/188  PVM Library functions – communication Parallel Programming Communication helper objects Message passing Mailbox – temporary store for incoming messages Occam Send buffer(s) – message assembly area PVM Design methods Receive buffer(s) – message processing area MPI Active send/receive buffer Design methods v2 JPVM Message structure DistSys Receiver ID Message tag (int) – used for classification (user defined) Message content (record) 142/188  PVM Library functions – communication Parallel Programming Sending Message passing Occam int pvm initsend( int encoding) PVM PvmDataDefault full conversion Design methods PvmDataRaw no conversion MPI PvmDataInPlace avoid double copy Design methods v2 int pvm pk*(...) – message assembly with type info JPVM DistSys int pvm send( int tid, int msgtag) – “blocking asynchronous send” int pvm mcast( int* tids, int ntask, int msgtag) – multicast 143/188  PVM (cont.) Library functions – communication Parallel Programming Receiving Message passing int pvm recv( int tid, int msgtag) – wait for message, Occam move to receive buffer PVM Design methods int pvm nrecv( int tid, int msgtag) – nonblocking MPI int pvm probe( int tid, int msgtag) – “peek” Design methods v2 int pvm trecv( int tid, int msgtag, struct JPVM timeval* timeout) – timed wait DistSys int pvm bufinfo( int bufid, int* bytes, int* msgtag, int* tid) int pvm upk*(...) – message disassembly 144/188  PVM Synchronous communication Parallel Programming #include "pvm3.h" #include #define SYNC_ACK 172 Message passing Occam int sync_send( int tid, int msgtag) { PVM int info= pvm_send( tid, msgtag); Design methods pvm_recv( tid, SYNC_ACK); MPI return info; } Design methods v2 JPVM int sync_recv( int tid, int msgtag) { DistSys int bufid= pvm_recv( tid, msgtag); if ( -1 == tid) pvm_bufinfo( bufid, NULL, NULL, &tid); pvm_initsend( PvmDataDefault); pvm_send( tid, SYNC_ACK); return bufid; } 145/188  PVM Pipeline processing Parallel Programming Message passing Occam PVM Design methods MPI Design methods v2 JPVM DistSys 146/188  PVM Pipeline processing Parallel Programming Message passing Occam PVM Design methods MPI Design methods v2 JPVM DistSys 147/188  PVM Pipeline sort – initialization Parallel Programming // pipemain.c Message passing tids= ( int*) malloc( N * sizeof ( int)); Occam pvm spawn( "pipecomp", NULL, PvmTaskDefault, "", N, tids); PVM for ( i= 0; i < N; ++i) { Design methods send_int( tids[ i], INIT, 0 == i ? pvm_mytid() : tids[ i-1]); MPI send_int( tids[ i], INIT, N-1 == i ? pvm_mytid() : tids[ i+1]); Design methods v2 send_int( tids[ i], INIT, N); JPVM } DistSys // pipecomp.c prev= recv_int( -1, INIT); succ= recv_int( -1, INIT); N= recv_int( -1, INIT); 148/188  PVM Pipeline sort – processing Parallel Programming // pipemain.c for ( i= 1; i