オリジナル16ビットCPUコアMoscoviumで、四則演算をしたいのです。しかし、Moscoviumの命令セットでは、加算(add命令)と減算(sub命令)は有るのですが、掛け算と割り算命令は無いのです。
例えば5×3という掛け算は、「5を3回足す」と、求められるので、適切にループを回して加算を繰り返すと、演算できます。ただ、135×316を計算しようとすると、316回(あるいは、135回)ループさせる必要があり、どんだけ計算時間がかかるのよ？ってことですよね？
割り算も同じです。1,023÷94は、1,023から94を引いて行って、引けなくなるまでの回数が商ですから。
もう少し2進数の演算としてスマートに実行するため、これを機にハードウェアで乗除算器を作って、Moscoviumを拡張したいと思います。
最初に挙げた例「5を3回足す」なんて言うのも同じなのですが、小中学校で習った縦積みの掛け算を思い出しながら、それを2進数に適用してみます(下図)。
縦積みの掛け算ですから、説明するまでもないと思いますが、数値は2進数になっています。各々乗数の桁毎に部分積を作って行き、最後に部分積の総和を取ると、一番下の段に2進数で計算した積が現れます。2進数の世界では、数字は0と1しか登場しないので、部分積も被乗数そのもの(上図例では0b1011)か0b0000の、2パタンしか存在しません。
2進数1桁の掛け算は、以下の通り論理AND演算と同じです。
0×0＝0
0×1＝0
1×0＝0
1×1＝1
10進数で言う所の九九は、上の4通りで終了です。
もう、お解りですよね？こうして眺めて見ると、2進数の掛け算は「論理AND演算とシフト演算と加算」に帰着しました。これを使って論理回路を設計して行きます。
ちなみに、Nビット×Nビットの乗算結果(積)は2×Nビットになります。
※log2((2N−1)×(2N−1))＜log2(2N×2N)＝log2(22N)＝2×Nビット
先ほどの縦積み掛け算を1段づつ、ステップを踏むように実行して行くのがステップ乗算器と呼ばれる回路です(下図)。
上図および説明文中、被乗数Mca(Multiplicand)、乗数Mer(Multiplier)、積Prd(Product)という記号を使います。
論理回路で作る場合には、1ステップ→1クロックなので、16×16ビットの掛け算では、結果が出てくるまでに16サイクル掛かります。また、順序回路が必要となるので、論理回路は少々複雑になります。全体を制御するctlブロックは、ステートマシンです。
ハードウェアで設計する時は、上のように1クロック毎に演算が進んでいくため、「ステップ乗算器」と言った方がしっくりくるのですが、同じことをソフトウェアで実行すると、あまり「ステップを踏む」と言う感覚がなくなるので、「シフト乗算」と呼んだ方がしっくりきます。
Moscoviumのシフト乗算ルーチンは、実はLEDキャンドル(mcoc_candle.asm)で使っていました(以下抜粋)。
// ================================
// unsigned 16*16=16 bits shift multiply routine:
// r0=r1*r2 ; disturbed r1,r2
// ================================
mulu16:
ldbiu r0,0
lsfti r2,-1
bcc pcnt+2
add r0,r1
cmpi r2,0
beq pcnt+4
lsfti r1,1
bne mulu16+2
rtn
演算時の数値によって多少ばらつくのですが、一番時間のかかるケース(例えば0x0001×0x8000)で約130サイクルほどかかります。最短(McaまたはMerが0の場合)だと、およそ8サイクルで演算は終了します。乗算のMcaとMerは可換なので、場合によっては予め、Mca≧Merとなる様に調整した方が高速に演算できる可能性が高いのですが、それを判定してレジスタ値を入れ替えたりしている間にオーバヘッドもかさむので、良し悪しです。
まあ、ここでは、「ハードウェアですら16サイクル掛かるけど、ソフトウェアだと絶望的に遅い」と言うことを頭に入れておいてください。
ソフトウェア(最大約130サイクル)に比べて圧倒的に速い、ハードウェアのステップ乗算器(16サイクル)ですが、もっと速い回路が有ります。それは、最初の縦積み乗算を1クロックサイクル内で一気に計算してしまう方式で、フラッシュ乗算器と言います(下図)。
ステップ乗算器とフラッシュ乗算器、どちらにしようかな？ってことですけど、まあ、ここはフラッシュ乗算器で良いでしょう。ステップ乗算器のConsにも書きましたが、順序回路が必要になるので、設計するとなると面倒くさいのですよ……。設計後の動作検証も含め、すごい手間がかかるくせに、1回の乗算に16サイクルもかかって性能は今一つ、これでは報われません。
RTLでフラッシュ乗算器を実装してみると、以下の様になります。
module mul4u (
ina,
inb,
out);
input [3:0] ina;
input [3:0] inb;
output [7:0] out;
// partial multiply
wire [7:0] pm0={ 4'h0,ina[3:0] }&{8{ inb[0] }};
wire [7:0] pm1={ 3'h0,ina[3:0],1'h0 }&{8{ inb[1] }};
wire [7:0] pm2={ 2'h0,ina[3:0],2'h0 }&{8{ inb[2] }};
wire [7:0] pm3={ 1'h0,ina[3:0],3'h0 }&{8{ inb[3] }};
// add all
assign out[7:0]=pm0[7:0] + pm1[7:0] + pm2[7:0] + pm3[7:0];
endmodule
※論理合成ツールによっては、演算子"*"を使うと乗算器を推定して展開してくれる場合があるかもしれません。その場合は、「assign out[7:0]＝ina[3:0]*inb[3:0];」で、終了です。TD IDEの論理合成ツールは、ちゃんと乗算器を推定しました。
上のコードはイメージです。検証は一切していませんのでご注意ください。4ビット符号無フラッシュ乗算器となっていて、4個の部分積(pm0〜pm3)を計算して、全てを加算すると完了です。この記述だと、普通に3個の8ビット加算器が生成され、論理規模や信号の伝搬速度は論理合成ツールに「お任せ」となり、結構大きくて遅い回路が生成されると思います。
実用的には、このコードを16ビットなどに拡張して、加算部分にWallace Treeを適用することになるはずです。
ですが、今回は作りません＼（１＾＾；）／。だって、TD IDEが乗算器マクロを持っているのですもの(↓)。
TD IDEの「Toolsメニュー ⇒ IP Generator」から、DSP(Digital Signal Processor)マクロを選択すると、上図のような画面となります。DSPだなんて大そうな名前ですが、ただのフラッシュ乗算器です。符号付／無とビット数が選択可能なので、上図の様に設定してください。
1個のDSPマクロで16ビット符号付／無乗算に対応させるので、17ビット幅で生成しています。入力データ16ビットに対して17ビット目は、符号付の場合には符号拡張、符号無の場合にはゼロ拡張してDSPマクロに接続します。
出力34ビットですが、入力が16ビットなら下位32ビットだけを使い、上位2ビットは無視して良いです。
なお、TD IDE(と言うより、FPGAチップEG4S20BG256)には、29個の18ビットDSPマクロ(ハードマクロ)が集積されているので、上図の様なDSPマクロを29個まで使用することが出来ます。
前節で生成したDSPマクロをMoscoviumに組み込んで、乗算命令を追加しようと思います。
追加する乗算命令
Moscoviumの構成上、何らかの数値演算を行うユニットは、ALUに追加するのが順当です(下図)。
ただ、ALUに演算機能を追加して行くと、折角シンプルに創り込んだMoscoviumが肥大化して行きます。乗算命令が不要な用途ではDSPマクロを切り離して、小規模なCPUコアとして使える方が良いでしょう。そもそも今回のタイトルを思い出していただくと、「四則演算」が最終目標なので、この後、除算器も追加することになります。
そこで、乗算器と除算器はコプロセッサとしてCPUとは分離し、使用者が自由に付け外しできるようにしたいと思います(下図)。
| ccmd[4:0] | コード | 内容 |
| MULU | 5'h01 | unsigned multiply：C＝Prd[15:0]，Prd＝A*B |
| MULS | 5'h02 | signed multiply：C＝Prd[15:0]，Prd＝A*B |
| MULH | 5'h03 | load high word：C＝Prd[31:16] |
| SDEN | 5'h04 | store dividend：C＝16'h0，Den=(A<<16) + B |
| SDSO | 5'h05 | store divisor：C＝16'h0，Dso=(A<<16) + B |
| SQUO | 5'h06 | store quotient：C＝16'h0，Quo=(A<<16) + B |
| SREM | 5'h07 | store reminder：C＝16'h0，Rem=(A<<16) + B |
| DIVU | 5'h08 | unsigned divide (32 bits)：C＝16'h0，Quo…Rem＝Den/Dso |
| DIVS | 5'h09 | signed divide (32 bits)：C＝16'h0，Quo…Rem＝Den/Dso |
| QUOH | 5'h0a | load quotient high word：C＝Quo[31:16] |
| QUOL | 5'h0b | load quotient low word：C＝Quo[15:0] |
| REMH | 5'h0c | load reminder high word：C＝Rem[31:16] |
| REML | 5'h0d | load reminder low word：C＝Rem[15:0] |
| DVWU | 5'h0e | unsigned divide (16 bits)：C＝16'h0，Quo…Rem＝A/B |
| DVWS | 5'h0f | signed divide (16 bits)：C＝16'h0，Quo…Rem＝A/B |
※コプロセッサの内部レジスタPrd，Den，Dso，Quo，Remは、全て32ビットレジスタです。
AバスとBバスがコプロセッサへの演算データ出力、Cバスがコプロセッサからの演算結果入力となりますが、全て16ビットのバスなので、例えば、16×16＝32ビットの乗算結果は、一度に転送することが出来ず、乗算コマンド(MULU，MULS)では、Cバスに積Prdの下位16ビットだけが出力されます。
積Prdの上位16ビットが必要な場合は、乗算コマンド実行後、次のサイクルでMULHコマンドを実行することで取得します。
即ち、DSPマクロとしては1サイクルで16×16＝32ビットの乗算を終了しますが、Moscoviumが全32ビットのデータを取得するためには2サイクルを要します。……16ビットCPUなので仕方ないですね……。
C言語などと同様16×16＝16ビット乗算で十分な場合には、状態レジスタsrに追加するMLビットの設定で、1サイクル実行が可能としておきます。
最終的にはTD IDEが用意したDSPマクロを使ってしまったので、前半の乗算アルゴリズムの解説は意味がなかったわけですが、ちゃんと基本アルゴリズムを理解しておくと、色々と応用が利く場合があるので覚えておいてください。
例えば、定数の乗算です。
ここで、定数10との掛け算「10×r0」が必要となります。乗算命令が使えるなら、それを使うのが速いです(きっと)。でも、乗算命令が無いCPUでは、シフト乗算ルーチンをコールすることになります。その時、以下のコードと見比べてみてください。
mov r3,r0
lsfti r3,3
add r0,r0
add r0,r3
上のコードは、r0を×10倍するコードです。4命令4サイクル実行ですので、多分、シフト乗算ルーチンをコールするよりは速いはずです。被乗数が10＝0b1010という定数になったことで、シフト乗算の加算値が確定するので、上コードの様にシフト演算命令と加算命令だけで実装することが出来るのです。
※簡易版atoi()関数相当のサブルーチンは、LEDキャンドルプログラム(mcoc_candle.asm)で使用していますので、全体像はそちらで確認してください。
尚、今回追加する乗算命令を使うと、
ldbiu r3,10
mulu r0,r3
と、2命令2〜3[サイクル]実行ですので、定数乗算であっても性能の向上が期待できます。
32ビットCPU等のC言語でint型に慣れてしまうと、16ビット幅の演算では不足するケースがあります。そのようなケースでも、16×16＝32ビット乗算命令が有れば、比較的容易に32ビット乗算を実現することが出来ます(以下コード)。
// ================================
// unsigned 32*32=32 bits multiply routine:
// r0:r1=r0:r1*r2:r3 ; disturbed r2,r3,Sr[ML]
// ================================
# r0:r1
# r2:r3
# *)-------
# r3:r1 : 3) ML=1
# r3:r0 : 1) ML=0
# r1:r2 : 2) ML=0
# r0:r2 : not calculate
# +)-----------
# r0:r1 : 4)
# ================================
mulu32:
clsr sreg_b_ml // ML=0
mulu r0,r3 // 1)
mulu r2,r1 // 2)
sesr sreg_b_ml // ML=1
mulu r1,r3 // 3)
add r0,r2 // 4)
add r0,r3
rtn
ご説明してきた様に、32×32ビットの積は64ビット幅となります。16×16ビットの時と同様に、C言語などの実装に倣って32×32＝32ビット乗算で十分な場合は、上コードとなります。7命令8サイクル実行＋サブルーチン分岐(jal命令＋rtn命令)です。
全64ビットの乗算が必要な場合、「not calculate」となっている乗算と、「ML＝0」とした乗算を全てML＝1で乗算し、全ての部分積をキャリを含めて加算する必要があります。
次回、引き続き除算器の設計を進め、Moscoviumに四則演算命令➕➖✖➗を揃えたいと思っています。
