IT業界で数学の才能が何の役に立つか

取り合えず僕に数学の特技があると思って聞いてもらえるといいと思います。😉

1999年の暗号LSI ICF3の開発で僕がモンゴメリ乗算を採用することに反対した理由を説明すれば、数学の才能が役に立つということが、わかるように思います。

ICF3を開発した部署は、ハードウェアの開発部なので電気・電子系の学科の人が多いのですが、現在の教育のようにRSAの数学について、知っている人は、いませんでした。研究所とは異なり頭を空っぽにして、全力で、最小限の工数で、開発を達成させることが仕事なのです。特に隣の大型コンピュータの開発部隊と異なり１年に１機種を開発するという無謀なことをやっていました。隣では４年に１機種というペースでやっています。なので勉強なんてさせてもらえず成果だけ出すという苦しいことをやらされます。１年に１機種が可能なのは、それなりの学歴の年配の方々が控えていて、できなければ、切り捨てられてしまうからです。

そんな中、新規にRSA暗号のLSIを開発することになった。検討を進めて方式が決まりそうになったところで日立のシステム開発研究所から海外の暗号の教科書がFAXで送信されてきた。22ページだけ抜き取ったものでした。モンゴメリ乗算を使ってRSAを実装できないかということだった。研究所の人が必要だと思った、バラバラの箇所の22ページで、最後の2ページにモンゴメリ乗算の式が、書かれていた。「14.3.2 Montgomery reduction」のところです。 そこから２日かけてRSA暗号の計算方法を、作り上げたわけです。実は教科書のアルゴリズム14.94にRSA暗号の計算方法があったのですがFAXには入っていませんでした。研究所の人は、ちゃんと読んで送っているのか、疑いました。😀 ただし、ハードウェアでは14.94の方法では難しくて、どのみち自身でRSA暗号の計算方法を作り上げる必要がありました。

モンゴメリ乗算の公式14.36 --- x・y・R-1 mod m

R-1は、引く１ではなくてマイナス１乗です。RSA暗号の計算で、R-1が消えるように、計算していけば、答えがでるだろうと予測して、C言語で、試してみたところ、正解が得られました。

ここで数学の才能の有無によって、判断に違いが出てくるのです。R-1という記号が、自分が知っている-1なのか、あらゆる値で、正しい答えが計算できるのか、教科書の読んでないところに、特異点が存在するみたいなことが書かれてないか。

大学１年のときの数学で整数論を習っていたのを思い出した。10年前に習ったことで、加減、乗除を定義して、それが閉じるのか、どうか、という講義だった。モンゴメリ乗算という定義が、閉じているのか、それを確認する必要があった。

ただコンピュータを作りたいと思う電気工学科が、整数論を、しっかり覚えていたわけではなく、特異点が存在しないか、おろおろ、やっていた。最初、感覚的に問題を感じ、自分がわかっていないことが、わかったのだが、徐々にわかっていないところが、何なのか、明らかになり整数論にたどり着いた。

ソフトウエアの開発では、間違いがあれば、バージョンアップをすればいいという考え方もありますが、ハードウェアの開発では、１回の間違いが致命的な損害になることもあり、数学の才能はIT業界で役に立つということになると思います。

以下はFAXで送信された教科書です。サンプル無料とありますが、全部あるようです。

cacr.uwaterloo.ca

2018年4月19日追記

この話は「車輪の再発明」ではなくて、なんかやってみたら正しい答えになるから大丈夫だと勘違いをしている可能性があることを問題として認識できるか？という点です。 自身で計算方法を作っていますから、公式が、正しい条件で運用されているかを、厳格に考えなければならない。 割算(÷)の記号が使われていても、実際の演算はユークリッド互除法だったり、べき乗剰余演算だったりするのです。大学の数学は。

ついでの話になりますが、この国には自分で考えたほうが、海外よりも、できる回答になる人がいることを、頭の中に入れてもらえないかと思うのです。

1997年 東大の「疑似非同期式マイクロプロセッサ」

僕は1994年に日立 中央研究所 超高速プロセッサ部に入ったが、次の年には超高速プロセッサ部は無くなった。プロセッサを作るやつは「犯罪者」であり受刑者のような雰囲気だったのは確かだ。そして僕はIBMのCPUを買うための仕事にとりかかった。

1996年、大学などの研究機関向けにVDECが設立されLSIの試作、研究が行えるようになったようです。VDECの年報、1996年と1997年を読みました。東大のプロセッサのための研究が、いくつか掲載されています。 この頃は、パイプライン段数を増やす、スーパーパイプラインという思想で、周波数を上げる技術の研究が盛んだったようです。加算器をパイプライン化する研究や、加算する値によって計算時間が異なることを利用し、1～3サイクルで加算をする「疑似非同期」というアイディアがあったようです。

僕のICF3-Vの「疑似パイプライン」は面積当たりの性能を向上させるためパイプライン段数を削減しつつ、パイプライン効果を得る方法なのだが、それは、おいておいて、実は「疑似非同期」も検討していた。

東大の疑似非同期の対象は加算器で、入力値によって変化する終了検出が必要だった。僕の疑似非同期は、除算が対象。除算支援ハードのために全体の周波数が落ちているのだ。除算演算をする場合、32bitの2命令を1サイクルとするみたいな、決まり事を作るだけ。値による終了検出はしないので、簡単。除算の性能が下がるが、決まり事を作るだけでハードウェアの変更の必要はない。同一のハードで、除算の性能が下がっても、周波数を上げたい場合、ソフトウェアのほうで対応する。

VDECの年報は基本的には教育を含め、学生が短期間に試作しているものだが、中には、興味あるものもあるかもしれませんね。 1998年以降も、ちょっとみてみようかな。

http://www.vdec.u-tokyo.ac.jp/REPORT/vdecreport.html

MicroBlaze性能評価

目的

手っ取り早く自作CPUの性能を評価するためMicroBlazeと比較できるようにする。ベンチマークは自作CPUの性能を測るプログラムを簡単にするため、あまり意味はなく四則演算や論理演算、シフト命令が適当に入るような小さいものを自作した。FPGAの経験は浅いので結果についての取り扱いは注意されたし。

MicroBlazeの構成

FPGAデバイス : Artix-7 35T Arty

	性能型	面積型	最小型	MCS型
Predefined Configuration	microcontroller	Minimum Area	Minimum Area	-
implementation optimization	PERFORMANCE	AREA	AREA	AREA
クロック	166MHz	166MHz	166MHz	166MHz
WNS	0.04 ns	0.01 ns	0.02 ns	0.01 ns
Debug Module	〇	〇	〇	〇
Enable Barrel Shiffter	〇	〇	〇	×
FPU	×	×	×	×
Integer Multi	MUL32	MUL32	×	×
Integer Divider	〇	〇	×	×
Optimaization	PERFORMANCE	AREA	AREA	-
Enable Branch Target Cache	×	×	×	×
S-RAM	32KB	32KB	32KB	32KB
追加IP	AXI GPIO AXI Uartlite	AXI GPIO AXI Uartlite	AXI GPIO AXI Uartlite	-

GPIOはArtix-7 35Tの基板上のLED 4個と接続されている

実装面積

	性能型	面積型	最小型	MCS型
LUT	1742	1512	1401	985
FF	1582	1274	1142	747
BRAM	8	8	8	8
DSP	3	3	0	0
LUTRAM	140	218	216	203

測定結果

パラメータ	性能型	面積型	最小型	MCS型
ループ数10000000 除算割合 10	7.9 秒	10.5秒	41.7 秒	51.0 秒

ベンチマーク プログラム

#include <stdint.h>
#include "xparameters.h"
#include "xil_printf.h"

#pragma GCC optimize("O2")

uint32_t xor(void) {
  static uint32_t y = 2463534242;
  y = y ^ (y << 13); y = y ^ (y >> 17);
  return y = y ^ (y << 15);
}

uint32_t xors(int loop,int div) {
    int i;
    uint32_t a,b,c;
    uint64_t w;
    uint32_t r;

    r = 0;
    for(i=0 ; i<loop ; i++) {
        do {
            a = xor();
        } while(a==0);
        do {
            b = xor();
        } while(b==0);
        do {
            c = xor();
        } while(c==0);

        w = a*b;
        if(i%div==0) w /= c;
        r += w;
    }
    return r;
}

#pragma GCC optimize("O0")

int main() {

    xil_printf("START!\n");
    uint32_t r = xors(10000000,10);
    xil_printf("%08X\n",r);

    return 0;
}

ベンチマークの演算結果

gccのオプションでハードウェア乗算器、除算器、バレルシフタの有無の設定ができる。MicroBlazeの構成をもとに正しくgccのオプションを設定する。乗算器がない構成で乗算命令を行うと演算結果が0になる。正しい演算結果になっているか確認する。測定したパラメータでは 次のような値になる。 0x3EEF270E

乗算の部分は32bit×32bit = 64bit のつもりで作成したが64bitにキャストしていなかったため32bit × 32bit = 32bitというようにCコンパイラは解釈するみたいです。結果の性能は32bitのままデータの再収取はしませんが、64bitにキャストした場合の期待値は

0xFC3BB111

Intel CPUとの比較

Intel Celeron E7500(2.93GHz)では0.13秒

2930 ÷ 166.667 ≒ 17.58倍 E7500の周波数を166.667MHzに換算した場合は2.3秒

考察

乗算器、除算器がある場合、性能は格段に向上する。乗算器のゲート数はASICでは大きなものになるはずだがFPGAではDSPで実装されるため注意する。性能型はパイプライン段数5で面積型はパイプライン段数3なので、性能型のほうが周波数が高くてもいいはずなのだが、今回は同じ166MHzだった。Xilinxのサイト見ても周波数の差は少ないので合っているものとも思われる。乗算命令とシフト命令のレイテンシが性能型と面積型で異なることが、今回の測定結果に反映されたのかもしれない。乗算命令のレイテンシは性能型で１、面積型で３。シフト命令のレイテンシは性能型で１、面積型で２。 MCS型はMicroBlaze MCSのこと。機能固定で面積をさらに小さくしたものと思われる。機能面では最小型とバレルシフタの有無が異なる。この結果、同じ周波数だが、バレルシフタがある最小型のほうが高性能になっているものと思われる。

追記 2018年4月14日 次のURLでMicroBlazeの乗算性能についての説明があって参考になります。

qiita.com

ICF3とICF3-Vの違いと、何ができそうかという話

ICF3をオープンにして２年近くになっています。そしてICF3が、これからどんな用途に使えるのか説明してきました。ネットワーク監視カメラのセキュリティに有用だと言った気がします。ICF3は1999年のLSIですが、世界一の高性能であったこともあり、廉価なIoTで使うにはゲート規模が大きかったかもしれない。そこで昨年、ICF3の1024bitの演算器を32bitにした小型のICF3-Vをフォークさせています。ICF3-Vは暗号プロセッサとしても使えますが、汎用マイコンとしても使えます。ICF3-Vの、だいたいの設計は、できていますが、現在、実装をFPGAでして検証を行なおうとしています。

ICF3-Vは家庭用ルータやセンサーデバイスをネットワークに接続する目的で効果的なんだと思っています。暗号演算に必要最低限の命令と疑似パイプラインによってゲート数を少なくすることができて製造原価を下げることが可能(予定)だからです。疑似パイプラインは従来のパイプラインアーキテクチャと異なるアーキテクチャ。

ICF3-Vはハード制御信号を命令セットアーキテクチャになるようにしている。すべての命令をハードで処理するには、ゲート規模が大きくなるので、複雑な命令はマイクロコードで処理する方式。ハード制御信号の命令とマイクロ実装の命令を、同一命令ストリーム上で処理する方式。32bitのハード制御信号は、制御情報とオペランドを含む、冗長なものになるため、オペランドが短い。これがマイクロ実装の16bit命令でのオペランドに一致させることを容易にした。性能が必要な場合はハード制御信号の命令コードによる、疑似パイプラインで、高速化。メモリを節約するためには16bit命令を利用する。16bit命令は、ユーザーが自由にプログラム可能で、アプリで必要なものだけ実装すれば良く、少し手間がかかるが、製造原価を下げる目標には、適しているように思う。

これが現状のマイコンの効率を上回っていると仮定する。

今後、これを上回る効率のものが考えだされなければ、ICF3-VのセンサーIoTは、１度作れば、半永久的に売れるみたいなことはあるのではないだろうか？ 例えばバッファローのBBR-4MGは、販売開始から、10年くらい経過していると思いますが、現役みたいですし。

openicf3.idletime.tokyo

1999年のICF3で楕円暗号を実装した社内資料の完全公開

以前から、１ページ目だけ公開していたのですが全ページを公開しました。ICF3でビットコインなどに使われているECDSAを実装するのに、あると便利な資料だと思います。

著作権は平山 直紀にあります。 以下のURLからダウンロードできます。

https://openicf3.idletime.tokyo/summary.html#ICF3EC