Workstealing Algorithms for Divide-And-Conquer Systems
|has title::Workstealing Algorithms for Divide-And-Conquer Systems|
|Master:||project within::High Performance Distributed Computing|
|Student name:||student name::Michał Urbanek|
|Second reader:||has second reader::Niels Drost|
In Satin divide-and-conquer framework idle processors get new work by 'stealing' from other processors. At the moment the processor to steal from is chosen randomly, with a refinement that for remote clusters a processor will try to steal from both a local node and a remote node simultaneously. Although this is usually very efficient, some improvements to this algorithm can be found. In particular things to investigate include:
* How can we avoid the large number of unsuccessful steal requests at the start and end of a run? * Does it help to have more than one or two steal requests outstanding? * Does it help to use weighted-random work-stealing instead of uniform-random work-stealing? * Would it help to use gossip algorithms to more directly distribute knowledge about available work?
The project will result in a simple experimental environment that implements the various work-steal options, plus a substantial number of benchmarks to evaluate these implementations. Results of this project will probably be used in the pending redesign of Satin implementation.