並行前綴加法器
想像一場接力賽,不是一根接力棒沿著長隊伍傳下去,而是排成淘汰賽對戰表:兩兩組合,再兩組兩組組合,再往上兩兩組合,於是整個賽場在幾輪內解決,而非一條長序列。並行前綴加法器把進位計算正是排成淘汰賽對戰表的樣子,將長長的進位鏈變成一棵淺淺的組合樹。
關鍵洞見是:進位前瞻觀點裡的產生與傳遞訊號,能以結合律的方式組合。定義一個運算子,把相鄰的兩個 (g, p) 對融合成一個涵蓋它們整段範圍的彙總對;由於這個融合滿足結合律,組合的順序無所謂,於是你能用一棵平衡樹來組合。樹的每一層融合長度加倍的範圍——先是位元,再是對,再是四個一組、八個一組,依此類推——大約經過 log2(寬度) 層後,每個位元都知道自己的進位。具名的設計在形狀上各有取捨:Kogge-Stone 最快(層數最少)但用很多線與閘;Brent-Kung 用的閘少得多但多幾層;Sklansky 等則介於其間。它們算出的進位都一樣,只是扇出、佈線與面積不同。
並行前綴加法器是現代寬 ALU 的高效能預設選擇,正因為它的延遲隨寬度的對數增長,又規整到足以在矽上佈局。誠實的取捨是把老調拉得更尖:最快的變體要付出佈線壅塞、面積與開關功耗的代價,所以設計者是在這個家族裡挑一個點——層數少求純速度、閘數少求功耗與面積——而非把「並行前綴」當成一個固定電路。
對 8 位元,第 1 層組合相鄰、涵蓋 2 位元的 (g,p) 對;第 2 層把它們組合成 4 位元的範圍;第 3 層組合成完整的 8 位元範圍。經過 3 層(8 的 log2)後,每個位元的進位都已知,相對於漣波要 8 級。
對產生/傳遞範圍做滿足結合律的合併,得到對數深度的進位樹。
所有前綴加法器算出的進位完全相同;它們只在樹的形狀上不同,因而在深度、扇出、佈線與功耗上有別。沒有單一「最好」的——Kogge-Stone 勝在速度,Brent-Kung 勝在閘數,真實選擇落在其間。