One solution to this problem of idle processors is to use a dynamic scheduling policy. Such policies allow for idle processors to find more work by executing tasks initially allocated to other processors (that are still busy). One such policy is Work stealing. In this model, each processor maintains a work queue and executes it sequentially. However, when a processor becomes idle, it can "steal" work that another active processor was scheduled to complete in the future; this keeps all processors busy. In class, we discussed how this model could be applied to demo 2. Each students' stack of numbers can be thought of as their work queue and each number is an atomic unit of work. When a student finishes adding up their pile, they can grab more from another student who is still working.
As an interesting side note, work stealing is the paradigm that the multithreaded language/library Cilk uses to schedule its threads. Recent instances of 15-210 have had students use Cilk to solve a computational geometry problem in parallel.
One solution to this problem of idle processors is to use a dynamic scheduling policy. Such policies allow for idle processors to find more work by executing tasks initially allocated to other processors (that are still busy). One such policy is Work stealing. In this model, each processor maintains a work queue and executes it sequentially. However, when a processor becomes idle, it can "steal" work that another active processor was scheduled to complete in the future; this keeps all processors busy. In class, we discussed how this model could be applied to demo 2. Each students' stack of numbers can be thought of as their work queue and each number is an atomic unit of work. When a student finishes adding up their pile, they can grab more from another student who is still working.
As an interesting side note, work stealing is the paradigm that the multithreaded language/library Cilk uses to schedule its threads. Recent instances of 15-210 have had students use Cilk to solve a computational geometry problem in parallel.
Links:
http://en.wikipedia.org/wiki/Work_stealing
http://en.wikipedia.org/wiki/Cilk