CSE 6362: Parallel Algorithms for Artificial Intelligence
Homework Assignment #1
Assigned: January 23, 1997
Due: February 6, 1997

1. During the first lecture, we designed a parallel algorithm to sum a set of numbers. Assume that eight processors are available, and that each add and communicate operation takes the same amount of time. If you could arrange the processors in any possible connection configuration, how would you arrange the processors to minimize the time taken to add the list of numbers? Describe the algorithm as it would work on your configuration. Analyze the algorithm for speedup, efficiency, and work.
2. Of the search algorithms that we have reviewed, which are easiest to parallelize, and which are hardest? Why? What type of parallel architecture (MIMD, SIMD, shared memory, distributed memory, etc.) is best suited for parallelizing search algorithms in general and why?
3. Using the Unix fork capability, write a parent and child program on a Unix machine that implements the following summation strategy: each child process receives an id and number of integers x to add, and computes the sum . Each child process sends its local sum back to the host, which then computes and outputs the global sum. Message passing is implemented using a shared file.

   To help you, a sample child program is given below.

   #include <stdio.h>
   
   main(argc, argv)
      int argc;
      char *argv[];
   {
      int i, size, id, sum=0;
      char data[80];
      FILE *fp;
   
      size = atoi(argv[1]);
      id = atoi(argv[2]);
   
      fp = fopen("data", "a");
   
      for (i=0; i<size; i++)
         sum += (id * size) + i;
   
      fprintf(fp, "%d\n", sum);
   }

Send your answers, your code and sample output to cs6362-turnin@cse. Have fun!

• About this document ...