Computer Science 338 - Spring 2003

Parallel Processing

Williams College

Final Projects


Each individual or group was able to choose a topic of interest for their final project. A wide range of topics were covered by the six groups. Copies of most of the papers are available upon request.

Diane Bennett '03

Title:Parallel Discrete Event Simulation (Toy Boats)
Abstract: The goal of this project was to learn the basics of Discrete Event Simulation...

Parth Doshi '03, Nathan Hodas '03, Dan Mevorach '03

Title:Achieving Parallelism utilizing non-traditional processors: Hacking the GPU
Abstract: A graphics processing unit (GPU) is well suited for problems that require repeated application of the same calculation to vast amounts of data. In our project we achieve parallelism by using an ATI Radeon 9000 Pro graphics card which is a Single Instruction Multiple Data (SIMD) processor. We further achieve double parallelism by using the card in parallel with the CPU. We implement the heat solver (like the one we did in class) and the time dependent wave equation using the graphics card s capabilities. We compare the speeds of computing the solutions using the standard CPU implementation with using our graphics card implementation. We find that that using the GPU as a coprocessor results in marked speed increase.

Chris Douglas '05 and Tom White '04

Title:Photon Mapping in Parallel using MPI
Abstract: One of the most effective techniques for generating images that has been developed in the past several years is photon mapping. It allows for the creation of nearly lifelike scenes using a realistic global illumination algorithm. However, rendering frames - especially of large or sequential scenes - requires more time and resources than is practical in serial execution. My distributing the most computationally intensive steps in generating each frame across a network, we may render even high-quality images and scenes efficiently. Using MPI, we achieved significant overall speedup after parallel optimization.

Evan Gee '04

Title:SALSA and the Actor Model of Computation
Abstract: A number of organizations including Seti@Home recognized quite some time ago that machines all over the world with system idle cycles represent a massive untapped resource in terms of computational power. Harnessing this capacity, however, has proven extremely challenging for most because of complex networking issues and the diverse nature of the platforms which might be used.

The Actor/Theater extension of the Object-Oriented programming paradigm provides a method for task parallelization over distributed systems. Actors with tasks move about until they find an appropriate machine 'theater' to begin computation. Current languages like Java lack several prerequisites for making this kind of programming safe and simple. One such language designed to remedy these problems is SALSA, Simple Actor Language System and Architecture, a dialect of JAVA designed at the University of Illinois at Urbana-Champaign.

With this in mind, we explore a couple of different algorithm implementations in SALSA to better understand the possible advantages and disadvantages of using Salsa for this type of computation.

Marty Mudd '04, C. Prosper Nwankpa '04, Sebastian Sorgenfrei '04

Title:Parallel N-Body Simulation
Abstract: We present software for modeling N-body particle interactions in parallel. The simulation uses the standard Pthread libraries to compute particle movements, gravitational attraction, velocities, and elastic collisions for a specified number of particles. Domain decomposition on the number of particles allows the software to parallelize the iterative recalculation of the particles' properties. The parallel simulation is then compared with the sequential version and tested over a certain number of iterations for various numbers of particles.

Brent Yorgey '04

Title: Approaches to Parallel Ray Tracing
Abstract: I discuss two approaches to parallel ray tracing in a message-passing environment. The first is a standard model where each process has a complete local copy of the scene description. I also implement this model, and discuss some results and possible extensions. The second approach applies in situations where it is impractical or undesirable to give each process a complete copy of the scene description. Implementing this model turned out to be more difficult than I had anticipated, but I discuss a possible approach to implementation, the difficulties involved, and some possible solutions.


Jim Teresco
Fri May 23 17:59:12 EDT 2003