(57)【要約】【課題】命令列間を跨いでデータを授受する目的プログラムを生成する。【解決手段】夫々一つの命令列に含まれる複数の小命令で実現されるデータパスが割り付けられるべき単位グラフであって、複数の機能要素をノードとし機能要素間のデータ線をエッジとした単位グラフを複数個命令列の実行順序に対応して配列し、単位グラフ間をハードウェア経路に対応するエッジで接続して命令列階層グラフを作成する命令列階層グラフ作成手段と、原始プログラムのデータフロー構造を実現するデータパスを命令列階層グラフを構成する各単位グラフへ割り付けるデータパス割り付け手段と、命令列階層グラフへ割り付けられたデータパスに基づいて命令列群を作成する目的プログラム出力手段と、を有する。【選択図】図２
2010204904.tif 000002
【特許請求の範囲】
【請求項１】
レジスタ、演算器を含む複数の機能要素を含み、前記夫々の機能要素に対しデータ入出力先の機能要素を夫々指定する複数の小命令を含む命令列を実行し、命令列を跨いだデータパスを実現可能なハードウェア経路を備えたプロセッサをターゲットプロセッサとした命令列群を作成するコンパイル装置において、
夫々一つの命令列に含まれる複数の小命令で実現されるデータパスが割り付けられるべき単位グラフであって、前記複数の機能要素をノードとし前記機能要素間のデータ線をエッジとした単位グラフを複数個命令列の実行順序に対応して配列し、前記配列された単位グラフ間を前記ハードウェア経路に対応するエッジで接続して命令列階層グラフを作成する命令列階層グラフ作成手段と、
原始プログラムのデータフロー構造を実現するデータパスを前記命令列階層グラフを構成する各単位グラフへ割り付けるデータパス割り付け手段と、
前記命令列階層グラフへ割り付けられたデータパスに基づいて命令列群を作成する目的プログラム出力手段と、
を有することを特徴とするコンパイル装置。
【請求項２】
前記ハードウェア経路はバイパスまたは／およびレジスタである、ことを特徴とする請求項１に記載のコンパイル装置。
【請求項３】
レジスタ、演算器を含む複数の機能要素を含み、前記夫々の機能要素に対しデータ入出力先の機能要素を夫々指定する複数の小命令を含む命令列を実行し、命令列を跨いだデータパスを実現可能なハードウェア経路を備えたプロセッサをターゲットプロセッサとした命令列群をコンピュータに作成させるコンパイルプログラムにおいて、
前記コンピュータに、
夫々一つの命令列に含まれる複数の小命令で実現されるデータパスが割り付けられるべき単位グラフであって、前記複数の機能要素をノードとし前記機能要素間のデータ線をエッジとした単位グラフを複数個命令列の実行順序に対応して配列し、前記配列された単位グラフ間を前記ハードウェア経路に対応するエッジで接続して命令列階層グラフを作成する命令列階層グラフ作成工程と、
原始プログラムのデータフロー構造を実現するデータパスを前記命令列階層グラフを構成する各単位グラフへ割り付けるデータパス割り付け工程と、
前記命令列階層グラフへ割り付けられたデータパスに基づいて命令列群を作成する目的プログラム出力工程と、
を実行させることを特徴とするコンパイルプログラム。
【請求項４】
前記ハードウェア経路はバイパスまたは／およびレジスタである、ことを特徴とする請求項３に記載のコンパイルプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンパイル装置およびコンパイルプログラムに関する。
【背景技術】
【０００２】
従来、複数の小命令（マイクロ命令）からなる命令列を並列に実行する演算処理装置（プロセッサ）において、命令列間のデータ授受の典型的な方法として、レジスタをどの演算器からも入出力アクセスが可能に構成する方法がある。以降、この構成を集中レジスタ方式といい、このようなレジスタを集中レジスタということとする。集中レジスタ方式を採用すると、多量のハードウェアコストが必要となる。なぜなら、並列に実行されるすべての処理ユニットとレジスタファイルとの間で、同時進行的にデータ参照および更新を行う必要があるため、並列度、すなわち同時に処理できる命令数に比例した数のデータバスおよび多ポートのメモリが必要になるからである。
【０００３】
これに対して、上記のポートやバスのハードウェアコストの低減を目的として、アクセス可能な演算器を限定したレジスタ（分散レジスタ）を有する構成がある（例えば特許文献１参照）。このような方式を分散レジスタ方式ということとする。この技術によれば、分散レジスタに対する所定のデータバスによりレジスタアクセスの分散が可能となる。しかしながら、そのデータバスがプログラマブルでなければ、汎用性という点で上記の集中レジスタ構成に劣る。またそのデータパスのコンパイル装置（コンパイラ）による実現方法については、特許文献１には記載されていない。
【０００４】
また、パイプラインレジスタも、一種の分散レジスタと考えることができる。このパイプラインレジスタを介して命令列間のデータ授受を行う方法もある。この方法によれば、データの依存解析結果を基に、先行命令の結果値を後続の入力となるようにパイプラインレジスタを介してバイパスさせることで、連続する命令間でのデータの授受を実現している。しかしながら、この依存解析、バイパス制御はハードウェアで実現されているものであった。
【０００５】
上記バイパス制御のためのハードウェア量の削減を目的とし、バイパスされるデータを命令オペランド中に指定することが可能な処理装置が特許文献２に開示されている。この技術によれば、コンパイラなどによりデータ依存解析を行い、自動でバイパスするべきデータを抽出して命令コードに埋め込むものと思われる。しかしながら、その方法、そのコンパイル手法については述べられていない。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００３−９９２４９号公報
【特許文献２】特開平１１−６５８４４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
命令列間を跨いでデータを授受する目的プログラムを生成するコンパイル装置およびコンパイルプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本願発明の一態様によれば、レジスタ、演算器を含む複数の機能要素を含み、前記夫々の機能要素に対しデータ入出力先の機能要素を夫々指定する複数の小命令を含む命令列を実行し、命令列を跨いだデータパスを実現可能なハードウェア経路を備えたプロセッサをターゲットプロセッサとした命令列群を作成するコンパイル装置において、夫々一つの命令列に含まれる複数の小命令で実現されるデータパスが割り付けられるべき単位グラフであって、前記複数の機能要素をノードとし前記機能要素間のデータ線をエッジとした単位グラフを複数個命令列の実行順序に対応して配列し、前記配列された単位グラフ間を前記ハードウェア経路に対応するエッジで接続して命令列階層グラフを作成する命令列階層グラフ作成手段と、原始プログラムのデータフロー構造を実現するデータパスを前記命令列階層グラフを構成する各単位グラフへ割り付けるデータパス割り付け手段と、前記命令列階層グラフへ割り付けられたデータパスに基づいて命令列群を作成する目的プログラム出力手段と、を有することを特徴とするコンパイル装置が提供される。
【０００９】
また、本願発明の一態様によれば、レジスタ、演算器を含む複数の機能要素を含み、前記夫々の機能要素に対しデータ入出力先の機能要素を夫々指定する複数の小命令を含む命令列を実行し、命令列を跨いだデータパスを実現可能なハードウェア経路を備えたプロセッサをターゲットプロセッサとした命令列群をコンピュータに作成させるコンパイルプログラムにおいて、前記コンピュータに、夫々一つの命令列に含まれる複数の小命令で実現されるデータパスが割り付けられるべき単位グラフであって、前記複数の機能要素をノードとし前記機能要素間のデータ線をエッジとした単位グラフを複数個命令列の実行順序に対応して配列し、前記配列された単位グラフ間を前記ハードウェア経路に対応するエッジで接続して命令列階層グラフを作成する命令列階層グラフ作成工程と、原始プログラムのデータフロー構造を実現するデータパスを前記命令列階層グラフを構成する各単位グラフへ割り付けるデータパス割り付け工程と、前記命令列階層グラフへ割り付けられたデータパスに基づいて命令列群を作成する目的プログラム出力工程と、を実行させることを特徴とするコンパイルプログラムが提供される。
【発明の効果】
【００１０】
本発明によれば、命令列間を跨いでデータを授受する目的プログラムを生成するコンパイル装置を提供することができるという効果を奏する。
【００１１】
また、本発明によれば、命令列間を跨いでデータを授受する目的プログラムを生成するコンパイルプログラムを提供することができるという効果を奏する。
【図面の簡単な説明】
【００１２】
【図１】図１は、ターゲットプロセッサの一例を示す図。
【図２】図２は、ＩＨＧの一例を示す図。
【図３】図３は、本発明の実施の形態の構成を説明するブロック図。
【図４】図４は、本発明の実施の形態のハードウェア構成を説明する図。
【図５】図５は、本発明の実施の形態の動作を説明するフローチャート。
【図６】図６は、アーキテクチャ図の一例を説明する図。
【図７】図７は、ＤＦＧの一例を説明する図。
【図８】図８は、本発明の実施の形態の動作を説明するフローチャート。
【図９】図９は、作成されたＩＨＧを説明する図。
【図１０】図１０は、特定ノードに関するテーブル形式の情報を説明する図。
【図１１】図１１は、データパス探索アルゴリズムの一例を説明する図。
【発明を実施するための形態】
【００１３】
以下に添付図面を参照して、本発明の実施の形態にかかるコンパイル装置およびコンパイルプログラムを詳細に説明する。なお、この実施の形態により本発明が限定されるものではない。
【００１４】
（実施の形態）
本発明の実施の形態のコンパイル装置およびコンパイルプログラムは、以下の特徴のうちの少なくとも一つを備えたプロセッサをターゲットプロセッサとした目的プログラムを作成する。すなわち、
・命令列間データ授受手段としての分散レジスタを持つプロセッサ。
・命令列間データ授受手段としてのバイパスを持つプロセッサ。
・カスケード接続された演算器間でもデータ授受が可能なプロセッサ。
・上記のうちの少なくとも１つの特徴を備えるプロセッサ、および上記のうちの少なくとも１つの特徴を備え、かつ集中レジスタを有するプロセッサ。
【００１５】
図１は、本発明の実施の形態のターゲットプロセッサの一例を説明する図である。図１は、ターゲットプロセッサのデータパスを明示的に示したマイクロアーキテクチャ図である。このプロセッサは、複数の小命令（マイクロ命令）からなる命令列をパイプライン処理することができる。パイプラインの段数は４段となっており、そのパイプライン処理のステージは、集中レジスタＳＲＦ、ＰＲＦからパイプラインレジスタＳＲＩＮ０〜２、ＶＲＩＮ０〜３、ＰＲＩＮ０にデータの入力を受け付けるステージ１と、受け付けたデータに対して１回目の演算を実行して演算結果をパイプラインレジスタＴＲ００〜ＴＲ０４に格納するステージ２と、パイプラインレジスタＴＲ００〜ＴＲ０４に格納されたデータに対して２回目の演算を実行してパイプラインレジスタＴＲ１０、ＴＲ１１に格納するステージ３と、パイプラインレジスタＴＲ１０、ＴＲ１１に格納されたデータに対して所定の処理を行ってメモリまたは集中レジスタであるＶＲＦに出力するステージ４とから成り立っている。なお、本発明の実施の形態では、パイプラインレジスタを分散レジスタとみなしている。また、以降、メモリも集中レジスタとみなす。
【００１６】
対象プロセッサの演算器、バッファ、レジスタなど各機能要素（Function  Unit；ＦＵ）は、マイクロ命令により機能や入出力先の指定が可能となっている必要がある。各機能要素はそれぞれ異なる機能を有しており、演算機能だけのものや、データパス制御機能を備えている要素もある。対象プロセッサにおいて、命令列内、及び命令列間でのデータパスを実現するためには、入出力先機能要素をマイクロ命令で指定する必要がある。
【００１７】
例えば、図１に示したプロセッサにおいて、ＡＳＵ０からの出力データとＡＳＵ１からの出力データとを加算する演算をＡＬＵにて実行させる場合、「ADD  ALU  ASU0  ASU1」というマイクロ命令を用いる。ＡＬＵの出力をＴＲ０１に格納する場合、「SET  TR01  ALU」というマイクロ命令を用いる。このように、命令列が含む夫々のマイクロ命令により夫々機能要素の入出力先を指定してデータパスを順次成立させることにより、一つの命令列により図示するようなデータパスを成立させることができる。
【００１８】
ここで、分散レジスタであるＴＲ０１に格納されているデータを次の命令列に受け渡す場合、「Hold  TR01」というマイクロ命令を用いる。このマイクロ命令により、ＴＲ０１に格納されているデータはそのままＴＲ０１に残るので、ＴＲ０１を介して次の命令列のマイクロ命令へのデータの授受を行うことができる。また、図１のプロセッサは、ステージ２にて動作するＡＬＵの出力結果をステージ１における入力データとしてＶＲＩＮ２に入力することができるバイパスを有している。このバイパスを介してＶＲＩＮ２に入力されたデータは、次の命令列のステージ１において取り扱われる。例えば、「Set  VRIN2  ALU」という小命令を用いることにより、このバイパスを利用したデータパスを成立させることができる。バイパスされたデータは、次の命令列の小命令により利用することが可能となる。このように、分散レジスタやバイパスなどのハードウェア経路と、前記ハードウェア経路を利用した入出力先を指定したマイクロ命令からなる命令列であるソフトウェアとの協働により、ハードウェア経路に命令列を跨ぐデータパスを実現することができる。しかしながら、特許文献１および特許文献２には、ソフトウェアを作成するコンパイル技術については開示されていない。
【００１９】
本発明の実施の形態は、前記した特徴を有するターゲットプロセッサにおいて、命令列を跨いだデータパスを成立させる命令列群（目的プログラム）を作成するために、命令列内および命令列間のデータパスの割り付けを簡単に実行することができるグラフを作成することが主たる特徴となっている。図２は、該グラフを説明する図である。
【００２０】
図２に示すように、このグラフは、ＦＵをノード、データ線をエッジとしたグラフを命令列毎に用意した構成となっている。個別のグラフ（単位グラフ）は、一つの命令列に含まれるマイクロ命令によるデータパスが割り付けられるものであって、複数の単位グラフは、命令列の実行順序に対応した順序で配列されている。この場合は、実行順序が後の命令列のグラフほど下に位置するように配列されている。エッジは、データの送信元のノードを起点ノード、データの送信先を終点ノードとした有向エッジある。命令列毎の個別のグラフはデータパスを明示したマイクロアーキテクチャ図に類似しているが、プロセッサがバイパスを有する場合、バイパスを介した起点ノードと終点ノードとの間を同一命令列のグラフ内でエッジ接続せず、各命令列における起点ノードは、次の命令列における終点ノードとがエッジで接続される点と、プロセッサが分散レジスタを有する場合、各命令列における分散レジスタを起点とし、次の命令列に属する同一の分散レジスタを終点ノードとするエッジで接続される点と、が前記マイクロアーキテクチャ図と異なっている。言い換えると、単位グラフ間は、ハードウェア経路に対応するエッジで接続されている。図２は、ノードｆとノードｄとがバイパス構造となっており、ノードｅが分散レジスタとなっているプロセッサのグラフである。図示するように、命令列０のノードｆから命令列１のノードｄにエッジ接続され、命令列１のノードｆから命令列２のノードｄにエッジ接続される。また、命令列０のノードｅから命令列１のノードｅにエッジ接続され、命令列１のノードｅから命令列２のノードｅにエッジ接続されている。すなわち、個別のグラフ間は、命令列間を跨いだハードウェア経路に対応するエッジで互いに接続されているので、データパス、すなわちデータや命令を各ＦＵ（Function  Unit）に簡単に割り付けることができる。なお、この複数の命令列毎の単位グラフからなるグラフ群を命令階層グラフ（Instruction  Hierarchy  Graph）ということとする。
【００２１】
図３は、本発明の実施の形態のコンパイル装置の機能構成を説明するブロック図である。図示するように、コンパイル装置１０は、上記した特徴を実現するための構成として、原始プログラム（ソースプログラム）およびプロセッサの構成情報（アーキテクチャ情報）の入力を受け付ける入力受け付け部１と、入力受け付け部１が受け付けた原始プログラムを解析してデータフローグラフ（Data  Flow  Graph；ＤＦＧ）を作成するデータフローグラフ（ＤＦＧ）作成部２と、入力受け付け部１が受け付けたアーキテクチャ情報に基づいて前記した命令階層グラフを作成する命令階層グラフ（ＩＨＧ）作成部３と、ＤＦＧ作成部２が作成したＤＦＧのデータフローを実現するためのデータフローをＩＨＧ作成部３が作成したＩＨＧに割り付けるデータパス割り付け部４と、ＩＨＧに割り付けられたデータフローに基づいて目的プログラムを生成して出力する目的プログラム出力部５と、を備えている。
【００２２】
入力受け付け部１に入力されるアーキテクチャ情報は、ＦＵ、データ線、およびデータ線を流れるデータフローの向きがわかる情報であればどのような情報であってよく、例えば図１に示すようなデータパスを明示したマイクロアーキテクチャ図であってよい。
【００２３】
図４は、コンパイル装置１０のハードウェア構成を説明する図である。コンパイル装置１０は、ＣＰＵ（Central  Processing  Unit）１１、ＲＯＭ（Read  Only  Memory）１２、ＲＡＭ（Random  Access  Memory）１３、表示部１４、入力部１５を備えるコンピュータ構成となっている。ＣＰＵ１１、ＲＯＭ１２、ＲＡＭ１３、表示部１４、入力部１５は、バスラインを介して夫々接続されている。
【００２４】
ＣＰＵ１１は、原始プログラムのコンパイルを行うコンピュータプログラムであるコンパイルプログラム１６を実行する。表示部１４は、液晶モニタなどの表示装置であり、ＣＰＵ１１からの指示に基づいて、操作画面などのユーザに対する出力情報を表示する。入力部１５は、マウスやキーボードを備えて構成され、ユーザからのコンパイル装置１０の操作が入力される。入力部１５へ入力された操作情報は、ＣＰＵ１１へ送られる。
【００２５】
コンパイルプログラム１６は、ＲＯＭ１２内に格納されており、バスラインを介してＲＡＭ１３へロードされる。ＣＰＵ１１はＲＡＭ１３内にロードされたコンパイルプログラム１６を実行する。具体的には、コンパイル装置１０では、設計者による入力部１５からの指示入力に従って、ＣＰＵ１１がＲＯＭ１２内からコンパイルプログラム１６を読み出してＲＡＭ１３内のプログラム格納領域に展開して各種処理を実行する。原始プログラムやアーキテクチャ情報は、外部記憶装置などから入力される。ＣＰＵ１１は、外部記憶装置などから入力された原始プログラムやアーキテクチャ情報に基づいて各種処理を実行し、この各種処理に際して生じるＤＦＧやＩＨＧなどのデータをＲＡＭ１３内に形成されるデータ格納領域に一時的に記憶させておく。ＣＰＵ１１は、作成した目的プログラムをＲＡＭ１３内のプログラム格納領域あるいは外部記憶装置などに出力する。なお、コンパイルプログラム１６は、ＤＩＳＫなどの記憶装置に格納しておいてもよい。また、コンパイルプログラム１６は、ＤＩＳＫなどの記憶装置にロードしてもよい。
【００２６】
本実施の形態のコンパイル装置１０で実行されるコンパイルプログラム１６は、前述の各部（入力受け付け部１、ＤＦＧ作成部２、ＩＨＧ作成部３、データパス割り付け部４、および目的プログラム出力部５）を含む構成となっており、上記各部が主記憶装置上にロードされ、入力受け付け部１、ＤＦＧ作成部２、ＩＨＧ作成部３、データパス割り付け部４、および目的プログラム出力部５が主記憶装置上に生成される。
【００２７】
なお、本実施の形態のコンパイル装置１０で実行されるコンパイルプログラム１６を、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また、本実施形態のコンパイル装置１０で実行されるコンパイルプログラム１６をインターネット等のネットワーク経由で提供または配布するように構成してもよい。また、本実施形態のコンパイルプログラム１６を、ＲＯＭ等に予め組み込んで本実施の形態のコンパイル装置１０に提供するように構成してもよい。
【００２８】
次に、本実施の形態のコンパイル装置１０の動作を説明する。図５は、本実施の形態のコンパイル装置１０の動作を説明するフローチャートである。
【００２９】
図５において、まず、入力受け付け部１は、外部記憶装置などから原始プログラムおよびアーキテクチャ情報の入力を受け付ける（ステップＳ１）。アーキテクチャ情報として、図６に示すアーキテクチャ図が入力されたとする。
【００３０】
図６に示すアーキテクチャ図では、集中レジスタまたはメモリから演算器ａ、ｂ、ｃにデータが入力される。演算器ａ、ｂ、ｃは夫々所定の演算を行い、演算器ａの出力データは演算器ｄに受け渡され、演算器ｂ、ｃの出力データは分散レジスタｅに格納される。演算器ｄと後段の演算器ｆとの間はバイパスが構成され、演算器ｄは演算器ａの出力データまたは／および演算器ｆからバイパスされたデータを用いて演算を行って演算器ｆに出力データを出力することができる。演算器ｆは、演算器ｄまたは／および分散レジスタｅからのデータを用いて演算を行って集中レジスタやメモリ、または演算器ｄに出力データを出力することができる。
【００３１】
図５に戻り、ＤＦＧ作成部２は、入力受け付け部１が受け付けた原始プログラムを解析してＤＦＧを作成する（ステップＳ２）。図７は、ＤＦＧ作成部２により作成されるＤＦＧの一例を説明する図である。ＤＦＧは、演算子をノードとし、データ依存関係を有向エッジとしたグラフである。
【００３２】
続いて、ＩＨＧ作成部３は、入力受け付け部１が受け付けたアーキテクチャ情報に基づいてＩＨＧを作成する（ステップＳ３）。図８は、ステップＳ３での動作をさらに詳しく説明するフローチャートである。
【００３３】
図８において、まず、ＩＨＧ作成部３は、ノードを定義する（ステップＳ１１）。すなわち、ノードとは、ＦＵ、すなわち演算器、集中／分散レジスタ、メモリである。図６の例では、演算器ａ、ｂ、ｃ、ｄ、ｆと、分散レジスタｅと、演算器ａ、ｂ、ｃへデータを供給し、演算器ｆからデータが供給される集中レジスタ、メモリとがノードとなる。
【００３４】
続いて、ＩＨＧ作成部３は、特定ノードを定義する（ステップＳ１２）。特定ノードとは、命令列間を跨るデータパスを入出力可能なノード、すなわち、分散レジスタ、バイパスを介してデータを送信することが可能な送信元（バイパス元）のＦＵである。図６の例では、分散レジスタｅに対応するノードであるノードｅおよびバイパス元の演算器ｆに対応するノードｆが特定ノードとなる。
【００３５】
続いて、ＩＨＧ作成部３は、ステップＳ１１、Ｓ１２で定義したノード群を複数用意し、各セットを一つの命令列にて実現されるデータパスの割り付け先、すなわち単位グラフとし、各単位グラフに属する夫々のノードの出力エッジを定義する（ステップＳ１３）。ＩＨＧ作成部３は、特定ノードではないノードの場合、アーキテクチャ情報に記述されたデータ線とデータフローの方向に基づいて同じ命令列の単位グラフ内で出力エッジを定義する。また、特定ノードのうちの分散レジスタのノードの場合、ＩＨＧ作成部３は、分散レジスタのノードを起点とし、次の命令列の単位グラフに属する同一のノードを終点とする出力エッジを定義する。また、特定ノードのうちのバイパス元のノードの場合、バイパス元のノードを起点とし、該ノードが属する命令列の次の命令列の単位グラフに属するバイパス先のノードを終点とする出力エッジを定義する。
【００３６】
以上により、図９に示すＩＨＧが完成する。太枠で描画されているノードは特定ノードである。ノードｇは集中レジスタである。ノードｇに出力されたデータは、ノードａ、ｂ、ｃに入力することができるが、ノードｇへの入出力には数サイクルの時間がかかるので、本来はノードｇを起点とし、数命令列後の命令列のノードａ、ｂ、ｃを夫々終点とする出力エッジを描画すべきであるが、煩雑を避けるために、ここではノードｇを起点としたエッジを省略している。
【００３７】
なお、本発明の実施の形態では、表示部１４に表示される情報として図９に示すようなグラフが表示されるようにしてよいが、コンパイル装置１０は、該グラフを表示するための元データとして、起点と終点を定義したテーブル形式の情報でＩＨＧを管理するようにするとよい。例えば、図１０は、図１に示したプロセッサにおける特定ノードおよび特定ノードに関する出力エッジを定義したテーブル形式の情報である。例えば、図１０の最上段に記載されている、分散レジスタであるＳＲＩＮ０に関する情報は、ＳＲＩＮ０を起点とし、同一命令列のＡＳＵ０を終点とした出力エッジと、次の命令列に属するＳＲＩＮ０を終点とした出力エッジが定義されている。また、上段から１０段目のＡＬＵに関する情報には、ＡＬＵを起点とし、同一命令内のＴＲ００、ＴＲ０１、ＴＲ０２、ＴＲ０３を終点とする出力エッジと、ＡＬＵをバイパス元とし、次の命令列に属するＶＲＩＮ２をバイパス先とする出力エッジと、が定義されている。
【００３８】
図５に戻り、ステップＳ３に続いて、データパス割り付け部４は、ＤＦＧ作成部２が作成したＤＦＧのデータフローを実現するためのデータパスをＩＨＧ作成部３が作成したＩＨＧに割り付ける（ステップＳ４）。割り付け方法は特に限定しないが、例えばＦＵの機能に基づいて各演算子とデータとを割り付ける工程と、割り付けた演算子、データのデータパスを探索してデータパスが成立していれば割り付けを確定させるという工程とでステップＳ４を実行する場合、データパス探索の工程は、例えば以下に説明するアルゴリズムを用いて実行することができる。
【００３９】
図１１は、データパス探索用のアルゴリズムの一例を説明する図である。図示したアルゴリズムにおいて、「srcN」はソースとなるノードを示している。「dstN」は、ディスティネーションとなるノードを示している。「curN」は、現在注目しているノードを示している。「ready」は「curN」の出力エッジの入力先ノードの集合を示している。「nextN」は、「ready」から一つ選択されたノードであり、「nextN」への入力エッジは「curN」の出力エッジとなる。「dataPath」は、辿ったノードの集合を示している。図示するように、「curN」＝「srcN」の状態から出発し、「curN」＝「dstN」という状態に等しくなるまで「curN」を起点とした出力エッジに基づいて次の「curN」を決定する。グラフの探索中に、異なる命令列へ遷移するためには、ステップＳ１２において定義した特定ノードを経由する必要があるが、ＩＨＧは、命令列毎にグラフを用意し、命令列を跨ぐ出力エッジが定義されているので、命令列を跨いだデータパスであっても簡単に検知することができる。つまり、命令列を跨いだデータパスを簡単に生成することができる。
【００４０】
図５に戻り、目的プログラム出力部５は、ＩＨＧに割り付けられたマイクロ命令に基づいて、命令列群、すなわち目的プログラムを生成し、外部記憶装置などに出力する。各単位グラフから一つの命令列が生成されるので、複数の単位グラフからなるＩＨＧから複数の命令列が生成される。
【００４１】
このように、本発明の実施の形態によれば、分散レジスタやバイパスなど命令列間を跨いだデータパスを実現するハードウェア経路を有するプロセッサに対して、分散レジスタやバイパスに関する演算器・レジスタからのデータパスの行き先をデータパス可能な命令列内ノードや命令列を超えたノードへと設定したグラフを定義し、この定義されたグラフ内のノード間でデータパスを構築するように構成したので、命令列間を跨いでデータを授受する目的プログラムを生成することができるようになる。
【００４２】
ところで、以上の説明においては、ＩＨＧを用いたデータパスの探索方法として深さ優先探索を例に挙げて説明したが、データパスの探索方法は深さ優先探索に限定しない。深さ優先探索のほかには、例えば、２分木探索や、ノード数優先探索などがある。
【符号の説明】
【００４３】
１  入力受け付け部、２  ＤＦＧ作成部、３  ＩＨＧ作成部、４  データパス割り付け部、５  目的プログラム出力部、１０  コンパイル装置、１１  ＣＰＵ、１２  ＲＯＭ、１３  ＲＡＭ、１４  表示部、１５  入力部、１６  コンパイルプログラム。
【図１】
2010204904.tif 000003
【図２】
2010204904.tif 000004
【図３】
2010204904.tif 000005
【図４】
2010204904.tif 000006
【図５】
2010204904.tif 000007
【図６】
2010204904.tif 000008
【図７】
2010204904.tif 000009
【図８】
2010204904.tif 000010
【図９】
2010204904.tif 000011
【図１０】
2010204904.tif 000012
【図１１】
2010204904.tif 000013