Back:Main Parallel Processing Page Next: Load Balancing and Task Scheduling

Undergraduate Year 3: Parallel Processing Course

Warning! This courseware is far from complete, and will not be updated. Many of the links will be dead ends. Sorry for any inconvenience.

Index

Load Balancing and Task Scheduling
Statement of General Problem
Static Task Assignment
Dynamic Task Assignment
Task Graphs
Communication Delay vs Parallelism
Algorithms for Task Assignment
Static Load Balancing
Optimal Static Algorithm
Binary Dissection Method
Greedy Algorithm
Dynamic Load Balancing
Dimension Exchange
Scattered Decomposition
Minimisation of a Hamiltonian or Energy Function
Formulation of Objective Function (E)
Simulated Annealing
Choosing the starting temperature Tstart
Example of using Simulated Annealing
Sparse Matrix Example of Simulated Annealing
Complexity of Basic Communication Structures
k-port Communication
Spanning Trees
Single Node Broadcast
Single Node Scatter
Multi Node Broadcast
Multi Node Scatter (Total Exchange)
Parallel Sorting Algorithms
Bitonic Sort
Hyperquicksort
Comparison of Bitonic Sort and Hyperquicksort
Analysis of Bitonic Sort
Analysis of Hyperquicksort
Matrix Multiplication (Fox's Algorithm)
Parallel Simulated Annealing