Parallel computing  23.1.2003

Exercise 1

No X-exercises this week.

Read the questions carefully, answer to all parts of each question. Draw
a picture of each exercise.

1) Design a manual message-passing sorting algorithm for a set of
   persons and A4 papers. Each paper has a name according to which it is
   sorted. At the beginning, all papers are in a stack by the first
   person.  At the end, the sorted papers should be returned to the
   first person. A person can perform local operations and give a stack
   of one or more papers for the neighboring person. The recipient need
   not to be ready to accept the stack (post-pox messaging). No person
   can move from his/hers position.


   Assume that you have a) 10 persons, b) 100 persons located in a single row.
   Assume that you have A) 100 papers, B) 10000 papers.


   Design the sorting algorithm (as fast as possible) to do the
   real-world sorting (in both a and b sitting arrangements and both A
   and B paper piles.). Estimate the time needed (in seconds) for all
   (Aa, Ab, Ba, Bb) cases.

   Hint: try to avoid situations when only one person is doing something
   useful.


2) Modify the previous case b) algorithm so that instead of a single
   row, the persons are located in a 10 by 10 matrix, and are able to
   pass the papers in 4 directions. Take advantage of the reduced
   diameter of the human network. Estimate the time again for both A and
   B cases.


3) Design an algorithm for 10000 papers and 1000 persons. Estimate again
   the time required. Notice the physical space requirements for 1000
   persons. Hint: try to avoid situations when only few people are doing
   something elaborate.


4) Lets build a NOW-cluster out of commodity PC-hardware. Find out
   component prices from some web-store (http://www.pricewatch.com/
   etc.).  We'll measure computing power by the misleading formula 1 GHz
   = 1 GFLOPS. Try to build as cheap as possible 100 GFLOPS computer.
   E.g., 33 * 3.06GHz is enough. The computers must be connected
   (network devices) and bootable (motherboard, memory, power, network).


5) Let us assume that our algorithm is inefficient by factor sqrt(P).
   Then 33 * 3.06GHz / sqrt(P) = 16.8 GFLOPS. Now the more efficient
   processors will gain with respect to the cheaper. Again, try to build
   as cheap as possible 100 GFLOPS computer.