Practice · Scheduling on Heterogeneous Systems: Workflows, HEFT and Beyond

Q1

In a workflow DAG, what does an edge T1 → T4 with weight 9 mean?

A T1 runs 9 times. B T1 and T4 must run on the same processor. C T4 must start exactly 9 units after T1. D T4 needs data from T1; transferring it takes 9 time units if they run on different processors.

Q2

Why is communication cost usually taken as zero when two dependent tasks run on the same processor?

A Because communication is always free. B Because the second task does not need the data. C Because processors cannot communicate. D Because the data is already in that processor's local memory.

Q3

What is the makespan of a schedule?

A The finish time of the last (exit) task B The number of tasks C The number of processors used D The sum of all computation costs

Q4

A workflow takes 22 time units on the best single processor and 17 with HEFT on 2 processors. What are the speedup and efficiency?

A 1.294 and 0.647 B 2.000 and 1.000 C 0.773 and 0.386 D 1.294 and 1.294

Q5

The makespan is 17 and the critical path computed with each task's minimum cost (CP_MIN) is 15. What is the SLR, and what does SLR = 1 mean?

A 15; the number of tasks B 1.133; SLR = 1 would mean the schedule reaches the lower bound of the critical path C 2; the number of processors D 0.88; the schedule is too short

Q6

Why do researchers use heuristics such as HEFT instead of computing the optimal schedule?

A Optimal schedules do not exist. B Optimal schedules are always slower. C The problem is NP-hard: the number of possible assignments grows exponentially, so optimal search is infeasible for realistic workflows. D Heuristics need no computation costs.

Q7

Task T4 has average cost w̄ = 4 and one successor T5 (rank_u = 3) with communication cost 2. What is rank_u(T4)?

A 7 B 9 C 11 D 4

Q8

Task T1 (w̄ = 5) has successors T2 (edge 2, rank_u 11) and T3 (edge 3, rank_u 17). What is rank_u(T1)?

A 25 B 18 C 20 D 38

Q9

In HEFT, in what order are tasks considered for scheduling?

A Random order B Decreasing upward rank C By task number only D Increasing upward rank

Q10

Why is decreasing rank_u always a valid topological order?

A It is not; HEFT must check it separately. B Because ranks are random. C Because every task's rank_u is larger than each successor's rank_u (it adds a positive w̄ and non-negative communication). D Because HEFT ignores dependencies.

Q11

T3 depends on T1 (edge cost 3). T1 runs on P1 and finishes at 4. T3 costs 6 on P1 (free from time 4) and 8 on P2 (idle). What is EFT(T3) on each processor?

A P1: 10, P2: 15 B P1: 13, P2: 15 C P1: 10, P2: 12 D P1: 6, P2: 8

Q12

What is HEFT's insertion-based policy?

A Tasks are duplicated on several processors. B New processors are inserted during scheduling. C Tasks are inserted at the end of the task list. D A task may be placed in an idle gap between tasks already scheduled on a processor, if the gap is long enough and starts after the task's data is ready.

Q13

How does HEFT choose a processor for a task?

A The least used processor B Round-robin over processors C The processor where the task's computation cost is smallest D The processor that gives the earliest finish time (EFT), considering data arrival and idle gaps

Q14

On the classic 10-task, 3-processor example from the HEFT paper, what makespan does HEFT produce?

A 86 B 108 C 73 D 80

Q15

Which tasks lie on the critical path used by CPOP?

A Tasks with no communication B Tasks whose rank_u + rank_d equals the maximum value (the entry task's rank_u) C Tasks with the largest computation cost D All exit tasks

Q16

What is the main weakness of HEFT that PEFT addresses?

A HEFT is greedy: it minimizes the current task's finish time without considering how that choice affects its successors. B HEFT cannot handle communication costs. C HEFT only works on one processor. D HEFT does not produce valid schedules.

Q17

In PEFT, a task can run on P1 with EFT 20 and OCT 30, or on P2 with EFT 24 and OCT 18. Which processor does PEFT choose?

A P2, because EFT + OCT = 42 < 50 B P1, because its EFT is smaller C Neither D Both

Q18

On the classic 10-task example, PEFT gives makespan 85 while HEFT gives 80. What is the correct research conclusion?

A The implementation must be wrong. B One instance proves nothing; heuristics must be compared on many workflows (random and real) with statistical summaries. C PEFT is a worse algorithm. D HEFT is optimal.

Q19

What does a high CCR (communication-to-computation ratio) mean for scheduling?

A Processors are identical. B Tasks cannot run in parallel. C Data transfers are expensive relative to computation, so placing dependent tasks on the same processor becomes more attractive. D Communication is negligible, so spreading tasks is always good.

Q20

Why do cloud versions of workflow scheduling add a budget constraint (as in BUDA or BUCAS)?

A Budgets only matter for storage. B Because faster VM types cost more per hour, so the fastest schedule may be unaffordable; the scheduler must trade makespan against monetary cost. C Because cloud processors are free. D Because budgets reduce communication.

Q21

What is the idea behind look-ahead algorithms such as PEFT and PPTS?

A Ignore dependencies. B Schedule tasks in reverse order. C Use a precomputed matrix that estimates, for each task–processor pair, the cost of the remaining path, and use it in ranking and/or processor selection. D Run each task twice.

Q22

How can reinforcement learning be used in list scheduling?

A To remove communication costs B To replace the DAG with a single task C To learn task priorities (or placement decisions) from experience instead of using a fixed formula such as rank_u D To guarantee optimal schedules on every instance

Q23

CPOP places all critical-path tasks on one processor. Which processor does it choose?

A The processor that minimizes the total computation time of the critical-path tasks B A random processor C The processor with the most idle time D The first processor

Q24

Why can HEFT's use of average computation costs in rank_u be misleading when processors are very heterogeneous?

A Averages ignore the number of tasks. B A task's average may not represent the cost on any processor it will actually use (e.g., 2 on a GPU and 100 on a CPU averages to 51), so the priority order can be distorted. C rank_u does not use computation costs. D Averages are always exact.

Q25

Which is a real scientific workflow commonly used to evaluate scheduling algorithms?

A A single-threaded calculator B The BIOS C Microsoft Word D Montage (astronomy image mosaics)

Q26

A research paper reports that its new scheduler beats HEFT, but it was tested on 5 hand-picked DAGs and does not report its own running time. What are the main weaknesses?

A None; 5 DAGs are enough. B Running time is never relevant. C Too few and possibly biased instances (no statistical evidence), and unknown scheduling overhead — a slow scheduler may cost more than it saves. D It should have used fewer DAGs.

Q27 Short answer

Compute rank_u and rank_d for the five-task example (costs P1/P2: T1 4/6, T2 5/3, T3 6/8, T4 3/5, T5 4/2; edges T1→T2 2, T1→T3 3, T2→T5 4, T3→T4 1, T4→T5 2), give the HEFT priority order and identify the critical path.

Q28 Short answer

Schedule the same five-task example with HEFT on two processors. Show EFT on each processor at every step, the final schedule and makespan, and compute speedup, efficiency and SLR.

Q29 Short answer

Explain the difference between HEFT's processor selection and PEFT's, and describe a DAG situation where PEFT's choice is better.

Q30 Short answer

EdgeCampus runs a video-analytics workflow on 2 edge GPUs and 1 cloud CPU VM rented at a price per minute. Describe how you would extend HEFT to respect a budget, and which trade-off the scheduler faces.