6.2.4. Combining the C++ Runtime Library and the PVM Library

Since access to the PVM is provided through a collection of library routines, a C++ program treats the PVM as any other library. Keep in mind that each PVM program is a standalone C++ program with its own main() function. This means that each PVM program has its own address space. When a PVM task is spawned, a new process is created. Each PVM program will have its own process and process id. The PVM processes are visible to the ps utility. Although two or more PVM tasks may be working together to solve some problem they will have their own copies of the C++ runtime library. Each program has its own iostream , template library, algorithms and so on. The scope of global C++ variables do not cross address space. This means global variables in one PVM task will be invisible to the other PVM tasks involved in the processing. Message passing is used to communicate between these separate tasks. Notice that this is in contrast to multithreaded programs where threads share the same address space and may communicate through parameter passing and global variables. If the PVM programs are executing on a single computer that has multiple processors then the programs may share a file system and can use pipes, FIFOs, shared memory, and files as additional means to communicate. While message passing is the premier method of communicating between PVM tasks, nothing prevents the use of shared file systems, clipboards, or even command line arguments as supplemental methods of communication between tasks. The PVM library adds to rather than restricts the capabilities of the C++ runtime library.

6.2 .5. Approaches to Using PVM Tasks

The work a C++ program performs can be distributed between functions, objects, or combinations of functions and objects. The units of work in a program usually fall into logical categories: input/output, user interface, database processing, signal processing, error handling, numerical computation, etc. Also, we try to keep user interface code separated from file processing code and printing routine code separated from the numerical computation code. Therefore, not only do we divide up the work our program does between functions or objects, we try to keep categories of functionality together. These logical groupings are organized into libraries, modules, object patterns, components and frameworks. We maintain this type of organization when introducing PVM tasks into a C++ program. We can arrive at the WBS (Work Breakdown Structures) using either a bottom up or top down approach. In either case, the parallelism should naturally fit within the work that a function, module, or object has to do.

It is not a good idea to attempt to force parallelism in a program. Forced parallelism produces awkward program architectures that are hard to understand by making them hard to maintain and often hard to determine program correctness. So when a program uses PVM tasks they should be a result of the natural division within the program. Each PVM task should be traceable to one of the categories of work within the program. For instance, if we have an application that has NLP (Natural Language Processing) and TTS (Text To Speech ) processing as part of its user interface and inferencing as part of its data retrieval, then the parallelism that is natural within NLP component should be represented as tasks within the NLP module or object that is responsible for NLP. Likewise the parallelism within the inferencing component should be represented as tasks within the data retrieval module or the object or framework that is responsible for data retrieval. That is, we identify PVM tasks where they logically fit within the work that the program is doing as opposed to dividing the work the program does into a set of generic PVM tasks.

The notion of logic first, parallelism second, has several implications for C++ programs. It means that we might spawn PVM tasks from the main() function. We might spawn PVM tasks from subroutines called from main() or from other subroutines. We might spawn PVM tasks from within methods belonging to objects. Where we spawn the tasks depends on the concurrency requirements of the function, module, or object that is performing the work. The PVM tasks generally fall into two categories. SPMD (a derivative of SIMD) and MPMD (a derivative of MIMD). In the SPMD model the tasks will execute the same set of instructions but on different pieces of data. In the MPMD model each task executes different instructions on different data. Whether we are using the SPMD model or the MPMD model the spawning of the task should be from the relevant areas of the program. Figure 6-4 shows some possible configurations for spawning PVM tasks.

Figure 6-4

6.2.5.1. Using the SPMD (SIMD) Model with PVM and C++

In Figure 6-4, Case 1 represents the situation where the function main() spawns from 1 to N tasks where each task performs the same set of instructions but on different data sets. There are several options for implementing this scenario. Example 6.1 shows main() using the pvm_spawn routine.

// Example 6.1 Calling pvm_spawn routine from main() 

int main(int argc, char *argv[])
{
   int TaskId[10];
   int TaskId2[5];
   pvm_spawn("set_combination",NULL,0,"",10,TaskId); // 1rst Spawn
   pvm_spawn("set_combination",argv,0,"",5,TaskId2); // 2nd Spawn
   //...
}

In Example 6.1, the first spawn creates 10 tasks. Each task will execute the same set of instructions contained in the set_combination program. The TaskId array will contain the task identifiers for the PVM tasks if the spawn was successful. Once the program in Example 6.1 has the TaskIds then it can use the pvm_send() routines to send specific data for each program to work on. This is possible because the pvm_send() routine contains the task identifier of the receiving task. The second spawn in Example 6.1 creates 5 tasks but in this case it passes each task information through the argv parameter. This is an additional method to pass information to tasks during start up. This is another way for a child task to uniquely identify itself by using values it receives in the argv parameter. In Example 6.2, the main() function uses multiple calls to pvm_spawn() to create N tasks as opposed to a single call.

// Example 6.2 Using multiple calls to pvm_spawn from main().

int main(int argc, char *argv[])
{
   int Task1;
   int Task2;
   int Task3;
   //...
   pvm_spawn("set_combination", NULL,1,"host1",1,&Task1);
   pvm_spawn("set_combination",argv,1,"host2",1,&,Task2);
   pvm_spawn("set_combination",argv++,1,"host 3",1,&,Task3);
   //...
}

The approach used in Example 6.2 can be used when you want the tasks to execute on specific computers. This is one of the advantages of the PVM environment. A program can take advantage of some particular resource on a particular computer, e.g. special math processor, graphics processor, or MPP capabilities. Notice in Example 6.2, each host is executing the same set of instructions but each host received a different command line argument. Case 2 in Figure 6-4 represents the scenario where the main() function does not spawn the PVM tasks. In this scenario the PVM tasks are logically related to funcB() and therefore funcB() spawns the tasks. The main() function and funcA() don't need to know anything about the PVM tasks so there is no reason to put any of the PVM housekeeping code in those functions. Case 3 in Figure 6-4 represents the scenario where the main() function and other functions in the program have natural parallelism. In this case the other function is funcA() . Also the PVM tasks executed by main() and the PVM tasks executed by funcA() execute different code. Although the tasks that main() spawns execute identical code and the tasks that funcA() spawns executes identical code, the two sets of tasks are different. This illustrates that a C++ program may use collections of tasks to solve different problems simultaneously. There is no reason that the program has to be restricted to one problem at a time. In Case 4 from Figure 6-4, the parallelism is contained within an object, therefore one of the object's methods spawns the PVM tasks. Here, the logical place to initiate the parallelism was within a class as opposed to some free floating function.

As in the other cases, the PVM tasks spawned in Case 4 all execute the same instructions but with different data. This SPMD (Single Program Multiple Data) method is a commonly used technique for parallelization of certain kinds of problem solving. The fact C++ has support for objects and generic programming using templates makes C++ a particularly powerful choice for this kind of programming. The objects and templates allow the C++ programmer to represent very general and flexible solutions to entire classes of problems with a single piece of code. This single piece of code fits in nicely with the SPMD model of parallelism. The notion of a class extends the SPMD model so that an entire class of problems can be solved. The templates allow the class of problems to be solved for virtually any data type. So although each task in the SPMD model is executing the same piece of code, it might be for an object or any of its descendants and it might be for different data types (different objects!). For example, Example 6.1 uses four PVM tasks to generate four sets in which each has C(n,r) elements: C(24,9), C(24,12), C(7,4), and C(7,3). Specifically Example 6.3 enumerates the combinations of a set of twenty-four colors taken nine and twelve at a time. It also enumerates the combinations of a set of seven floating point numbers taken four at a time and three at a time. For an explanation of the notation C(n,r) see Sidebar 6.1 Combination Notation.

// Example 6.3 Creating combinations of sets.

int main(int argc,char *argv[])
{
   int RetCode,TaskId[4];
   RetCode = pvm_spawn("pvm_generic_combination",NULL,0,"",4,TaskId);
   if(RetCode == 4){
      colorCombinations(TaskId[0],9);
      colorCombinations(TaskId[1],12);
      numericCombinations(TaskId[2],4);
      numericCombinations(TaskId[3],3);
      saveResult(TaskId[0]);
      saveResult(TaskId[1]);
      saveResult(TaskId[2]);
      saveResult(TaskId[3]);
      pvm_exit();
   }
   else{
        cerr << "Error Spawning ChildProcess" << endl;
        pvm_exit();
   }
   return(0);
}

Notice in Example 6.3 we spawn four PVM tasks:

pvm_spawn( "pvm_generic_combination ",NULL,0, "",4,TaskId);

Each task will execute the program named pvm_generic_combination. The NULL argument in our pvm_spawn call means that we are not passing any options via the argv[] parameter. The 0 in our pvm_spawn call means we don't care which computer the tasks execute on. TaskId is an array of 4 integers and will contain the task identifiers for each of the PVM tasks spawned if the call is successful. Notice in Example 6.3 we call colorCombinations() and numericCombinations() . These two functions assign the PVM tasks work. Example 6.4 contains the function definition for colorCombinations() .

// Example 6.4 Definition of colorCombinations() function

void colorCombinations(int TaskId,int Choices)
{
   int MessageId =1;
   char *Buffer;
   int Size;
   int N;
   string Source("blue purple green red yellow orange silver gray");
   Source.append("pink black white brown light_green aqua beige cyan");
   Source.append("olive azure magenta plum orchid violet maroon lavender");
   Source.append("\n");
   Buffer = new char[(Source.size() + 100)];
   strcpy(Buffer,Source.c_str());
   N = pvm_initsend(PvmDataDefault);
   pvm_pkint(&Choices,1,1);
   pvm_send(TaskId,MessageId);
   N = pvm_initsend(PvmDataDefault);
   pvm_pkbyte(Buffer,strlen(Buffer),1);
   pvm_send(TaskId,MessageId);
   delete Buffer;
}

Notice in Example 6.3 there are two calls to colorCombinations() . Each call assigns a PVM task a different number of color combinations to enumerate: C(24,9), and C(24,12). The first PVM task will produce 1,307,504 color combinations and the second task will produce 2,704,156 color combinations. The program named in the pvm_spawn() call does all the work. Each color is represented by a string. Therefore, when the pvm_generic_combination program is producing combinations it does so using a set of strings as the input. This is in contrast to the numericCombinations() function shown in Example 6.5. The code in Example 6.3 makes two calls to numericCombinations() function. The first generates C(7,4) combinations and the second generates C(7,3) combinations.

// Example 6.5 Using PVM tasks to produce numeric combinations

void numericCombinations(int TaskId,int Choices)
{
   int MessageId = 2;
   int N;
   double ImportantNumbers[7] = {3.00e+8,6.67e-11,1.99e+30, 
                                 1.67e-27,6.023e+23,6.63e-34,
                                 3.14159265359};
   N = pvm_initsend(PvmDataDefault);
   pvm_pkint(&Choices,1,1);
   pvm_send(TaskId,MessageId);
   N = pvm_initsend(PvmDataDefault);
   pvm_pkdouble(ImportantNumbers,5,1);
   pvm_send(TaskId,MessageId);
}