加算器を作ろう carry select adderによる加算

http://d.hatena.ne.jp/natsutan/20081121の続きです。

前回はlpm_add_subを使用しましたが、手動で高速化を図ってみましょう。今回はcarry select adderと呼ばれる手法を用いました。carry select adderとは上位の加算をキャリー有り、キャリー無しの両方で計算しておき、下位のキャリーをセレクターとして使用します。そのままつなげると+による加算器より速くならないので、セレクターの部分を一回FFで叩きパイプライン化してみました。

2008/11/22
図が間違っていたので差し替えました。前の図は、carry_rの部分にFFが入っていませんでした。

実装１

今回の実装方針です。1CLK目で上位64bitに関してはキャリー付き、キャリー無しの両方を計算し、下位64bitは普通に加算します。2CLK目で、下位64bitの加算結果から生じるキャリー信号で最終結果の上位ビットを選択しています。

図で書くとこのようになります。緑の箱がFFになります。

実際のソースはこうなります。

always @ (posedge clk or negedge reset_x)begin
	if(reset_x == 0)begin
		c <= 0;
		carry_r <= 0;
		tmp_l <= 0;
		tmp_h_no_carry <= 0;
		tmp_h_with_carry <= 1;
	end else begin
		{carry_r, tmp_l} <= a[63:0] + b[63:0];
		tmp_h_no_carry <= a[127:63] + b[127:63];
		tmp_h_with_carry <= a[127:63] + b[127:63] + 1'b1;
		c[63:0] <= tmp_l;
		//下位のキャリーの有無で上位の値を選択
		if(carry_r)begin
			c[128:64] <= tmp_h_with_carry;
		end else begin
			c[128:64] <= tmp_h_no_carry;
		end
	end
end

実際の合成結果ですが、Fmax=181.23MHzとほとんど増えていません。tmp_h_with_carry <= a[127:63] + b[127:63] + 1'b1;の+1が期待通りにキャリー入力に入っていないのかとも思いましたが、配置後の状態をchip plannerで確認したところ、ちゃんと期待通りの結果になっているようです。

こちらがタイミングレポートの結果です。どうもキャリーでは無いところがボトルネックになっているようです。本来bの入力は一つの加算器にのみ接続されるのですが、キャリー有り/無し両方の加算器に入るためにファンアウトと配線長が大きくなっているようです。これではcarry select adderを使った意味がありません。

しかし、原因がわかっているのであれば高速化が狙えます。

高速化

bの信号が複数の加算器に入っていることが速度向上を妨げているので、一つの加算器には一つのFFからの出力しか入らないようにしましょう。

図のように黄色の部分にレジスタを追加しています。上位bitに関しては、同じ値をコピーするのに1CLK使っていることになります。下位bitは上位bitとパイプラインを合わせるためにFFを追加しています。

最初に方に決めた「- set_global_assignment -name REMOVE_DUPLICATE_REGISTERS OFF」のオプションがここでも効いてきます。このオプションがONの場合、せっかく作ったコピー用のレジスタが最適化によって消されてしまいます。高速化を図るためには、REMOVE_DUPLICATE_REGISTERSのオプションは常にOFFと思って良いくらいです。

always @ (posedge clk or negedge reset_x)begin
	if(reset_x == 0)begin
		c <= 0;
		carry_r <= 0;
		a_copy1 <= 0;
		a_copy2 <= 0; 
		b_copy1 <= 0; 
		b_copy2 <= 0;
		tmp_l <= 0;
		tmp_h_no_carry <= 0;
		tmp_h_with_carry <= 1;
	end else begin
		a_copy1 <= a; //　コピーを作る
		a_copy2 <= a; 
		b_copy1 <= b; 
		b_copy2 <= b;
		{carry_r, tmp_l} <= a_copy1[63:0] + b_copy1[63:0];
		tmp_h_no_carry <= a_copy1[127:63] + b_copy1[127:63];
		tmp_h_with_carry <= a_copy2[127:63] + b_copy2[127:63] + 1'b1;
		c[63:0] <= tmp_l;
		if(carry_r)begin
			c[128:64] <= tmp_h_with_carry;
		end else begin
			c[128:64] <= tmp_h_no_carry;
		end
	end
end

これでFmax=248.2MHzとずいぶん高速化されました。lpm_add_subで自動生成された回路の方が速いのが残念ですが、FPGAの高速化としては面白いです。