CPS 206 Fall 1999, Problem 7. Team project.
Search for Maximum in Parallel
Write a program using Fibers to search an array A of N integers, for the maximum integer present in A, along with the index of one of the maximum values. Also, build a test program shell which (a) generates N random integers to fill the array with (values between 0 and 1000 are fine), (b) runs your parallel Fiber program, and ( c ) prints an error message if the result your Fiber program produces does not agree with the result a simple sequential test program gets.
Use the FR, Fiber, Sem classes available from a previous assignment to run the program, and obtain file "test.out", describing the sequence of Instruction Block Descriptors your program generates during execution. Then, find out how many cycles actual execution of the program would take by running either your own Fiber simulation, or the Java program Estimator in directory ~raw/public/cps206 on your "test.out" file. I suggest that you start with Fqt.java, and replace its QS(), array-generating program, and result-testing programs with ones suited to the current task.
The challenge in this problem is to obtain a Fiber program that runs at better than 75% efficiency, where efficiency is defined as the ratio of the average number of useful instructions executed per cycle, to F. (Use F=2, L=8.) To avoid the distortions introduced by loop end tests, you can simulate the compiler optimization called "loop unrolling", by duplicating the instructions needed to test one array element K times in sequence, where you can choose K equal to the exact number of elements in the array, or in that part of the array that one particular fiber examines. In other words, K is a value that is known to the compiler. If you wrote a loop like
for (i=0; i<K; i++) <body>;
where K was known to be 3, the compiler could unroll that loop to:
<body>;
<body>;
<body>;
To simulate loop unrolling, you can do this replacement yourself for this code.
Finally, you can choose N, (the size of the whole array), to be any value you think best. For example, you can make N exactly a product of P, the number of fibers your program runs, and K, the number of elements any one fiber examines. Or maybe N=(K+1)*P is best. You may choose K, P, and N to optimize your program's efficiency. Many parallel programs exhibit different degrees of efficiency, depending on the size of the problem they are applied to.
Submit the program in a file called Maxsearch.java. Submit also a report, which addresses issues of:
Any special problems you found, or "tricks" you discovered that improved program efficiency.
The overall strategy you designed into your program.
Any rules or patterns you discovered for choosing good values of the program parameters.
Any suggestions you might have for more "language facilities" like FR.D().
Include in your report the values of the parameters you are reporting on, and the number of instructions, and ratio of instructions to cycles, for the smallest value of N you found which gave efficiency >= 75%.
Note that you should not have to execute more than about 10 instructions per array element examined, on the average.