Lab 11: Parallel Algorithms

Goals: 

• To practice designing and evaluating parallel algorithms.

Collaboration: You will complete this lab in teams of 1-3 of your choice.  You may consult me or your classmates with proper attribution.

In-class Exercise: Predicting Space Junk Collisions

When launching a rocket to put a new satellite into Earth orbit, we want to avoid collisions between the rocket and existing satellites, manned vehicles, or "space junk" (insulation foam, lost tools, and other miscellaneous items that have been lost in space).  NASA tracks maintains a database of about 10,000 large objects in Earth orbit; this database might be expanded in the future to include as many as 100,000 smaller objects.

When a launch is planned, a four-hour launch window is identified.  For any launch time within this  window, we want to know whether the rocket is likely to collide with an object already in orbit.  (The current implementation tests once per minute, but we could imagine wanting to model time on a finer scale).

The rocket's trajectory is computed using an iterative timestep method.  At any given time, the rocket has an x, y, z position along with some error in the x, y, and z dimensions.  The position at time t+1 is a function of the position, velocity, and acceleration at time t.

Along with the rocket itself, we much track the positions of the in-space objects.  Each object has an initial position (with some error) at a given time, and two models for propogating that position and error over time: a coarse-grained model (which is fast but overly pessimistic) and fine-grained model (which is much slower but also much more accurate).

The goal is to report to a human operator the launch times that may result in collisions, and the likelihood of those collisions.  The operator can then avoid those risky launch times.

A straightforward sequential algorithm, then, is roughly this:

• for each launch time,
• for t = launch time to arrival time,
• compute the position of the rocket at time t
• for each object
• compute the position of the object at time t+1
• compare the position of the object to the position of the rocket
• if the error boxes around the position of the object and the position of the rocket overlap,
• use the fine-grained model to determine the likelihood of a collision and report this likelihood.

Consider approaches to parallelizing this algorithm: alternative partitionings, communication requirements, and strategies for agglomeration and mapping.  What further questions would you ask?

(Reference: Brooks Davis, personal communication)

Written Exercises

The following exercises relate to Chapters 1-3 of Designing & Building Parallel Programs by Ian Foster.

1. Foster 1.8
2. Foster 2.1
3. Foster 2.4
4. Foster 3.1
5. Foster 3.7

Janet Davis (davisjan@cs.grinnell.edu)