Workstealing Algorithms for Divide-And-Conquer Systems
From Master Projects
| has title::Workstealing Algorithms for Divide-And-Conquer Systems | |
|---|---|
status: finished
| |
| Master: | project within::High Performance Distributed Computing |
| Student name: | student name::Michał Urbanek |
| number: | student number::1824880 |
| Dates | |
| Start | start date:=2009/01/15 |
| End | end date:=2009/07/30 |
| Supervision | |
| Supervisor: | Jason Maassen |
| Second reader: | has second reader::Niels Drost |
| Company: | has company::VU |
| Poster: | has poster::Media:Media:Posternaam.pdf |
Signature supervisor
..................................
Abstract
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.
