Title: COSC330/530 - Lecture 5

COSC330/530 - Parallel and Distributed Computing

Lecture 5 - Interprocess Communication

Dr. Mitchell Welch

Reading

• Chapter 15 from Advanced Programming in the UNIX environment
• Assignment 1 Description

Summary

• Fibonacci on the ring of processes
• Patterns of Parallelism

Fibonacci on the Ring of Processes

• Let's finish off rings of processes with an application.
• We will look at Fibonacci in lectures.

• Recall that the Fibonacci series has to do with breeding rabbits:

  • 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

• If a pair of rabbits can mate at age 1 month and produce another pair.

• Question: How many rabbits do you get starting with a pair of babies after n months?
• Answer: Fib(n) .

Fibonacci on the Ring of Processes

• Recall that:

• We will use a ring to compute the Fibonacci numbers.

Fibonacci on the Ring of Processes

• We do this by passing a string around the ring.
• The original parent begins by passing the string "1 1" to it nearest neighbour.
• Then each other process in the ring does the following:
  1. It reads a string from its neighbour
  2. Decodes the string into the two numbers n_1 and n_2
  3. Computes the next number n_3 = n_1 + n_2
  4. Makes the string consisting of n_2 and n_3
  5. Sends this string to its neighbour.

Fibonacci on the Ring of Processes

• It should also check for overflow of the sum.
• The process then tells the world and exits.

Fibonacci on the Ring of Processes

• Solving a complex problem using procedural abstraction:

• So the first thing to do is, using procedural abstraction, get the basics right.

  1. We need to decode two numbers from a string.
  2. We need to encode two numbers into a string,
  3. We need to be able to add two numbers, and
  4. We also need to check for overflow.

Fibonacci on the Ring of Processes

• Getting integers from an input string is easy:

void get_integers(char buff[], long *first,long *second){
  read(STDIN_FILENO, buff, BUFFSIZE);
  *first  = atol(strtok(buff," "));
  *second = atol(strtok(NULL," ")); 
}

• Although I should probably do some error checking:
  1. atol is pretty bullet proof, except if you pass it NULL
  2. strtok could return NULL
  3. Note: strtok returns the next token from a string. It keeps its own offset into the string, hence, after the first call, the string address is not necessary.

4. See man strtok for the details.

Fibonacci on the Ring of Processes

#include <stdio.h>  /* for printf */
#include <stdlib.h> /* for atol   */
#include <unistd.h> /* for read   */
#include <string.h> /* for strtok */
#define BUFFSIZE 50
void get_integers(char buff[], long *first, long *second){
  read(STDIN_FILENO, buff, BUFFSIZE);
  *first  = atol(strtok(buff, " "));
  *second = atol(strtok(NULL, " ")); 
}
int main(void){
  char buff[BUFFSIZE];
  long first, second;
  get_integers(buff, &first, &second);
  printf("Got %ld and %ld\n", first, second);
  return 0;
}

Fibonacci on the Ring of Processes

• Play around with example01.c.
• Note how it is prone to SIGSEGVs. That is Segmentation Faults, caused by incorrect memory access.
• Tracking down SIGSEGVs. Two methods:
  • One using gdb or DDD, the other using valgrind
  • Usually one will work, often both.
• Valgrind will find errors even if you program doesn't crash (yet).

Fibonacci on the Ring of Processes

• First compile with the -g flag.
• Start gdb/DDD with the name of the executable:
• tabasco.Examples> gdb get_integers
• Issue the run command with any command line arguments your executable expects. (gdb) run
• Look at the state when it crashed using the back trace command bt.
• Read man gdb

Fibonacci on the Ring of Processes

• Call valgrind with the name of the executable and any command line arguments your executable expects. Read what it says.
• Read the documentation on the valgrind site: http://valgrind.org/docs/download_docs.html

Fibonacci on the Ring of Processes

void safe_get_integers(char buff[], long *first, long *second){
  char* token = NULL;
  int bytes;
  if((first == NULL) || (second == NULL)) return;
  bytes = read(STDIN_FILENO, buff, BUFFSIZE);
  if(bytes < 0){
    *first  = 0;
    *second = 0;
  } else {
  *first  = atol((((token = strtok(buff," ")) == NULL) ?  "0" : token));
  *second = atol((((token = strtok(NULL," ")) == NULL) ?  "0" : token)); 
  }
}

Fibonacci on the Ring of Processes

• Messing around with get_integers...

21641:examples $ ./example01

Segmentation fault: 11
21641:examples $ ./example01
1
Segmentation fault: 11
21641:examples $ ./example01
1 2
Got 1 and 2
21641:examples $ ./example02

Got 0 and 0
21641:examples $ ./example02
1
Got 1 and 0
21641:examples $ ./example02
1 3
Got 1 and 3
21641:examples $ 

Fibonacci on the Ring of Processes

• Sending numbers is also simple:

int send_numbers(char buff[], long num1, long num2){
  sprintf(buff, "%ld %ld", num1, num2);
  write(STDOUT_FILENO, buff, strlen(buff) + 1);
}

• A bullet proof version would check the return value of the write!
• So we are left with:
  • adding,
  • checking for overflow, and
  • telling the world.

Fibonacci on the Ring of Processes

• Note that overflow is detected simply by determining if the sum is negative.

void safe_sum(long first, long *second, long *third){
  *third = first + *second;
  if(*third < 0){
    *third   = 0;
    *second  = 0; };
}

• Check this out for more info on integer overflow

Fibonacci on the Ring of Processes

• Reporting the result is pretty routine, though a bit ugly to typeset nicely (pretty print):

void report_sum(int i,long fst,long old_snd,long snd,long thrd){
  fprintf(stderr,
          "\nProcess %d 
            with PID %d 
      and parent PID %d 
       recieved %ld %ld
       and sent %ld %ld.\n",
                      i, 
          (int)getpid(), 
         (int)getppid(),
                  fst, 
             old_snd, 
                 snd, 
                  thrd); }

Fibonacci on the Ring of Processes

int main(int argc,  char *argv[ ]){
   int    i;               
   char   buff[BUFFSIZE];  
   long   first;           
   long   second;          
   long   third ;          
   /* make the ring here */
   {
     /* ring process code  */     
     long old_second;
     if(i == 1){
       /* mother of all processes */
       send_numbers(buff, 1,1); }
     /* all processes     */
     get_integers(buff, &first, &second);
     old_second = second;
     safe_sum(first,&second,&third);
     if(i > 1){
         send_numbers(buff, second, third);
         report_sum( i, first, old_second, second, third); }
     else {
      fprintf(stderr,
              "\n\nfibonacci(%d) = %ld\n\n", 
              nprocs, 
              first); }
     exit (EXIT_SUCCESS); 
   }
}     /* end of main program here */

Fibonacci on the Ring of Processes

• Review the full listing:
• fibonacci.c

Patterns of Parallelisation

• From our study of pipes, we can start to see that problems can be broken down in different ways.
• The simplest pattern of parallelism is Result Parallelism (these are also referred to as embarrassingly parallel problems)
• Each result comprises part of the solution to a problem and can be calculated without any communication with the other processes.
• Parallelism can be fine-grained or coarse-grained

Patterns of Parallelisation

Patterns of Parallelisation

• Most problems will have some processing inter-dependencies (for example our fibonacci sequence and operations such as matrix multiplication.)
• We can refer to these as Sequential Dependencies where part of the computation requires synchronisation and communication to solve the problem.

Patterns of Parallelisation

Patterns of Parallelisation

• One variation on agenda parallelism that is of particular interest is Reduction
• Reduction involves calculating a single aggregate result from multiple results.
• In this arrangement, processes 1 through n calculate an intermediate result and a final process performs the reduction operation.

Patterns of Parallelisation

Patterns of Parallelisation

• An agenda parallel problem with more tasks than processors must use a clumping approach, where each processor is responsible for a selection of tasks that are partitioned to it.
• On a cluster parallel computer, the clumping approach is often implemented using a master-worker patterns
• Effectively, the master processor is responsible for the agenda and is responsible for sending tasks to a set of workers.
• Each worker completes the task and sends the result to the master.

Patterns of Parallelisation

Summary

• Fibonacci on the ring of processes
• Patterns of Parallelism

Questions?

Reading

• Chapter 15 from Advanced Programming in the UNIX environment
• Assignment 1 Description