F24 · Topic 4.3
Parallel scheduler
1. Predict first
For tasks[6,4,3,3], predict completion for assignments[0,1,0,1]to two workers, with no overhead.
Change it · step through · explain
Change an input, predict what will happen, then advance one step. Read why the state changes, reset and experiment. This fixed teaching model does not save progress or award XP.
Ready · Make a prediction
- Input 16,4,3,3Waiting
- Input 20,1,0,1Waiting
- Input 30Waiting
Ready to experiment
Why: Predict the first change, then advance one step.
Try this: Put every task on one worker, then balance the loads and add overhead.
2. Build your procedure
Write an algorithm that totals each worker load from an assignment list, then returns the maximum plus overhead. State the independent/indivisible-task assumptions.
Use AP CSP pseudocode, a language you know, or precise plain language. Your code is not executed here. Use the classroom assignment to save your response.
3. Check boundaries
| Input | Expected | Why this case |
|---|---|---|
| tasks[6,4,3,3]; assignments[0,1,0,1]; overhead 0 | Loads[9,7];finish 9;speedup 16/9 | Completion waits for the heavier worker. |
| same; overhead2 | Finish 11;speedup 16/11 | Explicit overhead added once afterprocessing. |
| assignments[0,0,0,0]; overhead 0 | Loads[16,0];finish 16;speedup 1 | Idle secondworker does not help. |
4. Explain and reflect
Give a lower bound on finishing time for these tasks on two workers. Why is 8 not achievable?
Model limits: A fixed scheduling model for independent indivisible tasks, identical workers and stated one-time overhead. It does not simulate dependencies, processor faults or a real network.