暗号計算機屋のブログ

なにか思いついたことを不定期に更新。

仮想マシンの加速支援機構つきの新型8bit CPU!?

概要

新型の8bit CPU(ICF3-Z)を設計してFPGAに実装。まだ動作検証中ですが、仮想マシンの加速支援機構を使った、簡単なスタックマシンで、サンプルプログラムがXilinx FPGA Artix-7(-1)の実機上で動作した。たった400LUT強の小さいCPUで。Intel 8051マイコンのFREEな実装にlight52があります。軽量なマイコンですがCPU部だけで約800LUTあるようです。light52は1命令、6サイクルですが、このICF3-Zは1命令、1サイクルが基本で、時に1サイクルに複数命令の実行ができます。周波数比較もICF3-Zが、おおよそ2倍のようで、圧倒的に勝ったのかも。他にあまり比較できるものがなかったという話もありますが。 ただ、まだ動作検証中であることに注意してください!

仮想マシンの加速支援機構とは

新型8bit CPU(ICF3-Z)なのですが命令コードが32bitで、一般的な8bit CPUと比べてメモリ効率が悪い。そこで16bitの圧縮命令の機能を追加した。この機能が仮想マシンの加速支援機構なのです。 圧縮命令のために作られたもので、加速支援機構として、最終的に成立するのかは、わからないですが、需要があって無理がなければ、加速支援機構として考えていく方向です。

加速支援機構が何の役に立つのか?

超低スペックなCPUでは、ソフトウエアで仮想マシンを実装しても性能的な問題で用途が狭められることがあります。この加速支援機構があれば実用の範囲が広がります。

なぜ低スペックなCPUで仮想マシンなのか?

仮想マシンJavaのようなスタックマシンにしたり、レジスタ1個のマシンにしたりできます。 CPUのアーキテクチャの違いを吸収して、いろいろな言語のコンパイラの開発を容易にします。 非C言語が利用できるようになることで、より多くの人がIoTデバイスなどを開発できるようになります。

試作プログラム

プログラムの上部で簡単なスタックマシンの命令を実装して、仮想マシンの命令列をFPGAの実機で動作させたものです。独自のアセンブラなので多少、わかりにくかもしれません。自作したアセンブラでバイナリを生成して、FPGAのプログラムメモリに、置きます。 即値の5をPUSH、メモリの0番の値をPUSH、メモリの1番の値をPUSH、乗算、加算、LEDに結果を出力。 メモリ0番には、最初のところで2を書き込んでいます。メモリ1番には3。つまり3*2+5 = 11がLEDに出力されます。(確認しました)

########################################################
# vm (Virtual Machie)
#
# C Register : SP(Stack Pointer)
# D Register : PRINT (LED x 8)
# MEM[0-255] : Memory
#
# PUSHI: SP=SP-1 , MEM[SP]=nn                     (5cyc)
# PUSHR: SP=SP-1 , MEM[SP]=MEM[nn]                (5cyc)
# POP  : MEM[nn]=MEM[SP] , SP=SP+1                (4cyc)
# ADD  : MEM[SP+1]=MEM[SP]+MEM[SP+1] , SP=SP+1    (7cyc)
# MUL  : MEM[SP+1]=MEM[SP]*MEM[SP+1] , SP=SP+1    (16cyc)
# PRINT: PRINT MEM[SP]      
########################################################
# Initial MEM[0]=0x02 , MEM[1]=0x03
########################################################
    ADDL=N;N=0x02;A=ANS
    STORE;Z=0
    ADDL=N;N=0x03;A=ANS
    B(START)
    STORE;Z=1;C=ANS;D=ANS
########################################################
%NOP:
    JRETURN
%PUSHI:
    ADDR=C;ADDL=N;N=0xFF;C=ANS
    RETURN;COPR;ADDL=N;A=ANS
    ADDR=C;R(ADDR);STORE
%PUSHR:
    ADDR=C;ADDL=N;N=0xFF;C=ANS
    RETURN;R(N);COPR
    MOV;ADDR=C;R(ADDR);STORE
%POP:
    RETURN;R(ADDR);ADDR=C;ONE;C=ANS
    MOV;COPR;R(N);STORE
%ADD:
    R(ADDR);ADDR=C;ONE;C=ANS
    B=REG;R(ADDR);ADDR=C
    B=REG;ADDR=B;A=ANS
    RETURN;ADDL=A;ADDR=B;A=ANS
    R(ADDR);ADDR=C;STORE
%MUL:
    R(ADDR);ADDR=C;ONE;C=ANS;D=ANS
    C=REG;R(ADDR);ADDR=C
    C=REG;ADDR=C;A=ANS
    B=ANS;I=X;X=7
    MUL;ADDL=A;ADDR=B;B=RSH;C=RSH;WAIT
    RETURN;ADDR=C;A=ANS
    R(ADDR);ADDR=D;STORE;C=ANS
%PRINT:
    RETURN;R(ADDR);ADDR=C
    D=REG
START:
    _%PUSHI,0x05,%PUSHR,0x00
    _%PUSHR,0x01,%MUL,0x00
    _%ADD,0x00,%PRINT,0x00
    EXIT(0);@D
END:
    B(END)
    NOP

ちなみに

割込みの実装もついていて400LUT強です。2つの割込みを受けられます。1サイクル毎に割込むことができるはずなのですが、まだ十分に動作検証できていません。2、3のテストを実機で確認したところです。

講演会に参加しました「IEEE Computer Society 2018会長を経験して」

2018年12月8日(土) 早稲田大学 グリーン・コンピューティング・システム研究開発センターで昨年からIEEEの会長をされている笠原先生の講演会「IEEE Computer Society 2018会長を経験して」に参加しました。 正しくは成田/笠原/木村研究室のOB会で身内だけで開催されました。僕は笠原研のOBで第一期生なのです。定義にもよりますが僕より上の学年は成田研から笠原研に異動しているので僕の学年が第一期かと。 IEEEは、とても有名な学会と思っていましたが、北米から初めて日本に、そして次期会長は、イタリアの方になるようです。ますます有名になっていくように思いました。 会長の仕事には、選挙結果の不平の仲裁みたいなものがあるとか、いろいろあったように思いますが、早稲田の今後の展開についてなどの話があって、あれと思ったら笠原先生からいただいた名刺に「副総長」とあり、なるほどと。早稲田の国際的な、さらなる知名度向上に向けての力強い話が良かったように思いました。

久々に研究室時代の人と話すのですが、僕の同期はOB会に来ないことが多く、1年下も来てませんでした。 2年下が1人来ていたので話せて、インターネットのシステムに詳しいようでした。 研究室時代の研究上の先輩にRFCとか論文とか書いている人がいてDNSに詳しくSSLアクセラレータの話をしても「ECDSAだよね」とか。^^; 楽しい1日でした。

モンゴメリ乗算の累積加算における分割加算の証明

はじめに

今年の4月にFPGAをはじめたときにFPGADSP(乗算器)が多数あることを知った。 これでモンゴメリ乗算が高速化できるわけだがアルゴリズムをそのまま実装するとビット長の大きな累積加算が、ビット長とともに周波数が下がり性能がでない。 そこで分割して加算しても、正しい加算結果になるような方法を考えた。これを使ったSSLアクセラレータ ICF3-F(商用版)の実装を急いでいるところだが、証明もしておかないと、いけないかと思って、急いで公開することにしました。産業スパイによる海賊版を抑止する目的です。ちなみに他にも応用ができる方法ではないかと思います。 この証明にコメントしたい方が、いらしゃるのかわかりませんが、もしあれば公開日(2018年9月26日)の2日後、28日の午後12時からでお願いします。とりあえず、その記録は残すようにします。

問題

非負の整数の変数Aを2進数表現すると、最下位ビットからrビットづつ区切ってs個のブロックに分割して表現できる。


\displaystyle A = \sum_{k = 0}^{s-1} a_k \cdot 2^{r k}

 a_k がrビットの場合はAはr×sビットの数を表現可能だが、 a_kが(r+1)ビットあってもr×sビットの数を表現できる。 最上位ビットを e_k、それ以外を f_kとすると a_k = e_k \cdot 2^r + f_kになるが

 \displaystyle A = \sum_{k = 0}^{s-1} e_k \cdot 2^{r (k+1)}  +  \sum_{k = 0}^{s-1} f_k \cdot 2^{r k}

として全加算してやればAは冗長性がなくなりr×s+2個のビットの数になる。 このような冗長性をもったAを考える。

 A = (A + t \cdot B + u \cdot C ) \div 2^{n} --- (1)

 r \geqq n + 2 --- (2)

t,uはnビットの数。B、Cはr×s-2ビットの数。  \displaystyle B = \sum_{k = 0}^{s-1} b_k \cdot 2^{r k} \displaystyle C = \sum_{k = 0}^{s-1} c_k \cdot 2^{r k}と表す。

式(1)の右辺を計算した結果、任意のA、B、C、t、uにおいて、 同じ冗長性、すなわち a_kが(r+1)ビットある左辺Aに正しく格納できることを証明せよ。

証明

式(1)右辺のカッコ内は

 A + t \cdot B + u \cdot C

 \displaystyle = \sum_{k = 0}^{s-1} a_k \cdot 2^{r k} + t \times \sum_{k = 0}^{s-1} b_k \cdot 2^{r k} + u \times \sum_{k = 0}^{s-1} c_k \cdot 2^{r k}

 \displaystyle = \sum_{k = 0}^{s-1} a_k \cdot 2^{r k} + \sum_{k = 0}^{s-1} t \cdot b_k \cdot 2^{r k} + \sum_{k = 0}^{s-1} u \cdot c_k \cdot 2^{r k}

 \displaystyle = \sum_{k = 0}^{s-1} ( a_k \cdot 2^{r k} + t \cdot b_k \cdot 2^{r k} + u \cdot c_k \cdot 2^{r k} )

 \displaystyle = \sum_{k = 0}^{s-1} ( a_k + t \cdot b_k + u \cdot c_k ) \cdot 2^{r k}

ここで p_k = a_k + t \cdot b_k + u \cdot c_kとする。t,uがnビットであるから p_kは最大でもr+n+2ビット。  p_kの最上位ビットから2bitを px_k、最上位ビットから2ビット、最下位ビットからnビットを除いたrビットを py_k、 最下位ビットからnビットを pz_kとする。

 p_k = px_k \cdot 2^{r+n} + py_k \cdot 2^{n} + pz_k  (0 \leqq k \leqq s-1) --- (3)

(1)の右辺は

 \displaystyle \sum_{k = 0}^{s-1} p_k  \cdot 2^{r k} \div 2^{n}

(3)より

 \displaystyle = \sum_{k = 0}^{s-1} ( px_k \cdot 2^{r+n} + py_k \cdot 2^{n} + pz_k )  \cdot 2^{r k} \div 2^{n}

k=0の項をシグマの外に出して整数にすると

 \displaystyle = px_0 \cdot 2^{r} + py_0 +  \sum_{k = 1}^{s-1}  ( px_k \cdot 2^{r+n} + py_k \cdot 2^{n} + pz_k )  \cdot 2^{r k} \div 2^{n}

 \displaystyle = px_0 \cdot 2^{r} + py_0 +  \sum_{k = 1}^{s-1}  ( px_k \cdot 2^{r} + py_k )  \cdot 2^{r k}  +  \sum_{k = 1}^{s-1}  pz_k  \cdot 2^{r k - n}

 \displaystyle = px_0 \cdot 2^{r} + py_0 +  \sum_{k = 1}^{s-1}  ( px_k \cdot 2^{r} + py_k )  \cdot 2^{r k}  +  \sum_{k = 1}^{s-1}  pz_k  \cdot 2^{r(k-1) + r-n}

 \displaystyle = py_0 +  pz_1 \cdot 2^{r-n} + \sum_{k = 1}^{s-2}  ( px_{k-1} + py_k + pz_{k+1} \cdot 2^{r-n}  )  \cdot 2^{r k} + ( px_{s-2} + py_{s-1} )  \cdot 2^{r (s-1)} + px_{s-1} \cdot 2^{r s}

ただしB、Cがr+n-2ビットなので必ず px_{s-1} =0

 \displaystyle = py_0 +  pz_1 \cdot 2^{r-n} + \sum_{k = 1}^{s-2}  ( px_{k-1} + py_k + pz_{k+1} \cdot 2^{r-n}  )  \cdot 2^{r k} + ( px_{s-2} + py_{s-1} )  \cdot 2^{r (s-1)}

ここで式(2)の条件からr-nは2以上。  w_k = px_{k-1} + pz_{k+1} \cdot 2^{r-n} (1 \leqq k \leqq s-2)とすると w_kはrビットの記憶素子を持つ1つの変数としてまとめられる。

 \displaystyle = py_0 +  pz_1 \cdot 2^{r-n} + \sum_{k = 1}^{s-2}  ( py_k + w_k  )  \cdot 2^{r k} + ( px_{s-2} + py_{s-1} )  \cdot 2^{r (s-1)}

これは(1)左辺のAとして次にようになる。

 \displaystyle A = \sum_{k = 0}^{s-1} a_k \cdot 2^{r k}

 a_k =
\left\{
\begin{array}{}
 py_0 +  pz_1 \cdot 2^{r-n} ( k = 0) \\
 py_k + w_k  ( 1 \leqq k \leqq  s-2 ) \\
 ( px_{s-2} + py_{s-1} )  ( k = s - 1)
\end{array}
\right.

 py_k w_kともにrビットの数なので加算してもr+1ビットの数である。k=0、k=s-1も同様にr+1ビット。 式(1)の右辺を計算した結果、同じ冗長性、すなわち a_kが(r+1)ビットある左辺Aに正しく格納できる。

補足

実際の実装では最後に、全加算を行って冗長性をなくしてr×sビットのレジスタに格納します。 このとき桁あふれが発生する可能性がありますが、一般のCPUのレジスタと同じで桁あふれはアルゴリズム側の責任。 モンゴメリ乗算では最終的な計算結果はCの2倍以下になるので全加算後、r×sビットのレジスタに必ず格納できます。 計算過程においても、上記証明によって、桁あふれすることなく計算できていることがわかります。 この問題では積和の数が2個の場合ですがn個にした証明など一般化できるように思います。いづれまた。

FPGAで加算器を共有して面積を小さくする

このページで説明する加算器を共有して面積を小さくするテクニックは勝手に使っていいのかという質問がありました。 勝手に使っていただいて大丈夫です。

はじめに

XilinxFPGA(Artix-7)でDSPを使用せずにLUTで加算器を作る場合、加算器の入力を構成するLUTに余裕があり、共有するためのセレクタを詰め込んでも面積は増えない。 そのテクニックが、現在、開発中のICF3-Fの制御部で使うことができそうで、効果がありそう。

論理合成ツール

XilinxのVivado 2018.2です。評価ボード Artyの(Artix-7 XC7A35T-L1CSG324I)の設定で合成しています。 合成オプションは、面積、最優先(Flow_AreaOptimaized_high)です。

対象となる論理

ICF3-Fは商用だがブロック図(2018年9月11日追加)を公開していいる。 図の左側にループ制御用の16bitレジスタI,Jがある。その部分の論理について加算器を共有させて面積を小さくする。 レジスタI,Jは即値(n)を代入すること、分岐命令(BI命令、BJ命令)のときには値を-1にする論理です。 BI命令とBJ命令は同時に来ることはないので-1をする加算器の共用化が可能です。

対象となるverilogコード

module subij(
    input CLK,
    input CEI,
    input CEJ,
    input BI,
    input BJ,
    input [15:0] n,
    output INOR,
    output JNOR);

    always @(posedge CLK) begin
        I<= BI ? I-1 : CEI ? n : I;
        J<= BJ ? J-1 : CEJ ? n : J;
    end

    assign INOR = ~|I;
    assign JNOR = ~|J;

Iレジスタにnを代入するにはCEIを1にします。分岐命令のBI命令の場合はCEIとBIが1になります。Jレジスタも同様。 このコードでは、論理合成ツールはBIとBJが同時にくる可能性のために加算器を共用できません。 少しコードを変更して加算器が共用できるコードに変更します。

module subij(
    input CLK,
    input CEI,
    input CEJ,
    input BI,
    input BJ,
    input [15:0] n,
    output INOR,
    output JNOR);

    always @(posedge CLK) begin
        I<= CEI ? (BI ? I-1 : n) : I;
        J<= CEJ ? (BI ? n : J-1) : J;
    end

    assign INOR = ~|I;
    assign JNOR = ~|J;

これ以外のコードも試しましたが、シミュレーションすると誤った結果となってしまいました。

論理合成ツールによる結果

38LUT 32FFで約10スライスの面積。加算器の共有ができていません。 f:id:icf:20180919033431p:plain

人間による結果

22LUT 32FFで8スライスの面積。まだLUTが8スライス内に入りそうです。 加算器を共有する論理をLUT,CARRY4,FFで作りスライスの場所を固定しました。固定したものはオレンジ色になるようです。 f:id:icf:20180919033804p:plain

まとめ

実際のケースで加算器を共有する方法をやってみました。 加算器を共有化を確実にするにはLUT、CARRY4、FFをスライスに固定するなど少々、手間がかかりますが面積を小さくすることはできるようです。 これ、ICF3-Fの1032bitの大型加算器でも使えるので、かなり効果があるかも。

Xilinxの論理合成ツールと勝負してみた

はじめに

論理合成ツールは、これまでほとんど使ったことがなく、論理合成ツールの性能がどのくらいなのか、ちょっとだけ試してみた。 もちろん人間が作った論理と比較して、人間が勝ったから、ブログに投稿しているわけで、この初戦の結果だけで判断しないようにお願いします。

論理合成ツール

XilinxのVivado 2018.2です。評価ボード Artyの(Artix-7 XC7A35T-L1CSG324I)の設定で合成しています。 合成オプションは、面積、最優先(Flow_AreaOptimaized_high)です。

論理合成対象

次のverilogのコード。使用するリソース、面積が最小となるように論理を作ります。

module s2add(
    input SW,
    input [3:0] A,
    input [3:0] B,
    input [3:0] C,
    input [3:0] D,
    output [3:0] O);
    assign O = SW ? A+B : C+D ; 
endmodule

論理合成ツールの結果

7 LUTです。面積的にはスライス2個分といったところでしょうか。 f:id:icf:20180915051140p:plain

人間の結果

4 LUTです。面積的にスライス 1個に収まっています。(シミュレーションで正しい答えになることは確認しています) f:id:icf:20180915051255p:plain

まとめ

論理合成ツールに人間が勝ちました。ちょっと試してみただけの結果なので、これだけで判断しないようにお願いします。

追記

4bitの加算では人間が勝ちましたが8bitにすると論理合成ツールも人間と同じ結果を生成しました。

追記2

現在、開発中のICF3-Fはループ制御用に2本の16bitレジスタがあります。 同時にデクリメントすることはないので、この論理合成対象のように加算器を共有できます。 しかしならが共有できるようなverilogの記述をしても、うまく共有されず、論理合成ツールのほうが大きな面積となりました。 人間だと8スライスに収まりますが、論理合成ツールでは10スライスくらいになります。 verilogの記述を操作して共有できるようなコードを探すとなると、時間がかかるし、論理を追加していくうちに、再び共有されなくなる心配も考えるなら人間がやってしまったほうがいいように思いました。 人間がやるためにはLUTのデータを自分で作成する必要がありますが、FORTHライクな言語を自作しました。様々なLUTデータを簡単に作れます。

結局、最初の結論の通り、「論理合成対象のコードは、良くあるケースのように思うので、この結果は使えるのではと思います。」であります。

 追記3

追記2の話を詳しくブログにしました。「FPGAで加算器を共有して面積を小さくする」