Workstealing Algorithms for Divide-And-Conquer Systems

From Master Projects
Jump to: navigation, search


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.