Computer Science 338 - Homework/Lab 5
Due: 9:55 AM, Thursday, November 16, 2000.

1.

Now that you have seen more partitioning and load balancing algorithms, reevaluate the partitioning strategy from Project 2 (the slice-by-slice method). What other algorithms may be appropriate for that problem? Discuss some advantages and disadvantages of using these algorithms.

2.

We have discussed several measures of partition quality when a partitioning or load balancing algorithm is used to distribute a computation to run on a parallel computer. Some of the important ones:

• Load imbalance
• Global surface index
• Maximum local surface index
• Average interpartition connectivity
• Maximum interpartition connectivity

Each of these has some effect on the total running time of an application. Discuss what types of applications and what types of parallel architectures make each of these measures more or less important.