Computer Science 338
Parallel Processing

Williams College
Spring 2006

Tutorial Assignment 8: Partitioning and Dynamic Load Balancing
Due: Before your tutorial meeting

This week we look in greater depth at the mesh partitioning and dynamic load balancing problems you read about last week.


Your parallel adaptive quadtree implementation is due soon. Phases 1 and 2 should be submitted by 5 PM on Friday, April 7. Phase 3 and the performance study should be submitted by 9 AM on Tuesday, April 11. There is no new programming assignment for this week.

Your groups for the final project should be formed by Tuesday, April 11. Your full proposals are due Friday, April 14.


In last week's readings, you learned the basics of several approaches to the partitioning and dynamic load balancing problems. For next week, each of you will choose one of these approaches and learn more about it by reading the original papers and by looking at implementations. You should be prepared lead a 15-20 minute discussion of that approach during our meetings on April 11 and 12. Bring an outline for me and your partner(s) to follow along. Tutorial partners may not choose the same approach, so please coordinate with each other when picking topics. Your choices:

Whichever you choose, your outline should discuss how the algorithm works, complexity and efficiency of implementations, the circumstances under which it is likely to be useful, and the general strengths and weaknesses of the approach and of the papers you read. See or e-mail me after choosing your topic for recommendations on appropriate papers to read and where to find sample implementations.

Submission and Grading Guidelines

Before your tutorial meeting, submit a plain text file tut08.txt that contains the outline that you will use to guide our discussion. Your grade for the week will be based on the quality of this outline.