2018-12-09

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

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

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

2018-09-26

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

はじめに

今年の4月にFPGAをはじめたときにFPGAにDSP(乗算器)が多数あることを知った。これでモンゴメリ乗算が高速化できるわけだがアルゴリズムをそのまま実装するとビット長の大きな累積加算が、ビット長とともに周波数が下がり性能がでない。そこで分割して加算しても、正しい加算結果になるような方法を考えた。これを使ったSSL アクセラレータ ICF3-F(商用版)の実装を急いでいるところだが、証明もしておかないと、いけないかと思って、急いで公開することにしました。産業スパイによる海賊版を抑止する目的です。ちなみに他にも応用ができる方法ではないかと思います。この証明にコメントしたい方が、いらしゃるのかわかりませんが、もしあれば公開日(2018年9月26日)の２日後、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ビットのレジスタに必ず格納できます。計算過程においても、上記証明によって、桁あふれすることなく計算できていることがわかります。この問題では積和の数が２個の場合ですがn個にした証明など一般化できるように思います。いづれまた。

2018-09-19

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

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

はじめに

XilinxのFPGA(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の大型加算器でも使えるので、かなり効果があるかも。

2018-09-15

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です。面積的にはスライス２個分といったところでしょうか。 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

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

2018-09-11

論理設計はどうやって学んだのか？

はじめに

僕の経歴を見ると早稲田の電気工学科を1992年3月に卒業し、同大学の大学院の計算機工学科を1994年3月に修士を卒業。日立の中央研究所の超高速プロセッサ部に1994年4月に入社と、CPUとか暗号プロセッサとかを開発するのに最適な経歴です。ところが奇跡的に論理設計を教えてもらえることが、全くなかったという話です。普段は、この経歴、便利だったりもするのですが、不都合なこともあるので、本当の話をすることにしました。興味がない人は、読まないほうがいい内容です。

子供の頃

中学、高校と大阪に住んでいました。小学校５年のときにはCASIOのプログラム電卓 FX-502Pで良く遊んでましたが、中学１年生ときはナイコン族でした。パソコンを持っていなかった。雑誌には紙に印刷されたキーボードの付録があって、それで練習するという時代。中学２年生のときにSHARP MZ-2000を買ってもらった。 CPUはZ80でしたがBASICでプログラムを書いても、とても遅くマシン語に興味を持ったのです。なんとか高速化できないかOSを調べてBREAKキーをポーリングしているサブルーチンを発見し、そこに1バイトのC9 ( RETURN )をパッチしてみた。1分かかった計算が、58秒になったことが、うれしかった。その後、WICSという整数型BASICコンパイラを買ってもらった。うちが計算機の英才教育していたのかというと、家族は、むしろ文系なみにコンピュータを知らない。中学２年生の普通の子供は、みなゲームに夢中だったが、科学にとても興味を持った変わった子供だったと思う。

大阪の日本橋は東京の秋葉原みたいな電気街なのだが、当時の僕は、デジットというジャンクパーツ屋が気に入ったようで、行ってみて、できそこないの150円のジョイスティックとか買って帰ることが多かった。古いテレビとかを分解した部品が売られていて、トグル式のスイッチを買って帰ったことがあった。それには目的があって加算器を作ることだった。スイッチは１ボタンで混線しないスイッチが多数あるので配線のみの加算器を作ることができた。すでにゲートディレイゼロの超高速加算器を発明していたのだ。(爆笑)

大学時代

パソコンを自分で作ってみたいという思いから電気工学科に入った。サークルはコンピュータサークルには入らないように親に言われていたので、鳥人間コンテストとかやっているサークルに入った。１年の頃は、ファインマンの電磁気学の本を読んでまじめに勉強した。夏休みに大阪に帰省したときに、自宅が大阪大学に近かったのでファインマンの光、熱、波動の本を買いにいったら、早稲田の大学生協のカードを見せても１割引きしてもらえなかった。当時の電気工学科で論理設計を教えてもらえる先生は１人で門倉先生でした。しかし門倉先生の授業は、ほとんどサボりました。なぜか？鳥人間コンテストの人力飛行機のプロペラ作りを、ほぼ１人でやっていて、全く余裕がなかった。門倉先生の授業は論理回路の授業というよりは歴史的なマシンLGP-30の説明で、あんまり役に立ちそうにないと思ったのは、そうですが、それよりもプロペラ作りが忙しく、役に立つとか、考える前に、サボるしかなかった。

研究室時代(大学院)

現在、IEEEの会長で超有名な笠原先生の研究室に入りました。コンピュータのハードウェアの研究室に入りたかったのだが、門倉先生は引退してしまって、コンパイラの研究室に入ったのです。わかりやすくいうとソフトウェアの研究室だった。つまり論理設計のカケラもないところでした。

日立中央研究所超高速プロセッサ部

CPUを研究する部署でしたが、僕が入った次の年には、名前が変わって別の部署になってます。日立の大型コンピュータのCPUのパイプラインのシミュレーションをする仕事をしましたが、中の論理をのぞかせてもらったわけではありません。 CISCの転送命令が、ちゃんと性能が出ているかを確認する仕事で、東京女子大卒のおねーさんと２人で、さびしくやってました。おねーさんのほうは基本命令の性能確認だったと思います。

日立メインフレーム開発部時代

東大卒の人がいっぱいの部署でしたが、僕は仲間に入れてもらえず、壁すらない隣の部屋で大型コンピュータのCPUを開発していたようですが、僕だけ隔離された環境で仕事してました。ちなみに隣の部屋のCPU開発部には、笠原研の同期がいたのです。卒業後、その同期と話しをしたことはないですから、この会社の隔離システムが、いかにすごいか、わかるのではないでしょうか。話すことはいっぱいあるのですが、ここでは全部省略して、要するに、全然、ここまで論理設計を勉強したことはなかった。

ところが、このことは会社の経営者にとっては好都合で、僕にいきなり暗号LSIを設計するように業務命令が出た。僕が開発すれば社内外の左に払う必要がないし、僕が潰れてもおいしいのだ。

そして僕に才能があったおかげで、システム開発研究所からFAXで送られてきたモンゴメリ乗算のアルゴリズムを元に、いきなり開発して世界一の性能の暗号LSIを開発してしまった。論理設計は、ANDとかORとか、すごく単純なものの組み合わせだけなので回路図を読むだけなら、ほとんど勉強しなくても読める。勘がいい人間なら、いきなりできることもある。

いいたかったこと

オープンソースハードウェアとして1999年世界一だった暗号LSIの論理図面を公開していますが、僕に先生は、いなくて、僕１人で設計している。僕１人で公開できるのは、そういうことだからなのです。

暗号計算機屋のブログ

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

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

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

はじめに

問題

証明

補足

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

はじめに

論理合成ツール

対象となる論理

対象となるverilogコード

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

人間による結果

まとめ

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

はじめに

論理合成ツール

論理合成対象

論理合成ツールの結果

人間の結果

まとめ

追記

追記2

追記3

論理設計はどうやって学んだのか？

はじめに

子供の頃

大学時代

研究室時代(大学院)

日立中央研究所超高速プロセッサ部

日立メインフレーム開発部時代

いいたかったこと

はじめに

問題

証明

補足

はじめに

論理合成ツール

対象となる論理

対象となるverilogコード

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

人間による結果

まとめ

はじめに

論理合成ツール

論理合成対象

論理合成ツールの結果

人間の結果

まとめ

追記

追記2

追記3

はじめに

子供の頃

大学時代

研究室時代(大学院)

日立 中央研究所 超高速プロセッサ部

日立メインフレーム開発部時代

いいたかったこと

　追記3

日立中央研究所超高速プロセッサ部