リプルキャリー・キャリールックアヘッド・キャリーセーブ加算器の違い：遅延・回路規模・用途を比較

どんなときに使うか

リプルキャリー加算器

ビット数が少ないとき、または速度より面積や消費電力を優先するときに使います。回路が単純で規則的なので、FPGAのように専用の高速な桁上げの経路をもつデバイスでは、この形で効率よく実装できます。

桁上げ先見加算器(キャリールックアヘッド)

2つの数の加算を1回で速く終える必要があるときに使います。CPUのALUや、クリティカルパスに入る加算器が代表的です。階層化の方法や並列プレフィックス加算器の種類によって、段数と、面積・配線量とのかね合いを選びます。

桁上げ保存加算器(キャリーセーブ)

3つ以上の数を足すときに使います。途中では桁上げの伝わりを待たずに数を減らし、最後に1回だけ桁上げ先見加算器などで足すので、多数の部分積を足す乗算器や、積和演算を繰り返すMACで効果が大きくなります。

理解度チェック

1. 乗算器で多数の部分積を足し合わせるのに、桁上げ保存加算器が使われる主な理由はどれか。
2. 高速な乗算器で使われるウォレスツリーの特徴として正しいものはどれか。
3. 全加算器の入力として正しい組み合わせはどれか。

計算機算術の練習問題へ

関連する用語の解説

全加算器

2つのビットと下位の桁からの桁上げの3入力を足し、和と上位への桁上げを出す回路。桁上げ入力のないものは半加算器。直列につなぐと多ビットの加算器になる。

桁上げ先見加算器

各桁の生成信号 g = a·b と伝搬信号 p = a ⊕ b から、桁上げを下位からの伝わりを待たずに並列に求める加算器。ビット数が多くても遅延が小さい。キャリールックアヘッド加算器ともいう。

桁上げ保存加算器

3つの数を、桁上げを伝えずに「和」と「桁上げ」の2つの数にまとめる加算器。全加算器を桁ごとに並べただけで遅延が一定なので、乗算器で多数の部分積を足すのに使われる。

ウォレスツリー

乗算器で、多数の部分積を桁上げ保存加算器の木で並列に減らしていく構成。段数がビット数の対数程度で済み、高速な乗算器に使われる。最後に2つの数を通常の加算器で足す。

ブースのアルゴリズム

乗数のビットの並びを2ビットずつなどに区切って符号付きの桁に置き換え、部分積の数を減らす乗算の方法。基数4のブース法では部分積がほぼ半分になる。

クリティカルパス

回路の中で遅延が最も大きく、動作できる最大のクロック周波数を決める経路。STAではスラックが最小の経路にあたり、高速化はこの経路の遅延を減らすことから始める。

関連する比較

• 固定小数点と浮動小数点の違い：表現・範囲と精度・演算器の規模・オーバーフロー・用途を比較固定小数点と浮動小数点を、表現のしかた・表せる範囲と精度・演算器の規模と電力・オーバーフローの扱い・プログラミングの手間・使われる場所の観点で表にして比較します。
• FP32・FP16・BF16・INT8の違い：ビット構成・範囲・精度・用途を比較FP32・FP16・BF16・INT8を、ビット構成(符号・指数・仮数)・表せる範囲・精度・FP32からの変換・メモリ・演算器の効率・学習と推論での用途の観点で表にして比較します。
• 幅優先探索と深さ優先探索の違い：訪れる順・データ構造・最短経路・メモリ・用途を比較幅優先探索(BFS)と深さ優先探索(DFS)を、訪れる順・使うデータ構造・最短経路・計算量・使うメモリ・解が見つかるか・木をたどる順・主な用途の観点で表にして比較します。
• 配列と連結リストの違い：読み出し・挿入と削除・メモリの並び・キャッシュ・計算量を比較配列と連結リストを、メモリ上の並び方・i番目の要素の読み出し・値の探索・途中への挿入と削除・末尾への追加・大きさの変更・使うメモリ・キャッシュの効きやすさ・主な用途の観点で表にして比較します。
• 教師あり学習・教師なし学習・強化学習の違い：データ・正解の与え方・目的・手法・例を比較教師あり学習・教師なし学習・強化学習を、学習に使うデータ・正解の与え方・学習の目的・主な課題・代表的な手法・評価のしかた・難しさ・使われる例の観点で表にして比較します。
• DRAMとSRAMの違い：構造・速度・コスト・用途を比較DRAMとSRAMを、セル構造・リフレッシュ・速度・集積度・コスト・消費電力・用途の観点で表にまとめて比較。どちらをどんなときに使うかも解説します。