Parallel and Distributed Processing CSE 8380Parallel Virtual Machine (PVM)Main Constructs in PVMPVM SoftwarePVM ApplicationApplication StructurePowerPoint PresentationSlide 8Pvm_spawnCommunication among TasksDifferent Receive in PVMTask SynchronizationBlocking ReceiveGroup Barrier in PVMReduction OperationWork Assignment (different programs)Work Assignment (Same Program)Using task ID array to get my_idSlide 19Slide 20Slide 21Using task groups to get my_idSlide 23Slide 24Computer Science and EngineeringParallel and Distributed Parallel and Distributed ProcessingProcessingCSE 8380CSE 8380February 24 2005February 24 2005Session 13Session 13Computer Science and EngineeringParallel Virtual Machine (PVM)Review SynchronizationReduction operationsWork AssignmentsComputer Science and EngineeringMain Constructs in PVMTask CreationCommunicationSynchronizationOthersComputer Science and EngineeringPVM SoftwareTwo Components:Library of PVM routinesDaemonComputer Science and EngineeringPVM ApplicationA number of sequential programs, each of which will correspond to one or more processes in a parallel programComputer Science and EngineeringApplication StructureStart graphTreeComputer Science and EngineeringW1 W2 W3 W4Sa) The supervisor creates four workers and send them four sublists to sortSW1 W2W3W4b) The supervisor is idle and the four workers are sorting their sublistsW1 W2 W3 W4Ssortsort sort sortc) The four workers are sending their sorted sublists to the supervisorSW1 W2W3W4merged) The supervisor is merging the four sorted sublists and the four workers are idleComputer Science and EngineeringW1 W2 W3 W4Sa) The supervisor creates four workers and send them four sublistsSW1 W2W3W4b) The supervisor is idle and the four workers are sorting their sublistsW1 W2 W3 W4Ssortsort sort sorte) Workers W1 and W3 send two sorted sublists to the supervisorSW1 W2W3W4mergef) Th supervisor is merging two sorted sublists and the four workers are idleSW1 W2W3W4d) Workers W1 and W3 are merging two sublists each and W2 and W4 are idlemergemergeW1 W2 W3 W4Sc) Workers W2 and W4 send their sorted sublists to W1 and W3, respectivelyComputer Science and EngineeringPvm_spawnnum = pvm_spawn(child, arguments, flag, where, howmany, &tids)Computer Science and EngineeringCommunication among TasksUser applicationLibraryDaemon12 34User applicationLibraryDaemon5678Sending Task Receiving TaskComputer Science and EngineeringDifferent Receive in PVMPvm_recv()waitTimeFuncitonis calledTime is expiredMessage arrivalBlockingPvm_nrecv()Continue executionNon-blockingPvm_trecv()waitTimeoutResume executionResume executionComputer Science and EngineeringTask SynchronizationSynchronization constructs are used to force a certain order of execution among the activities in a parallel program.Synchronization ConstructsBlocking ReceiveBarriersComputer Science and EngineeringBlocking Receivepvm_recv(100,tag)pvm_recv(100,tag)g()g()f()f()pvm_send(200,tag)pvm_send(200,tag)T0T0TID = 100TID = 100T1T1TID = 200TID = 200g() in T1 is not executed until f() in T0 has finishedg() in T1 is not executed until f() in T0 has finishedComputer Science and EngineeringGroup Barrier in PVMpvm_barrier(“slave”, 3)proceedwaitpvm_barrier(“slave”, 3)proceedwaitpvm_barrier(“slave”, 3)proceedT2T0 T1Group: slaveSynchronizationPointComputer Science and EngineeringReduction Operationinfo = pvm_reduce(func, data, n, datatype, tag, group_name, root)Exampleinfo = pvm_reduce(PvmSum, dataarray, 5, PVM_INT, tag, “slave”, root)T0 10,5,20,8,30 10,5,20,8,30T1(root) 2,15,4,12,6 20,45,30,30,50T2 8,25,6,10,14 8,25,6,10,14Before reduction after reductionComputer Science and EngineeringWork 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 EngineeringWork Assignment (Same Program)If we know that the IDs are 1, 2, .., n-1Switch (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 EngineeringUsing 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 Engineering0 1 2 n-1supervisor ’s TID workers’ TIDsindex(The index can be used to assign dif ferent work to workers within the same program)Computer Science and EngineeringSupervisor Code.....int tid[n];mytid = pvm_mytid(); /* get supervisor’s tid */tid[0] = mytid;pvm_spawn(..., ..., ..., n-1, tid+1); /* start up the children *//* Now send the array tid to all the workers */............../* Do the initialization and buffer packing here */pvm_mcast(tid,n,1);/* Now do any work that needs to be done in the parent */................/* put it in the zeroth element of the array *//* array to keep track of child TIDs */............../* ************************** Supervisor ************************ */Computer Science and EngineeringWorker Code/* ************************** Worker ************************ */worker_id = pvm_mytid(); /* Get the tid of this worker */supervisor_id = pvm_parent(); /* Get the tid of the supervisor */pvm_recv(supervisor_id,1); /* receive a message from the supervisor *//* do some unpacking to get the array tid here*/for(i = 0; i < n && tid[i] != worker_id; i++);my_id = i;/* my_id for each worker is a unique integer between 1 and n-1 *//* The switch statement should be inserted here */.............../* Search the array tid */Computer Science and EngineeringUsing 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-1Computer Science and EngineeringSupervisor Code/* ************************** Supervisor ************************ */int tid[n];mytid =