Before the questions, make sure you can: model an application as a directed acyclic graph with a computation-cost matrix and communication costs; explain why communication is free on the same processor; define and compute makespan, schedule length ratio (SLR), speedup and efficiency; explain why DAG scheduling on heterogeneous processors is NP-hard and what list-scheduling heuristics do; compute upward and downward ranks and the critical path; trace HEFT step by step (priority order, earliest start and finish times with the insertion policy, processor selection); explain CPOP and PEFT (optimistic cost table and look-ahead); describe how research extended these ideas (predict-cost look-ahead such as PPTS/IPPTS, budget- and deadline-aware scheduling, reinforcement-learning priorities); validate a schedule; and design a fair experiment that compares scheduling algorithms.
Chapters 4–5 scheduled independent processes on identical cores. Real workloads are often workflows: hundreds of tasks where each task needs the outputs of others — an astronomy image mosaic, an earthquake simulation, a genome analysis, or a machine-learning pipeline (load → clean → train → evaluate). And today's machines are heterogeneous: CPUs, GPUs, edge servers and cloud VMs, each fast at some tasks and slow at others. Deciding which task runs on which processor, and when, to finish as early as possible is a central research problem of parallel and distributed computing — and the instructor's research field. This chapter takes you from the classic algorithm (HEFT) to the research frontier.
The model
- Workflow = DAG G = (V, E): each node is a task; an edge (i → j) means j needs data produced by i. A task with no predecessors is an entry task; one with no successors an exit task.
- Processors P1 … Pp are heterogeneous: the computation cost matrix W gives w(i, k), the time of task i on processor k (a task may be fast on a GPU and slow on a CPU, and vice versa).
- Communication cost c(i, j): time to transfer i's output to j when they run on different processors; zero on the same processor (data is already in local memory).
- Tasks are non-preemptive; a task may start only when all its input data has arrived.
Goal: minimize the makespan = the finish time of the last exit task.
Metrics used in research:
- SLR (schedule length ratio) = makespan ÷ length of the critical path computed with each task's minimum cost (CP_MIN). The denominator is a lower bound, so SLR ≥ 1; smaller is better. SLR lets us compare DAGs of different sizes.
- Speedup = (time of the whole workflow on the best single processor) ÷ makespan.
- Efficiency = speedup ÷ number of processors.
Why it is hard. Even the simplest versions of this problem are NP-hard: the number of possible assignments grows like pⁿ (3 processors, 100 tasks: 3¹⁰⁰ ≈ 5 × 10⁴⁷). So we use heuristics. The most successful family is list scheduling:
- Prioritize — compute a priority for each task and sort.
- Select — take tasks in that order and give each one to the "best" processor.
Ranks: how important is a task?
The upward rank of task i measures the length of the longest path from i to the end of the workflow, using average costs (we do not know yet where tasks will run):
rank_u(i) = w̄ᵢ + max over successors j of ( c(i, j) + rank_u(j) ), with rank_u(exit) = w̄_exit
The downward rank measures the longest path from the start to i (excluding i):
rank_d(i) = max over predecessors j of ( rank_d(j) + w̄ⱼ + c(j, i) ), with rank_d(entry) = 0
Tasks with rank_u + rank_d equal to the maximum lie on the critical path — the chain that determines how short the schedule can be (the "serial part" of Chapter 1's Amdahl's law, in DAG form).
Worked example (small)
Five tasks on two processors:
| Task | P1 | P2 | Average w̄ |
|---|---|---|---|
| T1 | 4 | 6 | 5 |
| T2 | 5 | 3 | 4 |
| T3 | 6 | 8 | 7 |
| T4 | 3 | 5 | 4 |
| T5 | 4 | 2 | 3 |
Edges (communication cost): T1→T2 (2), T1→T3 (3), T2→T5 (4), T3→T4 (1), T4→T5 (2).
Upward ranks (computed from the exit backwards):
- rank_u(T5) = 3
- rank_u(T4) = 4 + (2 + 3) = 9
- rank_u(T2) = 4 + (4 + 3) = 11
- rank_u(T3) = 7 + (1 + 9) = 17
- rank_u(T1) = 5 + max(2 + 11, 3 + 17) = 25
Priority order (decreasing rank_u): T1, T3, T2, T4, T5. Critical path: T1 → T3 → T4 → T5 (rank_u + rank_d = 25 for each).
HEFT — Heterogeneous Earliest Finish Time
HEFT (Topcuoglu, Hariri and Wu, IEEE TPDS, 2002) is the most cited list-scheduling algorithm:
- Compute rank_u for all tasks; sort by decreasing rank_u (ties: smaller task index).
- For each task in that order, and for each processor k:
- ready time = max over predecessors q of ( finish(q) + (0 if q is on k, else c(q, i)) );
- EST(i, k) = the earliest time ≥ ready time at which k has an idle gap long enough for w(i, k) — HEFT may insert a task into an earlier gap between already scheduled tasks (insertion-based policy);
- EFT(i, k) = EST(i, k) + w(i, k).
- Assign the task to the processor with the minimum EFT (ties: lower processor index).
Trace on the small example:
| Step | Task | EFT on P1 | EFT on P2 | Chosen |
|---|---|---|---|---|
| 1 | T1 | 0 + 4 = 4 | 0 + 6 = 6 | P1 (0–4) |
| 2 | T3 | 4 + 6 = 10 | (4 + 3) + 8 = 15 | P1 (4–10) |
| 3 | T2 | 10 + 5 = 15 | (4 + 2) + 3 = 9 | P2 (6–9) |
| 4 | T4 | 10 + 3 = 13 | (10 + 1) + 5 = 16 | P1 (10–13) |
| 5 | T5 | max(9 + 4, 13) + 4 = 17 | max(9, 13 + 2) + 2 = 17 | P1 (13–17) — tie → P1 |
Makespan = 17. Best single processor: P1 needs 4 + 5 + 6 + 3 + 4 = 22 → speedup 22/17 = 1.294, efficiency 0.647. CP_MIN (minimum costs on T1 → T3 → T4 → T5) = 4 + 6 + 3 + 2 = 15 → SLR = 17/15 = 1.133.
On the classic 10-task, 3-processor example of the HEFT paper, HEFT produces a makespan of 80 (upward ranks 108 for the entry task down to 14.67 for the exit task; critical path T1 → T2 → T9 → T10 of length 108). Lab OS6.2 reproduces it exactly.
CPOP — critical path on a processor
CPOP (same paper) prioritizes by rank_u + rank_d and puts all critical-path tasks on the single processor that executes the whole critical path fastest; other tasks go to their minimum-EFT processor. It is simple and good when one path dominates, but usually slightly worse than HEFT on average.
PEFT — looking ahead with an optimistic cost table
HEFT is greedy: it picks the processor that finishes this task soonest, even if that choice makes the task's successors expensive later (for example, a processor that is fast for this task but slow for everything after it). PEFT (Arabnejad and Barbosa, IEEE TPDS, 2014) adds a look-ahead:
OCT(i, k) = max over successors j of [ min over processors x of ( OCT(j, x) + w(j, x) + (0 if x = k else c̄(i, j)) ) ], with OCT(exit, k) = 0
OCT(i, k) is an optimistic estimate of the remaining time after task i if i runs on processor k. PEFT ranks tasks by the average OCT (rank_oct), schedules the ready task with the highest rank, and chooses the processor that minimizes O_EFT(i, k) = EFT(i, k) + OCT(i, k) — "finish this task early and leave its successors in a good position."
On many randomly generated workflows, PEFT produces shorter schedules than HEFT on average. But on the classic 10-task example it gives 85 versus HEFT's 80. Lesson for research: no heuristic wins on every instance — algorithms are compared statistically on thousands of workflows.
From classic algorithms to current research
Work by the instructor's research group has built on this line of algorithms:
- Look-ahead with a predict cost matrix. PPTS (Djigal et al., ICPP 2019, "Task Scheduling for Heterogeneous Computing using a Predict Cost Matrix") uses a predict cost matrix both to prioritize tasks and to look ahead when choosing a processor, keeping list scheduling's low complexity; IPPTS improved the approach further, and MPPTS (2025) combines several predictive factors into the priority.
- Budget and deadline constraints. In clouds and edges, a faster processor usually costs more. BUDA (IWQoS 2022) schedules task graphs under both a budget and a deadline; BUCAS and an adaptive budget-constrained provisioning method (ICA3PP 2025) decide which cloud VM types to rent for a workflow within a budget.
- Learning to schedule. Reinforcement learning (e.g., Q-learning) can learn task priorities instead of using hand-made ranks; a 2024 study evaluated Q-learning-based list scheduling on heterogeneous systems.
- Edge resource allocation. A widely cited survey (IEEE Communications Surveys & Tutorials, 2022) reviews machine and deep learning for resource allocation in multi-access edge computing — the topic of Chapter 13.
How scheduling research is evaluated. A credible comparison uses:
- Workloads: random DAGs generated with controlled parameters — number of tasks, CCR (communication-to-computation ratio: high CCR means data transfers dominate), graph shape (wide vs. deep), heterogeneity factor (how much processors differ) — and real scientific workflows (for example Montage, CyberShake, Epigenomics, LIGO and SIPHT from the Pegasus workflow collection).
- Metrics: average SLR, speedup, efficiency, and "percentage of instances where algorithm A is better than, equal to, or worse than B"; for cloud versions, cost and deadline/budget success rate.
- Fairness: same DAGs and platforms for all algorithms, enough instances for statistical significance, reported running time of the scheduler itself (a scheduler that takes an hour to plan a 10-minute workflow is useless).
Adding processors helps only if the DAG has enough parallel tasks and the communication costs are small relative to computation. With high CCR, putting dependent tasks on the same processor (zero communication) is often better than spreading them — which is exactly why HEFT considers communication when computing EST.
For a HEFT question: (1) compute w̄ for each task, (2) compute rank_u from the exit tasks backwards, (3) sort, (4) for each task compute EFT on every processor — remember communication is 0 when the predecessor is on the same processor, and check idle gaps for insertion — (5) pick the minimum EFT, (6) the makespan is the maximum finish time. Show a table like the trace above.
Key takeaways
- Workflows are DAGs with a computation-cost matrix (heterogeneous processors) and communication costs (zero on the same processor).
- Metrics: makespan, SLR = makespan / CP_MIN, speedup = best sequential / makespan, efficiency = speedup / p.
- The problem is NP-hard; list scheduling = prioritize + select processor.
- rank_u(i) = w̄ᵢ + max_j (c(i, j) + rank_u(j)); critical path = tasks with maximal rank_u + rank_d.
- HEFT: decreasing rank_u, insertion-based EST, minimum EFT. CPOP: critical path on one processor. PEFT: optimistic cost table, choose minimum EFT + OCT (look-ahead).
- Research extends these with look-ahead matrices (PPTS/IPPTS), multiple predictive factors, budgets and deadlines (BUDA, BUCAS), and learning-based priorities — evaluated statistically on random and real workflows.
Ready? Close the notes and practise.
30 questions. Predict the output before you check — that is the skill the exam measures.