Transcript Session-12 - Lyle School of Engineering

Parallel and Distributed
Processing
CSE 8380
February 22 2005
Session 12
Computer Science and Engineering
Parallel Virtual Machine (PVM)
Review
Communication
Synchronization
Reduction operations
Work Assignments
Computer Science and Engineering
Main Constructs in PVM
Task Creation
Communication
Synchronization
Others
Computer Science and Engineering
PVM Software
Two Components:
Library of PVM routines
Daemon
Computer Science and Engineering
PVM Application
 A number of sequential programs, each
of which will correspond to one or more
processes in a parallel program
Computer Science and Engineering
Application Structure
Start graph
Tree
Computer Science and Engineering
To Create a child, you must specify:
1.
2.
3.
4.
The machine on which the child will be
started
A path to the executable file on the
specified machine
The number of copies of the child to be
created
An array of arguments to the child
tasks
Computer Science and Engineering
Pvm_spawn
num = pvm_spawn(child, arguments,
flag, where, howmany, &tids)
Computer Science and Engineering
Communication among Tasks
Sending Task
User
application
1
3
Daemon
User
application
Library
4
2
Receiving Task
5
Library
8
6
7
Daemon
Computer Science and Engineering
Standard PVM asynchronous
communication
 A sending task issues a send command (point 1)
 The message is transferred to the daemon
(point 2)
 Control is returned to the user application
(points 3 & 4)
 The daemon will transmit the message on the
physical wire sometime after returning control to
the user application (point 3)
Computer Science and Engineering
Standard PVM asynchronous
communication (cont.)



The receiving task issues a receive command
(point 5) at some other time
In the case of a blocking receive, the receiving
task blocks on the daemon waiting for a message
(point 6). After the message arrives, control is
returned to the user application (points 7 & 8)
In the case of a non-blocking receive, control is
returned to the user application immediately
(points 7 & 8)
Computer Science and Engineering
Send (3 steps)
1. A send buffer must be initialized
2. The message is packed into the buffer
3. The completed message is sent to its
destination(s)
Computer Science and Engineering
Receive (2 steps)
1. The message is received
2. The received items are unpacked
Computer Science and Engineering
Message Buffers

Buffer Creation (before packing)
Bufid = pvm_initsend(encoding_option)
Bufid = pvm_mkbuf(encoding_option)
Encoding option
0
1
2
Meaning
XDR
No encoding
Leave data in place
Computer Science and Engineering
Message Buffers (cont.)

Data Packing
pvm_pk*()

pvm_pkstr() – one argument
pvm_pkstr(“This is my data”);

Others – three arguments
1.
2.
3.

Pointer to the first item
Number of items to be packed
Stride
pvm_pkint(my_array, n, 1);
Packing functions can be called multiple times
to pack data into a single message
Computer Science and Engineering
Sending a message

Point to point (one receiver)
info = pvm_send(tid, tag)

broadcast (multiple receivers)
info = pvm_mcast(tids, n, tag)
info = pvm_bcast(group_name, tag)

Pack and Send (one step)
info = pvm_psend(tid, tag, my_array, length, data type)
Computer Science and Engineering
Receiving a message

Blocking
bufid = pvm_recv(tid, tag)
-1  wild card in either tid or tag

Nonblocking
bufid = pvm_nrecv(tid, tag)
bufid = 0 (no message was received)

Timeout
bufid = pvm_trecv(tid, tag, timeout)
bufid = 0 (no message was received)
Computer Science and Engineering
Different Receive in PVM
Time
Funciton
is called
Pvm_recv()
wait
Pvm_nrecv()
Continue
execution
Time is
expired
Message
arrival
Pvm_trecv()
wait
Resume
execution
Resume
execution
Blocking
Non-blocking
Timeout
Computer Science and Engineering
Data unpacking
pvm_upk*()

pvm_upkstr() – one argument
pvm_upkstr(string);

Others – three arguments
1.
2.
3.
Pointer to the first item
Number of items to be unpacked
Stride
pvm_upkint(my_array, n, 1);
Computer Science and Engineering
Task Synchronization
Synchronization constructs are used to
force a certain order of execution among
the activities in a parallel program.
Synchronization Constructs
Blocking Receive
Barriers
Computer Science and Engineering
Blocking Receive
T0
TID = 100
T1
TID = 200
f()
pvm_send(200,tag)
pvm_recv(100,tag)
g()
g() in T1 is not executed until f() in T0 has finished
Computer Science and Engineering
Group Barrier in PVM
T0
T1
T2
pvm_barrier(“slave”, 3)
pvm_barrier(“slave”, 3)
Synchronization
Point
wait
proceed
wait
pvm_barrier(“slave”, 3)
proceed
proceed
Group: slave
Computer Science and Engineering
Reduction Operation
info = pvm_reduce(func, data, n, datatype, tag,
group_name, root)
Example
info = pvm_reduce(PvmSum, dataarray, 5, PVM_INT, tag,
“slave”, root)
T0
T1(root)
T2
10,5,20,8,30
2,15,4,12,6
8,25,6,10,14
Before reduction
10,5,20,8,30
20,45,30,30,50
8,25,6,10,14
after reduction
Computer Science and Engineering
Work Assignment (different
programs)
info1 = pvm_spawn(“/user/rewini/worker1”, 0, 1, “lpc01”, 1, &tid1)
info2 = pvm_spawn(“/user/rewini/worker2”, 0, 1, “lpc02”, 1, &tid2)
info3 = pvm_spawn(“/user/rewini/worker3”, 0, 1, “lpc03”, 1, &tid3)
info4 = pvm_spawn(“/user/rewini/worker4”, 0, 1, “lpc04”, 1, &tid4)
Computer Science and Engineering
Work Assignment (Same Program)
If we know that the IDs are 1, 2, .., n-1
Switch (my_id) {
case 1:
/* Work assigned to the worker whose id number is 1 */
break;
case 2:
/* Work assigned to the worker whose id number is 2 */
break;
…
case n-1:
/* Work assigned to the worker whose id number is n-1 */
break;
default:;} /* end switch */
Computer Science and Engineering
Using task ID array to get my_id
 The supervisor sends an array containing
the TIDs of all the tasks to all the workers.
 The supervisor’s TID is saved in the zero
element of the array and the workers are
saved in elements 1 to n-1.
 Each worker searchers for its own TID and
the index can be used to identify the
corresponding worker.
Computer Science and Engineering
Using task groups to get my_id



All the tasks join one group and the
instance numbers are used as the new
task identifiers.
The supervisor is the first one to join the
group and gets instance number 0.
The workers get instance numbers in the
range from 1 to n-1
Computer Science and Engineering