Due: Wednesday, October 8th, 2008 10:45am
For this homework, you'll create a new framework that can drive reduce and scan pieces originally written to work with the framework provided with HW4. For simplicity, we use a variant of the framework without prepare_temps.
The HW4 framework is implemented in terms of message passing. Your new implementation of the framework will use threads, instead. You'll have to implement full/empty variables that work with threads instead of message passing. Also, your framework should support any number of threads, as specified on the command line at run time.
Note: In the message-passing framework, a full/empty variable is identified using a number. That's because the identifier has to be passed in a message back to the central manager for full/empty variables. In a shared-memory setting, you should instead implement a full/empty variable as a structure or object.
You can implement the framework in either C or Java:
For C, start with rs_c.zip, which provides a sum and dist_sum to plug into a reduce framework, and it provides an area_delta and convert to plug into a scan framework. They work with the framework supplied in reducescan.zip, and they should work unmodified with your HW6 solution.
Implement full/empty variables using POSIX mutexes and condition variables.
A typical homework submission will include fullempty.c and fullempty.h to implement full/empty variables (needed by both frameworks), reduce.c to implement a reduce framework, and scan.c to implement a scan framework. Then, for example, compiling and linking together fullempty.c, reduce.c, sum/reduce_client_data.c, and sum/reduce_server_procs.c should produce a single executable; the execution should accept a number on the command line and run that many threads to produce a sum.
For Java, start with rs_java.zip, which provides a SumReduce.java and DistSumReduce.java to plug into a Reduce framework, and it provides an AreaDeltaScan and ConvertScan to plug into a Scan framework. Unlike C, No message-passing implementation of the framework is available, but ReduceSeq.java and ScanSeq.java are supplied, and they implement a verison of the framework (breaking the input array into two pieces that are nevertheless processed sequentially). See README_rs_java.txt for information the framework interface.
Implement full/empty variables using Lock and Condition objects. Since the point of the assignment is to understand mutexes and condition variables, do not use other synchronization constructs that Java or its libraries supply. In particular, you should not need synchronized anywhere in your implementation.
A typical homework submission will include FullEmpty.java to implement full/empty variables (needed by both frameworks), Reduce.java (a drop-in replacement for ReduceSeq.java) to implement a reduce framework, and Scan.java (a drop-in replacement for ScanSeq.java) to implement a scan framework. Then, for example, after compiling Fullempty.java, Reduce.java, SumReduceClient.java, SumReduceServer.java, and SumReduce.java, then java SumReduce n should run n threads to produce a sum.
To work with your new framework, a “server” should not assume that the local portion of the input or result array is indexed from 0. For a given thread, accum and reduceGen or scanGen might be called with indices p to p+size instead of 0 to size. In other words, as you create a framework that uses with threads and shared memory, you can (and should) use offsets into a single array instead of creating separate arrays for each thread. All of the given uses of the framework are compatible with this refinement to the framework interface.
Last update: Monday, December 1st, 2008mflatt@cs.utah.edu |