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.
Where it lands in Jayverse
- Verex: measure the matching engine's actual span, not just its work. Before adding worker threads to the off-chain matching engine, compute the critical path of order dependencies; if span dominates, more workers won't help and the code structure needs to change, not the worker count.
- Devnet: decide whether Amdahl or Gustafson is the right model for a future L2's block execution. If Devnet's OP-Stack L2 pursues parallel transaction execution, state upfront whether the goal is a fixed workload going faster (Amdahl) or bigger blocks in the same time (Gustafson), since they call for different engineering.
- CI: benchmark ChainJob-style batch settlement against core count. Overlay Verex's batch settlement throughput against increasing parallelism to find where the serial fraction (session-key nonce lane, DB writes) caps the speedup, rather than assuming more concurrency helps indefinitely.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| hold (something) fixed | ~을 고정된 값으로 두다 · 비교를 위해 한 변수를 상수로 취급할 때. "they just hold different things fixed" |
| cap (the speedup) | 상한선을 씌우다, 제한하다 · 특정 값이 최댓값을 넘지 못하게 할 때. "a serial fraction s caps the speedup at 1/s" |
| tell apart | 구별하다, 분간하다 · 원인이 여러 개일 때 어느 것인지 가려낼 때. "failing to tell apart whether the cause is" |
| tune the wrong thing | 엉뚱한 것을 고치려 하다 · 원인을 잘못 짚고 튜닝할 때. "leads to tuning the wrong thing" |
| comfortably larger than | 넉넉히 더 큰, 여유 있게 큰 · 비교 대상보다 충분히 클 때. "parallelism needs to be comfortably larger than p" |
| approach (linear scaling) | 선형 확장에 근접하다 · 이상적인 성능 향상에 가까워질 때. "to approach linear scaling" |
| pays off | 보람이 있다, 이득이 되다 · 투자한 노력이 결실을 맺을 때. "how far parallelization pays off in block-execution parallelism" |
| work-stealing | 워크 스틸링(유휴 코어가 다른 코어의 작업을 가져와 처리하는 스케줄링 기법) · 병렬 스케줄러의 대표적 구현 방식. "A good scheduler (e.g., work-stealing) guarantees that Tp is" |
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/.