ブランチング・プログラム・マシン及び並列プロセッサ
【課題】ＱＤＤを模擬する演算を実行することが可能なブランチング・プログラム・マシンを提供する。
【解決手段】命令メモリ７には、２アドレス２分岐命令、３アドレス４分岐命令、出力命令の３種の命令を少なくとも含む命令系列が記憶され、命令メモリ７はプログラムカウンタ１０に設定されたアドレス情報に従って該アドレス情報で指令されるアドレスに格納された命令を命令レジスタ８に出力する。命令デコーダ９は、２アドレス２分岐命令又は３アドレス４分岐命令の場合、入力セレクタ３で入力変数を入力レジスタ４に設定し、この値に基づきジャンプ先の命令メモリ７のアドレス情報を選択しプログラムカウンタ１０に設定する。また、出力命令の場合、指定される出力レジスタ５のアドレスに、指定される出力データを設定する。
【解決手段】命令メモリ７には、２アドレス２分岐命令、３アドレス４分岐命令、出力命令の３種の命令を少なくとも含む命令系列が記憶され、命令メモリ７はプログラムカウンタ１０に設定されたアドレス情報に従って該アドレス情報で指令されるアドレスに格納された命令を命令レジスタ８に出力する。命令デコーダ９は、２アドレス２分岐命令又は３アドレス４分岐命令の場合、入力セレクタ３で入力変数を入力レジスタ４に設定し、この値に基づきジャンプ先の命令メモリ７のアドレス情報を選択しプログラムカウンタ１０に設定する。また、出力命令の場合、指定される出力レジスタ５のアドレスに、指定される出力データを設定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多値論理決定グラフ（ＭＤＤ：Multiple-valued Decision Diagram）を模擬する演算が可能なブランチング・プログラム・マシン（ＢＭ：Branching Program Machine）及びブランチング・プログラム・マシンを並列に接続した多段ブランチング・プログラム・マシン（多段ブランチング・プログラム・マシン）、並びに多段ブランチング・プログラム・マシンを並列に接続した並列プロセッサに関する。
【背景技術】
【０００２】
二分決定グラフ（以下「ＢＤＤ（Binary Decision Diagram）」という。）を模擬するブランチング・プログラム・マシンは、分岐命令と出力命令の２種類の命令を有するプロセッサである（非特許文献１，２参照）。従って、ブランチング・プログラム・マシンは、汎用プロセッサに比べてアーキテクチャが単純である。また、制御回路などに於いて多く用いられる条件分岐を、専用命令で実行するため、特定のアプリケーションに於いては汎用プロセッサよりも高速の処理が可能となる。ブランチング・プログラム・マシンのアプリケーションは、制御回路、回路シミュレータ、ネットワーク機器の経路表やパケット分類、及びパターンマッチングなどが挙げられる。従来のブランチング・プログラム・マシンとしては、２値の入力変数に対するＢＤＤを模擬するものが知られている（非特許文献１，２参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】P. C. Baracos, R. D. Hudson, L. J. Vroomen, and P. J. A. Zsombor-Murray, "Advances in binary decision based programmable controllers," IEEE Transactions on Industrial Electornics, Vol. 35, No. 3, pp. 417-425, Aug., 1988.
【非特許文献２】R. T. Boute, "The binary-decision machine as programmable controller," Euromicro Newsletter, Vol. 1, No. 2, pp. 16-22, 1976.
【非特許文献３】R. E. Bryant, "Graph-based algorithms for boolean function manipulation," IEEE Trans. Comput., Vol. C-35, No. 8, pp. 677-691, Aug. 1986.
【非特許文献４】Y. Iguchi, T. Sasao, and M. Matsuura, "Evaluation of multiple-output logic functions," Asia and South Pacific Design Automation Conference'2003, Kitakyushu, Japan, pp. 312-315, Jan. 21-24, 2003.
【非特許文献５】T. Kam, T. Villa, R. K. Brayton, and A. L. Sagiovanni-Vincentelli, "Multi-valued decision diagrams: Theory and Applications," Multiple-Valued Logic, Vol. 4, No. 1-2, pp. 9-62, 1998.
【非特許文献６】Y. Iguchi, T. Sasao, and M. Matsuura, "Implementation of multiple-output functions using PROMDDs," 30th International Symposium on Mulitple-Valued Logic, Portland, Oreon, U.S.A, pp. 199-205, May 23-25 2000.
【非特許文献７】S. Nagayama, T. Sasao, Y. Iguchi, and M. Matsuura, "Area-time complexities of multi-valued decision diagrams," IEICE Transactions on Fundamentals of Electronics, Vol. E87-A, No. 5, pp. 1020-1028, May 2004.
【非特許文献８】S. Nagayama, and T. Sasao, "On the optimization of heterogeneous MDDs," IEEE Transactions on CAD, Vol. 24, No. 11, pp. 1645-1659, Nov. 2005.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
任意のｎ入力論理関数はＢＤＤにより表現することができる（非特許文献３）。多出力論理関数を表現するＢＤＤはＭＴＢＤＤ（multi-terminal binary decision diagram）と呼ばれ、高々ｎ回のテーブル参照で多出力を同時に評価することができる（非特許文献４）。図１にＭＴＢＤＤの例を示す。テーブル参照の回数の平均値を平均パス長という。ＢＤＤの評価時間は平均パス長に比例する。
【０００５】
ところで、ＢＤＤの評価時間を更に削減する方法として、多値論理決定グラフ（以下「ＭＤＤ（Multiple-valued Decision Diagram）」という。）を用いる方法が知られている（非特許文献５参照）。ＭＤＤでは、入力変数はｋ個の２値変数の組に分割される。ｋ個の２値変数の組は２ｋ値の超変数となる。２ｋ値の超変数で表現した決定グラフをＭＤＤ（ｋ）と記す。ＢＤＤはＭＤＤ（１）と等価である。
【０００６】
ＭＤＤ（２）は各節点が４分岐を持つので、本稿に於いてはＭＤＤ（２）をＱＤＤ（Quaternary Decision Diagram）という。入力変数を組み分けした際の各組の２値変数の個数がすべて等しいＭＤＤを「ホモジニアスＭＤＤ」という。一方、各組の２値変数の個数がすべて等しくはないＭＤＤを「ヘテロジニアスＭＤＤ」という。
【０００７】
ヘテロジニアスＭＤＤは、変数の組み分け（グルーピング）を工夫することによって、ホモジニアスＭＤＤよりもテーブル参照回数と節点数を削減することができる（非特許文献８参照）。以下、本稿ではヘテロジニアスＭＴＱＤＤ（multi-terminal Quaternary Decision Diagram）を単にＱＤＤと呼ぶ。図２に、図１のＭＴＢＤＤを変換して得られたＱＤＤを示す。図２のＱＤＤは、最上位の節点のみが２分岐であり、他の節点は４分岐となっている。
【０００８】
論理関数をＭＤＤ（ｋ）で表現すると、ＢＤＤで表現した場合に比べてメモリの参照回数をしばしば１／ｋまで削減することができる（非特許文献６）。従って、ｋを増加させると、論理関数の評価時間を短縮することができる。しかしながら、１つの節点を表現するために必要なメモリ量は２ｋのオーダーで増加する。そのため、多くのベンチマーク関数に於いて、ｋ＝２のときのＭＤＤ（ｋ）の総メモリー量が最小となる（非特許文献７参照）。従って、論理関数の評価に於いては、ＢＤＤよりもＱＤＤの方がより適しているといえる。
【０００９】
そこで、本発明の目的は、かかるＱＤＤを模擬する演算を実行することが可能なブランチング・プログラム・マシンを提供することにある。また、本発明の目的は、さらなる高速化のため、ブランチング・プログラム・マシンを並列に接続した多段ブランチング・プログラム・マシン、並びに多段ブランチング・プログラム・マシンを並列に接続した並列プロセッサを提供することにある。
【課題を解決するための手段】
【００１０】
本発明に係るブランチング・プログラム・マシンは、複数の入力変数が入力される変数入力バスと、
前記変数入力バスから入力変数を選択する入力セレクタと、
前記入力セレクタにより選択される入力変数が一時的に設定される入力レジスタと、
出力変数が設定される出力レジスタと、
前記出力レジスタに設定された出力変数が出力される変数出力バスと、
プログラムにおいて実行する各命令が記憶された命令メモリと、
命令メモリから順次読み出される命令が一時的に設定される命令レジスタと、
入力レジスタから読み出される入力変数と、命令レジスタから読み出される命令とに基づいて当該命令を実行する命令デコーダと、
次に読み出す命令の命令メモリ内のアドレス情報を記憶するプログラムカウンタと、
を備えたブランチング・プログラム・マシンであって、
前記命令メモリには、（１）参照する入力変数のインデックス、入力変数が０のときにジャンプする先の命令メモリのアドレス情報、及び入力変数が１のときにジャンプする先の命令メモリのアドレス情報を含む２アドレス２分岐命令、（２）参照する入力変数のインデックス、入力変数が第１の値のときにジャンプする先の命令メモリのアドレス情報、入力変数が第２の値のときにジャンプする先の命令メモリのアドレス情報、及び入力変数が第３の値のときにジャンプする先の命令メモリのアドレス情報を含む３アドレス４分岐命令、並びに、（３）出力先の出力レジスタのアドレス情報、及び出力データを含む出力命令の３種の命令を少なくとも含む命令系列が記憶され、前記プログラムカウンタに設定されたアドレス情報に従って該アドレス情報で指令されるアドレスに格納された命令を前記命令レジスタに出力するものであり、
前記命令デコーダは、（ａ）前記命令レジスタに設定された命令が前記２アドレス２分岐命令又は前記３アドレス４分岐命令の場合、当該命令で指定される入力変数のインデックスに基づき前記入力セレクタにより入力変数を選択して前記入力レジスタに設定し該入力レジスタに設定される入力変数の値に基づいて、当該命令で指定されるジャンプする先の命令メモリのアドレス情報を選択して前記プログラムカウンタに設定する処理を実行し、（ｂ）前記命令レジスタに設定された命令が前記出力命令の場合、当該命令で指定される出力レジスタのアドレス情報に従って該アドレス情報で指令される前記出力レジスタのアドレスに、当該命令で指定される出力データを設定する処理を実行することを特徴とする。
【００１１】
この構成により、ＱＤＤを模擬する演算を実行することが可能となる。
【００１２】
また、本発明に於いては、前記命令メモリに記憶された３アドレス４分岐命令は、参照する入力変数のインデックス、入力変数の値に対する分岐先アドレスの組み合わせを指定する機能選択フラグ、入力変数が第１の値のときにジャンプする先の命令メモリのアドレス情報ADDR0、入力変数が第２の値のときにジャンプする先の命令メモリのアドレス情報ADDR1、及び入力変数が第３の値のときにジャンプする先の命令メモリのアドレス情報ADDR2を含み、前記命令デコーダは、前記命令レジスタに設定された命令が前記３アドレス４分岐命令の場合には、当該命令で指定される入力変数のインデックスに基づき前記入力セレクタにより入力変数を選択して前記入力レジスタに設定し、該入力レジスタに設定される入力変数の値が前記第１，第２，第３の値の場合、それぞれ、当該命令で指定されるジャンプする先の命令メモリの前記アドレス情報ADDR0，ADDR1，ADDR2を選択し、該入力レジスタに設定される入力変数の値が前記第１，第２，又は第３の値以外の場合、現在の命令のアドレスPの次のアドレス(P+1)のアドレス情報を選択して前記プログラムカウンタに設定する処理を実行するようにすることもできる。
【００１３】
本発明に係る多段ブランチング・プログラム・マシンは、前記のブランチング・プログラム・マシンが直列に接続され、後段の前記ブランチング・プログラム・マシンの変数入力バスの少なくとも一部には、前段の前記ブランチング・プログラム・マシンの前記変数出力バスが接続され、残りの変数入力バスには入力変数が入力されることを特徴とする。
【００１４】
このようにブランチング・プログラム・マシンを多段に直列に接続することで、より大きな論理関数の演算を行うことができる。
【００１５】
また、本発明に於いて、前記各ブランチング・プログラム・マシンの前記変数出力バスは、プログラマブル・ルーティング・ボックスを介して後段のブランチング・プログラム・マシンの前記変数入力バスに接続された構成とすることができる。
【００１６】
これにより、各段のブランチング・プログラム・マシンの出力変数の順序を自由に組み替えて後段のブランチング・プログラム・マシンの入力変数として入力することができる。従って、順序回路を実現するための各段のブランチング・プログラム・マシンの命令のコーディングが容易となる。
【００１７】
本発明に係る並列プロセッサは、複数個並列に接続された上述の多段ブランチング・プログラム・マシンと、
複数の選択入力ノードと複数の選択出力ノードとを備え、前記各多段ブランチング・プログラム・マシンの前記各変数出力バスが前記各選択入力ノードに接続され、選択出力ノードの少なくとも一部が前記各多段ブランチング・プログラム・マシンの変数入力バスの一部に接続され、前記各選択入力ノードと前記各選択出力ノードとの接続を組み替え可能としたプログラマブル相互接続回路と、を備えたことを特徴とする。
【００１８】
これにより、並列演算が可能となり、論理関数の演算速度を更に速めることができる。
【発明の効果】
【００１９】
以上のように、本発明のブランチング・プログラム・マシンによれば、ＱＤＤを模擬する演算を実行することが可能となる。また、本発明の多段ブランチング・プログラム・マシンによれば、多段化することでより大きな論理関数の演算を行うことが可能となる。また、本発明に係る並列プロセッサによれば、並列演算により論理関数の演算速度を更に速めることができる。
【図面の簡単な説明】
【００２０】
【図１】ＭＴＢＤＤの例である。
【図２】図１のＭＴＢＤＤを変換して得られたＱＤＤである。
【図３】本発明の実施例１に係るブランチング・プログラム・マシンの構成を表すブロック図である。
【図４】図３の出力レジスタを構成するダブルランク・フリップフロップを示す図である。
【図５】各命令のニーモニックとメモリ内部表現を示す図である。
【図６】４種の３アドレス４分岐命令における分岐先アドレスの組み合わせを示す図である。
【図７】図５の命令セットのコードによって各３アドレス４分岐命令（Q_BRANCH）のアドレスを割り当てた結果である。
【図８】実施例２に係る多段ブランチング・プログラム・マシンの構成を表すブロック図である。
【図９】実施例３に係る並列プロセッサ３０の構成を表すブロック図である。
【発明を実施するための形態】
【００２１】
以下、本発明を実施するための形態について、図面を参照しながら説明する。
【実施例１】
【００２２】
図３は、本発明の実施例１に係るブランチング・プログラム・マシン（以下、略して「ＢＭ」という。）の構成を表す図である。
【００２３】
ＢＭ１は、変数入力バス２、入力セレクタ３、入力レジスタ４、レジスタ・ファイル５、変数出力バス６、命令メモリ７、命令レジスタ８、命令デコーダ９、プログラムカウンタ１０、及びフラグ出力バス１１を備えている。
【００２４】
変数入力バス２は、ＭＰＵなどの外部回路から複数の入力変数が入力されるバスである。入力セレクタ３は、変数入力バス２から入力される入力変数を選択するセレクタである。入力セレクタ３としては、シフタ、クロスバースイッチ、マルチプレクサ等が使用される。入力レジスタ４は、入力セレクタ３により選択される入力変数が一時的に設定されるレジスタである。
【００２５】
命令メモリ７は、プログラムにおいて実行する各命令が記憶されたメモリである。本実施例では、命令メモリ７は、語長が３２ビットのＢＭ命令を２５６個格納することができる。命令レジスタ８は、命令メモリ７から順次読み出される命令が一時的に設定されるレジスタである。命令デコーダ９は、命令メモリ７から命令レジスタ８へ読み出された命令を解釈し、実行を行うデコーダである。この命令デコーダ９は、入力レジスタ４へ設定される入力変数と、命令レジスタ８へ設定される命令とに基づいて当該命令を実行する。プログラムカウンタ１０は、次に読み出す命令の命令メモリ７内のアドレス情報を記憶する。
【００２６】
ここで、命令メモリ７には、２アドレス２分岐命令（B_BRANCH）、３アドレス４分岐命令（Q_BRANCH）、データセット命令（出力命令）（DATASET）、及び無条件ジャンプ命令の４種類の命令セットからなる命令系列が記憶されている。２アドレス２分岐命令（B_BRANCH）、３アドレス４分岐命令（Q_BRANCH）、及び無条件ジャンプ命令は、ＭＴＢＤＤ又はＱＤＤの非終端節点を評価する命令であり、データセット命令（DATASET）はＱＤＤの終端節点を評価する命令である。図５に各命令のニーモニックとメモリ内部表現を示す。
【００２７】
尚、１命令の長さを削減するために、２アドレス２分岐命令（B_BRANCH）に代わる１アドレス２分岐命令も提案されているが（例えば、非特許文献２参照）、１アドレス方式を用いると実行時間がしばしば増加する。そこで、本発明に於いては２アドレス方式の２分岐命令を採用している。
【００２８】
また、ＱＤＤにおいて、２変数を２個同時に評価する命令は、４アドレス４分岐命令によって実現できる。４アドレス４分岐命令は２分岐命令に比べて評価時間を半分に削減することができる。しかしながら、４アドレス４分岐命令は長い命令語を必要とし、現在の組み込みプロセッサの標準的な語長（３２ビット）には適していない。そこで、本発明では４アドレス４分岐命令の代わりに３アドレス４分岐命令（Q_BRANCH）を採用している。
【００２９】
図５（ａ）は２アドレス２分岐命令（B_BRANCH）である。２アドレス２分岐命令（B_BRANCH）は、２つの分岐先アドレスのうち、１つのアドレスにジャンプする命令である。２アドレス２分岐命令は、参照する入力変数のインデックス（INDEX）、入力変数が０のときにジャンプする先の命令メモリのアドレス情報（ADDR0）、及び入力変数が１のときにジャンプする先の命令メモリのアドレス情報（ADDR1）を含む。インデックス（INDEX）で指定された変数の値が０であればアドレス情報（ADDR0）に指定されたアドレスにジャンプし、そうでなければアドレス情報（ADDR1）に指定されたアドレスにジャンプする。本実施例では、図５（ａ）に示すように、アドレス情報（ADDR0），（ADDR1）は８ビット、入力変数のインデックス（INDEX）は６ビットで表現する。また、２アドレス２分岐命令（B_BRANCH）のメモリ内部表現における２９−３１ビットに格納されたコード「１１１」は、この命令が２アドレス２分岐命令（B_BRANCH）であることを表す命令識別コードである。
【００３０】
図５（ｂ）はデータセット命令（DATASET）である。データセット命令（DATASET）は指定されたデータを指定された出力レジスタに出力する命令である。データセット命令（DATASET）は、出力先の出力レジスタのアドレス情報（REG）、出力データ（DATA）、及び命令実行後にジャンプする先の命令メモリのアドレス情報（ADDR）を含む。本実施例では、図５（ｂ）に示すように、出力データ（DATA）は１６ビット、アドレス情報（ADDR）は８ビット、出力レジスタのアドレス情報（REG）は６ビットで表現する。また、データセット命令（DATASET）のメモリ内部表現における３０−３１ビットに格納されたコード「１０」は、この命令がデータセット命令（DATASET）であることを表す命令識別コードである。
【００３１】
図５（ｃ）は３アドレス４分岐命令（Q_BRANCH）である。３アドレス４分岐命令（Q_BRANCH）は、４つの分岐先アドレスのうち、１つのアドレスにジャンプする命令である。３アドレス４分岐命令（Q_BRANCH）は、参照する入力変数のインデックス（INDEX）、入力変数の値に対する分岐先アドレスの組み合わせを指定する機能選択フラグ（SEL）、入力変数が第１の値のときにジャンプする先の命令メモリのアドレス情報（ADDR0）、入力変数が第２の値のときにジャンプする先の命令メモリのアドレス情報（ADDR1）、及び入力変数が第３の値のときにジャンプする先の命令メモリのアドレス情報（ADDR2）を含む。本実施例では、図５（ｃ）に示すように、アドレス情報（ADDR0），（ADDR1），（ADDR2）は８ビット、入力変数のインデックス（INDEX）は５ビット、機能選択フラグ（SEL）は２ビットの合計３１ビットで表現する。また、３アドレス４分岐命令（Q_BRANCH）のメモリ内部表現における３１ビットに格納されたコード「０」は、この命令が３アドレス４分岐命令（Q_BRANCH）であることを表す命令識別コードである。
【００３２】
３アドレス４分岐命令（Q_BRANCH）において、４つの分岐先アドレスのうちの３つのアドレスは、アドレス情報（ADDR0, ADDR1, ADDR2）により指定される。残り１つの分岐先アドレスは、現在の命令のアドレス（PC）の次のアドレス（PC+1）とする。
【００３３】
本発明に於いては、評価時間とステップ数の削減のため、図６に示すような４種の３アドレス４分岐命令を用いる。３アドレス４分岐命令（Q_BRANCH）内の機能選択フラグ（SEL）は、４種の３アドレス４分岐命令のうちの１つを指定するフラグである。入力変数のインデックス（INDEX）で指定された変数をｉとすると、SEL＝iのときに次のアドレス（PC+1）にジャンプする。アドレスの割り付けを工夫することによって、ステップ数や実行時間を最適化することができる。
【００３４】
尚、３アドレス４分岐命令（Q_BRANCH）を使用する場合、現在の命令アドレス（PC）の次のアドレス（PC+1）が、他の３アドレス４分岐命令（Q_BRANCH）のPC+1と競合する場合が生じる。従って、かかる競合を避けるため、無条件ジャンプ命令が必要となる。無条件ジャンプ命令は、強制的に指定されたアドレスにジャンプする命令である。この無条件ジャンプ命令は、上述の２アドレス２分岐命令（B_BRANCH）を用いて実現される。無条件ジャンプ命令の場合、インデックス（INDEX）には無効値（例えば「０」）が設定され、アドレス情報（ADDR0）及びアドレス情報（ADDR1）には同じジャンプ先のアドレスが設定される。これにより、無条件ジャンプ命令が実行されると、入力変数の値を評価することなく、無条件にアドレス情報（ADDR0），（ADDR1）に設定されたアドレスにジャンプする。
【００３５】
図３の命令デコーダ９は、命令レジスタ８に設定された命令が２アドレス２分岐命令（B_BRANCH）又は３アドレス４分岐命令（Q_BRANCH）の場合、当該命令で指定される入力変数のインデックス（INDEX）に基づき入力セレクタ３により入力変数を選択して入力レジスタ４に設定し、入力レジスタ４に設定される入力変数の値（｛０，１｝又は｛００，０１，１０，１１｝）に基づいて、当該命令で指定されるジャンプする先の命令メモリのアドレス情報（（ADDR0），（ADDR1），（ADDR2））を選択してプログラムカウンタ１０に設定する処理を実行する。また、命令レジスタ８に設定された命令がデータセット命令（DATASET）の場合、当該命令で指定される出力レジスタのアドレス情報（REG）で指令されるレジスタ・ファイル５内の出力レジスタに、当該命令で指定される出力データ（DATA）を設定する処理を実行し、当該命令で指定されるジャンプする先の命令メモリのアドレス情報（ADDR）を選択してプログラムカウンタ１０に設定する処理を実行する。
【００３６】
図３のレジスタ・ファイル５は、「出力レジスタ」や「状態レジスタ」、及び「入力選択レジスタ」や「フラグレジスタ」と呼ばれるレジスタで構成される。出力レジスタ及び状態レジスタは、出力変数が設定されるレジスタである。出力レジスタ及び状態レジスタは、図４に示したようなダブルランク・フリップフロップにより構成されている。
【００３７】
図４において、Ｌ１，Ｌ２はＤラッチである。出力レジスタや状態レジスタはデータセット命令によって更新されるが、このデータセット命令は１６ビット毎にしか値を更新することができない。そのため、１６ビットよりもビット数の大きな出力や状態変数を持つ回路を評価する場合、前後の状態の値が混ざってしまうという問題が生じる。そこで、このダブルランク・フリップフロップを用いて、状態遷移信号（S_Clock）がＨｉｇｈのときに一度に値を更新する。
【００３８】
入力選択レジスタには、入力セレクタ３が入力レジスタ４に設定する変数を選択するための入力選択信号（ＩＳＲ）が設定される。
【００３９】
フラグレジスタは、ＢＭ１の動作を指定する特殊なレジスタである。フラグレジスタは、「ＲＵＮビット」、「ＩＲＱビット」、「ＲＣＯＰＹビット」、「ＡＣＴビット」、及び「ＦＥＴＣＨビット」を有し、各ビットはそれぞれ以下のような固有の役割を持つ。
（１）「ＲＵＮビット」は、１のときのみＢＭ１のプログラムカウンタ１０の更新が行われる。
（２）「ＩＲＱビット」は、１のとき割り込み信号が外部に送られる。
（３）「ＲＣＯＰＹビット」は、１のときダブルランク・フリップフロップのデータ転送が行われる。
（４）「ＡＣＴビット」は、１のとき後述するＢＭ１を接続する回路を起動する。
（５）「ＦＥＴＣＨビット」は１のとき入力レジスタ４に値が取り込まれる。
【００４０】
変数出力バス６は、レジスタ・ファイル５内の出力レジスタや状態レジスタに設定された出力変数及び状態変数が出力されるバスである。また、フラグ出力バス１１は、レジスタ・ファイル５内のフラグレジスタに設定された各フラグが出力されるバスである。
【００４１】
ＢＭ１は、出力レジスタに設定された出力変数を入力レジスタ４にフィードバックして順序回路を実現することができる。入力レジスタ４には、これらのフィードバックされた値や外部入力や隣接するＢＭ１から送られてくる出力変数が設定される。これらは、入力選択レジスタの値を用いて、入力セレクタ３が選択する。
【００４２】
以上のように構成された本実施例に係るＢＭ１について、以下その動作を説明する。ここでは簡単な具体例として、図１に示したＭＴＢＤＤを実行する場合と、図２に示したＱＤＤを実行する場合とを採り上げてＢＭ１の動作を説明することにする。
【００４３】
（１）図１に示したＭＴＢＤＤを実行する場合
図１に示したＭＴＢＤＤを実行する場合に命令メモリ７に格納される命令セットのコードは次表の通りである。
【００４４】
【表１】
【００４５】
まず、初期状態では、プログラムカウンタ１０にはアドレス情報としてＡ０が設定される。
【００４６】
プログラムの実行が開始されると、まず、命令メモリ７は、プログラムカウンタ１０のアドレス情報Ａ０を参照して、アドレスＡ０に格納された命令B_BRANCH (A1,A7),x0を命令レジスタ８に出力し設定する。命令デコーダ９は、命令レジスタ８に設定された命令B_BRANCH (A1,A7),x0を参照し、解読・実行する。この場合、２アドレス２分岐命令なので、まず、入力変数のインデックス（INDEX）をレジスタ・ファイル５内の「入力選択レジスタ」に設定し、レジスタ・ファイル５内の「フラグレジスタ」の「ＦＥＴＣＨビット」を一定期間１に設定する。入力セレクタ３は、「ＦＥＴＣＨビット」を１に設定されると、「入力選択レジスタ」に設定された入力変数ｘ０のインデックス（INDEX）に従って、変数入力バス２のラインの１つを選択し、選択されたラインから入力される入力変数ｘ０を入力レジスタ４に設定する。次に、命令デコーダ９は、入力レジスタ４に設定された入力変数ｘ０の値を参照し、ｘ０が０の場合にはアドレスＡ１をプログラムカウンタ１０に設定し、ｘ０が１の場合にはアドレスＡ７をプログラムカウンタ１０に設定する。
【００４７】
ここでは例として、ｘ０＝１であったとする。この場合、プログラムカウンタ１０にはアドレスＡ７が設定される。
【００４８】
次に、命令メモリ７は、プログラムカウンタ１０のアドレス情報Ａ７を参照して、アドレスＡ７に格納された命令B_BRANCH (A3,A8),x1を命令レジスタ８に出力し設定する。命令デコーダ９は、命令レジスタ８に設定された命令B_BRANCH (A3,A8),x1を参照し、解読・実行する。この場合、２アドレス２分岐命令なので、まず、入力変数ｘ１のインデックス（INDEX）をレジスタ・ファイル５内の「入力選択レジスタ」に設定し、レジスタ・ファイル５内の「フラグレジスタ」の「ＦＥＴＣＨビット」を一定期間１に設定する。入力セレクタ３は、「ＦＥＴＣＨビット」を１に設定されると、「入力選択レジスタ」に設定された入力変数ｘ１のインデックス（INDEX）に従って、変数入力バス２のラインの１つを選択し、選択されたラインから入力される入力変数ｘ１を入力レジスタ４に設定する。次に、命令デコーダ９は、入力レジスタ４に設定された入力変数ｘ１の値を参照し、ｘ１が０の場合にはアドレスＡ３を、ｘ１が１の場合にはアドレスＡ８をプログラムカウンタ１０に設定する。
【００４９】
ここでは例として、ｘ１＝０であったとする。この場合、プログラムカウンタ１０にはアドレスＡ３が設定される。
【００５０】
次に、命令メモリ７は、プログラムカウンタ１０のアドレス情報Ａ３を参照して、アドレスＡ３に格納された命令B_BRANCH (A4,A5),x2を命令レジスタ８に出力し設定する。命令デコーダ９は、命令レジスタ８に設定された命令B_BRANCH (A4,A5),x2を参照し、解読・実行する。この場合、２アドレス２分岐命令なので、まず、入力変数ｘ２のインデックス（INDEX）をレジスタ・ファイル５内の「入力選択レジスタ」に設定し、レジスタ・ファイル５内の「フラグレジスタ」の「ＦＥＴＣＨビット」を一定期間１に設定する。入力セレクタ３は、「ＦＥＴＣＨビット」を１に設定されると、「入力選択レジスタ」に設定された入力変数ｘ２のインデックス（INDEX）に従って、変数入力バス２のラインの１つを選択し、選択されたラインから入力される入力変数ｘ２を入力レジスタ４に設定する。次に、命令デコーダ９は、入力レジスタ４に設定された入力変数ｘ２の値を参照し、ｘ２が０の場合にはアドレスＡ４を、ｘ２が１の場合にはアドレスＡ５をプログラムカウンタ１０に設定する。
【００５１】
ここでは例として、ｘ２＝０であったとする。この場合、プログラムカウンタ１０にはアドレスＡ４が設定される。
【００５２】
次に、命令メモリ７は、プログラムカウンタ１０のアドレス情報Ａ４を参照して、アドレスＡ４に格納された命令DATASET 10,0,A0を命令レジスタ８に出力し設定する。命令デコーダ９は、命令レジスタ８に設定された命令DATASET 10,0,A0を参照し、解読・実行する。この場合、データセット命令なので、まず、レジスタ・ファイル５内のアドレス０にある「出力レジスタ」に出力データ「１０」を出力し設定する。そして、次に、命令デコーダ９は、アドレスＡ０をプログラムカウンタ１０に設定した後、終端節点なのでプログラムの実行を終了する。
【００５３】
（２）図２に示したＱＤＤを実行する場合
図２に示したＱＤＤを実行する場合に命令メモリ７に格納される命令セットのコードは次表の通りである。
【００５４】
【表２】
【００５５】
この命令セットのコードによって各３アドレス４分岐命令（Q_BRANCH）のアドレスを割り当てた結果を図７に示す。
【００５６】
まず、初期状態では、プログラムカウンタ１０にはアドレス情報としてＡ０が設定される。
【００５７】
プログラムの実行が開始されると、まず、命令メモリ７は、プログラムカウンタ１０のアドレス情報Ａ０を参照して、アドレスＡ０に格納された命令Q_BRANCH (A2,A2,A5),X0,00を命令レジスタ８に出力し設定する。命令デコーダ９は、命令レジスタ８に設定された命令Q_BRANCH (A2,A2,A5),X0,00を参照し、解読・実行する。この場合、３アドレス４分岐命令（Q_BRANCH）なので、まず、入力変数ｘ０のインデックス（INDEX）をレジスタ・ファイル５内の「入力選択レジスタ」に設定し、レジスタ・ファイル５内の「フラグレジスタ」の「ＦＥＴＣＨビット」を一定期間１に設定する。入力セレクタ３は、「ＦＥＴＣＨビット」を１に設定されると、「入力選択レジスタ」に設定された入力変数ｘ０のインデックス（INDEX）に従って、変数入力バス２のラインの１つを選択し、選択されたラインから入力される入力変数ｘ０を入力レジスタ４に設定する。次に、命令デコーダ９は、入力レジスタ４に設定された入力変数ｘ０の値を参照し、機能選択フラグ（SEL）が「００」なので、ｘ０が「００」の場合には現在のアドレスＡ０の次のアドレスＡ１を、ｘ０が「０１」の場合にはアドレスＡ２を、ｘ０が「１０」の場合にはアドレスＡ２を、ｘ０が「１１」の場合にはアドレスＡ５をプログラムカウンタ１０に設定する。
【００５８】
ここでは例として、ｘ０＝１１であったとする。この場合、プログラムカウンタ１０にはアドレスＡ５が設定される。
【００５９】
次に、命令メモリ７は、プログラムカウンタ１０のアドレス情報Ａ５を参照して、アドレスＡ５に格納された命令Q_BRANCH (A4,A4,A4),X1,10を命令レジスタ８に出力し設定する。命令デコーダ９は、命令レジスタ８に設定された命令Q_BRANCH (A4,A4,A4),X1,10を参照し、解読・実行する。この場合、３アドレス４分岐命令（Q_BRANCH）なので、まず、入力変数ｘ１のインデックス（INDEX）をレジスタ・ファイル５内の「入力選択レジスタ」に設定し、レジスタ・ファイル５内の「フラグレジスタ」の「ＦＥＴＣＨビット」を一定期間１に設定する。入力セレクタ３は、「ＦＥＴＣＨビット」を１に設定されると、「入力選択レジスタ」に設定された入力変数ｘ１のインデックス（INDEX）に従って、変数入力バス２のラインの１つを選択し、選択されたラインから入力される入力変数ｘ１を入力レジスタ４に設定する。次に、命令デコーダ９は、入力レジスタ４に設定された入力変数ｘ１の値を参照し、機能選択フラグ（SEL）が「１０」なので、ｘ１が「００」の場合にはアドレスＡ４を、ｘ０が「０１」の場合にはアドレスＡ４を、ｘ１が「１０」の場合には現在のアドレスＡ５の次のアドレスＡ６を、ｘ０が「１１」の場合にはアドレスＡ４をプログラムカウンタ１０に設定する。
【００６０】
ここでは例として、ｘ１＝１０であったとする。この場合、プログラムカウンタ１０にはアドレスＡ６が設定される。
【００６１】
次に、命令メモリ７は、プログラムカウンタ１０のアドレス情報Ａ６を参照して、アドレスＡ６に格納された命令B_BRANCH (A3,A3),--を命令レジスタ８に出力し設定する。命令デコーダ９は、命令レジスタ８に設定された命令B_BRANCH (A3,A3),--を参照し、解読・実行する。この場合、命令コードの種類は２アドレス２分岐命令（B_BRANCH）であるが、指定された２つのジャンプ先のアドレスが等しいので、入力変数の値には依存せず、無条件ジャンプ命令となる。従って、命令デコーダ９は、指定されたアドレスＡ３をプログラムカウンタ１０に設定する。
【００６２】
次に、命令メモリ７は、プログラムカウンタ１０のアドレス情報Ａ３を参照して、アドレスＡ３に格納された命令DATASET 10,0,A0を命令レジスタ８に出力し設定する。命令デコーダ９は、命令レジスタ８に設定された命令DATASET 10,0,A0を参照し、解読・実行する。この場合、データセット命令（DATASET）なので、まず、レジスタ・ファイル５内のアドレス「０」にある「出力レジスタ」に出力データ「１０」を出力し設定する。そして、次に、命令デコーダ９は、アドレスＡ０をプログラムカウンタ１０に設定した後、終端節点なのでプログラムの実行を終了する。
【実施例２】
【００６３】
本実施例では、実施例１で説明したＢＭ１を８個直列に接続した多段ブランチング・プログラム・マシン（以下「多段ＢＭ」という。）について説明する。
【００６４】
図８に、実施例２に係る多段ＢＭの構成を表すブロック図である。図８において、ＢＭ１、並びに変数入力バス２、入力セレクタ３、入力レジスタ４、レジスタ・ファイル５、変数出力バス６、命令メモリ７、命令レジスタ８、命令デコーダ９、及びプログラムカウンタ１０は図３と同様のものである。
【００６５】
本実施例の多段ＢＭ２０は、８個のＢＭ１（ＢＭ０〜ＢＭ７）がカスケード接続された構成からなる。
【００６６】
各ＢＭｎの変数出力バス６は、プログラマブル・ルーティング・ボックス２２を介して後段のＢＭｎ＋１の変数入力バス２又は後段のプログラマブル・ルーティング・ボックス２２若しくは出力レジスタ２４に接続されている。また、各ＢＭｎのフラグ出力バス１１は、プログラマブル・ルーティング・ボックス２１を介して後段のＢＭｎ＋１の変数入力バス２又は後段のプログラマブル・ルーティング・ボックス２１若しくはフラグレジスタ２３に接続されている。また、出力レジスタ２４の外部出力バスr_outは、外部回路に接続されると共に、分岐して最前段のＢＭ１の入力バスにカスケード接続されたプログラマブル・ルーティング・ボックス２２に接続されている。また、フラグレジスタ２３の外部出力バスf_outは、外部回路に接続されると共に、分岐して最前段のＢＭ１の入力バスにカスケード接続されたプログラマブル・ルーティング・ボックス２１に接続されている。
【００６７】
各プログラマブル・ルーティング・ボックス２１，２２は、入力配線と出力配線との接続を再構成可能に組み替える接続回路である。各プログラマブル・ルーティング・ボックス２１，２２は、クロスバースイッチ、マルチプレクサ等によって構成される。
【００６８】
また、各プログラマブル・ルーティング・ボックス２１，２２は、コンフィギュレーションを変えることで、前段のＢＭ１の出力と現在のＢＭの出力のビットワイズＡＮＤやビットワイズＯＲ演算ができる。また、定数出力もできる。ビットワイズＡＮＤ演算を行う場合、末端（図８で斜線で示された部分）のプログラマブル・ルーティング・ボックス２１，２２で定数１を生成する。一方、ビットワイズＯＲ演算を行う場合、末端（図８で斜線で示された部分）のプログラマブル・ルーティング・ボックス２１，２２で定数０を生成する。
【００６９】
これにより、各ＢＭｎにおいて演算結果としてレジスタ・ファイル５内の各出力レジスタ及び各状態レジスタに設定された出力変数、並びにフラグレジスタに設定された各フラグは、カスケード接続されたプログラマブル・ルーティング・ボックス２２，２１を経由して、一旦、出力レジスタ２４及びフラグレジスタ２３に格納される。出力レジスタ２４及びフラグレジスタ２３に格納された値は、フードバックされて再び各ＢＭの入力変数バス２に送られる。
【００７０】
また、最前段のＢＭ１の入力バスにカスケード接続されたプログラマブル・ルーティング・ボックス２１，２２には、外部回路からの外部入力バスf_in，r_inも接続されている。従って、これらの外部入力バスf_in，r_inを介して入力される外部入力も、各プログラマブル・ルーティング・ボックス２１，２２を経由して各ＢＭ１にブロードキャストされる。
【００７１】
また、多段ＢＭ２０の出力をフィードバックして各ＢＭ１で参照することもできる。従って、各ＢＭ１を独立に動作させることもできる。
【００７２】
この多段ＢＭ２０では、各ＢＭ１間の通信時間は、レジスタ（フラグレジスタ２３又は出力レジスタ２４）を１つ経由するだけなので、レジスタに値を書き込んだ後、１クロック後に参照可能である。ＢＭ１は１命令の処理に２クロック使用しており、多段ＢＭ２０内であれば命令レベルの通信時間の遅延は発生しない。
【実施例３】
【００７３】
本実施例では、実施例１で説明したＢＭ１を１２８個用いた並列プロセッサ３０について説明する。１２８個のＢＭ１を、実施例２のようにカスケード状に多段接続し、相互に通信可能とした場合、接続回路（プログラマブル・ルーティング・ボックス２１，２２）は非常に大きくなり、現実的ではない。そこで、本実施例では階層的な接続回路を用いる。本実施例では、実施例２で説明したような、ＢＭ１を８台カスケード接続した多段ＢＭ２０を１ユニットとし、この多段ＢＭ２０を１６個並べて階層構造を構成する。
【００７４】
順序回路を模擬する場合には、状態遷移を行うため他の多段ＢＭ２０を参照する。この際、各多段ＢＭ２０間の接続には、プログラマブル接続回路３１を用いる。前述したように、各多段ＢＭ２０内のＢＭ１間の通信は１クロックで行うことができる。一方、異なる多段ＢＭ２０間の通信は、４クロック必要となる。
【００７５】
図９は、実施例３に係る並列プロセッサ３０の構成を表すブロック図である。並列プロセッサ３０は、１６個の多段ＢＭ２０（８−ＢＭ＿０〜８−ＢＭ＿１５）、プログラマブル接続回路３１、ビットワイズＡＮＤ／ＯＲ回路３２、及びＡＣＴ積演算回路３３を備えている。
【００７６】
各多段ＢＭ２０の出力レジスタ２４の外部出力バスr_outは、プログラマブル接続回路３１の入力側に接続されている。また、各多段ＢＭ２０の最前段のプログラマブル・ルーティング・ボックス２２の外部入力バスr_inは、プログラマブル接続回路３１の出力側に接続されている。
【００７７】
プログラマブル接続回路３１は、入力側に接続されるバスの各配線と出力側に接続されるバスの各配線との接続順序を再構成可能に切り替える接続回路である。プログラマブル接続回路３１は、複雑な信号選択を行うため、多段のマルチプレクサによって構成される。従って、単純な構成ではこのプログラマブル接続回路３１がクリティカルパスとなり、並列プロセッサ３０全体の動作周波数が極端に低下する。そこで、プログラマブル接続回路３１内にはパイプライン・レジスタを挿入し、動作周波数を向上させるように構成する。但し、パイプライン・レジスタを挿入するため、プログラマブル接続回路３１の出力を確定させるためには４クロック必要である。並列プロセッサ３０では１命令につき２クロック使用しているため、プログラマブル接続回路３１を通してデータを転送するには２命令待つ必要がある。
【００７８】
各多段ＢＭ２０のフラグレジスタ２３の外部出力バスf_outは、ビットワイズＡＮＤ／ＯＲ回路３２の入力側に接続されている。また、各多段ＢＭ２０の最前段のプログラマブル・ルーティング・ボックス２１の外部入力バスf_inは、ビットワイズＡＮＤ／ＯＲ回路３２の出力側に接続されている。
【００７９】
ビットワイズＡＮＤ／ＯＲ回路３２は、入力側に接続されるバスの各配線と出力側に接続されるバスの各配線との接続順序を再構成可能に切り替えるとともに、コンフィギュレーションを変えることで、各多段ＢＭ２０の出力するフラグ間のビットワイズＡＮＤやビットワイズＯＲ演算ができるように構成した接続回路である。
【００８０】
また、各多段ＢＭ２０のフラグレジスタ２３の外部出力バスf_outの中の出力線f_out[12]は、プログラマブル接続回路３１を活性化するＡＣＴフラグとして使用されている。各多段ＢＭ２０の出力線f_out[12]は、ＡＣＴ積演算回路３３に接続されている。ＡＣＴ積演算回路３３はこれらのＡＣＴフラグのＡＮＤ演算を行い、ＡＣＴ信号を生成する。このＡＣＴ信号はプログラマブル接続回路３１のＡＣＴ入力端子に入力される。プログラマブル接続回路３１はＡＣＴ信号が１のときに活性化され、前回の活性時に確定した値を保持する。
【符号の説明】
【００８１】
１ ブランチング・プログラム・マシン
２ 変数入力バス
３ 入力セレクタ
４ 入力レジスタ
５ レジスタ・ファイル
６ 変数出力バス
７ 命令メモリ
８ 命令レジスタ
９ 命令デコーダ
１０ プログラムカウンタ
１１ フラグ出力バス
２０ 多段ブランチング・プログラム・マシン
２１ プログラマブル・ルーティング・ボックス
２２ プログラマブル・ルーティング・ボックス
２３ フラグレジスタ
２４ 出力レジスタ
３０ 並列プロセッサ
３１ プログラマブル接続回路
３２ ビットワイズＡＮＤ／ＯＲ回路
３３ ＡＣＴ積演算回路
【技術分野】
【０００１】
本発明は、多値論理決定グラフ（ＭＤＤ：Multiple-valued Decision Diagram）を模擬する演算が可能なブランチング・プログラム・マシン（ＢＭ：Branching Program Machine）及びブランチング・プログラム・マシンを並列に接続した多段ブランチング・プログラム・マシン（多段ブランチング・プログラム・マシン）、並びに多段ブランチング・プログラム・マシンを並列に接続した並列プロセッサに関する。
【背景技術】
【０００２】
二分決定グラフ（以下「ＢＤＤ（Binary Decision Diagram）」という。）を模擬するブランチング・プログラム・マシンは、分岐命令と出力命令の２種類の命令を有するプロセッサである（非特許文献１，２参照）。従って、ブランチング・プログラム・マシンは、汎用プロセッサに比べてアーキテクチャが単純である。また、制御回路などに於いて多く用いられる条件分岐を、専用命令で実行するため、特定のアプリケーションに於いては汎用プロセッサよりも高速の処理が可能となる。ブランチング・プログラム・マシンのアプリケーションは、制御回路、回路シミュレータ、ネットワーク機器の経路表やパケット分類、及びパターンマッチングなどが挙げられる。従来のブランチング・プログラム・マシンとしては、２値の入力変数に対するＢＤＤを模擬するものが知られている（非特許文献１，２参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】P. C. Baracos, R. D. Hudson, L. J. Vroomen, and P. J. A. Zsombor-Murray, "Advances in binary decision based programmable controllers," IEEE Transactions on Industrial Electornics, Vol. 35, No. 3, pp. 417-425, Aug., 1988.
【非特許文献２】R. T. Boute, "The binary-decision machine as programmable controller," Euromicro Newsletter, Vol. 1, No. 2, pp. 16-22, 1976.
【非特許文献３】R. E. Bryant, "Graph-based algorithms for boolean function manipulation," IEEE Trans. Comput., Vol. C-35, No. 8, pp. 677-691, Aug. 1986.
【非特許文献４】Y. Iguchi, T. Sasao, and M. Matsuura, "Evaluation of multiple-output logic functions," Asia and South Pacific Design Automation Conference'2003, Kitakyushu, Japan, pp. 312-315, Jan. 21-24, 2003.
【非特許文献５】T. Kam, T. Villa, R. K. Brayton, and A. L. Sagiovanni-Vincentelli, "Multi-valued decision diagrams: Theory and Applications," Multiple-Valued Logic, Vol. 4, No. 1-2, pp. 9-62, 1998.
【非特許文献６】Y. Iguchi, T. Sasao, and M. Matsuura, "Implementation of multiple-output functions using PROMDDs," 30th International Symposium on Mulitple-Valued Logic, Portland, Oreon, U.S.A, pp. 199-205, May 23-25 2000.
【非特許文献７】S. Nagayama, T. Sasao, Y. Iguchi, and M. Matsuura, "Area-time complexities of multi-valued decision diagrams," IEICE Transactions on Fundamentals of Electronics, Vol. E87-A, No. 5, pp. 1020-1028, May 2004.
【非特許文献８】S. Nagayama, and T. Sasao, "On the optimization of heterogeneous MDDs," IEEE Transactions on CAD, Vol. 24, No. 11, pp. 1645-1659, Nov. 2005.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
任意のｎ入力論理関数はＢＤＤにより表現することができる（非特許文献３）。多出力論理関数を表現するＢＤＤはＭＴＢＤＤ（multi-terminal binary decision diagram）と呼ばれ、高々ｎ回のテーブル参照で多出力を同時に評価することができる（非特許文献４）。図１にＭＴＢＤＤの例を示す。テーブル参照の回数の平均値を平均パス長という。ＢＤＤの評価時間は平均パス長に比例する。
【０００５】
ところで、ＢＤＤの評価時間を更に削減する方法として、多値論理決定グラフ（以下「ＭＤＤ（Multiple-valued Decision Diagram）」という。）を用いる方法が知られている（非特許文献５参照）。ＭＤＤでは、入力変数はｋ個の２値変数の組に分割される。ｋ個の２値変数の組は２ｋ値の超変数となる。２ｋ値の超変数で表現した決定グラフをＭＤＤ（ｋ）と記す。ＢＤＤはＭＤＤ（１）と等価である。
【０００６】
ＭＤＤ（２）は各節点が４分岐を持つので、本稿に於いてはＭＤＤ（２）をＱＤＤ（Quaternary Decision Diagram）という。入力変数を組み分けした際の各組の２値変数の個数がすべて等しいＭＤＤを「ホモジニアスＭＤＤ」という。一方、各組の２値変数の個数がすべて等しくはないＭＤＤを「ヘテロジニアスＭＤＤ」という。
【０００７】
ヘテロジニアスＭＤＤは、変数の組み分け（グルーピング）を工夫することによって、ホモジニアスＭＤＤよりもテーブル参照回数と節点数を削減することができる（非特許文献８参照）。以下、本稿ではヘテロジニアスＭＴＱＤＤ（multi-terminal Quaternary Decision Diagram）を単にＱＤＤと呼ぶ。図２に、図１のＭＴＢＤＤを変換して得られたＱＤＤを示す。図２のＱＤＤは、最上位の節点のみが２分岐であり、他の節点は４分岐となっている。
【０００８】
論理関数をＭＤＤ（ｋ）で表現すると、ＢＤＤで表現した場合に比べてメモリの参照回数をしばしば１／ｋまで削減することができる（非特許文献６）。従って、ｋを増加させると、論理関数の評価時間を短縮することができる。しかしながら、１つの節点を表現するために必要なメモリ量は２ｋのオーダーで増加する。そのため、多くのベンチマーク関数に於いて、ｋ＝２のときのＭＤＤ（ｋ）の総メモリー量が最小となる（非特許文献７参照）。従って、論理関数の評価に於いては、ＢＤＤよりもＱＤＤの方がより適しているといえる。
【０００９】
そこで、本発明の目的は、かかるＱＤＤを模擬する演算を実行することが可能なブランチング・プログラム・マシンを提供することにある。また、本発明の目的は、さらなる高速化のため、ブランチング・プログラム・マシンを並列に接続した多段ブランチング・プログラム・マシン、並びに多段ブランチング・プログラム・マシンを並列に接続した並列プロセッサを提供することにある。
【課題を解決するための手段】
【００１０】
本発明に係るブランチング・プログラム・マシンは、複数の入力変数が入力される変数入力バスと、
前記変数入力バスから入力変数を選択する入力セレクタと、
前記入力セレクタにより選択される入力変数が一時的に設定される入力レジスタと、
出力変数が設定される出力レジスタと、
前記出力レジスタに設定された出力変数が出力される変数出力バスと、
プログラムにおいて実行する各命令が記憶された命令メモリと、
命令メモリから順次読み出される命令が一時的に設定される命令レジスタと、
入力レジスタから読み出される入力変数と、命令レジスタから読み出される命令とに基づいて当該命令を実行する命令デコーダと、
次に読み出す命令の命令メモリ内のアドレス情報を記憶するプログラムカウンタと、
を備えたブランチング・プログラム・マシンであって、
前記命令メモリには、（１）参照する入力変数のインデックス、入力変数が０のときにジャンプする先の命令メモリのアドレス情報、及び入力変数が１のときにジャンプする先の命令メモリのアドレス情報を含む２アドレス２分岐命令、（２）参照する入力変数のインデックス、入力変数が第１の値のときにジャンプする先の命令メモリのアドレス情報、入力変数が第２の値のときにジャンプする先の命令メモリのアドレス情報、及び入力変数が第３の値のときにジャンプする先の命令メモリのアドレス情報を含む３アドレス４分岐命令、並びに、（３）出力先の出力レジスタのアドレス情報、及び出力データを含む出力命令の３種の命令を少なくとも含む命令系列が記憶され、前記プログラムカウンタに設定されたアドレス情報に従って該アドレス情報で指令されるアドレスに格納された命令を前記命令レジスタに出力するものであり、
前記命令デコーダは、（ａ）前記命令レジスタに設定された命令が前記２アドレス２分岐命令又は前記３アドレス４分岐命令の場合、当該命令で指定される入力変数のインデックスに基づき前記入力セレクタにより入力変数を選択して前記入力レジスタに設定し該入力レジスタに設定される入力変数の値に基づいて、当該命令で指定されるジャンプする先の命令メモリのアドレス情報を選択して前記プログラムカウンタに設定する処理を実行し、（ｂ）前記命令レジスタに設定された命令が前記出力命令の場合、当該命令で指定される出力レジスタのアドレス情報に従って該アドレス情報で指令される前記出力レジスタのアドレスに、当該命令で指定される出力データを設定する処理を実行することを特徴とする。
【００１１】
この構成により、ＱＤＤを模擬する演算を実行することが可能となる。
【００１２】
また、本発明に於いては、前記命令メモリに記憶された３アドレス４分岐命令は、参照する入力変数のインデックス、入力変数の値に対する分岐先アドレスの組み合わせを指定する機能選択フラグ、入力変数が第１の値のときにジャンプする先の命令メモリのアドレス情報ADDR0、入力変数が第２の値のときにジャンプする先の命令メモリのアドレス情報ADDR1、及び入力変数が第３の値のときにジャンプする先の命令メモリのアドレス情報ADDR2を含み、前記命令デコーダは、前記命令レジスタに設定された命令が前記３アドレス４分岐命令の場合には、当該命令で指定される入力変数のインデックスに基づき前記入力セレクタにより入力変数を選択して前記入力レジスタに設定し、該入力レジスタに設定される入力変数の値が前記第１，第２，第３の値の場合、それぞれ、当該命令で指定されるジャンプする先の命令メモリの前記アドレス情報ADDR0，ADDR1，ADDR2を選択し、該入力レジスタに設定される入力変数の値が前記第１，第２，又は第３の値以外の場合、現在の命令のアドレスPの次のアドレス(P+1)のアドレス情報を選択して前記プログラムカウンタに設定する処理を実行するようにすることもできる。
【００１３】
本発明に係る多段ブランチング・プログラム・マシンは、前記のブランチング・プログラム・マシンが直列に接続され、後段の前記ブランチング・プログラム・マシンの変数入力バスの少なくとも一部には、前段の前記ブランチング・プログラム・マシンの前記変数出力バスが接続され、残りの変数入力バスには入力変数が入力されることを特徴とする。
【００１４】
このようにブランチング・プログラム・マシンを多段に直列に接続することで、より大きな論理関数の演算を行うことができる。
【００１５】
また、本発明に於いて、前記各ブランチング・プログラム・マシンの前記変数出力バスは、プログラマブル・ルーティング・ボックスを介して後段のブランチング・プログラム・マシンの前記変数入力バスに接続された構成とすることができる。
【００１６】
これにより、各段のブランチング・プログラム・マシンの出力変数の順序を自由に組み替えて後段のブランチング・プログラム・マシンの入力変数として入力することができる。従って、順序回路を実現するための各段のブランチング・プログラム・マシンの命令のコーディングが容易となる。
【００１７】
本発明に係る並列プロセッサは、複数個並列に接続された上述の多段ブランチング・プログラム・マシンと、
複数の選択入力ノードと複数の選択出力ノードとを備え、前記各多段ブランチング・プログラム・マシンの前記各変数出力バスが前記各選択入力ノードに接続され、選択出力ノードの少なくとも一部が前記各多段ブランチング・プログラム・マシンの変数入力バスの一部に接続され、前記各選択入力ノードと前記各選択出力ノードとの接続を組み替え可能としたプログラマブル相互接続回路と、を備えたことを特徴とする。
【００１８】
これにより、並列演算が可能となり、論理関数の演算速度を更に速めることができる。
【発明の効果】
【００１９】
以上のように、本発明のブランチング・プログラム・マシンによれば、ＱＤＤを模擬する演算を実行することが可能となる。また、本発明の多段ブランチング・プログラム・マシンによれば、多段化することでより大きな論理関数の演算を行うことが可能となる。また、本発明に係る並列プロセッサによれば、並列演算により論理関数の演算速度を更に速めることができる。
【図面の簡単な説明】
【００２０】
【図１】ＭＴＢＤＤの例である。
【図２】図１のＭＴＢＤＤを変換して得られたＱＤＤである。
【図３】本発明の実施例１に係るブランチング・プログラム・マシンの構成を表すブロック図である。
【図４】図３の出力レジスタを構成するダブルランク・フリップフロップを示す図である。
【図５】各命令のニーモニックとメモリ内部表現を示す図である。
【図６】４種の３アドレス４分岐命令における分岐先アドレスの組み合わせを示す図である。
【図７】図５の命令セットのコードによって各３アドレス４分岐命令（Q_BRANCH）のアドレスを割り当てた結果である。
【図８】実施例２に係る多段ブランチング・プログラム・マシンの構成を表すブロック図である。
【図９】実施例３に係る並列プロセッサ３０の構成を表すブロック図である。
【発明を実施するための形態】
【００２１】
以下、本発明を実施するための形態について、図面を参照しながら説明する。
【実施例１】
【００２２】
図３は、本発明の実施例１に係るブランチング・プログラム・マシン（以下、略して「ＢＭ」という。）の構成を表す図である。
【００２３】
ＢＭ１は、変数入力バス２、入力セレクタ３、入力レジスタ４、レジスタ・ファイル５、変数出力バス６、命令メモリ７、命令レジスタ８、命令デコーダ９、プログラムカウンタ１０、及びフラグ出力バス１１を備えている。
【００２４】
変数入力バス２は、ＭＰＵなどの外部回路から複数の入力変数が入力されるバスである。入力セレクタ３は、変数入力バス２から入力される入力変数を選択するセレクタである。入力セレクタ３としては、シフタ、クロスバースイッチ、マルチプレクサ等が使用される。入力レジスタ４は、入力セレクタ３により選択される入力変数が一時的に設定されるレジスタである。
【００２５】
命令メモリ７は、プログラムにおいて実行する各命令が記憶されたメモリである。本実施例では、命令メモリ７は、語長が３２ビットのＢＭ命令を２５６個格納することができる。命令レジスタ８は、命令メモリ７から順次読み出される命令が一時的に設定されるレジスタである。命令デコーダ９は、命令メモリ７から命令レジスタ８へ読み出された命令を解釈し、実行を行うデコーダである。この命令デコーダ９は、入力レジスタ４へ設定される入力変数と、命令レジスタ８へ設定される命令とに基づいて当該命令を実行する。プログラムカウンタ１０は、次に読み出す命令の命令メモリ７内のアドレス情報を記憶する。
【００２６】
ここで、命令メモリ７には、２アドレス２分岐命令（B_BRANCH）、３アドレス４分岐命令（Q_BRANCH）、データセット命令（出力命令）（DATASET）、及び無条件ジャンプ命令の４種類の命令セットからなる命令系列が記憶されている。２アドレス２分岐命令（B_BRANCH）、３アドレス４分岐命令（Q_BRANCH）、及び無条件ジャンプ命令は、ＭＴＢＤＤ又はＱＤＤの非終端節点を評価する命令であり、データセット命令（DATASET）はＱＤＤの終端節点を評価する命令である。図５に各命令のニーモニックとメモリ内部表現を示す。
【００２７】
尚、１命令の長さを削減するために、２アドレス２分岐命令（B_BRANCH）に代わる１アドレス２分岐命令も提案されているが（例えば、非特許文献２参照）、１アドレス方式を用いると実行時間がしばしば増加する。そこで、本発明に於いては２アドレス方式の２分岐命令を採用している。
【００２８】
また、ＱＤＤにおいて、２変数を２個同時に評価する命令は、４アドレス４分岐命令によって実現できる。４アドレス４分岐命令は２分岐命令に比べて評価時間を半分に削減することができる。しかしながら、４アドレス４分岐命令は長い命令語を必要とし、現在の組み込みプロセッサの標準的な語長（３２ビット）には適していない。そこで、本発明では４アドレス４分岐命令の代わりに３アドレス４分岐命令（Q_BRANCH）を採用している。
【００２９】
図５（ａ）は２アドレス２分岐命令（B_BRANCH）である。２アドレス２分岐命令（B_BRANCH）は、２つの分岐先アドレスのうち、１つのアドレスにジャンプする命令である。２アドレス２分岐命令は、参照する入力変数のインデックス（INDEX）、入力変数が０のときにジャンプする先の命令メモリのアドレス情報（ADDR0）、及び入力変数が１のときにジャンプする先の命令メモリのアドレス情報（ADDR1）を含む。インデックス（INDEX）で指定された変数の値が０であればアドレス情報（ADDR0）に指定されたアドレスにジャンプし、そうでなければアドレス情報（ADDR1）に指定されたアドレスにジャンプする。本実施例では、図５（ａ）に示すように、アドレス情報（ADDR0），（ADDR1）は８ビット、入力変数のインデックス（INDEX）は６ビットで表現する。また、２アドレス２分岐命令（B_BRANCH）のメモリ内部表現における２９−３１ビットに格納されたコード「１１１」は、この命令が２アドレス２分岐命令（B_BRANCH）であることを表す命令識別コードである。
【００３０】
図５（ｂ）はデータセット命令（DATASET）である。データセット命令（DATASET）は指定されたデータを指定された出力レジスタに出力する命令である。データセット命令（DATASET）は、出力先の出力レジスタのアドレス情報（REG）、出力データ（DATA）、及び命令実行後にジャンプする先の命令メモリのアドレス情報（ADDR）を含む。本実施例では、図５（ｂ）に示すように、出力データ（DATA）は１６ビット、アドレス情報（ADDR）は８ビット、出力レジスタのアドレス情報（REG）は６ビットで表現する。また、データセット命令（DATASET）のメモリ内部表現における３０−３１ビットに格納されたコード「１０」は、この命令がデータセット命令（DATASET）であることを表す命令識別コードである。
【００３１】
図５（ｃ）は３アドレス４分岐命令（Q_BRANCH）である。３アドレス４分岐命令（Q_BRANCH）は、４つの分岐先アドレスのうち、１つのアドレスにジャンプする命令である。３アドレス４分岐命令（Q_BRANCH）は、参照する入力変数のインデックス（INDEX）、入力変数の値に対する分岐先アドレスの組み合わせを指定する機能選択フラグ（SEL）、入力変数が第１の値のときにジャンプする先の命令メモリのアドレス情報（ADDR0）、入力変数が第２の値のときにジャンプする先の命令メモリのアドレス情報（ADDR1）、及び入力変数が第３の値のときにジャンプする先の命令メモリのアドレス情報（ADDR2）を含む。本実施例では、図５（ｃ）に示すように、アドレス情報（ADDR0），（ADDR1），（ADDR2）は８ビット、入力変数のインデックス（INDEX）は５ビット、機能選択フラグ（SEL）は２ビットの合計３１ビットで表現する。また、３アドレス４分岐命令（Q_BRANCH）のメモリ内部表現における３１ビットに格納されたコード「０」は、この命令が３アドレス４分岐命令（Q_BRANCH）であることを表す命令識別コードである。
【００３２】
３アドレス４分岐命令（Q_BRANCH）において、４つの分岐先アドレスのうちの３つのアドレスは、アドレス情報（ADDR0, ADDR1, ADDR2）により指定される。残り１つの分岐先アドレスは、現在の命令のアドレス（PC）の次のアドレス（PC+1）とする。
【００３３】
本発明に於いては、評価時間とステップ数の削減のため、図６に示すような４種の３アドレス４分岐命令を用いる。３アドレス４分岐命令（Q_BRANCH）内の機能選択フラグ（SEL）は、４種の３アドレス４分岐命令のうちの１つを指定するフラグである。入力変数のインデックス（INDEX）で指定された変数をｉとすると、SEL＝iのときに次のアドレス（PC+1）にジャンプする。アドレスの割り付けを工夫することによって、ステップ数や実行時間を最適化することができる。
【００３４】
尚、３アドレス４分岐命令（Q_BRANCH）を使用する場合、現在の命令アドレス（PC）の次のアドレス（PC+1）が、他の３アドレス４分岐命令（Q_BRANCH）のPC+1と競合する場合が生じる。従って、かかる競合を避けるため、無条件ジャンプ命令が必要となる。無条件ジャンプ命令は、強制的に指定されたアドレスにジャンプする命令である。この無条件ジャンプ命令は、上述の２アドレス２分岐命令（B_BRANCH）を用いて実現される。無条件ジャンプ命令の場合、インデックス（INDEX）には無効値（例えば「０」）が設定され、アドレス情報（ADDR0）及びアドレス情報（ADDR1）には同じジャンプ先のアドレスが設定される。これにより、無条件ジャンプ命令が実行されると、入力変数の値を評価することなく、無条件にアドレス情報（ADDR0），（ADDR1）に設定されたアドレスにジャンプする。
【００３５】
図３の命令デコーダ９は、命令レジスタ８に設定された命令が２アドレス２分岐命令（B_BRANCH）又は３アドレス４分岐命令（Q_BRANCH）の場合、当該命令で指定される入力変数のインデックス（INDEX）に基づき入力セレクタ３により入力変数を選択して入力レジスタ４に設定し、入力レジスタ４に設定される入力変数の値（｛０，１｝又は｛００，０１，１０，１１｝）に基づいて、当該命令で指定されるジャンプする先の命令メモリのアドレス情報（（ADDR0），（ADDR1），（ADDR2））を選択してプログラムカウンタ１０に設定する処理を実行する。また、命令レジスタ８に設定された命令がデータセット命令（DATASET）の場合、当該命令で指定される出力レジスタのアドレス情報（REG）で指令されるレジスタ・ファイル５内の出力レジスタに、当該命令で指定される出力データ（DATA）を設定する処理を実行し、当該命令で指定されるジャンプする先の命令メモリのアドレス情報（ADDR）を選択してプログラムカウンタ１０に設定する処理を実行する。
【００３６】
図３のレジスタ・ファイル５は、「出力レジスタ」や「状態レジスタ」、及び「入力選択レジスタ」や「フラグレジスタ」と呼ばれるレジスタで構成される。出力レジスタ及び状態レジスタは、出力変数が設定されるレジスタである。出力レジスタ及び状態レジスタは、図４に示したようなダブルランク・フリップフロップにより構成されている。
【００３７】
図４において、Ｌ１，Ｌ２はＤラッチである。出力レジスタや状態レジスタはデータセット命令によって更新されるが、このデータセット命令は１６ビット毎にしか値を更新することができない。そのため、１６ビットよりもビット数の大きな出力や状態変数を持つ回路を評価する場合、前後の状態の値が混ざってしまうという問題が生じる。そこで、このダブルランク・フリップフロップを用いて、状態遷移信号（S_Clock）がＨｉｇｈのときに一度に値を更新する。
【００３８】
入力選択レジスタには、入力セレクタ３が入力レジスタ４に設定する変数を選択するための入力選択信号（ＩＳＲ）が設定される。
【００３９】
フラグレジスタは、ＢＭ１の動作を指定する特殊なレジスタである。フラグレジスタは、「ＲＵＮビット」、「ＩＲＱビット」、「ＲＣＯＰＹビット」、「ＡＣＴビット」、及び「ＦＥＴＣＨビット」を有し、各ビットはそれぞれ以下のような固有の役割を持つ。
（１）「ＲＵＮビット」は、１のときのみＢＭ１のプログラムカウンタ１０の更新が行われる。
（２）「ＩＲＱビット」は、１のとき割り込み信号が外部に送られる。
（３）「ＲＣＯＰＹビット」は、１のときダブルランク・フリップフロップのデータ転送が行われる。
（４）「ＡＣＴビット」は、１のとき後述するＢＭ１を接続する回路を起動する。
（５）「ＦＥＴＣＨビット」は１のとき入力レジスタ４に値が取り込まれる。
【００４０】
変数出力バス６は、レジスタ・ファイル５内の出力レジスタや状態レジスタに設定された出力変数及び状態変数が出力されるバスである。また、フラグ出力バス１１は、レジスタ・ファイル５内のフラグレジスタに設定された各フラグが出力されるバスである。
【００４１】
ＢＭ１は、出力レジスタに設定された出力変数を入力レジスタ４にフィードバックして順序回路を実現することができる。入力レジスタ４には、これらのフィードバックされた値や外部入力や隣接するＢＭ１から送られてくる出力変数が設定される。これらは、入力選択レジスタの値を用いて、入力セレクタ３が選択する。
【００４２】
以上のように構成された本実施例に係るＢＭ１について、以下その動作を説明する。ここでは簡単な具体例として、図１に示したＭＴＢＤＤを実行する場合と、図２に示したＱＤＤを実行する場合とを採り上げてＢＭ１の動作を説明することにする。
【００４３】
（１）図１に示したＭＴＢＤＤを実行する場合
図１に示したＭＴＢＤＤを実行する場合に命令メモリ７に格納される命令セットのコードは次表の通りである。
【００４４】
【表１】
【００４５】
まず、初期状態では、プログラムカウンタ１０にはアドレス情報としてＡ０が設定される。
【００４６】
プログラムの実行が開始されると、まず、命令メモリ７は、プログラムカウンタ１０のアドレス情報Ａ０を参照して、アドレスＡ０に格納された命令B_BRANCH (A1,A7),x0を命令レジスタ８に出力し設定する。命令デコーダ９は、命令レジスタ８に設定された命令B_BRANCH (A1,A7),x0を参照し、解読・実行する。この場合、２アドレス２分岐命令なので、まず、入力変数のインデックス（INDEX）をレジスタ・ファイル５内の「入力選択レジスタ」に設定し、レジスタ・ファイル５内の「フラグレジスタ」の「ＦＥＴＣＨビット」を一定期間１に設定する。入力セレクタ３は、「ＦＥＴＣＨビット」を１に設定されると、「入力選択レジスタ」に設定された入力変数ｘ０のインデックス（INDEX）に従って、変数入力バス２のラインの１つを選択し、選択されたラインから入力される入力変数ｘ０を入力レジスタ４に設定する。次に、命令デコーダ９は、入力レジスタ４に設定された入力変数ｘ０の値を参照し、ｘ０が０の場合にはアドレスＡ１をプログラムカウンタ１０に設定し、ｘ０が１の場合にはアドレスＡ７をプログラムカウンタ１０に設定する。
【００４７】
ここでは例として、ｘ０＝１であったとする。この場合、プログラムカウンタ１０にはアドレスＡ７が設定される。
【００４８】
次に、命令メモリ７は、プログラムカウンタ１０のアドレス情報Ａ７を参照して、アドレスＡ７に格納された命令B_BRANCH (A3,A8),x1を命令レジスタ８に出力し設定する。命令デコーダ９は、命令レジスタ８に設定された命令B_BRANCH (A3,A8),x1を参照し、解読・実行する。この場合、２アドレス２分岐命令なので、まず、入力変数ｘ１のインデックス（INDEX）をレジスタ・ファイル５内の「入力選択レジスタ」に設定し、レジスタ・ファイル５内の「フラグレジスタ」の「ＦＥＴＣＨビット」を一定期間１に設定する。入力セレクタ３は、「ＦＥＴＣＨビット」を１に設定されると、「入力選択レジスタ」に設定された入力変数ｘ１のインデックス（INDEX）に従って、変数入力バス２のラインの１つを選択し、選択されたラインから入力される入力変数ｘ１を入力レジスタ４に設定する。次に、命令デコーダ９は、入力レジスタ４に設定された入力変数ｘ１の値を参照し、ｘ１が０の場合にはアドレスＡ３を、ｘ１が１の場合にはアドレスＡ８をプログラムカウンタ１０に設定する。
【００４９】
ここでは例として、ｘ１＝０であったとする。この場合、プログラムカウンタ１０にはアドレスＡ３が設定される。
【００５０】
次に、命令メモリ７は、プログラムカウンタ１０のアドレス情報Ａ３を参照して、アドレスＡ３に格納された命令B_BRANCH (A4,A5),x2を命令レジスタ８に出力し設定する。命令デコーダ９は、命令レジスタ８に設定された命令B_BRANCH (A4,A5),x2を参照し、解読・実行する。この場合、２アドレス２分岐命令なので、まず、入力変数ｘ２のインデックス（INDEX）をレジスタ・ファイル５内の「入力選択レジスタ」に設定し、レジスタ・ファイル５内の「フラグレジスタ」の「ＦＥＴＣＨビット」を一定期間１に設定する。入力セレクタ３は、「ＦＥＴＣＨビット」を１に設定されると、「入力選択レジスタ」に設定された入力変数ｘ２のインデックス（INDEX）に従って、変数入力バス２のラインの１つを選択し、選択されたラインから入力される入力変数ｘ２を入力レジスタ４に設定する。次に、命令デコーダ９は、入力レジスタ４に設定された入力変数ｘ２の値を参照し、ｘ２が０の場合にはアドレスＡ４を、ｘ２が１の場合にはアドレスＡ５をプログラムカウンタ１０に設定する。
【００５１】
ここでは例として、ｘ２＝０であったとする。この場合、プログラムカウンタ１０にはアドレスＡ４が設定される。
【００５２】
次に、命令メモリ７は、プログラムカウンタ１０のアドレス情報Ａ４を参照して、アドレスＡ４に格納された命令DATASET 10,0,A0を命令レジスタ８に出力し設定する。命令デコーダ９は、命令レジスタ８に設定された命令DATASET 10,0,A0を参照し、解読・実行する。この場合、データセット命令なので、まず、レジスタ・ファイル５内のアドレス０にある「出力レジスタ」に出力データ「１０」を出力し設定する。そして、次に、命令デコーダ９は、アドレスＡ０をプログラムカウンタ１０に設定した後、終端節点なのでプログラムの実行を終了する。
【００５３】
（２）図２に示したＱＤＤを実行する場合
図２に示したＱＤＤを実行する場合に命令メモリ７に格納される命令セットのコードは次表の通りである。
【００５４】
【表２】
【００５５】
この命令セットのコードによって各３アドレス４分岐命令（Q_BRANCH）のアドレスを割り当てた結果を図７に示す。
【００５６】
まず、初期状態では、プログラムカウンタ１０にはアドレス情報としてＡ０が設定される。
【００５７】
プログラムの実行が開始されると、まず、命令メモリ７は、プログラムカウンタ１０のアドレス情報Ａ０を参照して、アドレスＡ０に格納された命令Q_BRANCH (A2,A2,A5),X0,00を命令レジスタ８に出力し設定する。命令デコーダ９は、命令レジスタ８に設定された命令Q_BRANCH (A2,A2,A5),X0,00を参照し、解読・実行する。この場合、３アドレス４分岐命令（Q_BRANCH）なので、まず、入力変数ｘ０のインデックス（INDEX）をレジスタ・ファイル５内の「入力選択レジスタ」に設定し、レジスタ・ファイル５内の「フラグレジスタ」の「ＦＥＴＣＨビット」を一定期間１に設定する。入力セレクタ３は、「ＦＥＴＣＨビット」を１に設定されると、「入力選択レジスタ」に設定された入力変数ｘ０のインデックス（INDEX）に従って、変数入力バス２のラインの１つを選択し、選択されたラインから入力される入力変数ｘ０を入力レジスタ４に設定する。次に、命令デコーダ９は、入力レジスタ４に設定された入力変数ｘ０の値を参照し、機能選択フラグ（SEL）が「００」なので、ｘ０が「００」の場合には現在のアドレスＡ０の次のアドレスＡ１を、ｘ０が「０１」の場合にはアドレスＡ２を、ｘ０が「１０」の場合にはアドレスＡ２を、ｘ０が「１１」の場合にはアドレスＡ５をプログラムカウンタ１０に設定する。
【００５８】
ここでは例として、ｘ０＝１１であったとする。この場合、プログラムカウンタ１０にはアドレスＡ５が設定される。
【００５９】
次に、命令メモリ７は、プログラムカウンタ１０のアドレス情報Ａ５を参照して、アドレスＡ５に格納された命令Q_BRANCH (A4,A4,A4),X1,10を命令レジスタ８に出力し設定する。命令デコーダ９は、命令レジスタ８に設定された命令Q_BRANCH (A4,A4,A4),X1,10を参照し、解読・実行する。この場合、３アドレス４分岐命令（Q_BRANCH）なので、まず、入力変数ｘ１のインデックス（INDEX）をレジスタ・ファイル５内の「入力選択レジスタ」に設定し、レジスタ・ファイル５内の「フラグレジスタ」の「ＦＥＴＣＨビット」を一定期間１に設定する。入力セレクタ３は、「ＦＥＴＣＨビット」を１に設定されると、「入力選択レジスタ」に設定された入力変数ｘ１のインデックス（INDEX）に従って、変数入力バス２のラインの１つを選択し、選択されたラインから入力される入力変数ｘ１を入力レジスタ４に設定する。次に、命令デコーダ９は、入力レジスタ４に設定された入力変数ｘ１の値を参照し、機能選択フラグ（SEL）が「１０」なので、ｘ１が「００」の場合にはアドレスＡ４を、ｘ０が「０１」の場合にはアドレスＡ４を、ｘ１が「１０」の場合には現在のアドレスＡ５の次のアドレスＡ６を、ｘ０が「１１」の場合にはアドレスＡ４をプログラムカウンタ１０に設定する。
【００６０】
ここでは例として、ｘ１＝１０であったとする。この場合、プログラムカウンタ１０にはアドレスＡ６が設定される。
【００６１】
次に、命令メモリ７は、プログラムカウンタ１０のアドレス情報Ａ６を参照して、アドレスＡ６に格納された命令B_BRANCH (A3,A3),--を命令レジスタ８に出力し設定する。命令デコーダ９は、命令レジスタ８に設定された命令B_BRANCH (A3,A3),--を参照し、解読・実行する。この場合、命令コードの種類は２アドレス２分岐命令（B_BRANCH）であるが、指定された２つのジャンプ先のアドレスが等しいので、入力変数の値には依存せず、無条件ジャンプ命令となる。従って、命令デコーダ９は、指定されたアドレスＡ３をプログラムカウンタ１０に設定する。
【００６２】
次に、命令メモリ７は、プログラムカウンタ１０のアドレス情報Ａ３を参照して、アドレスＡ３に格納された命令DATASET 10,0,A0を命令レジスタ８に出力し設定する。命令デコーダ９は、命令レジスタ８に設定された命令DATASET 10,0,A0を参照し、解読・実行する。この場合、データセット命令（DATASET）なので、まず、レジスタ・ファイル５内のアドレス「０」にある「出力レジスタ」に出力データ「１０」を出力し設定する。そして、次に、命令デコーダ９は、アドレスＡ０をプログラムカウンタ１０に設定した後、終端節点なのでプログラムの実行を終了する。
【実施例２】
【００６３】
本実施例では、実施例１で説明したＢＭ１を８個直列に接続した多段ブランチング・プログラム・マシン（以下「多段ＢＭ」という。）について説明する。
【００６４】
図８に、実施例２に係る多段ＢＭの構成を表すブロック図である。図８において、ＢＭ１、並びに変数入力バス２、入力セレクタ３、入力レジスタ４、レジスタ・ファイル５、変数出力バス６、命令メモリ７、命令レジスタ８、命令デコーダ９、及びプログラムカウンタ１０は図３と同様のものである。
【００６５】
本実施例の多段ＢＭ２０は、８個のＢＭ１（ＢＭ０〜ＢＭ７）がカスケード接続された構成からなる。
【００６６】
各ＢＭｎの変数出力バス６は、プログラマブル・ルーティング・ボックス２２を介して後段のＢＭｎ＋１の変数入力バス２又は後段のプログラマブル・ルーティング・ボックス２２若しくは出力レジスタ２４に接続されている。また、各ＢＭｎのフラグ出力バス１１は、プログラマブル・ルーティング・ボックス２１を介して後段のＢＭｎ＋１の変数入力バス２又は後段のプログラマブル・ルーティング・ボックス２１若しくはフラグレジスタ２３に接続されている。また、出力レジスタ２４の外部出力バスr_outは、外部回路に接続されると共に、分岐して最前段のＢＭ１の入力バスにカスケード接続されたプログラマブル・ルーティング・ボックス２２に接続されている。また、フラグレジスタ２３の外部出力バスf_outは、外部回路に接続されると共に、分岐して最前段のＢＭ１の入力バスにカスケード接続されたプログラマブル・ルーティング・ボックス２１に接続されている。
【００６７】
各プログラマブル・ルーティング・ボックス２１，２２は、入力配線と出力配線との接続を再構成可能に組み替える接続回路である。各プログラマブル・ルーティング・ボックス２１，２２は、クロスバースイッチ、マルチプレクサ等によって構成される。
【００６８】
また、各プログラマブル・ルーティング・ボックス２１，２２は、コンフィギュレーションを変えることで、前段のＢＭ１の出力と現在のＢＭの出力のビットワイズＡＮＤやビットワイズＯＲ演算ができる。また、定数出力もできる。ビットワイズＡＮＤ演算を行う場合、末端（図８で斜線で示された部分）のプログラマブル・ルーティング・ボックス２１，２２で定数１を生成する。一方、ビットワイズＯＲ演算を行う場合、末端（図８で斜線で示された部分）のプログラマブル・ルーティング・ボックス２１，２２で定数０を生成する。
【００６９】
これにより、各ＢＭｎにおいて演算結果としてレジスタ・ファイル５内の各出力レジスタ及び各状態レジスタに設定された出力変数、並びにフラグレジスタに設定された各フラグは、カスケード接続されたプログラマブル・ルーティング・ボックス２２，２１を経由して、一旦、出力レジスタ２４及びフラグレジスタ２３に格納される。出力レジスタ２４及びフラグレジスタ２３に格納された値は、フードバックされて再び各ＢＭの入力変数バス２に送られる。
【００７０】
また、最前段のＢＭ１の入力バスにカスケード接続されたプログラマブル・ルーティング・ボックス２１，２２には、外部回路からの外部入力バスf_in，r_inも接続されている。従って、これらの外部入力バスf_in，r_inを介して入力される外部入力も、各プログラマブル・ルーティング・ボックス２１，２２を経由して各ＢＭ１にブロードキャストされる。
【００７１】
また、多段ＢＭ２０の出力をフィードバックして各ＢＭ１で参照することもできる。従って、各ＢＭ１を独立に動作させることもできる。
【００７２】
この多段ＢＭ２０では、各ＢＭ１間の通信時間は、レジスタ（フラグレジスタ２３又は出力レジスタ２４）を１つ経由するだけなので、レジスタに値を書き込んだ後、１クロック後に参照可能である。ＢＭ１は１命令の処理に２クロック使用しており、多段ＢＭ２０内であれば命令レベルの通信時間の遅延は発生しない。
【実施例３】
【００７３】
本実施例では、実施例１で説明したＢＭ１を１２８個用いた並列プロセッサ３０について説明する。１２８個のＢＭ１を、実施例２のようにカスケード状に多段接続し、相互に通信可能とした場合、接続回路（プログラマブル・ルーティング・ボックス２１，２２）は非常に大きくなり、現実的ではない。そこで、本実施例では階層的な接続回路を用いる。本実施例では、実施例２で説明したような、ＢＭ１を８台カスケード接続した多段ＢＭ２０を１ユニットとし、この多段ＢＭ２０を１６個並べて階層構造を構成する。
【００７４】
順序回路を模擬する場合には、状態遷移を行うため他の多段ＢＭ２０を参照する。この際、各多段ＢＭ２０間の接続には、プログラマブル接続回路３１を用いる。前述したように、各多段ＢＭ２０内のＢＭ１間の通信は１クロックで行うことができる。一方、異なる多段ＢＭ２０間の通信は、４クロック必要となる。
【００７５】
図９は、実施例３に係る並列プロセッサ３０の構成を表すブロック図である。並列プロセッサ３０は、１６個の多段ＢＭ２０（８−ＢＭ＿０〜８−ＢＭ＿１５）、プログラマブル接続回路３１、ビットワイズＡＮＤ／ＯＲ回路３２、及びＡＣＴ積演算回路３３を備えている。
【００７６】
各多段ＢＭ２０の出力レジスタ２４の外部出力バスr_outは、プログラマブル接続回路３１の入力側に接続されている。また、各多段ＢＭ２０の最前段のプログラマブル・ルーティング・ボックス２２の外部入力バスr_inは、プログラマブル接続回路３１の出力側に接続されている。
【００７７】
プログラマブル接続回路３１は、入力側に接続されるバスの各配線と出力側に接続されるバスの各配線との接続順序を再構成可能に切り替える接続回路である。プログラマブル接続回路３１は、複雑な信号選択を行うため、多段のマルチプレクサによって構成される。従って、単純な構成ではこのプログラマブル接続回路３１がクリティカルパスとなり、並列プロセッサ３０全体の動作周波数が極端に低下する。そこで、プログラマブル接続回路３１内にはパイプライン・レジスタを挿入し、動作周波数を向上させるように構成する。但し、パイプライン・レジスタを挿入するため、プログラマブル接続回路３１の出力を確定させるためには４クロック必要である。並列プロセッサ３０では１命令につき２クロック使用しているため、プログラマブル接続回路３１を通してデータを転送するには２命令待つ必要がある。
【００７８】
各多段ＢＭ２０のフラグレジスタ２３の外部出力バスf_outは、ビットワイズＡＮＤ／ＯＲ回路３２の入力側に接続されている。また、各多段ＢＭ２０の最前段のプログラマブル・ルーティング・ボックス２１の外部入力バスf_inは、ビットワイズＡＮＤ／ＯＲ回路３２の出力側に接続されている。
【００７９】
ビットワイズＡＮＤ／ＯＲ回路３２は、入力側に接続されるバスの各配線と出力側に接続されるバスの各配線との接続順序を再構成可能に切り替えるとともに、コンフィギュレーションを変えることで、各多段ＢＭ２０の出力するフラグ間のビットワイズＡＮＤやビットワイズＯＲ演算ができるように構成した接続回路である。
【００８０】
また、各多段ＢＭ２０のフラグレジスタ２３の外部出力バスf_outの中の出力線f_out[12]は、プログラマブル接続回路３１を活性化するＡＣＴフラグとして使用されている。各多段ＢＭ２０の出力線f_out[12]は、ＡＣＴ積演算回路３３に接続されている。ＡＣＴ積演算回路３３はこれらのＡＣＴフラグのＡＮＤ演算を行い、ＡＣＴ信号を生成する。このＡＣＴ信号はプログラマブル接続回路３１のＡＣＴ入力端子に入力される。プログラマブル接続回路３１はＡＣＴ信号が１のときに活性化され、前回の活性時に確定した値を保持する。
【符号の説明】
【００８１】
１ ブランチング・プログラム・マシン
２ 変数入力バス
３ 入力セレクタ
４ 入力レジスタ
５ レジスタ・ファイル
６ 変数出力バス
７ 命令メモリ
８ 命令レジスタ
９ 命令デコーダ
１０ プログラムカウンタ
１１ フラグ出力バス
２０ 多段ブランチング・プログラム・マシン
２１ プログラマブル・ルーティング・ボックス
２２ プログラマブル・ルーティング・ボックス
２３ フラグレジスタ
２４ 出力レジスタ
３０ 並列プロセッサ
３１ プログラマブル接続回路
３２ ビットワイズＡＮＤ／ＯＲ回路
３３ ＡＣＴ積演算回路
【特許請求の範囲】
【請求項１】
複数の入力変数が入力される変数入力バスと、
前記変数入力バスから入力変数を選択する入力セレクタと、
前記入力セレクタにより選択される入力変数が一時的に設定される入力レジスタと、
出力変数が設定される出力レジスタと、
前記出力レジスタに設定された出力変数が出力される変数出力バスと、
プログラムにおいて実行する各命令が記憶された命令メモリと、
命令メモリから順次読み出される命令が一時的に設定される命令レジスタと、
入力レジスタから読み出される入力変数と、命令レジスタから読み出される命令とに基づいて当該命令を実行する命令デコーダと、
次に読み出す命令の命令メモリ内のアドレス情報を記憶するプログラムカウンタと、
を備えたブランチング・プログラム・マシンであって、
前記命令メモリには、（１）参照する入力変数のインデックス、入力変数が０のときにジャンプする先の命令メモリのアドレス情報、及び入力変数が１のときにジャンプする先の命令メモリのアドレス情報を含む２アドレス２分岐命令、（２）参照する入力変数のインデックス、入力変数が第１の値のときにジャンプする先の命令メモリのアドレス情報、入力変数が第２の値のときにジャンプする先の命令メモリのアドレス情報、及び入力変数が第３の値のときにジャンプする先の命令メモリのアドレス情報を含む３アドレス４分岐命令、並びに、（３）出力先の出力レジスタのアドレス情報、及び出力データを含む出力命令の３種の命令を少なくとも含む命令系列が記憶され、前記プログラムカウンタに設定されたアドレス情報に従って該アドレス情報で指令されるアドレスに格納された命令を前記命令レジスタに出力するものであり、
前記命令デコーダは、（ａ）前記命令レジスタに設定された命令が前記２アドレス２分岐命令又は前記３アドレス４分岐命令の場合、当該命令で指定される入力変数のインデックスに基づき前記入力セレクタにより入力変数を選択して前記入力レジスタに設定し、当該入力レジスタに設定される入力変数の値に基づいて、当該命令で指定されるジャンプする先の命令メモリのアドレス情報を選択して前記プログラムカウンタに設定する処理を実行し、（ｂ）前記命令レジスタに設定された命令が前記出力命令の場合、当該命令で指定される出力レジスタのアドレス情報に従って該アドレス情報で指令される前記出力レジスタのアドレスに、当該命令で指定される出力データを設定する処理を実行することを特徴とするブランチング・プログラム・マシン。
【請求項２】
前記命令メモリに記憶された３アドレス４分岐命令は、参照する入力変数のインデックス、入力変数の値に対する分岐先アドレスの組み合わせを指定する機能選択フラグ、入力変数が第１の値のときにジャンプする先の命令メモリのアドレス情報ADDR0、入力変数が第２の値のときにジャンプする先の命令メモリのアドレス情報ADDR1、及び入力変数が第３の値のときにジャンプする先の命令メモリのアドレス情報ADDR2を含み、
前記命令デコーダは、前記命令レジスタに設定された命令が前記３アドレス４分岐命令の場合には、当該命令で指定される入力変数のインデックスに基づき前記入力セレクタにより入力変数を選択して前記入力レジスタに設定し、該入力レジスタに設定される入力変数の値が前記第１，第２，第３の値の場合、それぞれ、当該命令で指定されるジャンプする先の命令メモリの前記アドレス情報ADDR0，ADDR1，ADDR2を選択し、該入力レジスタに設定される入力変数の値が前記第１，第２，又は第３の値以外の場合、現在の命令のアドレスPの次のアドレス(P+1)のアドレス情報を選択して前記プログラムカウンタに設定する処理を実行すること
を特徴とする請求項１記載のブランチング・プログラム・マシン。
【請求項３】
複数個の請求項１又は２に記載のブランチング・プログラム・マシンがカスケード接続され、後段の前記ブランチング・プログラム・マシンの変数入力バスの少なくとも一部には、前段の前記ブランチング・プログラム・マシンの前記変数出力バスが接続され、残りの変数入力バスには入力変数が入力されることを特徴とする多段ブランチング・プログラム・マシン。
【請求項４】
前記各ブランチング・プログラム・マシンの前記変数出力バスは、プログラマブル・ルーティング・ボックスを介して後段のブランチング・プログラム・マシンの前記変数入力バスに接続されていることを特徴とする請求項３記載の多段ブランチング・プログラム・マシン。
【請求項５】
複数個並列に接続された請求項３又は４記載の多段ブランチング・プログラム・マシンと、
複数の選択入力ノードと複数の選択出力ノードとを備え、前記各多段ブランチング・プログラム・マシンの前記各変数出力バスが前記各選択入力ノードに接続され、選択出力ノードの少なくとも一部が前記各多段ブランチング・プログラム・マシンの変数入力バスの一部に接続され、前記各選択入力ノードと前記各選択出力ノードとの接続を組み替え可能としたプログラマブル相互接続回路と、
を備えたことを特徴とする並列プロセッサ。
【請求項１】
複数の入力変数が入力される変数入力バスと、
前記変数入力バスから入力変数を選択する入力セレクタと、
前記入力セレクタにより選択される入力変数が一時的に設定される入力レジスタと、
出力変数が設定される出力レジスタと、
前記出力レジスタに設定された出力変数が出力される変数出力バスと、
プログラムにおいて実行する各命令が記憶された命令メモリと、
命令メモリから順次読み出される命令が一時的に設定される命令レジスタと、
入力レジスタから読み出される入力変数と、命令レジスタから読み出される命令とに基づいて当該命令を実行する命令デコーダと、
次に読み出す命令の命令メモリ内のアドレス情報を記憶するプログラムカウンタと、
を備えたブランチング・プログラム・マシンであって、
前記命令メモリには、（１）参照する入力変数のインデックス、入力変数が０のときにジャンプする先の命令メモリのアドレス情報、及び入力変数が１のときにジャンプする先の命令メモリのアドレス情報を含む２アドレス２分岐命令、（２）参照する入力変数のインデックス、入力変数が第１の値のときにジャンプする先の命令メモリのアドレス情報、入力変数が第２の値のときにジャンプする先の命令メモリのアドレス情報、及び入力変数が第３の値のときにジャンプする先の命令メモリのアドレス情報を含む３アドレス４分岐命令、並びに、（３）出力先の出力レジスタのアドレス情報、及び出力データを含む出力命令の３種の命令を少なくとも含む命令系列が記憶され、前記プログラムカウンタに設定されたアドレス情報に従って該アドレス情報で指令されるアドレスに格納された命令を前記命令レジスタに出力するものであり、
前記命令デコーダは、（ａ）前記命令レジスタに設定された命令が前記２アドレス２分岐命令又は前記３アドレス４分岐命令の場合、当該命令で指定される入力変数のインデックスに基づき前記入力セレクタにより入力変数を選択して前記入力レジスタに設定し、当該入力レジスタに設定される入力変数の値に基づいて、当該命令で指定されるジャンプする先の命令メモリのアドレス情報を選択して前記プログラムカウンタに設定する処理を実行し、（ｂ）前記命令レジスタに設定された命令が前記出力命令の場合、当該命令で指定される出力レジスタのアドレス情報に従って該アドレス情報で指令される前記出力レジスタのアドレスに、当該命令で指定される出力データを設定する処理を実行することを特徴とするブランチング・プログラム・マシン。
【請求項２】
前記命令メモリに記憶された３アドレス４分岐命令は、参照する入力変数のインデックス、入力変数の値に対する分岐先アドレスの組み合わせを指定する機能選択フラグ、入力変数が第１の値のときにジャンプする先の命令メモリのアドレス情報ADDR0、入力変数が第２の値のときにジャンプする先の命令メモリのアドレス情報ADDR1、及び入力変数が第３の値のときにジャンプする先の命令メモリのアドレス情報ADDR2を含み、
前記命令デコーダは、前記命令レジスタに設定された命令が前記３アドレス４分岐命令の場合には、当該命令で指定される入力変数のインデックスに基づき前記入力セレクタにより入力変数を選択して前記入力レジスタに設定し、該入力レジスタに設定される入力変数の値が前記第１，第２，第３の値の場合、それぞれ、当該命令で指定されるジャンプする先の命令メモリの前記アドレス情報ADDR0，ADDR1，ADDR2を選択し、該入力レジスタに設定される入力変数の値が前記第１，第２，又は第３の値以外の場合、現在の命令のアドレスPの次のアドレス(P+1)のアドレス情報を選択して前記プログラムカウンタに設定する処理を実行すること
を特徴とする請求項１記載のブランチング・プログラム・マシン。
【請求項３】
複数個の請求項１又は２に記載のブランチング・プログラム・マシンがカスケード接続され、後段の前記ブランチング・プログラム・マシンの変数入力バスの少なくとも一部には、前段の前記ブランチング・プログラム・マシンの前記変数出力バスが接続され、残りの変数入力バスには入力変数が入力されることを特徴とする多段ブランチング・プログラム・マシン。
【請求項４】
前記各ブランチング・プログラム・マシンの前記変数出力バスは、プログラマブル・ルーティング・ボックスを介して後段のブランチング・プログラム・マシンの前記変数入力バスに接続されていることを特徴とする請求項３記載の多段ブランチング・プログラム・マシン。
【請求項５】
複数個並列に接続された請求項３又は４記載の多段ブランチング・プログラム・マシンと、
複数の選択入力ノードと複数の選択出力ノードとを備え、前記各多段ブランチング・プログラム・マシンの前記各変数出力バスが前記各選択入力ノードに接続され、選択出力ノードの少なくとも一部が前記各多段ブランチング・プログラム・マシンの変数入力バスの一部に接続され、前記各選択入力ノードと前記各選択出力ノードとの接続を組み替え可能としたプログラマブル相互接続回路と、
を備えたことを特徴とする並列プロセッサ。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１０−２０４９６９（Ｐ２０１０−２０４９６９Ａ）
【公開日】平成２２年９月１６日（２０１０．９．１６）
【国際特許分類】
【出願番号】特願２００９−４９９８１（Ｐ２００９−４９９８１）
【出願日】平成２１年３月３日（２００９．３．３）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２０年度、文部科学省、地域科学技術振興事業委託事業「高速パターンマッチング回路の合成とその応用に関する研究開発」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（５０４１７４１３５）国立大学法人九州工業大学 (489)
【出願人】（５０３１２１１０３）株式会社ルネサステクノロジ (4,790)
【Ｆターム（参考）】
【公開日】平成２２年９月１６日（２０１０．９．１６）
【国際特許分類】
【出願日】平成２１年３月３日（２００９．３．３）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２０年度、文部科学省、地域科学技術振興事業委託事業「高速パターンマッチング回路の合成とその応用に関する研究開発」委託研究、産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（５０４１７４１３５）国立大学法人九州工業大学 (489)
【出願人】（５０３１２１１０３）株式会社ルネサステクノロジ (4,790)
【Ｆターム（参考）】
[ Back to top ]