Wallace 樹乘法器

移位相加在迴圈裡乘，一個週期一個部分積，很慢。Wallace 樹乘法器則一次把所有部分積攤開，再用一棵由小加法器構成的樹，盡可能快地把它們全部相加。想像有人遞給你四十張收據要結算：一張張加很慢，但若分組、各組平行結算、再合併各組小計，你能在少得多的回合內完成。Wallace 樹就是把這種平行分組套用到部分積的各欄上。

首先，所有部分積同時產生——對一個 n 位元乘 n 位元的乘法，那是多達 n 列的移位列（常先用 Booth 編碼減半）。關鍵元件是進位儲存加法器：它吃三個數、把它們化簡成兩個（一個和向量與一個進位向量），全程不讓進位跨字組傳播，所以它快、而且延遲不隨寬度增長。樹分層套用進位儲存加法器，每一層把三列部分和變成兩列，每層讓列堆大約以 3 比 2 縮小。約莫對數多層後只剩兩列，再用單一個普通的快速加法器（前瞻或前綴加法器）把這最後兩列相加，產生最終乘積。緩慢的進位傳播只在最後發生一次。

結果是一個延遲隨運算元寬度的對數、而非線性增長的乘法器——當乘法吞吐量很重要時的標準選擇，例如訊號處理與機器學習硬體。誠實的代價是面積與功耗：你蓋了一片加法器叢林，把移位相加在時間裡做的事改在空間裡做。規整的陣列乘法器是較簡單、較易佈局的表親（稍慢、較好佈線）；Wallace 與相關的 Dadda 樹以較不規整的結構為代價，把加法器層數降到最少。