キャリースキップ加算器

キャリースキップ加算器^{[注 1] （}キャリーバイパス加算器とも呼ばれる）は、他の加算器に比べてほとんど手間をかけずにリップルキャリー加算器の遅延を改善する加算器の実装です。最悪の場合の遅延の改善は、複数のキャリースキップ加算器を使用してブロックキャリースキップ加算器を形成することで実現されます。

他の高速加算器とは異なり、キャリースキップ加算器のパフォーマンスは、入力ビットの組み合わせの一部でのみ向上します。つまり、速度の向上は確率的にすぎません。

単純な1レベルリップルキャリー加算器の最悪のケースは、各桁のペアに対して伝播条件^[1]が真である場合に発生します。その後、キャリーインはビット加算器を介してリップルされ、後にキャリーアウトとして現れます。 ${\displaystyle (a_{i},b_{i})}$${\displaystyle n}$${\displaystyle \tau_{CRA}(n)\approx n\cdot \tau_{VA}}$

各オペランド入力ビット ペアについて、伝播条件はXOR ゲートを使用して決定されます。すべての伝播条件がtrueの場合、キャリーイン ビットによってキャリーアウト ビットが決定されます。 ${\displaystyle (a_{i},b_{i})}$${\displaystyle p_{i}=a_{i}\oplus b_{i}}$${\displaystyle c_{0}}$

nビットキャリー スキップ加算器は、nビット キャリー リップル チェーン、n入力 AND ゲート、および 1 つのマルチプレクサで構成されます。キャリー リップル チェーンによって提供される各伝播ビットは、n入力 AND ゲートに接続されます。結果のビットは、最後のキャリー ビットまたはキャリー入力をキャリー出力信号に切り替えるマルチプレクサの選択ビットとして使用されます。 ${\displaystyle p_{i}}$${\displaystyle c_{n}}$${\displaystyle c_{0}}$${\displaystyle c_{out}}$

• ${\displaystyle s=p_{n-1}\wedge p_{n-2}\wedge \dots \wedge p_{1}\wedge p_{0}=p_{[0:n-1]}}$

これにより、各ブロックのキャリー ビットが、グループ伝搬信号が論理 1 に設定されたブロックを「スキップ」できるため、クリティカル パスを介した加算器のレイテンシが大幅に削減されます (長いリップル キャリー チェーンでは、キャリーが加算器の各ビットにリップルする必要があります)。AND ゲートの入力数は、加算器の幅と同じです。幅が大きい場合、これは非現実的になり、AND ゲートをツリーとして構築する必要があるため、遅延が増加します。合計ロジックがn入力 AND ゲートとマルチプレクサと同じ深さである場合、適切な幅が実現されます。

キャリー スキップ加算器のクリティカル パスは、最初の全加算器から始まり、すべての加算器を通過して合計ビットで終了します。 単一ビットのキャリー スキップ加算器は、ビット リップル キャリー加算器と比較して実際の速度上の利点がないため、キャリー スキップ加算器は連鎖され (ブロック キャリー スキップ加算器を参照)、全体的なクリティカル パスが削減されます。 ${\displaystyle s_{n-1}}$${\displaystyle n}$${\displaystyle n}$

${\displaystyle \tau _{CSA}(n)=\tau _{CRA}(n)}$

スキップ ロジックは、1 つの入力 AND ゲートと 1 つのマルチプレクサで構成されます。 ${\displaystyle m}$

${\displaystyle T_{SK}=T_{AND}(m)+T_{MUX}}$

伝播信号は並列に計算され、早期に利用可能になるため、キャリースキップ加算器のスキップ ロジックのクリティカル パスは、マルチプレクサによって課される遅延 (条件付きスキップ) のみで構成されます。

${\displaystyle T_{CSK}=T_{MUX}=2D}$。

ブロック キャリー スキップ加算器は、複数のキャリー スキップ加算器で構成されています。ブロック キャリー スキップ加算器には 2 つのタイプがあり、 2 つのオペランドはビットのブロックに分割されます。 ${\displaystyle A=(a_{n-1},a_{n-2},\dots ,a_{1},a_{0})}$${\displaystyle B=(b_{n-1},b_{n-2},\dots ,b_{1},b_{0})}$${\displaystyle k}$${\displaystyle (m_{k},m_{k-1},\dots ,m_{2},m_{1})}$

• ブロックキャリースキップ加算器が使用されるのはなぜですか?
• ブロック サイズは定数にすべきですか、それとも可変にすべきですか?
• 固定ブロック幅と可変ブロック幅

固定サイズのブロック キャリー スキップ加算器は、入力ビットを各ビットのブロックに分割し、ブロックを生成します。クリティカル パスは、最初のブロックのリップル パスとスキップ要素、最初のブロックと最後のブロックの間にあるスキップ パス、そして最後のブロックのリップル パスで構成されます。 ${\displaystyle n}$${\displaystyle m}$${\displaystyle k={\frac {n}{m}}}$

${\displaystyle T_{FCSA}(n)=T_{CRA_{[0:c_{out}]}}(m)+T_{CSK}+(k-2)\cdot T_{CSK}+T_{CRA}(m)=3D+m\cdot 2D+(k-1)\cdot 2D+(m+2)2D=(2m+k)\cdot 2D+5D}$

与えられた加算器幅nに対する最適なブロックサイズは、0と等しくすることで導かれる。

${\displaystyle {\frac {dT_{FCSA}(n)}{dm}}=0}$

${\displaystyle 2D\cdot \left(2-n\cdot {\frac {1}{m^{2}}}\right)=0}$

${\displaystyle \Rightarrow m_{1,2}=\pm {\sqrt {\frac {n}{2}}}}$

正のブロックサイズのみが実現可能

${\displaystyle \Rightarrow m={\sqrt {\frac {n}{2}}}}$

ブロックサイズを変えることで、パフォーマンスを向上させることができます。つまり、すべてのキャリーがより速く伝播されます。したがって、加算器の最初のブロックは、さらに伝播する必要があるキャリー生成をすばやく検出できるように小さくされ、中間のブロックは問題にならないため大きくされ、その後、最も重要なブロックは、遅れて到着するキャリー入力をすばやく処理できるように再び小さくされます。^[2]

追加のレイヤーで追加のスキップ ブロックを使用すると、ブロック伝播信号がさらに要約され、より大きなスキップを実行するために使用されます。 ${\displaystyle p_{[i:i+3]}}$

${\displaystyle p_{[i:i+15]}=p_{[i:i+3]}\wedge p_{[i+4:i+7]}\wedge p_{[i+8:i+11]}\wedge p_{[i+12:i+15]}}$

これにより、加算器がさらに高速化されます。

物理的に最も高速なキャリースキップ加算器を作成するために必要なブロック サイズとレベル数を決定する問題は、「キャリースキップ加算器最適化問題」として知られています。この問題は、キャリースキップ加算器が物理デバイスで実装され、そのサイズやその他のパラメータも加算時間に影響するという事実によって複雑になっています。

任意のデバイス プロセス ノードの可変ブロック サイズと複数レベルのキャリー スキップ最適化問題は、IBM の Oklobdzija と Barnes によって解決され、1985 年に公開されました。

これをより具体的に説明すると、4 ビットのキャリーバイパス加算器を構築するには、6 つの全加算器が必要になります。入力バスは、キャリーイン ( CIN ) 信号を持つ 4 ビットのAと 4 ビットのBになります。出力は、4 ビットのバス X とキャリーアウト信号 ( COUT )になります。

最初の 2 つの全加算器は、最初の 2 ビットを加算します。2 番目の全加算器 ( ) からのキャリー出力信号は、3 つの 2 対 1 マルチプレクサの選択信号を駆動します。2 番目の 2 つの全加算器のセットは、が論理 0 であると想定して最後の 2 ビットを加算します。最後の全加算器のセットは、が論理 1 であると想定します。 ${\displaystyle C_{1}}$${\displaystyle C_{1}}$${\displaystyle C_{1}}$

マルチプレクサは、COUT および に使用される出力信号を制御します。 ${\displaystyle X_{2}}$${\displaystyle X_{3}}$

• 可変スキップ加算器のクリティカルパスの説明