加算器を作ろう　最初の一歩

加算器のFPGA実装について調べた所、奥が深くとても面白い事がわかりました。特にFPGA実装に限ると、キャリー専用配線や、LUT構造により通常の加算器とは少し違った性能になることがあります。加算器をいかに速くできるかについて、いろいろと挑戦してみました。速さの定義はいくつかあるのですが、いかにクロック周波数を上げるかが最優先、次にスループットに注目して加算器を実装しました。

関連リンク
FPGAに特化しない加算器の説明http://ja.wikipedia.org/wiki/加算器
 FPGAの速さについては、以前まとめた事があるのでこちらを、なつたん：デジタル回路の速度と高位合成
息抜き用加算器の動画【計算機】全・半加算器【基礎】

基本回路

まずは素直にVerilogの+を使って128bit加算器を作ってみました。こちらをCycloneで合成してみます。

always @ (posedge clk or negedge reset_x)begin
	if(reset_x == 0)begin
		c <= 0;
	end else begin
		c <= a + b;
	end
end

条件をまとめました

デバイスはCycloneとのみ指定して、後はauto
set_global_assignment -name REMOVE_DUPLICATE_REGISTERS OFFのみ指定。
非同期リセット
レジスタ入力のレジスタ出力
Quartus II Version 8.1
タイミング制約は200MHz create_clock -name {clk} -period 5.000 [get_ports {clk}]。ただし、200MHzを達成したときは、250MHz → 300MHzと50MHz単位で制約を厳しくしていく。

結果はFmax = 187.06 MHzとなりました。この時点で十分速い事に驚きます。普通の回路なら加算器がボトルネックに入ってくることはまずなさそうです。

トップモジュールについて

加算器を呼び出しているトップモジュールも、少し工夫しています。

always @ (posedge clk or negedge reset_x)begin
	if(reset_x == 0)begin
		a <= 0;
		b <= 0;
		sum <= 0;
	end else begin
		t <= ~t;
		sum <= c;
		if(t[0])begin
			a[31:0] <= input_a[31:0];
		end else begin
			b[31:0] <= input_a[31:0];
		end
		if(t[1])begin
			a[63:32] <= input_a[63:32];
		end else begin
			b[63:32] <= input_a[63:32];
		end
		if(t[2])begin
			a[95:33] <= input_a[95:33];
		end else begin
			b[95:33] <= input_a[95:33];
		end
		if(t[3])begin
			a[127:96] <= input_a[127:96];
		end else begin
			b[127:96] <= input_a[127:96];
		end			
	end
end

加算器の入力a,bに対してデマルチプレクサを入れました。入力信号を時分割してa,bに入れています。分割には全く意味が無く、速度の比較をできるだけ正確にするためにデマルチプレクサを入れています。周波数の高いところで回路の速度を評価するには、論理合成だけでなく配置配線まで考慮する必要があります。128bit加算器の入出力をFPGAの空きピンに出すと、それだけでFPGAが無駄に大きくなってしまうのでデマルチプレクサを入れて、ピン数を圧縮しています。

デマルチプレクサの制御には4bitの信号tを使っています。こちらも回路的な意味は全くありません。128bitのデマルチプレクサの切り替え信号を1bitで構成すると、後々クロック周波数を上げたときにデマルチプレクサ自体がボトルネックとなったため、4bit使って32bitずつ信号を切り替えています。1つのFFで128個のLUTをドライブすると、そこの配線容量がボトルネックとなって出てきます。FANOUTの制限を加えれば良いのですが、上手くやらないと加算器自体の合成結果にも影響しそうなので、こういう形にしました。最適化によって4つのFFが1つにされることを防ぐために、REMOVE_DUPLICATE_REGISTERSをOFFにしています。

入力部分にはデマルチプレクサが入り、出力部分にはFFが一段入っています。加算器の出力がレジスタ出力ですが、さらにもう一回FFでたたき直しています。レジスタの入出力をそのままピンに出すと、入出力専用レジスタに割り当てられてしまい、物理的なピン配置がパフォーマンスに影響します。例えば、加算結果の0bit目と128bit目が物理的に距離があるため、配線長が長くなりボトルネックとなるような状況が発生します。それを避ける為に、ただ出力を叩くだけの専用レジスタを作り、その一段でピンの物理的な配置による差を吸収します。

リセットについて

リセットについては以前にまとめたことがあり、今のFPGAでは同期リセットが基本となります。
なつたん：FPGAのリセット回路

教科書的な回路としては、非同期のリセットを2段のFFで同期化して内部のリセット信号として使います。この構成は、Quartus II Handbook Version 8.1 Volume 1: Design and Synthesis Chapter 5: Design Recommendations for Altera Devices and the Quartus II Design Assistantにも記載されています。

Rule ID: R102 External Reset Should Be Synchronized Using Two Cascaded Registers より抜粋。

ところが、Cycloneには同期リセットが存在しないので、同期リセットのまま合成を行うと前段に0とのマルチプレクサが挿入されます。

実際には100本以上ある入力が1本増えたからといって劇的に遅くなるわけではないのですが、加算器そのものの評価に近づけるために今回は非同期リセットとしています。

非同期リセットで合成した結果がこちらです。マルチプレクサが無くなっており、CLR端子にリセット信号が直結されています。

まとめ

何も考えずにVerilogを書くと、Cycloneでは Fmax = 187.06 MHzになります。加算自体を1CLKで行うようにすれば、加算器がボトルネックに入ってくることはまずありません。加算器がボトルネックになる場合は、前後になんらかの処理が入っている場合がほとんどです。入力にマルチプレクサが入っていたり、加算の結果がステートマシーンの遷移の条件になっていると、加算器がボトルネックに入って来ます。

ぱたへね

はてなダイアリーはrustの色分けができないのでこっちに来た

加算器を作ろう　最初の一歩

基本回路

トップモジュールについて

リセットについて

まとめ