Parallel Algorithm Models TODO
Concept
The work-span model views a parallel computation as a DAG and summarizes it with two numbers. Work T1 is the total amount of computation (the time on a single processor); span T-infinity is the length of the critical path of dependencies (the time you can't shrink even with infinite processors); parallelism is defined as T1/T-infinity. A good scheduler (e.g., work-stealing) guarantees that Tp is roughly T1/p + T-infinity, so parallelism needs to be comfortably larger than p to approach linear scaling. Amdahl's law says that for a fixed problem size, a serial fraction s caps the speedup at 1/s. Gustafson's law instead assumes that as processors increase, people scale up the problem size too, so the work done in a fixed time grows roughly proportional to the number of processors. The two aren't contradictory — they just hold different things fixed.
When adding cores doesn't improve performance, failing to tell apart whether the cause is the serial portion, the critical path, or scheduling overhead leads to tuning the wrong thing.
Code & Formula
# 병렬 알고리즘 모델 — DAG의 work(T1)/span(T∞)을 계산하고, Amdahl vs Gustafson 속도향상을 비교한다.
from collections import defaultdict
# 태스크: id -> (실행시간, 선행 태스크 목록)
tasks = {
"a": (2, []), "b": (3, ["a"]), "c": (1, ["a"]),
"d": (4, ["b"]), "e": (2, ["c"]), "f": (1, ["d", "e"]),
}
def topo_order():
indeg = {k: len(v[1]) for k, v in tasks.items()}
children = defaultdict(list)
for k, (_, ds) in tasks.items():
for d in ds:
children[d].append(k)
ready = [k for k, v in indeg.items() if v == 0]
order = []
while ready:
n = ready.pop()
order.append(n)
for c in children[n]:
indeg[c] -= 1
if indeg[c] == 0:
ready.append(c)
return order
order = topo_order()
work = sum(d for d, _ in tasks.values()) # T1: 프로세서 1개로 걸리는 총 시간
finish = {}
for t in order:
start = max((finish[d] for d in tasks[t][1]), default=0)
finish[t] = start + tasks[t][0]
span = max(finish.values()) # T∞: 임계 경로(의존성 사슬) 길이
parallelism = work / span
def amdahl(p, serial_fraction):
return 1 / (serial_fraction + (1 - serial_fraction) / p)
def gustafson(p, serial_fraction):
return p - serial_fraction * (p - 1)
print(f"work T1={work}, span T∞={span}, 병렬성 T1/T∞={parallelism:.2f}")
for p in (1, 2, 4, 8):
lower_bound = max(work / p, span) # 좋은 스케줄러가 보장하는 하한
print(f"p={p}: 하한 Tp>={lower_bound:.2f}, "
f"Amdahl(s=0.1)={amdahl(p, 0.1):.2f}x, Gustafson(s=0.1)={gustafson(p, 0.1):.2f}x")
docs/code/algorithms/algorithms-17.py
Exercise
Compute the work and span of a parallel merge sort or parallel prefix sum by hand, then in Go increase the number of goroutines from 1 up to the core count and overlay the measured speedup curve against the prediction.
Practical Connection
This is the basis for judging how far parallelization pays off in block-execution parallelism (where inter-transaction state dependencies form the DAG's edges) or in Verex's batch settlement and off-chain matching engine.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.