Schedule independent work

Sequential computing processes work one step after another. Parallel computing uses multiple processors simultaneously. Distributed computing uses multiple networked devices; a system can be both distributed and parallel. Sending data, coordinating workers and dependencies add costs.

For independent indivisible tasks with known durations, sequential time is their sum. Given a fixed assignment to parallel workers, completion time is the largest worker load, plus any stated overhead. Use an explicit schedule instead of simply dividing total time by the worker count.

Independent tasksA 6,B 4,C 3,D 3 seconds; two identical workers, no overhead, tasks indivisible.

1. Sequential time 6+4+3+3=16 seconds.
2. Schedule 1:worker 1 A+B=10;worker 2 C+D=6;finish 10.
3. Schedule 2:worker 1 A=6;worker 2 B+C+D=10;also 10.
4. A better schedule:worker 1 A+C=9;worker 2 B+D=7;finish 9. It is optimal: a finish 8 would require a subset summing 8, which these tasks cannot form.

Claim: Two processors always halve runtime.

Task sizes, indivisibility, dependencies and coordination can prevent equal loads and ideal speedup.

Schedule tasks[5,5,2,2]on two workers with no overhead to minimize finishing time. Show loads.

Work with a partner. Make a prediction, compare your reasoning, then identify the rule that supports your answer.

For tasks[6,4,3,3] and schedule loads 9 and 7, compute speedup relative to sequential 16. What if total overhead 2 seconds is added after the work?

Why must a speedup comparison use the same task and equivalent results?

Write your reasoning before comparing with a classmate. If your teacher assigned this task, submit it through My classes to save your work and receive feedback.