Next: About this document
CSE 6362: Parallel Algorithms for Artificial Intelligence
Homework Assignment #1
Assigned: January 23, 1997
Due: February 6, 1997
- 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.
- 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?
- 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.
int i, size, id, sum=0;
size = atoi(argv);
id = atoi(argv);
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!
Diane J. Cook
Mon Jan 20 13:36:34 CST 1997