![[ Prev ]](../gx/navbar/prev.jpg){kind=small}
![[ Table of Contents ]](../gx/navbar/toc.jpg){kind=small}
![[ Front Page ]](../gx/navbar/frontpage.jpg){kind=small}
![[ Talkback ]](../gx/navbar/talkback.jpg){kind=small}
![[ FAQ ]](./../gx/navbar/faq.jpg){kind=small}
![[ Next ]](../gx/navbar/next.jpg){kind=small}
This article aims to provide an introduction to PVM and MPI, two widely used software systems for implementing parallel message passing programs. They enable us to use a group of heterogeneous UNIX/LINUX computers connected by a network as a single machine for solving a large problem.
Parallel processing is a form of computing in which a number of activities are carried out concurrently so that the effective time required to solve the problem is reduced. In the previous days, parallel processing was used for such thing as large scale simulations (e.g. molecular simulations, simulation of the explosion of an atomic bomb etc), solving large number crunching and data processing problems (e.g. compiling the census data) etc. However, as the cost of hardware is decreasing rapidly, parallel processing is being uses more and more in routine tasks. Multiple processor servers have been in existence for a long time. Parallel processing is also used in your own PC too. For example, a graphics processor working along with the main processor to render graphics on your monitor is also a form of parallel processing.
However, apart from the hardware facilities for parallel processing, some software support too is required so that we can run the programs in parallel and coordinate their execution. Such a coordination is necessary due to the dependencies of the parallel programs on one other. This will become clearer when we work through an example. The most widely used method to achieve such coordination is message passing in which the programs coordinate their execution and in general communicate with each other by passing message's to one other. So, for example, a program may tell another program, ``Ok! Here is the intermediate result you need to proceed.'' If all this sounds too abstract, lets proceed with a very simple example.
In this section, we will consider a very simple problem and consider how we can use parallel processing to speed up its execution. The problem is to find the sum of a list of integers stored in an array. Let us say that there are 100 integers stored in an array say items. Now, how do we parallelize this program? That is, we must first find out a way in which this problem can be solved by a number of programs working concurrently. Many a times, due to data dependencies, parallelization becomes a difficult problem. For example, if you want to evaluate (a + b) * c, which involves two operations, we cannot do them concurrently, the addition must be done before the multiplication. Fortunately, for the problem that we have chosen, parallelization is easy. Suppose that 4 program or processors will be working simultaneously to solve the addition problem. Then the simplest strategy would be to break the array items into 4 parts and have each program process one part. Thus the parallelization of the problem is as follows:
items[0] to items[24]. Similarly, P1 will find the sum of items[25] to items[49], P2 items[50] to items[74] and P3 items[75] to items[99].items are not known to the programs P0 to P3 and hence some program must tell these programs the values of the elements. Thus, apart from P0 to P3, we will require one more program that distributes data, collects results and coordinates execution. We call such a program as master and the programs P0 to P3 as slaves and this organization as the master - slave paradigm.With this organization in mind, let us write the algorithms for the master and the slave programs.
/* Algorithm for the master program */
initialize the array `items'.
/* send data to the slaves */
for i = 0 to 3
Send items[25*i] to items[25*(i+1)-1] to slave Pi
end for
/* collect the results from the slaves */
for i = 0 to 3
Receive the result from slave Pi in result[i]
end for
/* calculate the final result */
sum = 0
for i = 0 to 3
sum = sum + result[i]
end for
print sum
/* Algorithm for the slave program */
Receive 25 elements from the master in some array say `items'
/* calculate intermediate result */
sum = 0
for i = 0 to 24
sum = sum + items[i]
end for
send `sum' as the intermediate result to the master
Now that the basic algorithm has been designed, let us now consider how we can implement it. What hardware shall we run this program on? Clearly, very few of us have access to special machines designed to run parallel programs. However, no special hardware requirements are there in order to implement this program. A single computer or a group of interconnected computers will do, thanks to PVM, a software system that enables us to use interconnected computers for parallel program execution. PVM stands for Parallel Virtual Machine. It enables you to create number of programs or processes that run concurrently on same or different machines and provided functions with which you can pass messages among the processes for coordination. Even if you have a single computer, PVM will work on it, although there will be no ``real'' parallel processing as such. However, for learning purpose, that should be fine. Later on I will describe how to do ``real'' parallel processing using the PVM.
In order to use the PVM system, you need to install the PVM software on your Linux system. In case you are using Red Hat Linux, then the RPM package for PVM is included on the CD, so that you can install it as you normally install other packages. Assuming that you have installed PVM system on your machine, create the following directories(s) in your home directory: ~/pvm3/bin/LINUX/. Why ? Because PVM requires that some of the executables you create be copied in this directory. Once you have done this, your setup is ready. Test this by giving the command pvm on the prompt. This will start the PVM Console from which you can give commands to the PVM system and query status information. If everything is set OK, you will see the pvm> prompt. Here enter the command conf. The output should look something like this.
pvm> conf
conf
1 host, 1 data format
HOST DTID ARCH SPEED DSIG
joshicomp 40000 LINUX 1000 0x00408841
What does this mean? The PVM System allows you to consider a group of interconnected LINUX system to be viewed as a ``virtual'' computer having much higher computing capacity than the individual machines. Thus, PVM will distribute the processes among a number of computers. However, by default, PVM considers that only the host that you are working on is to be included in the PVM machine, i.e. all processes you create will be scheduled to run on the same host. The conf command shows what hosts or nodes are in the PVM. Currently, there is only one. Later on, we will see how to add more hosts. Presently, exit the PVM console by giving the command halt
Now that you are ensured that the PVM system has been properly installed, let us see how to write the programs. Programs for the PVM system can be written in both FORTRAN and C. We will be using the C language. To use the PVM system, you include some calls to the PVM functions in your C program along with the other statements and link the PVM library with your programs. To get you started with PVM, let us write a simple program in which there will be a master and a slave. The master will send the slave some string, which the slave will convert to upper case and send back to the master. The master and the slave programs are given as follows. To compile the programs, give the command make -f makefile.demo.
[Click here for a tar file containing the program listings.]
1 /* -------------------------------------------------------------------- *
2 * master_pvm.c *
3 * *
4 * This is the master program for the simple PVM demonstration. *
5 * -------------------------------------------------------------------- */
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <pvm3.h> /* declares PVM constants and functions */
9 #include <string.h>
10 int main()
11 {
12 int mytid; /* our task ID */
13 int slave_tid; /* task ID of the slave */
14 int result;
15 char message[] = "hello pvm";
16
17 /* enroll ourselves into the PVM system and get our ID */
18 mytid = pvm_mytid();
19 /* spawn the slave */
20 result = pvm_spawn("slave_pvm", (char**)0, PvmTaskDefault,
21 "", 1, &slave_tid);
22 /* check if the slave was spawned successfully */
23 if(result != 1)
24 {
25 fprintf(stderr, "Error: Cannot spawn slave.\n");
26 /* clean up and exit from the PVM system */
27 pvm_exit();
28 exit(EXIT_FAILURE);
29 }
30 /* initialize the data buffer to send data to slave */
31 pvm_initsend(PvmDataDefault);
32 /* ``pack'' the string into the data buffer */
33 pvm_pkstr(message);
34 /* send the string to the slave with a message tag of 0 */
35 pvm_send(slave_tid, 0);
36 /* wait and receive the result string from the slave */
37 pvm_recv(slave_tid, 0);
38
39 /* ``unpack'' the result from the slave */
40 pvm_upkstr(message);
41 /* show the result from the slave */
42 printf("Data from the slave : %s\n", message);
43 /* clean up and exit from the PVM system */
44 pvm_exit();
45
46 exit(EXIT_SUCCESS);
47 } /* end main() */
48 /* end master_pvm.c */
1 /* -------------------------------------------------------------------- *
2 * slave_pvm.c *
3 * *
4 * This is the slave program for the simple PVM demonstration *
5 * -------------------------------------------------------------------- */
6 #include <stdio.h>
7 #include <ctype.h>
8 #include <stdlib.h>
9 #include <pvm3.h>
10 #define MSG_LEN 20
11 void convert_to_upper(char*);
12 int main()
13 {
14 int mytid;
15 int parent_tid;
16 char message[MSG_LEN];
17 /* enroll ourselves into the PVM system */
18 mytid = pvm_mytid();
19 /* get the task ID of the master */
20 parent_tid = pvm_parent();
21 /* receive the original string from master */
22 pvm_recv(parent_tid, 0);
23 pvm_upkstr(message);
24 /* convert the string to upper case */
25 convert_to_upper(message);
26 /* send the converted string to the master */
27 pvm_initsend(PvmDataDefault);
28 pvm_pkstr(message);
29 pvm_send(parent_tid, 0);
30 /* clean up and exit from the PVM system */
31 pvm_exit();
32
33 exit(EXIT_SUCCESS);
34 } /* end main() */
35 /* function to convert the given string into upper case */
36 void convert_to_upper(char* str)
37 {
38 while(*str != '\0')
39 {
40 *str = toupper(*str);
41 str++;
42 }
43 } /* end convert_to_upper() */
44 /* end slave_pvm.c */
1 # Make file for the demo PVM program
2 .SILENT :
3 # paths fro PVM include files and libraries
4 INCDIR=-I/usr/share/pvm3/include
5 LIBDIR=-L/usr/share/pvm3/lib/LINUX
6 # link the PVM library
7 LIBS=-lpvm3
8 CFLAGS=-Wall
9 CC=gcc
10 TARGET=all
11 # this is where the PVM executables go
12 PVM_HOME=$(HOME)/pvm3/bin/LINUX
13 all : $(PVM_HOME)/master_pvm $(PVM_HOME)/slave_pvm
14 $(PVM_HOME)/master_pvm : master_pvm.c
15 $(CC) -o $(PVM_HOME)/master_pvm master_pvm.c $(CFLAGS) $(LIBS) \
16 $(INCDIR) $(LIBDIR)
17 $(PVM_HOME)/slave_pvm : slave_pvm.c
18 $(CC) -o $(PVM_HOME)/slave_pvm slave_pvm.c $(CFLAGS) $(LIBS) \
19 $(INCDIR) $(LIBDIR)
Once your programs have been compiled, you must copy them into the ~/pvm3/bin/LINUX directory. (The makefile does it by default). Now to run the programs, you must first start the PVM system. To do this give the command pvm to start the PVM Console. Now at the pvm> prompt, type quit. The output will be as follows:
pvm> quit quit Console: exit handler called pvmd still running.Notice the last line, indicating that the PVM daemon (
pvmd) is still running. To run the PVM programs, you need to run the PVM daemon which manages the exchange of messages and that what we are doing here. Once the PVM daemon is running, you can run the program by the following commands:
[rahul@joshicomp rahul]$ cd ~/pvm3/bin/LINUX/ [rahul@joshicomp LINUX]$ ./master_pvm Data from the slave : HELLO PVM [rahul@joshicomp LINUX]$
Notice that the string is now in upper case as expected.
In this section, we will see exactly how this program works. First of all to use PVM function, you need to include a header file pvm3.h in your programs. This is done in line 8 of master_pvm.c and in line 9 of slave_pvm.c. Also when compiling the programs, you need to link it with the PVM library. This is done by specifying the -lpvm3 option to the compiler, as done in line 7 of makefile.demo. Also, you need to specify to the compiler the paths of header and library files, as is done on lines 4 and 5 of the makefile.
In the master program, we first get the task ID of the master by calling the PVM function pvm_mytid(). The PVM system assigns each process a unique 32 bit integer called as its task ID in the same way as Linux assigns each process a process ID. The task ID helps us identify the process with which we need to communicate. However, the master does not uses its task ID (stored in mytid) ever. Our intention here is just to call the function pvm_mytid(). This function enrolls the process into the PVM system and generates a unique task ID for the process. If we do not explicitly enroll the process, PVM automatically enrolls our process on the first call to any PVM function. Next we use pvm_spawn() to create the slave process. The first parameter, "slave_pvm" is the name of the executable for the slave. The second parameter is the arguments that you wish to the pass to the slaves (similar to argv in normal C). Since we do not want to send any arguments, we set this value to 0. The third parameter is a flag with which we can control how and where PVM starts the slave. Since we have only a single machine, we set this flag to PvmTaskDefault, specifying PVM to use default criteria while spawning the slave. The fourth parameter is the name of the host or the architecture on which we wish to run the program and here it is kept empty. It is used to specify the host or the architecture when the flag is other than PvmTaskDefault.The fifth parameter specifies the number of slaves to spawn and the sixth parameter is a pointer to an array in which the IDs of the slaves will be returned. This function returns the number of slaves actually spawned which we check for correctness.
A message in PVM consists of basically two parts, the data and a tag that identifies the type of the message. The tag helps us distinguish between different messages. For example, in the addition example, which we are going to implement, suppose that you are expecting that each slave will send to the master an integer which is the sum of the elements it added. It is also quite possible that some slave may encounter some error and may want to send the master an integer which indicates the error code. How does the master distinguish whether an integer it received from the slave is an intermediate result or an error code? This is where tags come in picture. You may assign the message for intermediate result a tag say MSG_RESULT which you will #define in some header file and a tag say MSG_ERROR for the message indicating error. The master will then look at the message tags to decide whether the message contains intermediate result or error.
To send a message, you first need to ``initialize'' the send buffer. This is done by calling the pvm_initsend() function. The parameter to this function specifies the ``encoding'' scheme to be used. When we want to exchange data between machines with different architectures (like say between a Pentium machine and a SPARC Workstation) then we need to encode the data at the sending end and decode at the receiving end so that data is properly delivered. The parameter to pvm_initsend() specifies the encoding scheme to be used. The value PvmDataDefault specifies an encoding scheme which enables data to be safely exchanged between heterogeneous architectures. Once the buffer has been initialized, we need to put data into the buffer and encode it. In our case, the data is a string, so we use the function pvm_pkstr() to ``pack'' i.e. encode and put the data into the buffer. If we had to send an integer, there is a different function pvm_pkint(). Similarly, there are functions for other data types. Once the data is packed, we call pvm_send() to send the message. The first argument is the ID of the process to which the message is to be sent and the second argument is the message tag. Since there is only one type of message here, we set the tag to 0.
Once the data is sent to the slave, the slave will process it and return it to the master as we shall see. So we now call pvm_recv() to receive the data from the slave. Again, the parameters are the task ID from which the message is expected and the tag of the expected message. If the desired message has not yet been sent, this function waits and does not return. Thus, in effect, the master is now waiting for the slave to process the data. Once the message arrives, the data is still in the receive buffer. It needs to be ``unpacked'' i.e decoded to get the original message. This decoding is done by the pvm_upkstr() function. We then display the processes string.
Before the PVM program exits, it must tell the PVM system that it is leaving the PVM system so that resources occupied by the process can be released. This is done by calling the pvm_exit() function. After that, the master exits.
The slave program is easy to understand. First it finds the task ID of the master (which is also its parent as the master spawned the slave) by calling the function pvm_parent(). It then receives the message string from the master, converts it to uppercase and send the resulting string to the master.
Now that you know some basics of a PVM program, let us implement the addition algorithm we developed using PVM. There will be one master and 4 slaves. The master will first spawn 4 slaves and send each one their part of data. The slaves will add the data and send the results to the master. Thus, two types of messages are exchanged, one when the master send data to slaves, for which we will use the tag MSG_DATA and the other when the slaves send results to master, for which we will use the tag MSG_RESULT. The rest is simple. The master and the slave programs are given below.
1 /* -------------------------------------------------------------------- *
2 * common.h *
3 * *
4 * This header file defines some common constants. *
5 * -------------------------------------------------------------------- */
6 #ifndef COMMON_H
7 #define COMMON_H
8 #define NUM_SLAVES 4 /* number of slaves */
9 #define SIZE 100 /* size of total data */
10 #define DATA_SIZE (SIZE/NUM_SLAVES) /* size for each slave */
11 #endif
12 /* end common.h */
1 /* -------------------------------------------------------------------- *
2 * tags.h *
3 * *
4 * This header file defines the tags that will be used for messages. *
5 * -------------------------------------------------------------------- */
6 #ifndef TAGS_H
7 #define TAGS_H
8 #define MSG_DATA 101 /* data from master to slave */
9 #define MSG_RESULT 102 /* result from slave to master */
10 #endif
11 /* end tags.h */
1 /* -------------------------------------------------------------------- *
2 * master_add.c *
3 * *
4 * Master program for adding the elements of an array by using PVM *
5 * -------------------------------------------------------------------- */
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <pvm3.h> /* PVM constants and declarations */
9 #include "tags.h" /* tags for messages */
10 #include "common.h" /* common constants */
11 int get_slave_no(int*, int);
12 int main()
13 {
14 int mytid;
15 int slaves[NUM_SLAVES]; /* array to store the task IDs of slaves */
16 int items[SIZE]; /* data to be processes */
17 int result, i, sum;
18 int results[NUM_SLAVES]; /* results from the slaves */
19 /* enroll into the PVM system */
20 mytid = pvm_mytid();
21 /* initialize the array `items' */
22 for(i = 0; i < SIZE; i++)
23 items[i] = i;
24 /* spawn the slaves */
25 result = pvm_spawn("slave_add", (char**)0, PvmTaskDefault,
26 "", NUM_SLAVES, slaves);
27 /* check if proper number of slaves are spawned */
28 if(result != NUM_SLAVES)
29 {
30 fprintf(stderr, "Error: Cannot spawn slaves.\n");
31 pvm_exit();
32 exit(EXIT_FAILURE);
33 }
34 /* distribute the data among the slaves */
35 for(i = 0; i < NUM_SLAVES; i++)
36 {
37 pvm_initsend(PvmDataDefault);
38 pvm_pkint(items + i*DATA_SIZE, DATA_SIZE, 1);
39 pvm_send(slaves[i], MSG_DATA);
40 }
41 /* receive the results from the slaves */
42 for(i = 0; i < NUM_SLAVES; i++)
43 {
44 int bufid, bytes, type, source;
45 int slave_no;
46
47 /* receive message from any of the slaves */
48 bufid = pvm_recv(-1, MSG_RESULT);
49 /* get information about the message */
50 pvm_bufinfo(bufid, &bytes, &type, &source);
51
52 /* get the slave number that sent the message */
53 slave_no = get_slave_no(slaves, source);
54 /* unpack the results at appropriate position */
55 pvm_upkint(results + slave_no, 1, 1);
56 }
57 /* find the final result */
58 sum = 0;
59 for(i = 0; i < NUM_SLAVES; i++)
60 sum += results[i];
61 printf("The sum is %d\n", sum);
62 /* clean up and exit from the PVM system */
63 pvm_exit();
64 exit(EXIT_SUCCESS);
65 } /* end main() */
66
67 /* function to return the slave number of a slave given its task ID */
68 int get_slave_no(int* slaves, int task_id)
69 {
70 int i;
71 for(i = 0; i < NUM_SLAVES; i++)
72 if(slaves[i] == task_id)
73 return i;
74 return -1;
75 } /* end get_slave_no() */
76 /* end master_add.c */
1 /* -------------------------------------------------------------------- *
2 * slave_add.c *
3 * *
4 * Slave program for adding elements of an array using PVM *
5 * -------------------------------------------------------------------- */
6 #include <stdlib.h>
7 #include <pvm3.h>
8 #include "tags.h"
9 #include "common.h"
10 int main()
11 {
12 int mytid, parent_tid;
13 int items[DATA_SIZE]; /* data sent by the master */
14 int sum, i;
15
16 /* enroll into the PVM system */
17 mytid = pvm_mytid();
18 /* get the task ID of the master */
19 parent_tid = pvm_parent();
20 /* receive the data from the master */
21 pvm_recv(parent_tid, MSG_DATA);
22 pvm_upkint(items, DATA_SIZE, 1);
23 /* find the sum of the elements */
24 sum = 0;
25 for(i = 0; i < DATA_SIZE; i++)
26 sum = sum + items[i];
27 /* send the result to the master */
28 pvm_initsend(PvmDataDefault);
29 pvm_pkint(&sum, 1, 1);
30 pvm_send(parent_tid, MSG_RESULT);
31 /* clean up and exit from PVM */
32 pvm_exit();
33
34 exit(EXIT_SUCCESS);
35 } /* end main() */
1 # Make file for the PVM program for addition - makefile.add
2 .SILENT :
3 # paths fro PVM include files and libraries
4 INCDIR=-I/usr/share/pvm3/include
5 LIBDIR=-L/usr/share/pvm3/lib/LINUX
6 # link the PVM library
7 LIBS=-lpvm3
8 CFLAGS=-Wall
9 CC=gcc
10 TARGET=all
11 # this is where the PVM executables go
12 PVM_HOME=$(HOME)/pvm3/bin/LINUX
13 all : $(PVM_HOME)/master_add $(PVM_HOME)/slave_add
14 $(PVM_HOME)/master_add : master_add.c common.h tags.h
15 $(CC) -o $(PVM_HOME)/master_add master_add.c $(CFLAGS) $(LIBS) \
16 $(INCDIR) $(LIBDIR)
17
18 $(PVM_HOME)/slave_add : slave_add.c common.h tags.h
19 $(CC) -o $(PVM_HOME)/slave_add slave_add.c $(CFLAGS) $(LIBS) \
20 $(INCDIR) $(LIBDIR)
Let us consider the slave program first, because it is simple. The slave receives the 25 array elements from the master in the array items, finds their sum and sends the result to the master with the message tag as MSG_RESULT. Now consider the master. We define an array slaves of size NUM_SLAVES which will store the task ID's of the slaves spawned by the parent. There is another array results in which the results from the slaves are stored. The master first initializes the array items and then spawns the slaves. After that it distributes the data among the slaves. In the call to pvm_pkint() on line 38, the first parameter is the pointer to the array in which the integers are stored, the second is the number of integers to pack and the third is the ``stride.'' Stride means how many elements to skip when packing. When it is 1, consecutive elements are packed. When it is 2, PVM will skip 2 elements when packing with the result that all even numbered elements (0, 2, 4 ...) will be packed. Here we keep its value as 1.
Once the data has been distributed among the slaves, the master has to wait till the slaves return the intermediate results. One possibility when accepting the results is that the master will first collect the result from slave 0 (i.e slave whose task ID is stored in slave[0]), then from slave 1 and so on. However, this may not be an efficient approach. For example, it may be that slave 0 is working on a slower machine than slaves 1, 2 and 3. In that case, since the master is waiting from slave 0, the results from slaves 1, 2 and 3 are yet to be collected even though the calculations are completed. In this case it may be fine, but consider the situation in which the slave, when finished doing one job is given another job. In that case, we would like to give a slave its next job immediately after it has completed its current job. Thus, the master must be in a position to respond messages from any of the slaves. This is what is being done here.
In the call to pvm_recv() on line 48, we know that the first parameter is the task ID of the message source. If this value is kept -1, it signifies a wild card i.e. messages from any process with message tag MSG_RESULT will be received by the master. The received message along with some control information is stored in a buffer called as active receive buffer. The call returns a unique ID for this buffer. Now, we want to know who is the sender of the message so that we can assign the message data to the appropriate element of the array results. The function pvm_bufinfo() returns information about the message in the buffer, such as the message tag, the number of bytes and the senders task ID. Once we have the senders task ID, we set the appropriate element of the results array to the integer sent by the slave. The rest of the program should be easy to understand.
In case you are interested, you can think of some problems for which you can write parallel programs. Many a times, due to bugs etc., you may need to clean up the state of the things before starting. The PVM Console provides with the command halt that kills the PVM daemon. Then all the PVM processes will halt or you can halt them with the Linux kill command. In case you have a network of Linux machines interconnected by say a LAN, then you can also do ``real'' parallel processing. First of all, install PVM on all the hosts you wish to use and then use the add command in the PVM Console to add hosts to the virtual machine. Then PVM will schedule some of the processes to run on these hosts, so that real parallel processing is achieved.
We have seen in the previous section the implementation of the addition program using the PVM. Now let us consider another approach that can be used in developing parallel programs. This approach is using the MPI library. MPI stands for Message Passing Interface. It is a standard developed to enable us to write portable message passing applications. It provides functions for exchanging messages and many other activities as well. It must be noted that unlike PVM which is a software system, MPI is a standard, so that many implementations of the MPI standard exist. We will use an implementation of MPI called LAM which stands for Local Area Multicomputer. It is also available on the Red Hat Linux CD as an RPM package, so installation may not be a problem.
After you have installed the RPM package, go to the /usr/boot directory and create a file named conf.lam and type in a single line in it: lamd $inet_topo. The same directory will also have a file named bhost.def else create it and type in a single line in it: localhost. Now to test whether everything is working correctly, type at the prompt, lamboot. You will get the following response:
[rahul@joshicomp boot]$ lamboot LAM 6.3.1/MPI 2 C++/ROMIO - University of Notre Dame [rahul@joshicomp boot]$
If the output indicates an error, then there is some problem with the installation, either follow the above steps or see the lamboot(1) manual page for troubleshooting.
Assuming that LAM/MPI is properly installed on your system, let us again write a small demonstration program for MPI.
We will again write a simple master - slave program in which we are supposed to evaluate the expression (a + b) * (c - d). The master will read the values of a, b, c, and d from the user and one slave will calculate (a + b) and the other one will calculate (c - d). The program is as follows.
1 /* -------------------------------------------------------------------- *
2 * mpi_demo.c *
3 * *
4 * A simple MPI demonstration program to evaluate an expression. *
5 * -------------------------------------------------------------------- */
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <lam/mpi.h> /* for MPI constants and functions */
9 #define MSG_DATA 100 /* message from master to slaves */
10 #define MSG_RESULT 101 /* message from slave to master */
11 #define MASTER 0 /* rank of master */
12 #define SLAVE_1 1 /* rank of first slave */
13 #define SLAVE_2 2 /* rank of second slave */
14 /* functions to handle the tasks of master, and the two slaves */
15 void master(void);
16 void slave_1(void);
17 void slave_2(void);
18 int main(int argc, char** argv)
19 {
20 int myrank, size;
21
22 /* initialize the MPI system */
23 MPI_Init(&argc, &argv);
24 /* get the size of the communicator i.e. number of processes */
25 MPI_Comm_size(MPI_COMM_WORLD, &size);
26 /* check for proper number of processes */
27 if(size != 3)
28 {
29 fprintf(stderr, "Error: Three copies of the program should be run.\n");
30 MPI_Finalize();
31 exit(EXIT_FAILURE);
32 }
33
34 /* get the rank of the process */
35 MPI_Comm_rank(MPI_COMM_WORLD, &myrank);
36 /* perform the tasks according to the rank */
37 if(myrank == MASTER)
38 master();
39 else if(myrank == SLAVE_1)
40 slave_1();
41 else
42 slave_2();
43 /* clean up and exit from the MPI system */
44 MPI_Finalize();
45 exit(EXIT_SUCCESS);
46 } /* end main() */
47 /* function to carry out the masters tasks */
48 void master(void)
49 {
50 int a, b, c, d;
51 int buf[2];
52 int result1, result2;
53 MPI_Status status;
54 printf("Enter the values of a, b, c, and d: ");
55 scanf("%d %d %d %d", &a, &b, &c, &d);
56 /* send a and b to the first slave */
57 buf[0] = a;
58 buf[1] = b;
59 MPI_Send(buf, 2, MPI_INT, SLAVE_1, MSG_DATA, MPI_COMM_WORLD);
60 /* send c and d to the secons slave */
61 buf[0] = c;
62 buf[1] = d;
63 MPI_Send(buf, 2, MPI_INT, SLAVE_2, MSG_DATA, MPI_COMM_WORLD);
64 /* receive results from the slaves */
65 MPI_Recv(&result1, 1, MPI_INT, SLAVE_1, MSG_RESULT,
66 MPI_COMM_WORLD, &status);
67 MPI_Recv(&result2, 1, MPI_INT, SLAVE_2, MSG_RESULT,
68 MPI_COMM_WORLD, &status);
69 /* final result */
70 printf("Value of (a + b) * (c - d) is %d\n", result1 * result2);
71 } /* end master() */
72 /* function to carry out the tasks of the first slave */
73 void slave_1(void)
74 {
75 int buf[2];
76 int result;
77 MPI_Status status;
78
79 /* receive the two values from the master */
80 MPI_Recv(buf, 2, MPI_INT, MASTER, MSG_DATA, MPI_COMM_WORLD, &status);
81
82 /* find a + b */
83 result = buf[0] + buf[1];
84 /* send result to the master */
85 MPI_Send(&result, 1, MPI_INT, MASTER, MSG_RESULT, MPI_COMM_WORLD);
86 } /* end slave_1() */
87 /* function to carry out the tasks of the second slave */
88 void slave_2(void)
89 {
90 int buf[2];
91 int result;
92 MPI_Status status;
93
94 /* receive the two values from the master */
95 MPI_Recv(buf, 2, MPI_INT, MASTER, MSG_DATA, MPI_COMM_WORLD, &status);
96
97 /* find c - d */
98 result = buf[0] - buf[1];
99 /* send result to master */
100 MPI_Send(&result, 1, MPI_INT, MASTER, MSG_RESULT, MPI_COMM_WORLD);
101 } /* end slave_2() */
102 /* end mpi_demo.c */
1 # Makefile for MPI demo program - makefile.mpidemo
2 .SILENT:
3 CFLAGS=-I/usr/include/lam -L/usr/lib/lam
4 CC=mpicc
5 mpi_demo : mpi_demo.c
6 $(CC) $(CFLAGS) mpi_demo.c -o mpi_demo
To compile this program, give the command make -f makefile.mpidemo. Once you have compiled the program, to run the program you first need to ``start'' or ``boot'' the Local Area Multicomputer system. This is done with the lamboot command. After that, to run the program by giving the following command: mpirun -np 3 mpi_demo.
[rahul@joshicomp parallel]$ lamboot LAM 6.3.1/MPI 2 C++/ROMIO - University of Notre Dame [rahul@joshicomp parallel]$ mpirun -np 3 mpi_demo Enter the values of a, b, c, and d: 1 2 3 4 Value of (a + b) * (c - d) is -3 [rahul@joshicomp parallel]$
To use the MPI system and functions, you first need to include the header file mpi.h as is done in line 8. In case of PVM, different processes are identified with their task ID's. In case of MPI, the MPI system assigns each process a unique integer called as its rank beginning with 0. The rank is used to identify a process and communicate with it. Secondly, each process is a member of some communicator. A communicator can be thought of as a group of processes that may exchange messages with each other. By default, every process is a member of the communicator called MPI_COMM_WORLD. Although we can create new communicators, this leads to an unnecessary increase in complexity, so we suffice ourselves by using the MPI_COMM_WORLD communicator.
Any MPI program must first call the MPI_Init() function. This function is used by the process to enter the MPI system and also do any specific initialization required by the system. Next, we get the size of the MPI_COMM_WORLD communicator i.e. the number of processes in it using the MPI_Comm_size() function. The first parameter is the communicator and the second is a pointer to an integer in which the size will be returned. Here, we need exactly 3 processes, one master and two slaves. After that, we get the rank by calling MPI_Comm_rank(). The three processes will have ranks 0, 1 and 2. All these processes are essentially identical i.e. there is no inherent master - slave relationship between them. So it is up to us to decide who will be the master and who will be the slaves. We choose rank 0 as master and ranks 1 and 2 as slaves. It can also be seen that we have included the code for both the master and the two slaves in the same program. Depending upon the rank, we choose to execute the appropriate function. Note that there is no spawning of processes as in PVM, and as we shall see, we choose to decide the number of process to be spawned from a command line argument rather than the program spawning slaves. Once the execution is finished, we must call the MPI_Finalize() function to perform final clean up.
Let us now consider the master function. After reading the values of a, b, c, and d from the user, the master must send a and b to slave 1 and c and d to slave 2. Instead of sending the variables individually, we choose to pack them up in an array and send the array of 2 integers instead. It is always better to pack up the data you want to send into a single message rather than to send a number of messages for individual data items, this saves the communication overhead involved in passing the messages. Once the buffer is ready, unlike PVM, we do not need to pack or encode the data, MPI will manage these details internally. So we can directly call the MPI_Send() function to send the data. The first parameter (line 59) is the address of the buffer, the second one the number of elements in the message, the third is a specification of the data type of the buffer, which here is MPI_INT specifying that the buffer is an array of integers. Next comes the rank of the process to which we want to send the message. Here it is SLAVE_1 (#defined as 1). Next is the message tag similar to that in case of PVM. Final parameter is the communicator of which the receiver is a member, which in this case, is MPI_COMM_WORLD.
Once the data is distributed among the slaves, the master must wait for the slaves to send the results. For simplicity, we first collect the message from the slave 1 and then from slave 2. To receive a message, we use the MPI_Recv() function. Again, packing and decoding is handled by MPI internally. The first argument (line 65) is the address of the buffer in which to receive the data. The second is the size of the buffer in terms of the number of elements, which in this case is 1. Next is the data type, which is MPI_INT here. Next three parameters specify the rank of the source of the message, the tag of the expected message and the communicator of which the source is the member. The final argument is a pointer to a structure of type MPI_Status in which some status information will be returned (however, we ignore this information). Now that you know about the basic MPI terms, the slave_1() and slave_2() functions should be clear.
In this program, the code for the master as well as the slaves was in the same executable file. Later on we will see how we can execute multiple executables. From the makefile, we see that to compile the MPI program, a wrapper program mpicc is provided which links the required libraries automatically. To run the program, use the mpirun -np 3 mpi_demo command after booting the LAM. Here we specify LAM to create 3 processes, one master and two slaves.
Let us now re implement the addition program that we designed before using MPI. Here we will also show you how to execute separate programs in MPI. When we use a single executable in the MPI program, we call it Single Program Multiple Data (SPMD) application. When two or more executables are involved, we call it Multiple Program Multiple Data (MPMD) application. With LAM, MPMD programs are executed with the help of an application schema. But before that, let us see the source of the master and the slave programs.
1 /* -------------------------------------------------------------------- *
2 * master_mpi.c *
3 * *
4 * Master program for adding the elements of an array using MPI *
5 * -------------------------------------------------------------------- */
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <lam/mpi.h> /* MPI constants and functions */
9 #include "tags.h" /* tags for different messages */
10 #include "common.h" /* common constants */
11 int main(int argc, char** argv)
12 {
13 int size, i, sum;
14 int items[SIZE];
15 int results[NUM_SLAVES];
16 MPI_Status status;
17 /* initlalize the MPI System */
18 MPI_Init(&argc, &argv);
19 /* check for proper number of processes */
20 MPI_Comm_size(MPI_COMM_WORLD, &size);
21 if(size != 5)
22 {
23 fprintf(stderr, "Error: Need exactly five processes.\n");
24 MPI_Finalize();
25 exit(EXIT_FAILURE);
26 }
27 /* initialize the `items' array */
28 for(i = 0; i < SIZE; i++)
29 items[i] = i;
30 /* distribute the data among the slaves */
31 for(i = 0; i < NUM_SLAVES; i++)
32 MPI_Send(items + i*DATA_SIZE, DATA_SIZE, MPI_INT, i + 1,
33 MSG_DATA, MPI_COMM_WORLD);
34 /* collect the results from the slaves */
35 for(i = 0; i < NUM_SLAVES; i++)
36 {
37 int result;
38
39 MPI_Recv(&result, 1, MPI_INT, MPI_ANY_SOURCE, MSG_RESULT,
40 MPI_COMM_WORLD, &status);
41 results[status.MPI_SOURCE - 1] = result;
42 }
43 /* find the final answer */
44 sum = 0;
45 for(i = 0; i < NUM_SLAVES; i++)
46 sum = sum + results[i];
47 printf("The sum is %d\n", sum);
48 /* clean up and exit the MPI system */
49 MPI_Finalize();
50 exit(EXIT_SUCCESS);
51 } /* and main() */
52 /* end master_mpi.c */
1 /* -------------------------------------------------------------------- *
2 * slave_mpi.c *
3 * *
4 * Slave program for adding array elements using MPI. *
5 * -------------------------------------------------------------------- */
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <lam/mpi.h> /* MPI functions and constants */
9 #include "tags.h" /* message tags */
10 #include "common.h" /* common constants */
11 #define MASTER 0 /* rank of the master */
12 int main(int argc, char** argv)
13 {
14 int items[DATA_SIZE];
15 int size, sum, i;
16 MPI_Status status;
17 /* initialize the MPI system */
18 MPI_Init(&argc, &argv);
19 /* check for proper number of processes */
20 MPI_Comm_size(MPI_COMM_WORLD, &size);
21 if(size != 5)
22 {
23 fprintf(stderr, "Error: Need exactly five processes.\n");
24 MPI_Finalize();
25 exit(EXIT_FAILURE);
26 }
27 /* receive data from the master */
28 MPI_Recv(items, DATA_SIZE, MPI_INT, MASTER, MSG_DATA,
29 MPI_COMM_WORLD, &status);
30 /* find the sum */
31 sum = 0;
32 for(i = 0; i < DATA_SIZE; i++)
33 sum = sum + items[i];
34 /* send the result to the master */
35 MPI_Send(&sum, 1, MPI_INT, MASTER, MSG_RESULT, MPI_COMM_WORLD);
36 /* clean up and exit MPI system */
37 MPI_Finalize();
38 exit(EXIT_SUCCESS);
39 } /* end main() */
40 /* end slave_mpi.c */
1 # Makefile for MPI addition program - makefile.mpiadd
2 .SILENT:
3 CFLAGS=-I/usr/include/lam -L/usr/lib/lam
4 CC=mpicc
5 all : master_mpi slave_mpi
6 master_mpi : master_mpi.c common.h tags.h
7 $(CC) $(CFLAGS) master_mpi.c -o master_mpi
8 slave_mpi : slave_mpi.c common.h tags.h
9 $(CC) $(CFLAGS) slave_mpi.c -o slave_mpi
To compile the programs, type make -f makefile.mpiadd. (The files common.h and tags.h are the same as used for the PVM program.) This will create the master_mpi and slave_mpi executables. Now how do we tell MPI to run both these executables. This is where application schema file comes in. The application schema file specifies the executables to be run, the nodes on which to run and the number of copies of the executable to run. Create a new file add.schema and type in it the following lines:
# Application schema for the addition program using MPI n0 master_mpi n0 -np 4 slave_mpi
This file specifies that MPI should start 1 copy of the master (which will have rank 0) and 4 copies of slaves on the node n0, i.e. the local node. You can specify many more parameters in this schema file like command line arguments etc., see the manual page appschema(1). Once the schema file is ready, you can run the programs as follows:
[rahul@joshicomp parallel]$ lamboot LAM 6.3.1/MPI 2 C++/ROMIO - University of Notre Dame [rahul@joshicomp parallel]$ mpirun add.schema The sum is 4950 [rahul@joshicomp parallel]$
Much of the program should be easy to understand. On line 39, when receiving intermediate results from the slaves, we specify the source as MPI_ANY_SOURCE, since we want to respond to slaves in the order in which they complete the calculations, as discussed earlier. In this case, the status structure contains the actual source in the field MPI_SOURCE. We use this information to set the appropriate element from the results array to the intermediate result received.
In case you have a network of interconnected computers, you can make programs run on many computers by suitably modifying the application schema file. Instead of specifying n0 as the host, specify the name of the host and the number of processes you wish to schedule on that host. For more information about this, see the manual pages and the references.
We have seen how to write parallel programs using the PVM and MPI libraries. Since there libraries are available on many platforms and these are the defacto standards used for implementing parallel programs, programs written with PVM or MPI will run with little or no modification on large scale machines, if the need arises. What we have basically concentrated on in this article is the point to point communication functions provides by these libraries and their use in message passing. Apart from these facilities, both PVM and MPI provide a number of advanced features such as collective communication (broadcasting or multicasting), process groups and group management, reduction functions etc. You are welcome to explore these advanced features. These public domain softwares enable us to use a network of computers as a single large computer, so in case you have some such large problem to solve, you may consider using a network at your college or office. You will have to refer to the books given below for the exact details of how such a setup may be established. Many tutorials as well as books are available to help you. Below is a list of the material I referred.
I would like to thank my project guide Dr. Uday Khedker for his encouragement and help. I would like to thank the Center for Developement of Advanced Computing for allowing me to run the MPI and PVM programs on the PARAM Supercomputer and Dr. Anabarsu for guiding me during the implementation.