JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Amdahl 定律與平行的極限

買八顆核心，幾乎從不等於買到八倍的速度——而其中有一個精確又誠實的理由。這篇導覽從一張簡單的圖把 Amdahl 定律推導出來，說明為什麼一小片串列就封住了一切，掂量 Gustafson 定律那個樂觀的回應，再把真實世界裡的那些稅——一致性、同步與 NUMA——算進來，看它們如何把真實加速再往下拉。

定律背後的那張圖

我們花了一整級在讓許多核心彼此合作：私有快取靠一致性協定步調一致，執行緒靠同步維持次序。現在輪到誠實的結算了。多核心的承諾是：加核心就加上執行緒層級平行、於是加上速度。Amdahl 定律就是那條潑冷水的規則，它精確地說出這份承諾你究竟能領回多少——而答案幾乎總是比你盼的少。

整條定律就從一張簡單的圖裡掉出來。把你程式的執行時間拆成兩部分：一個能被完美平行化的比例 P（有多少核心就在多少核心上做），以及其餘的 (1 − P)，那部分本質上是串列的——無論旁邊有多少核心閒著，它都得一步一步跑。現在把工作交給 N 顆核心。串列那部分仍佔原來時間的 (1 − P)，因為平行硬體對它毫無作用。平行那部分則從 P 縮到 P/N，因為 N 顆核心把它分成 N 份。把兩者加起來，就是新的執行時間。

  serial part           parallel part
  |<-- (1 - P) -->|<--------- P --------->|     time on 1 core  = 1

  with N cores:
  |<-- (1 - P) -->|< P/N >|                      time on N cores = (1 - P) + P/N

  speedup  S(N) = 1 / ( (1 - P) + P/N )
  ceiling  S(infinity) = 1 / (1 - P)        <- set by the serial fraction alone
一張圖裡的 Amdahl 定律。串列那片永遠不縮；只有平行那片被 N 除。當 N 無限增大，平行那片消失了，但串列那片還在，於是加速封頂於 1 / (1 − P)。

為什麼一小片串列就毀掉一切

給它套上真實的數字，結果令人清醒。假設你程式的 95% 能完美平行化，於是 P = 0.95，只有 5% 是串列的。用 16 顆核心，加速是 1 / (0.05 + 0.95/16)，約莫 9 倍——不是 16 倍。推到 256 顆核心，你得到 1 / (0.05 + 0.95/256)，勉強 19 倍，儘管你花的硬體是那台 16 核機器的十六倍。而無窮多顆核心下的絕對上限，不過是 1 / 0.05 = 20 倍。那頑固的 5% 串列片把你永遠封在 20 倍；你用再多核心都買不過它。

現在把核心數一路往上加，看那報酬如何遞減。在 5% 串列（P = 0.95）下，4 顆核心約給 3.5 倍，16 顆 9.1 倍，64 顆只有 15.4 倍，256 顆勉強 18.6 倍，無窮多顆給 20 倍——你越是朝上限爬，核心每翻倍買到的就越是薄薄一片。最深的教訓在於對照：把串列那部分削到僅僅 1%（P = 0.99），上限便從 20 倍躍到 100 倍，而 64 顆核心此時抵達 39 倍而非 15 倍。把串列比例砍半，遠比任何數量的額外核心值錢——削掉串列工作，勝過買硬體。

樂觀者的回應：Gustafson 定律

如果 Amdahl 定律是故事的全部，那麼擁有一百萬顆核心的超級電腦就毫無意義了——但它們並非毫無意義。癥結在於 Amdahl 設定裡藏著一個假設：它把問題規模固定住，問的是同一份工作能跑快多少。這叫做強擴展（strong scaling）。但實務上，當人們拿到一台更大的機器，他們通常會去解一個更大的問題——更細的天氣網格、更大的神經網路、每秒更多的網路請求。這叫做弱擴展（weak scaling），而 Gustafson 定律描述的正是它。

關鍵的洞見在這裡。程式的串列部分——讀輸入、做設定、印出答案——往往隨著問題長大而大致維持原來的大小，而平行部分卻隨之膨脹。於是問題越大，串列比例就越小，Amdahl 砌起的那道牆便悄悄退去。Gustafson 定律說，擴展後的加速大約是 (1 − P) + P 乘以 N：只要你讓問題長大到足以餵飽核心，加速就幾乎隨核心數線性增長。這正是倉儲規模電腦裡請求層級平行的運作方式——兩倍的伺服器幾乎完美地服務兩倍的使用者，因為每個使用者的請求都是彼此獨立的工作。

Amdahl 從沒向你收的那些稅

Amdahl 定律本就已經悲觀，卻仍然太樂觀了，因為它假裝平行那部分能免費地裂成 N 份。它並不能。我們在這一級裡為了讓共享安全而造的每一個機制，也都要花時間，而那筆花費是 Amdahl 那條乾淨公式忽略掉的純粹額外開銷。維持快取步調一致要付出一致性流量；每當一顆核心寫一條共享的快取行，一致性協定就必須讓其他每顆核心桌上的副本失效，而那些訊息得橫越晶片，真正的工作只能等著。

三種稅咬得最狠。第一，同步：為了碰共享資料而去取鎖的執行緒，在等待時得花時間空轉或睡眠，而一把握太久的鎖會把你原本指望平行的那部分硬生生串列化——悄悄地把 (1 − P) 灌大。第二，假共享：兩顆核心更新一個陣列中相鄰的格子，碰的是不同的變數，卻是同一條快取行，於是儘管兩條執行緒從未真正衝突，一致性仍把那條行來回乒乓——這在本級稍早講過，是讓一個「平行」迴圈跑得比串列還慢的經典手法。第三，NUMA：在一台多晶片機器上，一條跑得離自己資料很遠的執行緒，抵達非均勻記憶體要慢，於是資料實際住在哪裡，如今會改變答案。

  1. 先剖析、找出真正的串列瓶頸——不要用猜的。那最大、最頑固的串列片，正是 Amdahl 上限建立其上的東西；去攻別處只是白費力氣。
  2. 在加核心之前先縮小串列比例：一個更小的 (1 − P) 會把整道上限抬高，而那是再多額外核心都辦不到的。
  3. 把共享與同步壓到最小：替資料加上填充以避開假共享，讓臨界區保持短小，並偏好讓執行緒各自處理獨立資料的設計。
  4. 把資料擺在用它的那顆核心附近（NUMA 感知的配置），這樣執行緒就不會因為每次存取都得橫越整台機器而被默默課稅。

誠實地讀加速數字

把這一切握在手裡，你就能用清醒的眼睛去讀平行效能的宣稱。一個報出來的「加速」只有對照一個明說的基準時才有意義——而公平的基準是最好的單核心實作，不是一個故意做慢的版本。一個常見的偷天換日，是拿一個調校過的平行版去比一個沒調校的串列版，再把其實來自更好程式碼的進步算到核心頭上。永遠要問：加速是相對於什麼、又在多大的問題規模下？

有一種真正出人意料的情況值得誠實一提：有時你在 N 顆核心上量到超過 N 倍的加速，稱為超線性加速。這不是魔法，也沒有打破 Amdahl 定律。它通常之所以發生，是因為 N 顆核心帶來了 N 倍的總快取，於是一個原本在單核心快取裡顛簸的工作集，如今橫跨許多核心剛好放得下——那份加速來自更大的合併快取，而不是平行本身。把真正的成因說出來能讓你保持誠實，也提醒你：「核心」與「快取」是一起擴展的，其方式正是那條乾淨公式從未捕捉到的。

退後一步，看這整道階梯的弧線。功率牆逼出了從一顆快核心走向許多彼此合作的核心，而自此之後的一切——一致性、一致性模型、原子操作與鎖、NUMA——都是那份合作的代價。Amdahl 定律是那塊誠實的計分板，結算你能領回什麼：真實、有價值，卻被那段沒有任何硬體能切分的串列工作所限。平行效能的功夫不在於買更多核心；而在於找出彼此獨立的工作、把它乾淨地餵給核心，並尊重串列比例所設下的那道上限。