今回フォーカスするのは、シフト演算です。
FPGAボード(Sipeed Lichee Tang Primer)を使って設計したオリジナル16ビットCPUコアMoscovium／オリジナル32ビットCPUコアNihoniumのシフト演算を強化しようと思います。
整数データを2進数の数字列として見た時、左または右に平行移動させるような演算をシフト演算⏪⏩と呼びます。Moscovium／Nihoniumには、論理シフト演算命令と算術シフト演算命令の2種類が実装されています。
論理シフト演算の様子を以下図で説明します。
四角い箱に0〜31の数字が入っている物は、Nihoniumの汎用レジスタ32ビットの内容です。箱の中に「C」の文字があるのは、Nihoniumの状態レジスタsrに存在するキャリCフラグ値です。
青線矢印にある通り、左シフトと右シフトが存在します。論理シフト演算では、シフトしたことによって汎用レジスタの外にはみ出したビットがSrレジスタのCフラグに設定され、外から0のビットが挿入されます。
Nihonium(／Moscovium)では、lsft命令／lsfti命令が相当します。
汎用レジスタRdを32ビット符号無整数値として見た時、Nビット左シフトはRd×2N、Nビット右シフトはRd÷2Nに相当します。左シフト(乗算)によって32ビットを超えたビットは無視、右シフト(除算)によってシフトアウトしたビットは切り捨てとなります。
算術シフト演算の様子を以下図で説明します。
四角い箱に0〜31の数字が入っている物は、Nihoniumの汎用レジスタ32ビットの内容です。箱の中に「C」の文字があるのは、Nihoniumの状態レジスタsrに存在するキャリCフラグ値です。
青線矢印にある通り、左シフトと右シフトが存在します。算術左シフト演算は、前節の論理左シフト演算と全く同じ結果となります。一方、算術右シフトでは、下位ビット側にはみ出したビットがSrレジスタのCフラグに設定されるのは同じですが、上位側に0のビットが挿入される論理シフトと異なり、最上位のビット値がコピーされます。
汎用レジスタ値を2の補数表現による32ビット符号付整数値として見た場合、最上位ビットは符号ビットに相当しており、符号ビットを保存したまま、シフト演算を実行したことになります。
Nihonium(／Moscovium)では、asft命令／asfti命令が相当します。
汎用レジスタRdを32ビット符号付整数値として見た時、Nビット左シフトはRd×2N、Nビット右シフトはRd÷2Nに相当します。左シフト(乗算)によって32ビットを超えたビットは無視、右シフト(除算)によってシフトアウトしたビットは切り捨てとなります。
符号ビットが保存されるため、負数の右シフトも、なんとなく、÷2N倍になっているように見えます(下表)。
| Rd | 右シフト | 演算結果Rd’ | |||
| −8 | 0xffff_fff8 | 2ビット | ÷22＝4 | 0xffff_fffe | −2 |
| −100 | 0xffff_ff9c | 4ビット | ÷24＝16 | 0xffff_fff9 | −7 |
| −1 | 0xffff_ffff | 8ビット | ÷28＝256 | 0xffff_ffff | −1 |
ただし、−1の演算だけは、明らかに正しくないことに注意してください。上表の例では、−1＝0xffff_ffffを8ビット右シフトしていますが、符号ビットが保存されるので、シフト後の値は0xffff_ffff(＝−1)のまま変わりません。
整数値として見た時には、(−1)÷28＝0、となるべき(コンピュータ除算)なので、結果が合わないのです。
※除算結果の小数点以下に着目して、もう少し厳密に考察してみると、二進数のコンピュータ除算が「0方向への丸め」になっているのに対して、算術右シフトは「元の数を超えない最大の整数(floor)」になっていることが解ります。このため、負数の2冪数除算とシフト演算では、演算結果が異なります。
シフト演算は除算に比べて高速に実行可能なので、2冪数で割る代わりにシフト演算を使う方も多いと思いますが、符号付整数の2冪数除算の代わりに算術シフト演算を使う場合には十分注意してください。
※論理(logical)？算術(arithmetical)？： 昔から、この用語で通っているのですが、正直、意味不明です。何が論理的で、何が算術的なのでしょうか？普通に、符号無シフト／符号付シフト等と呼んだ方が、実際の演算を正しく言い表していると思います。
C言語などの高級言語がサポートしているのは、論理シフト演算と算術シフト演算の2種類なので、Moscovium／Nihoniumでも、この2種類だけ実装しました。
typedef short int16; // 32ビットCPUの場合
int16 a=0x8765;
int16 b=(a>>4);
上の例では、b=0xf876となります。変数aが、16ビット符号付整数型(int16)で宣言されているためです。これは算術シフト演算に相当します。
typedef unsigned short int16; // 32ビットCPUの場合
uint16 a=0x8765;
uint16 b=(a>>4);
今度の例では、b=0x0876となります。変数aが、16ビット符号無整数型(uint16)で宣言されているためです。こっちは論理シフト演算に相当します。
少なくともC言語がサポートしているシフト演算は、この2種類だったため、Moscoviumでも2種類だけ実装すれば十分であろうとの判断でした。
C言語などの高級言語でサポートされるのは、論理／算術シフト演算だけですが、アセンブラレベルでは、もう一種類、回転シフト演算と言うシフト演算がサポートされていることが多いです(下図)。
状態レジスタsrのCフラグと、汎用レジスタ32ビット(Moscoviumの場合は16ビット)を連結した合計33ビット(Moscoviumの場合は17ビット)がくるくる回転する様にシフトします。Cフラグを含めた回転シフト演算なので、「C回転シフト演算命令」と呼ぶことにします。他にも、CPUによっていくつかのバリエーションがあります。
今回、Moscovium／Nihoniumへは以下の2命令を追加しようと思っています。
csft命令： rotate shift with C flag
csfti命令： rotate shift with C flag immediate
ユニークなシフト演算ですが、色々と使い道はあると思います。次節では、その内の1つについて解説したいと思います。
Moscoviumは16ビットCPUなので、汎用レジスタは16ビット幅です。この場合、16ビットを超えて、例えば32ビット幅の整数演算はできないのか？と言うと、そうではありません。
// Moscovium： 32ビット整数加算
// (r0：r1)＋＝(r2：R3)
add r1，r3
adc r0，r2
上のコード例は、レジスタペアr0：r1(32ビット)に、レジスタペアr2：r3(32ビット)を加算するコードです。いずれのレジスタペアも、偶数レジスタが上位16ビット、奇数レジスタが下位16ビットとなっているので、まず、下位側の加算を実行します(add命令)。この時、加算によって桁上がりが発生すると、状態レジスタsrのキャリCフラグに1が立ちます。
下位桁からの桁上がり(キャリ)は、上位桁に加算しなくてはならないため、上位桁の加算を実行する時、Cフラグ値を一緒に加算するadc命令を使います。
adc命令(adc Rd，Rs)： Rd＋＝Rs＋Sr[C]
レジスタペアを3個に拡張(r0：r1：r2等)して加算すると48ビットの加算が可能ですし、4個に拡張すると64ビットの加算も実行することができます。
同様に、多倍長整数の減算や比較をするためにsbb命令とcmb命令を持って備えています。
では、多倍長整数のシフト演算は、どのように実行するのでしょうか？従来のMoscoviumだと、シフト演算命令によってシフトアウトしたCフラグ値を判定して分岐する条件分岐命令を使って、以下の様にコーディングする必要がありました。
// Moscovium： 32ビット整数論理左シフト演算
// (r0：r1)<<＝1
lsfti r0，1
lsfti r1，1
bcc pcnt＋2
ori r0，1
左シフトの場合は、上位16ビット側のレジスタr0からシフトを実行します。続いて、下位16ビット側r1をシフトした時、シフトアウトした最上位ビットが状態レジスタsrのキャリCフラグに設定されているので、これを条件分岐命令(bcc命令)で判定して、もし、C＝1だった場合には、r0の最下位ビットに1を立てています。
右シフトの場合、逆に下位ビット側からシフト演算する必要があるのと、上位ビット側のシフト演算後、Cフラグによって下位ビット側レジスタr1の最上位ビットに1を立てなくてはならない点が異なります。
いずれにしても、多倍長整数のシフト演算を実行するためには、4命令以上の組み合わせが必要となることが解ります。
ここで、前節に示したcsfti命令を追加すると、以下の様に簡単になります。
// Moscovium： 32ビット整数論理左シフト演算
// (r0：r1)<<＝1
lsfti r1，1
csfti r0，1
// Moscovium： 32ビット整数論理右シフト演算
// (r0：r1)>>＝1
lsfti r0，−1
csfti r1，−1
符号付シフト(算術シフト)演算を実行したい場合には、上のコードでlsfti命令をasfti命令に挿し換えると実現できます。
この例では、追加したcsft命令が多倍長整数演算実行時のadc命令，sbb命令，cmb命令などの様な役割を果たしていることが解ります。adc命令等もそうなのですが、無ければ無いで、条件分岐命令を使ってコーディングすることは可能です。専用命令を追加したことで、ずっと簡易に多倍長整数演算をコーディングすることができます。
Moscovium／Nihoniumに命令を追加しました。今回追加するのは、csft命令、csfti命令の2個だけですので、命令コードは何とか割り当て可能でした。
CPUのバリエーションには、Moscovium／Nihonium／Nihonium-SS(スーパスケイラ版)と3種類あるため、全てのRTLに変更を加える必要がありました。更に、Nihoniumには16ビットモード(NHビット＝0)と32ビットモード(NHビット＝1)があるので、都合5通りのコーディングと検証が必要となりました。
結構面倒……。
以下リンクより、オリジナルCPUコアを搭載したマイコンのデザインをダウンロードできます。FPGAボード(Sipeed Lichee Tang Primer)への書き込み手順はこちらを参照してください。
CPU自体のデザインが差し替わっていますので、どのマイコンでも拡張した新命令が使えるようになっています。CPUセルフテストプログラム(mcvm_self.asm，niho_self.asm)も、新命令のテストを追加して更新しておきました。
早速、追加したcsft命令を使って見ようと思います。
やはり、多倍長整数のシフト演算に使うのが順当なので、Moscoviumを使って32ビット整数の割り算を実行してみようと思います。
Moscoviumに除算コプロセッサDIVC32を接続すると、divlu命令などを使って、32ビット除算を実行することができます。今回は、同じ32ビット除算をソフトウェアで実装してみます。
※コプロセッサなしでも除算を実行できるようになりますし、作っておいて損はないかと。
32ビット符号無シフト(ステップ)除算ルーチンを作ります。
シフト(ステップ)除算のアルゴリズムについては、「#16-3 除算器の設計」に解説してあります。
Moscoviumの汎用レジスタは16ビット幅ですので、32ビット整数値を表現するためには、2個の汎用レジスタを組み合わせて使う必要があります(←レジスタペア)。ここでは、レジスタペアを「r0：r1」などと記載します。上位16ビット側がr0、下位16ビット側がr1です。
シフト除算ルーチンは、(r0：r1)÷(r2：r3)＝(r0：r1)…(r2：r3)として演算結果を返すこととします。
// ================================
// unsigned 32/32=32...32 bits shift divide routine:
// r0:r1...r2:r3=r0:r1/r2:r3 ; disturbed none
// ================================
divu32:
pushwm r4,r5,r6
ldbiu r4,0
ldbiu r5,0
ldbiu r6,32
sdl_loop:
lsl64 r4,r5,r0,r1
cmpi r4,0
bpl pcnt+6
addl r4,r5,r2,r3
bra pcnt+6
subl r4,r5,r2,r3
ori r1,1
// end of loop
subi r6,1
bne sdl_loop
// remainder
lsl32 r0,r1
cmpi r4,0
bpl pcnt+6
addl r4,r5,r2,r3
bra pcnt+2
ori r1,1
// r4:r5 is Rem
movl r2,r3,r4,r5
sdl_return:
popwm r6,r5,r4
rtn
ルーチン内で使っているマクロの中身などは、完成版プログラム等で確認してください。……肝心なcsfti命令等の新命令は、ユーザマクロlsl64やlsl32の中で使っているので、上のコード中には登場していません（１＾＾；）。
完成プログラム： mcvm_ldt_sft_divu32.asm
上の完成プログラムは、32ビットシフト除算ルーチンと、64個の期待値データが入っていて、作成した除算ルーチンが期待値通りの結果を返すことを確認しています。たった64個の期待値が一致した程度ですので、検証としては不十分です。皆様の責任で検証してお使いください。
実験、と言っても、今回は実機(FPGAボード)は使いません。
新規追加した回転シフト演算命令と、シフト除算ルーチンの動作を確認するだけですので、シミュレーション確認だけで十分だからです。
iverilogを使ったシミュレーションの実行方法などについてはこちらをご確認ください。
Moscoviumを搭載したマイコンなら何でも良いので、久しぶりにMCOC115MN0408を使って見ようと思います。シミュレーション用のパラメータファイル(test.lst)と、テストベンチ(test.v)のデザインをmcoc115mn0408(.v)に変更して、シミュレーションを実行してください。
※Moscovium(／Nihonium)のネットリストだけは、こちらで更新した、回転シフト演算命令対応の最新版に挿し換えておく必要があります。
実験サンプル：【 】内はCygwinシェルウインドウからの実行コマンド
【iverilog -f test.lst ; if ( ! $status ) vvp a.out】
：
VCD info: dumpfile test.vcd opened for output.
06c9 61af 0002 104a
214c bf84 0001 1d40
：
： (中略)
：
3fa9 8e3a 0002 59a5
11be b88e 0003 ab8a
Test Pass
CPI: 31646/ 26328( 0)= 1201/1000
finish: 1267440 ns
シミュレーションがパスしましたので、用意した64個の期待値とは一致が取れたようです。
タイミング図で除算ルーチン1回分の実行時間を計測したところ、Moscoviumで約440サイクル掛かっていました。除算コプロセッサDIVC32を使うと14サイクルですので、だいぶ遅いですね。その分、コプロセッサの論理が不要になって、マイコンを小さくすることができます。より規模の小さいFPGAボードに実装できるなどの利点があります。
