CS249 Project List for May Term 2001
Lab One - [5 pts.] (due 4/23/01) Set up accounts to make
and mpirun projects. Make and mpirun examples cpi.c
and greetings.c.
Project One - [50 pts.] (due 4/26/01) Routing
in a Static Interconnection Network - One of each of the three teams
will be assigned one of each of the k-level tree, the n by n torus and the
k-dimensional hypercube. The team will write shortest path algorithms for
their assigned topologies. Input will consist of a size indicator k or
n, a source node and a destination node. The program will output
the nodes along a shortest path in the topology. Critical to the project
will be a function which computes the first step from source to destination.
Project Two - [75 pts.] (due 5/1/01) Buffered Producer-Consumer
Problem. The program will create three processes a producer, a buffer
and a consumer. The producer will send a steam of messages (single ints
or floats are sufficient) ending with some sentinel value. The consumer
will request and then receive a message from the buffer process, ending
when it receives the sentinel. The buffer will monitor a queue, enqueing
messages from the producer and dequeueing and sending them to the consumer
when requested.
Issues - a) Must not accept a message from the producer if the queue
is full. b) Must not accept a request from the consumer if the queue is
empty. c) Must correctly handle a fast producer with a slow consumer and
vice versa. d) Queue size must not be so large as to make the problem trivial.
Project
Three - [75 pts.] (due 5/7/01) Parallelization of Newton's Basins
of Attraction using the 'farm' model. The serial code provided computes
basins of attraction for the newton's method solution of f(z) = z^3 + 1.
The students will design and implement parallelizations of the code using
the 'farm' model. Step One will be an in-class design and Step Two an implementation
based on the class design.
Project Four - [100 pts]
(due 5/14/01) Heat Flow Boundary Value Problem Students will simulate
communication on a mesh/torus computer to solve a heat flow problem. A room
in the shape of a square has a fireplace in the center of one wall and no
other features. The fireplace maintains a constant temperature of 200 degrees
Celsius. The walls conduct heat to the outside at a rate that will keep
them at a constant 20 degrees Celsius. Use the techniques discussed in class
to calculate the equilibrium temperature at a grid of points in the room.
Construct a PPM output file to 'visual' your results.
Issues - The final program should allow: a) use of 9,16, 25, 36, 49,
64 or 81 processes. b) use of between 2x2 to 50x50 grid points per processor.
Project Five - [50 pts] (due 5/17/01) (An individual
project-students are restricted from assisting one another) Rock-Sxissors-Paper
An implementation of the project introduced on test one. Three processes
- Player A, Player B and a Judge. Each player sends an "R", "S",
or "P" to the judge, the judge tallies the win for one of the
players and tells each player what the other chose. Play continues for ten
rounds after which the judge reports the final results to the screen.
Issues - The players should employ different "strategies".