Channels ▼
RSS

Design

Parallel Processing Clusters & PVM

Source Code Accompanies This Article. Download It Now.


November, 2005: Parallel Processing Clusters & PVM

Dave is a professor in the Department of Mathematics and Computer Science at Northern Michigan University. He can be reached at dpowers@nmu.edu.


Parallel Virtual Machine (PVM) is freely available network clustering software (http://www.csm.ornl.gov/pvm/) that provides a scalable network for parallel processing. Developed at the Oak Ridge National Lab and similar in purpose to the Beowulf cluster, PVM supports applications written in Fortran and C/C++. In this article, I explain how to set up parallel processing clusters and present C++ applications that demonstrate multiple tasks executing in parallel.

Setting up PVM-based parallel processing clusters is straightforward and can be done with existing workstations that are also used for other purposes. There is no need to dedicate computers to the cluster; the only requirements are that the workstations must be on a network and use UNIX/Linux. PVM creates a single logical host from multiple workstations and uses message passing for task communication and synchronization (Figure 1).

My motivation for setting up a parallel processing cluster was to provide a system that students could use for coursework and research projects in parallel processing. My specific goals were to set up a working cluster and demonstrate with test software that multiple tasks could execute in parallel using the cluster.

Why Use PVM?

Granted, there is other software—most notably Beowulf—for clustering workstations together for parallel processing. So why PVM? The main reasons I decided to use PVM were that it is freely available, requires no special hardware, is portable, and that many UNIX/Linux platforms are supported. The fact that I could use Linux workstations that were already available in our computer lab without dedicating the use of those machines to PVM was a major advantage for it.

Other important PVM features include:

  • A PVM cluster can be heterogeneous, combining workstations of different architectures. For example, Intel-based computers, Sun SPARC workstations, and Cray supercomputers could all be in the same cluster. Also, workstations from different types of networks could be combined into one cluster.
  • PVM is scalable. The cluster can become more robust and powerful by just adding additional workstations to the cluster.
  • PVM can be configured dynamically by using the PVM console utility or under program control using the PVM API. For example, workstations can be added or deleted while the cluster is operational.
  • PVM supports both the SPMD and MPMD parallel processing models. SPMD is single program/multiple data. With PVM, multiple copies of the same task can be spawned to execute on different sets of data. MPMD is multiple program/multiple data. With PVM, different tasks can be spawned to execute with their own set of data.

How PVM Works

A PVM background task is installed on each workstation in the cluster. The pvm daemon (pvmd) is used for interhost communication. Each pvmd communicates with the other pvm daemons via User Datagram Protocol (UDP). PVM tasks written using the PVM API communicate with pvmd via Transmission Control Protocol (TCP). Parallel-executing PVM tasks can also communicate with each other using TCP. Communication between tasks using UDP or TCP is commonly referred to as "communication using sockets" (Figure 2).

The pvmd task also acts as a task scheduler for user-written PVM tasks using available workstations (hosts) in the cluster. In addition, each pvmd manages the list of tasks that are running on its host computer. When a parent task spawns a child task, the parent can specify which host computer the child task runs on, or the parent can defer to the PVM task scheduler which host computer is used.

A PVM console utility gives users access to the PVM cluster. Users can spawn new tasks, check the cluster configuration, and change the cluster using the PVM console utility. For example, a typical cluster change would be to add/delete a workstation to/from the cluster. Other console commands list all the current tasks that are running on the cluster. The halt command kills all pvm daemons running on the cluster. In short, halt essentially shuts the cluster down.

The PVM console utility can be started from any workstation in the cluster. For example, if workstations in the cluster are separated by some physical distance, access to the cluster may be from different locations. However, when the cluster is shut down, the first use of the PVM console utility restarts the PVM software on the cluster. The machine on which the first use of the console utility occurs is the "master host." The console utility starts the pvmd running on the master host, then starts pvmd running on all the other workstations in the cluster. The original pvmd (running on the master host) can stop or start the pvm daemon on the other machines in the cluster. All console output from PVM tasks is directed to the master host. Any machine in the cluster can be a master host. Once the cluster is started up, only one machine in the cluster is considered the master host.

Installing PVM

Installing and running PVM is straightforward if you do it on a single machine. You can then use the PVM API to simulate parallel processing. However, to demonstrate true parallel processing (that is, multiple tasks executing at the same time), more workstations need to be added to the cluster. However, installing and configuring PVM in a multiworkstation cluster can initially be painful. PVM requires this hardware/software environment to function:

  • A heterogeneous cluster of workstations networked together.
  • A machine architecture that uses a supported version of UNIX/Linux.
  • rsh (remote shell), command network support for PVM.

The configuration I selected consisted of five 850-MHz Pentium workstations (with network connections) running Red Hat 9.0 Linux. The reason I used this hardware and operating system was because it was already available in our campus computer lab. The installation and configuration of PVM may vary depending on the version of UNIX/Linux used.

If you already have a workstation with a version of UNIX/Linux installed, there are three steps to installing PVM on your workstation:

  1. Install and enable the rsh server.
  2. Set environment variables for PVM.
  3. Download and install the PVM software.

The first two steps are the most challenging. Step 3 is relatively straightforward. In setting up PVM, I wanted nonroot users to be able to use the PVM cluster even though some of the installation steps may require root privileges.

PVM will not run a cluster of machines unless rsh is installed and enabled on all workstations in the cluster. The rsh set-up is somewhat problematic and the man pages for rsh confusing. Additional information is available on the Web by using the phrase "Redhat rsh" on Google. There are five steps to installing and enabling the rsh server:

  1. Install the rsh server. To install the rsh server on Red Hat 9, click on the red hat (lower-left of screen), select System Settings, and click on Add/Remove Applications. You must wait while the system checks to see which software packages are already installed. You are then presented with a screen from which you can add/delete applications by checking/unchecking the appropriate box. Under the Servers category and Network Servers subcategory, check the box for rsh-server, then click the Update button. You will be asked to insert a distribution CD for Red Hat. The rsh-server is copied from the CD and installed on your system.
  2. Enable the rsh server. To install the rsh server on Red Hat 9, click on the red hat, then select System Settings, Server Settings, and Services. You are then presented with a screen from which you can add/delete applications by checking/unchecking the appropriate box. Check the rsh box, select the xinetd item, and press the restart icon. Quit the Services and save changes.
  3. Create a file of users who can execute commands on this workstation. Create a file, /ect/hosts.equiv or $HOME/.rhosts, which lets users on other workstations execute commands on the workstation where this file exists. The /etc/hosts.equiv file is used system wide but will not provide root or superuser access for rsh (Figure 3). The $HOME/.rhosts file is created for a specific user, where $HOME refers to the user's home directory, such as /home/dsmith or ~dsmith. This file can be created for any user, including root (Figure 4). This file lets the same user from a different workstation execute commands on this workstation.
  4. Set file permissions for the file in Step 3. The file permissions for /etc/hosts.equiv or $HOME/.rhosts must be set to 600 (rw access for the owner only) by using the chmod command. The owner of the file must issue the chmod command: chmod 600 /etc/hosts.equiv or chmod 600 $HOME/.rhosts.
  5. Test rsh as a root user (if .rhosts file used) and nonroot user. To see if you can rsh to yourself, try: rsh your_host_name ' -l'. To see if you can rsh to another host, try: rsh another_host_name 's -l'. You will get the error "Permission denied" if the user account does not exist on the remote host or if the host/user is not in the remote host /etc/hosts.equiv or $HOME/.rhosts file. Set the environment variables for PVM in the /etc/profile or $HOME/.bash_profile file before downloading and installing PVM (Figure 5).

Restart the computer so that the environment variables can take effect. Download and install the PVM software. Select the file pvm3.4.4.tgz and download PVM to the $HOME directory on the workstation. Uncompress the tgz file: tar xvfz pvm3.4.4.tgz. This creates a directory, pvm3, under the $HOME directory, which contains all of the PVM files. Build and install the PVM software using the command make from the $HOME/pvm3 directory.

For example, assume that a cluster of four Linux workstations have the network hostnames alpha, beta, delta, and gamma. Also assume that PVM will be run by the nonroot user, myaccount, on all the workstations. When logged in as the user myaccount, $HOME is equal to /home/myaccount. On each host or workstation:

  1. As a root user, create the file /etc/hosts.equiv with the contents:
  2. alpha myaccount
    beta myaccount
    delta myaccount
    gamma myaccount

  3. Set the file permissions chmod 600 /etc/hosts.equiv.
  4. As a root user, edit the file /etc/profile and add:
  5. # PVM environment variables
    PVM_ROOT=/home/myaccount/pvm3
    PVM_ARCH=LINUX
    export PVM_ROOT PVM_ARCH
    # location of the pvm daemon, pvmd
    PVM_DPATH=/home/myaccount/pvm3/lib/ pvmd
    export PVM_DPATH

  6. Restart the workstation so that the environment variables can take effect.
  7. Download and install the PVM software in the /home/myaccount folder.
  8. Create and compile programs. Store the binaries in the /home/myaccount/ pvm3/bin/LINUX folder.
  9. On the master host, login as user "myaccount" and create a hostfile called "pvm_hosts" in /home/myaccount with the contents alpha, beta, delta, and gamma.
  10. Run the pvm console utility using the command /home/myaccount/pvm3/console/LINUX/pvm pvm_hosts. This command starts the pvm console utility and the pvmd running on the master host. Also, slave pvmds are started on all the other hosts in the cluster, which are listed in pvm_hosts.
  11. Using the conf (configuration) command at the pvm prompt lists all the host workstations in the PVM cluster.
  12. Use the console command to start the first PVM task: pvm>spawn -> p1.

Using PVM

To create and compile programs that use the PVM API, you must include the header file pvm3.h and link with libpvm3.a. To compile and link a program (say, p1.cpp) to use the PVM API, enter the command:

g++ -o $HOME/pvm3/bin/$PVM_ARCH/p1
-I $PVM_ROOT/include p1.cpp
-L $PVM_ROOT/lib/$PVM_ARCH -lpvm3

The default folder for the executable program files (PVM binaries) is $HOME/ pvm3/bin/$PVM_ARCH. This is where the pvmd task looks for tasks to execute (spawn). If multiple architectures are used in the cluster, programs need to be compiled and linked for each architecture because any program could execute on any available workstation in the cluster.

To execute tasks in the PVM environment, start the pvm console utility using: $HOME/pvm3/console/$PVM_ARCH/pvm hostfile. The pvm console utility starts the pvmd task(s) running if the daemon(s) are not running. Again, the workstation that starts up the pvmds is the master host. Additional hosts may be added from a list of hosts in the hostfile, by using the "add hostname" command at the pvm> console prompt or by adding hostnames from executing PVM tasks. The file hostfile, stored in the $HOME directory, can use any filename and contains a list of computers (DNS names or hostnames) to be added to the cluster.

User programs can be started in one of these three ways:

  • From the pvm console utility by issuing: pvm>spawn -> p1. This requires a space after spawn and before the task name.
  • From the system prompt if pvmd is already running on the host: <system_ prompt>./p1.
  • By spawning the task from a currently executing task.

The PVM execution environment requires the location of the program binaries on each host and the location of the pvmd on each host. The execution environment is set by editing /etc/profile.

The PVM API

The PVM API contains functions that can be grouped into several categories, including:

  • Process Management and Control, which contains functions that spawn child tasks, kill specific tasks, halt all pvm tasks and daemons, add hosts to the cluster, and delete hosts from the cluster.
  • Message Sending and Receiving, which contains functions for sending and receiving messages from one task to another. There is also a multicast function that lets one task send a message to multiple tasks. Messages are routed by using a task identification (TID). Each task running in the PVM cluster has a unique task ID. Communication is synchronized by using blocking receives. This means that the task's execution is suspended until the requested information is received.
  • Message Buffer Management and Packing/Unpacking, which handles message buffering and data conversion. PVM handles the data conversion involved when data is sent/received over different architectures. All data is packed before sending and unpacked after receiving.

Test Programs and Results

Getting multiple programs to run at the same time on multiple hosts is more complicated than merely starting several programs and assigning them to different hosts. Normally, there is a main program, which is started from the console utility via the spawn command. The main program then spawns child tasks.

Example 1 is pseudocode for a main program that loops n times, each time spawning a new child task and sending information to the child task that it needs to continue processing. Then the parent task receives the results from the child when the child is done processing. The problem with this algorithm is that the child tasks are not executing at the same time. Receive operations are blocking and the first child task must finish and send a message to the parent before the next child is spawned. So even though multiple tasks are being executed on multiple hosts, the tasks are not executing in parallel; see the results in Figure 6.

Example 2 is pseudocode for a revised main program. This main program contains two loops. The first loop spawns all of the child tasks and sends the information necessary for each child to begin processing. All the child tasks start execution about the same time and execute in parallel because there are no blocking operations in the first loop. The second loop waits for each child task to complete processing and sends results back to the parent task; see the results in Figure 7. The actual listings for the parent and child programs are in Listing One. Data can be passed from a parent task to a child task in one of two ways: Using a message (Listing Two; available electronically, see "Resource Center" page 4) or by using argument values when the child is spawned (Listing Three; also available electronically).

Conclusion

Using the techniques presented here, it is fairly easy to create a cluster of networked workstations that can be used for parallel processing. The cluster works as one virtual machine to reduce the elapsed execution time of multiple tasks. The test programs demonstrate that multiple tasks execute at the same time on multiple hosts.

Future work with PVM would include efficient ways to load software changes over the cluster. Every time a program is updated and rebuilt, the program binaries must be updated on all machines in the cluster. A primary use of PVM in the future would be to implement and test algorithms decomposed for parallel operation. Some possible algorithms would include matrix multiplication, sorting, and puzzle solutions using trees.

DDJ



Listing One
(a)

#include <stdio.h>
#include <string.h>
#include <time.h>
#include <pvm3.h>

// David J. Powers. This program spawns another 10 tasks, sends a text message
// to each child task, then waits to receive a message from each child task.

void itoa(int n, char w[]);

int main(int argc, char *argv[])
{
    struct tm *p1, *p2;
    time_t     t1, t2;
    int r;      // spawn return code
    int m = 1;  // message id
    int PTid;   // parent task id
    int Tid[10]; // array of child task id's
    char mess[100]; // send buffer
    long res;       // result value
    PTid = pvm_mytid();
    printf("P5: Parent id = %d\n",PTid);
    t1 = time(NULL);
    p1 = localtime(&t1);
    printf("P5: Start time: %d:%d:%d \n",p1->tm_hour,p1->tm_min,p1->tm_sec);
        for (int k=0; k<10; k++)
        {
            // spawn child task, p6
                // no argument values, let pvm select host
                // spawn 1 task and save child task id in Tid[k]
                pvm_spawn("p6",NULL,PvmTaskDefault,"",1,&Tid[k]);

            // send message
            itoa(k+27,mess);
            printf("P5:  message:%s: \n",mess);
            pvm_initsend(PvmDataDefault);
            pvm_pkstr(mess);
            pvm_send(Tid[k],m);

            // receive message:  blocking
            pvm_recv(Tid[k],m);
            pvm_upklong(&res,1,1);

            // display result
            printf("P5: k = %d, Fibonacci number = %ld \n",(k+27),res);
        }
    t2 = time(NULL);
    p2 = localtime(&t2);
    printf("P5: Stop  time: %d:%d:%d \n",p2->tm_hour,p2->tm_min,p2->tm_sec);
    printf("P5: Elapsed time = %d seconds. \n",(t2-t1));
    pvm_exit();
    return 0;
}
void itoa(int n, char w[])
{
   int i=0;
    int j, c;
    do
    {
        w[i++] = n % 10 + '0';
    }
    while ( (n /= 10) > 0);
    w[i] = '\0';
    // now reverse the chars
    for (i=0, j = strlen(w) - 1;  i<j;  i++, j--)
    {
        c = w[i];
        w[i] = w[j];
        w[j] = c;
    }
}  // end of itoa

(b)
#include <stdio.h>
#include <stdlib.h>
#include <pvm3.h>

// David J. Powers. This program receives a text message. The ASCII string is 
// converted to an integer value which is used as n in a Fibonacci function.  
// The Fibonacci number is sent back to the calling task.

long fibr(long k);
int main(int argc, char *argv[])
{
    int m=1;         // message id
      int PTid;        // parent task id
      char mess[100];  // send buffer
      int num;         // float value received
      long res;        // result after division
      PTid = pvm_parent();  // get parent task id
      printf("P6: Parent id = %d\n",PTid);

    // receive value:  blocking
    pvm_recv(PTid,m);
    pvm_upkstr(mess);

    // calculate Fibonacci number
    num = atoi(mess);
      res = fibr(num);

    // send results
      pvm_initsend(PvmDataDefault);
    pvm_pklong(&res,1,1);
    pvm_send(PTid,m);

    pvm_exit();
    return 0;
}
// recursive Fibonacci function
long fibr(long k)
{
  if (k==0 || k==1) return k;
  return fibr(k-1) + fibr(k-2);
}
Back to article


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video