(57)【特許請求の範囲】
【請求項１】
多ビット長のカウンタを持つ乱数生成サーバと、該カウンタの値を要求するクライアントと、これら回路間のメッセージを伝達するためのスイッチネットワークとを有する乱数生成装置であって、
前記乱数生成サーバ、前記クライアントおよび前記スイッチネットワークは独立したタイミングで動作する非同期回路であり、
前記スイッチネットワークは、同じ出力方向に対するメッセージを同時に複数受け取った時にどのメッセージを先に伝達するかをアービタによって決定する複数のルーチングスイッチを有し、
前記クライアントが前記スイッチネットワークを通じて前記乱数生成サーバに前記カウンタの値の読み出しを要求すると、前記乱数生成サーバは前記カウンタの値を前記スイッチネットワークを通じて前記クライアントに返却し、
前記乱数生成サーバは、前記クライアントが前記カウンタの値を読み出すよりも十分高い頻度で、前記スイッチネットワークを通じて、自身に、前記クライアントからの読み出し要求と排他的に処理される更新要求を送り、前記カウンタの値を変更することで前記クライアントに乱数を供給することを特徴とする乱数生成装置。
【請求項２】
請求項１において、
前記クライアントと前記乱数生成サーバをＰＣＡの可変機能部の集まりである論理層に構成し、前記スイッチネットワークを前記ＰＣＡの組み込み機能部の集まりであるルーチング層に構成したことを特徴とする乱数生成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は非同期回路により乱数を生成する乱数生成装置に関するものである。
【０００２】
【従来の技術】
従来の擬似乱数でない乱数を生成する方法は、専用ハードウェア（ＡＳＩＣ：Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）上で、放射線や温度などの非決定的な物理現象をサンプリングすることに基づいている。
【０００３】
パーソナルコンピュータ環境で利用される他の乱数生成方法としては、マウスのクリック、ＣＰＵの負荷のバラツキ、ネットワーク上のパケットの到着回数、およびハードディスクのアクセスパターンなどのランダムなＩ／Ｏイベントを利用する方法がある。
【０００４】
【発明が解決しようとする課題】
しかしながら、このようなランダムなＩ／Ｏイベントを利用することができない場合がある。
【０００５】
本発明の目的は、Ｉ／Ｏイベントの存在を前提とできない装置において、暗号、進化可能ハードウェア、遺伝子アルゴリズムに関するアプリケーション等を実現するため、擬似乱数ではない乱数を生成する装置を提供することである。
【０００６】
【課題を解決するための手段】
上記課題を解決するための第１の発明は、多ビット長のカウンタを持つ乱数生成サーバと、該カウンタの値を要求するクライアントと、これら回路間のメッセージを伝達するためのスイッチネットワークとを有する乱数生成装置であって、前記乱数生成サーバ、前記クライアントおよび前記スイッチネットワークは独立したタイミングで動作する非同期回路であり、前記スイッチネットワークは、同じ出力方向に対するメッセージを同時に複数受け取った時にどのメッセージを先に伝達するかをアービタによって決定する複数のルーチングスイッチを有し、前記クライアントが前記スイッチネットワークを通じて前記乱数生成サーバに前記カウンタの値の読み出しを要求すると、前記乱数生成サーバは前記カウンタの値を前記スイッチネットワークを通じて前記クライアントに返却し、前記乱数生成サーバは、前記クライアントが前記カウンタの値を読み出すよりも十分高い頻度で、前記スイッチネットワークを通じて、自身に、前記クライアントからの読み出し要求と排他的に処理される更新要求を送り、前記カウンタの値を変更することで前記クライアントに乱数を供給するよう構成した。
【０００７】
第２の発明は、第１の発明において、前記クライアントと前記乱数生成サーバをＰＣＡの可変機能部の集まりである論理層に構成し、前記スイッチネットワークを前記ＰＣＡの組み込み機能部の集まりであるルーチング層に構成した。
【０００８】
【発明の実施の形態】
［本発明の原理］
図１に本発明の基本構成を示す。図１において、１０は多ビット長のカウンタを有する乱数生成サーバ、２０はクライアント、３０は多数のルーティングスイッチ３１を含むスイッチネットワークであり、互いに独立したタイミングで非同期で動作するようＶＬＳＩ上に構成されている。
【０００９】
乱数生成サーバ１０は、スイッチネットワーク３０を通じて自身に更新要求を送ることで自律的にカウンタの値を高い頻度（ｆｃｈａｎｇｅ）で変化させている。これはカウンタのビット数をＮとすると、２Ｎ個の場所をもつルーレットとみなすことができる。
【００１０】
一方、クライアント２０はこの動作とは独立に、カウンタの更新頻度より十分に低い頻度（ｆｒｅａｄ）で読み出し要求のメッセージをスイッチネットワーク３０を通じて乱数生成サーバ１０に送り、その時点のカウンタの値を乱数として取得する。
【００１１】
このメッセージの送達については、クライアント２０、乱数生成サーバ１０およびスイッチネットワーク３０が各々非同期回路で構成されているので、そのタイミングが独立している。
【００１２】
更に、この読み出しのタイミングは、ＶＬＳＩの製造上のバラツキ、温度のドリフト、スイッチネットワーク３０上のメッセージの衝突とアービタによる調停動作の時間等に起因して、ジッタ（到着時刻のバラツキ）を含むことになる。
【００１３】
これは回転するルーレットに玉を投げ込む行為のように結果の予測を不可能にする。以上から、クライアント２０が得るカウンタの値は、ルーレットの原理に基づく乱数となる。
【００１４】
［実施形態］
ここでは、非同期方式に基づくＰＣＡ（Ｐｌａｓｔｉｃ  Ｃｅｌｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ）で実現した実施形態を述べる。ＰＣＡは、命令の実行機能を固定的に組み込んだ組み込み機能部と、その組み込み機能部からの指定により機能または記憶が決定される可変機能部を基本単位（セル）とし、そのセルをメッシュ状に接続したアーキテクチャである（特願平９−３３２７３７号）。
【００１５】
ＰＣＡの可変機能部の集まりを布線論理層４０と呼ぶ（これに対し、組み込み機能部の集まりをルーチング層５０と呼ぶ。）が、これは、従来のＦＰＧＡ（Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）に対応していると考えることができる。しかしながら、組み込み機能部の働きによって、ＰＣＡは既存のＦＰＧＡではできなかったこと、すなわち、回路間の動的なメッセージ通信や回路による回路の自律的かつ動的な書き換えを可能にしている。
【００１６】
ＰＣＡの論理層４０（可変機能部の集まり）は、図２に示される非同期の論理回路オブジェクト（複数のクライアントオブジェクトＣＬＩと１個の乱数生成サーバオブジェクトＲＧＳ（Ｒａｎｄｏｍ  Ｎｕｍｂｅｒ  Ｇｅｎｅｒａｔｏｒ  Ｓｅｒｖｅｒ））を構成する。クライアントオブジェクトＣＬＩ（ＣＬＩ−１，ＣＬＩ−２，・・・、ＣＬＩ−Ｍ）は図１のクライアント２０に対応し、乱数生成サーバオブジェクトＲＧＳは図１の乱数生成サーバ１０に対応する。
【００１７】
一方、ＰＣＡのルーチング層５０（組み込み機能部の集まり）は、図１のスイッチネットワーク３０に対応し、論理層４０の複数の独立したクライアントオブジェクトＣＬＩ（ＣＬＩ−１，ＣＬＩ−２，・・・，ＣＬＩ−Ｍ）と１個の乱数生成サーバオブジェクトＲＧＳの相互間のメッセージの伝達機能を持つ。
【００１８】
これら２種類のオブジェクトＣＬＩ、ＲＧＳの相互間での通信プロトコルは、図３に明示されている書式の要求メッセージＭ１と応答メッセージＭ２によって与えられる。クライアントオブジェクトＣＬＩ（ＣＬＩ−１，ＣＬＩ−２，・・・，ＣＬＩ−Ｍ）が乱数生成サーバオブジェクトＲＧＳに要求メッセージＭ１を送ることによって新しい乱数を要求する。乱数生成サーバオブジェクトＲＧＳはこの要求メッセージＭ１に応じて乱数を含む応答メッセージＭ２を送出する。
【００１９】
要求メッセージＭ１は、クライアントオブジェクトＣＬＩから乱数生成サーバオブジェクトＲＧＳまでの通信路を動的に設定する往路設定命令列「ＲＯＵＴＥ」、乱数生成サーバオブジェクトＲＧＳから送信元のクライアントオブジェクトＣＬＩまでの復路を与える復路設定命令列「ＲＥＴＵＲＮ」、カウンタの値を読み出すコマンド「ＲＥＡＤ」、クライアントオブジェクトＣＬＩから乱数生成サーバオブジェクトＲＧＳまでの往路やその逆の復路の経路設定を解除するコマンド「ＣＬＥＡＲ」から構成されている。また、応答メッセージＭ２は前記したコマンド「ＲＥＴＲＵＮ」、データ「乱数」、コマンド「ＣＬＥＡＲ」から構成されている。
【００２０】
ルーチング層５０の組み込み機能部のルーチングスイッチ３１は、アービタ（調停回路）３１１によって、乱数生成サーバオブジェクトＲＧＳが同時に受け取るメッセージが必ず一つとなるよう制限する。メッセージの競合に伴うメタステーブルな状態はこのアービタ３１１が解決する。３１２はルーチングスイッチ３１の入力ポート、３１３は出力ポートである。入力ポート３１２のＮ，Ｅ，Ｗ，Ｓ，ＰＰは入力元の方向を示し、それぞれＮｏｒｔｈ方向、Ｅａｓｔ方向、Ｗｅｓｔ方向、Ｓｏｕｔｈ方向、布線論理層からの入力に対応するものであることを示す。同様に、アービタ３１１と出力ポート３１３のＮ，Ｅ，Ｗ，Ｓ，ＰＰは出力先の方向に対応するものである。
【００２１】
図４は乱数生成サーバオブジェクトＲＧＳを示すブロック図である。この乱数生成サーバオブジェクトＲＧＳは入力ポート１１、出力ポート１２、ハンドシェーク制御部１３、デコーダ部１４、ルーレットホイールとして働く可変ビット長（２Ｎの範囲の乱数に対しＮビット）のカウンタ部１５、メッセージ生成器１６、それにマルチプレクサ１６から構成される。
【００２２】
ハンドシェーク制御部１３は入出力ポート１１，１２と非同期のハンドシェークをとりながらカウンタ部１５とメッセージ生成器１６を制御する。またデコーダ部１４は入力したメッセージを解釈して「ＷＥＳＴ」、「ＮＯＲＴＨ」、「ＥＡＳＴ」、「ＳＯＵＴＨ」、「ＰＰ」などのルーチング命令をフォワードする一方、「ＩＮＣ」（インクリメント）、「ＲＥＡＤ」、および「ＣＬＥＡＲ」コマンドを実行する。またメッセージ生成器１６はカウンタ部１５に対するインクリメント（１を加算する）メッセージを再帰的に作り出す。またマルチプレクサ１７はデコーダ部１４の出力もしくはカウンタ部１５のレジスタの中身もしくはメッセージ生成器１６の出力のいずれかを選び、出力ポート１２に送る。入力ポート１１は同時に受け付けるメッセージを一つに限るため一つであるが、出力ポート１２の数はカウンタ部１５のビット幅に応じて１つ乃至複数設ける。
【００２３】
メッセージ生成器１６は乱数生成サーバオブジェクトＲＧＳの初期化時に、そのＲＧＳの入力ポート１１に対しインクリメントメッセージＭ３を発行する。
【００２４】
このインクリメントメッセージＭ３の書式は図３，図４に示され、乱数生成サーバオブジェクトＲＧＳの入力ポート１１に通信路を動的に設定するルーチングコマンド「ＲＯＵＴＥ」、カウンタ部１５をインクリメントさせるコマンド「ＩＮＣ」、それに通信路を解放するコマンド「ＣＬＥＡＲ」からなる。このインクリメントメッセージＭ３がデコードされると、カウンタ部１５の値は１加算され、同時にメッセージ生成器１６から新たなインクリメントメッセージＭ３が入力ポート１１に向けて発行される。この繰り返しによりカウンタ部１５は、０から２Ｎ−１までの範囲を数え上げる。
【００２５】
次に、クライアントオブジェクトＣＬＩからの要求メッセージＭ３を乱数生成サーバオブジェクトＲＧＳが入力ポート１１に受け取ると、その要求メッセージＭ３はデコード部１５で解釈される。要求メッセージＭ３のルーチングコマンドの「ＲＥＴＵＲＮ」部分は、結果を返すための通信路（復路）を形成するために、出力ポート１２にそのまま転送される。「ＲＥＡＤ」コマンドは、マルチプレクサ１７を切り替えて、そのときのカウンタ部１５の値を出力ポート１２に流すので、ランダムなカウント値がクライアントオブジェクトＣＬＩへの復路上に送り出される。最後に、「ＣＬＥＡＲ」コマンドが復路の経路設定を解除するために発行される。
【００２６】
なお、本実施形態では、乱数生成を行う乱数生成サーバオブジェクトＲＧＳの使用法としてクライアントサーバ型のモデルで説明しているが、複数の乱数生成サーバオブジェクトＲＧＳを、パイプライン形態もしくは、ツリー構造、スター型構造、その他のトポロジーの接続によって繋ぎ合わせて使うこともできる。
【００２７】
また、その接続中にＸＯＲ（排他的論理和）スクランブラや他の論理オペレータのような様々な機能オブジェクトを挿入して使うこともできる。
【００２８】
更に、本実施形態では、乱数生成サーバオブジェクトＲＧＳのカウンタ部１５をラウンドカウンタとして実現しているが、ＬＦＳＲ（Ｌｉｎｅａｒ  Ｆｅｅｄｂａｃｋ  Ｓｈｉｆｔ  Ｒｅｇｉｓｔｅｒ）あるいはＦＣＳＲ（Ｆｅｅｄｂａｃｋ  Ｃａｒｒｙ  Ｓｈｉｆｔ  Ｒｅｇｉｓｔｅｒ）に基づく擬似乱数発生器に置き換えた実施形態も可能である。
【００２９】
【発明の効果】
本発明によれば、以下の要因に依存したランダム性をもつ乱数を生成することができる。（１）高周期で自律的に更新されるカウンタ部と低周期の要求メッセージの到着間隔との間の非決定的な非同期のタイミングの関係（周期とフェーズ）、（２）スイッチネットワーク上の共有されるルーチングリソースをめぐる競合の度合いおよびネットワークのトラフィック、（３）クライアントの数、（４）温度の変化に依存する各回路の動作速度のバラツキ、およびＶＬＳＩの実装に依存する半導体の特性のバラツキ、等である。また、本発明を利用することでＰＣＡの上で疑似乱数でない乱数を得ることが可能になる。よって、暗号、進化可能ハードウェア、遺伝子アルゴリズムに関するアプリケーションの実現に寄与できる。
【図面の簡単な説明】
【図１】本発明の基本構成を示す説明図である。
【図２】ＰＣＡの説明図である。
【図３】（ａ）はルーチングスイッチの説明図、（ｂ）はＰＣＡを用いた装置の構成とメッセージの書式の説明図である。
【図４】乱数生成サーバオブジェクトＲＧＳのブロック図である。
【符号の説明】
１０：乱数生成サーバ、ＲＧＳ：乱数生成サーバオブジェクト、１１：入力ポート、１２：出力ポート、１３：ハンドシェーク制御部、１４：デコーダ部、１５：カウンタ部、１６：メッセージ生成器、１７：マルチプレクサ
２０：クライアント、ＣＬＩ：クライアントオブジェクト
３０：スイッチネットワーク、３１：ルーチングスイッチ、３１１：アービタ、３１２：入力ポート、３１３：出力ポート
４０：布線論理層（可変機能部の集まり）
５０：ルーチング層（組み込み機能部の集まり）
【図１】
0003558162.tif 000002
【図２】
0003558162.tif 000003
【図３】
0003558162.tif 000004
【図４】
0003558162.tif 000005