Question

problem 1
critical path, workers, and the hybrid schedule

task graphs | critical path | data parallel

givens - task runtimes (minutes)

task	description	time	depends
t2	build feature schema	6	—
t3	train (data parallel)	8*	t1, t2
t4	combine / sync	3	t3
t5	apply update	4	t4
t6	evaluate accuracy	7	t5
t7	evaluate fairness	9	t5

*8 min is the total compute. t3 has 1-min setup + parallel compute + 1-min combine.

dependency graph
numbers next to each task = runtime in minutes.

(a) max concurrency? how many workers should you provision?
(b) makespan with 1 worker?
(c) makespan with 4 workers?
(d) makespan with 2 workers — and where does the difference come from?

Explanation:

🆕 New Concept Discovered: Task Scheduling and Makespan
Calculating execution times with resource constraints.

Step 1: Max Concurrency and Worker Provisioning (a)

To find the maximum concurrency, we look at the maximum number of tasks that can run in parallel at any single point in time:
- At the start, **T1** and **T2** can run in parallel (concurrency of 2).
- **T3** is a data-parallel task. The note states: *"T3 has 1-min setup + parallel compute + 1-min combine."* The total compute is \(8\) minutes. Thus, the parallel compute portion takes:
\[ 8 - 1 \text{ (setup)} - 1 \text{ (combine)} = 6 \text{ minutes of compute} \]
In a data-parallel setting, this compute can be split across multiple workers.
- At the end, **T6** and **T7** can run in parallel (concurrency of 2).

Therefore, the maximum structural concurrency of independent tasks in the graph is 2 (either T1/T2 or T6/T7). If we provision for this maximum task-level concurrency, we should provision **2 workers**.

Step 2: Makespan with 1 Worker (b)

With only 1 worker, no tasks can be executed in parallel. The total time (makespan) is simply the sum of the runtimes of all tasks:
\[ \text{Total Time} = \text{Time}(T1) + \text{Time}(T2) + \text{Time}(T3) + \text{Time}(T4) + \text{Time}(T5) + \text{Time}(T6) + \text{Time}(T7) \]
\[ \text{Total Time} = 10 + 6 + 8 + 3 + 4 + 7 + 9 = 47 \text{ minutes} \]

Step 3: Makespan with 4 Workers (c)

With 4 workers, we can parallelize tasks up to the maximum available concurrency at each stage:
1. **Start (T1, T2):**
- Worker 1 takes T1 (10 min).
- Worker 2 takes T2 (6 min).
- Both finish at \(t = 10\) min.
2. **Train (T3):**
- Starts at \(t = 10\).
- 1-min setup (sequential): \(t = 10\) to \(11\).
- 6-min parallel compute split among 4 workers:
\[ \frac{6 \text{ min}}{4 \text{ workers}} = 1.5 \text{ minutes} \]
This runs from \(t = 11\) to \(12.5\).
- 1-min combine (sequential): \(t = 12.5\) to \(13.5\).
3. **Combine/sync (T4):**
- Runs from \(t = 13.5\) to \(16.5\) (3 min).
4. **Apply update (T5):**
- Runs from \(t = 16.5\) to \(20.5\) (4 min).
5. **Evaluate (T6, T7):**
- Worker 1 takes T7 (9 min) \( ightarrow\) finishes at \(20.5 + 9 = 29.5\).
- Worker 2 takes T6 (7 min) \( ightarrow\) finishes at \(20.5 + 7 = 27.5\).

The total makespan is determined by the last finishing task (T7) at **29.5 minutes**.

Step 4: Makespan with 2 Workers (d)

With 2 workers:
1. **Start (T1, T2):**
- Worker 1 takes T1 (10 min), Worker 2 takes T2 (6 min).
- Both finish by \(t = 10\).
2. **Train (T3):**
- Starts at \(t = 10\).
- 1-min setup: \(t = 10\) to \(11\).
- 6-min parallel compute split among 2 workers:
\[ \frac{6 \text{ min}}{2 \text{ workers}} = 3 \text{ minutes} \]
This runs from \(t = 11\) to \(14\).
- 1-min combine: \(t = 14\) to \(15\).
3. **Combine/sync (T4):**
- Runs from \(t = 15\) to \(18\) (3 min).
4. **Apply update (T5):**
- Runs from \(t = 18\) to \(22\) (4 min).
5. **Evaluate (T6, T7):**
- Worker 1 takes T7 (9 min) \( ightarrow\) finishes at \(22 + 9 = 31\).
- Worker 2 takes T6 (7 min) \( ightarrow\) finishes at \(22 + 7 = 29\).

The total makespan is **31 minutes**.

Where does the difference come from?

Comparing 2 workers (31 min) vs 4 workers (29.5 min), the difference of **1.5 minutes** comes entirely from the parallel compute phase of **T3**:
- With 2 workers, the parallel compute of T3 takes \(\frac{6}{2} = 3\) minutes.
- With 4 workers, it takes \(\frac{6}{4} = 1.5\) minutes.
- All other phases (T1/T2 and T6/T7) only have a maximum concurrency of 2, meaning the extra 2 workers sit idle during those stages and do not speed them up.

Answer:

• (a) Max concurrency is 2. You should provision 2 workers for task-level concurrency.
• (b) Makespan with 1 worker is 47 minutes.
• (c) Makespan with 4 workers is 29.5 minutes.
• (d) Makespan with 2 workers is 31 minutes. The 1.5-minute difference comes entirely from the parallel compute portion of T3, which scales from 3 minutes (with 2 workers) down to 1.5 minutes (with 4 workers).