(57)【要約】  事前にデータ登録されている並列演算装置の制約条件に基づいて、入力されたオブジェクトコードの単一階層の状態遷移グラフ構造からループ構造を抽出し、ループ構造を含むような状態遷移を別階層の状態遷移となるように状態遷移グラフを変換し、これを新たなオブジェクトコードとして出力する。
2009044635.tif 000002
【特許請求の範囲】
【請求項１】
複数の演算器及び前記演算器の接続を切り換える相互接続部を備え、前記演算器に対する演算命令及び前記演算器の接続関係を示す情報を含む少なくとも一つの構成情報から成るオブジェクトコードにしたがって複数の処理を並列に実行する並列演算装置に対して供給する前記オブジェクトコードを生成するデータ処理装置であって、
前記並列演算装置の物理構造及び物理特性に対応した制約条件を保持する条件記憶手段と、
単一階層の状態遷移で構成される前記オブジェクトコードから、前記制約条件に基づいて多階層の状態遷移で構成されるオブジェクトコードを生成するオブジェクトコード変換手段と、
を有するデータ処理装置。
【請求項２】
前記オブジェクトコード変換手段は、
単一階層の状態遷移で構成される前記オブジェクトコードに含まれる状態遷移グラフ及び状態遷移に関する情報からループ構造となる状態遷移を抽出するループ抽出手段と、
前記ループ抽出手段で抽出された状態遷移に対してループ構造の特性に応じた優先順位を付与するループ優先順位付け手段と、
前記優先順位付けされたループ構造から前記制約条件に対応するループ構造を選択し、別階層の状態遷移グラフであるグループリストを抽出するグループ候補抽出手段と、
前記グループリストを用いて単一階層の状態遷移で構成される前記オブジェクトコードに含まれる状態遷移グラフをカバーリングし、多階層の状態遷移で構成されるオブジェクトコードを生成するマクロ状態遷移生成手段と、
を有する請求項１記載のデータ処理装置。
【請求項３】
前記オブジェクトコード変換手段は、
前記単一階層の状態遷移で構成されるオブジェクトコードに含まれる状態遷移グラフと前記多階層の状態遷移で構成されるオブジェクトコードに含まれる多階層の状態遷移グラフを用いて、前記並列演算装置が次に遷移する状態以降に遷移すると予測される状態に対応する構成情報を要求するためのプリロード情報を生成するプリロード情報生成手段を有する請求項２記載のデータ処理装置。
【請求項４】
複数の演算器及び前記演算器の接続を切り換える相互接続部を備え、前記演算器に対する演算命令及び前記演算器の接続関係を示す情報を含む少なくとも一つの構成情報から成るオブジェクトコードにしたがって複数の処理を並列に実行する並列演算装置に対して供給する前記オブジェクトコードを生成するためのデータ処理方法であって、
前記並列演算装置の物理構造及び物理特性に対応した制約条件を条件記憶手段に保持しておき、
単一階層の状態遷移で構成される前記オブジェクトコードから、前記制約条件に基づいて多階層の状態遷移で構成されるオブジェクトコードを生成するデータ処理方法。
【請求項５】
前記単一階層の状態遷移で構成されるオブジェクトコードに含まれる状態遷移グラフ及び状態遷移に関する情報からループ構造となる状態遷移を抽出し、
該抽出した状態遷移に対してループ構造の特性に応じた優先順位を付与し、
前記優先順位付けされたループ構造から前記制約条件に対応するループ構造を選択し、別階層の状態遷移グラフであるグループリストを抽出し、
前記グループリストを用いて前記単一階層の状態遷移で構成されるオブジェクトコードに含まれる状態遷移グラフをカバーリングし、多階層の状態遷移で構成されるオブジェクトコードを生成する請求項４記載のデータ処理方法。
【請求項６】
前記単一階層の状態遷移で構成されるオブジェクトコードに含まれる状態遷移グラフと前記多階層の状態遷移で構成されるオブジェクトコードに含まれる多階層の状態遷移グラフを用いて、前記並列演算装置が次に遷移する状態以降に遷移すると予測される状態に対応する構成情報を要求するためのプリロード情報を生成する請求項５記載のデータ処理方法。
【請求項７】
複数の演算器及び前記演算器の接続を切り換える相互接続部を備え、前記演算器に対する演算命令及び前記演算器の接続関係を示す情報を含む少なくとも一つの構成情報から成るオブジェクトコードにしたがって複数の処理を並列に実行する並列演算装置に対して供給する前記オブジェクトコードをデータ処理装置に生成させるためのプログラムであって、
前記並列演算装置の物理構造及び物理特性に対応した制約条件を条件記憶手段に保持させ、
単一階層の状態遷移で構成される前記オブジェクトコードから、前記制約条件に基づいて多階層の状態遷移で構成されるオブジェクトコードを前記データ処理装置で生成するためのプログラム。
【請求項８】
前記単一階層の状態遷移で構成されるオブジェクトコードに含まれる状態遷移グラフ及び状態遷移に関する情報からループ構造となる状態遷移を抽出し、
該抽出した状態遷移に対してループ構造の特性に応じた優先順位を付与し、
前記優先順位付けされたループ構造から前記制約条件に対応するループ構造を選択し、別階層の状態遷移グラフであるグループリストを抽出し、
前記グループリストを用いて前記単一階層の状態遷移で構成されるオブジェクトコードに含まれる状態遷移グラフをカバーリングし、多階層の状態遷移で構成されるオブジェクトコードを生成するための請求項７記載のプログラム。
【請求項９】
前記単一階層の状態遷移で構成されるオブジェクトコードに含まれる状態遷移グラフと前記多階層の状態遷移で構成されるオブジェクトコードに含まれる多階層の状態遷移グラフを用いて、前記並列演算装置が次に遷移する状態以降に遷移すると予測される状態に対応する構成情報を要求するためのプリロード情報を生成するための請求項８記載のプログラム。
【請求項１０】
請求項７から９のいずれか１項記載のプログラムが格納された記録媒体。
【請求項１１】
複数の演算器、前記演算器の接続を切り換える相互接続部及び請求項１から３のいずれか１項記載のデータ処理装置で生成された前記オブジェクトコードを格納するための外部記憶手段を備え、
前記演算器に対する演算命令及び前記演算器の接続関係を示す情報を含む少なくとも一つの構成情報から成るオブジェクトコードにしたがって各種の処理を実行する並列演算装置。
【請求項１２】
複数の演算器及び前記演算器の接続を切り換える相互接続部を備え、
請求項１から３のいずれか１項記載のデータ処理装置で生成されたオブジェクトコードが入力される、前記演算器に対する演算命令及び前記演算器の接続関係を示す情報を含む少なくとも一つの構成情報から成るオブジェクトコードにしたがって各種の処理を実行する並列演算装置。
【請求項１３】
請求項１から３のいずれか１項記載のデータ処理装置と、
前記データ処理装置で生成されたオブジェクトコードが入力される請求項１２に記載の並列演算装置と、
を有するデータ処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、所定の処理を実行するアレイ型プロセッサ等のプログラマブルデバイスで構成される並列演算装置を動作させるためのオブジェクトコードを生成するデータ処理装置および方法に関する。
【背景技術】
【０００２】
従来より所望の処理を実現するプロセッサユニットとしてＣＰＵ（Central  Processing  Unit）が知られている。また、小型化・高性能化を目的とする、複数のプロセッサをアレイ状に並べたアレイ型プロセッサで構成される並列演算装置は、特許３５７６８３７号公報、特許第３４４４２１６号公報、特許第３２６９５２６号公報、特許第３６１６５１８号公報、特許第３６７４５１５号公報及び特許第３５２８９２２号公報に記載されている（以下、これを第１背景技術と称す）。【０００３】
この並列演算装置で動作するプログラム（オブジェクトコード）を生成する技術は、特許第３９２１３６７号公報に記載されている（以下、これを第２背景技術と称す)。【０００４】
第１背景技術の並列演算装置では、処理対象となるデータに応じて生成された１つ以上の構成情報から成るオブジェクトコードに基づいて処理を実行する。また、第１背景技術では、並列演算装置に格納された構成情報の位置を直接指定しつつ処理を実行する手法が採用されている。構成情報とは、演算器に対して発行する演算命令、各演算器の接続関係を示す情報、イベント信号とそれに対応して次に選択すべき構成情報の関係を示す情報を含む、並列演算装置内に仮想的に回路を構成するために必要な情報である。オブジェクトコードは、所望の処理を実行するために必要な構成情報の集まりを指す。オブジェクトコードには、所望の処理を実行する過程における、並列演算装置の状態遷移グラフ情報が含まれる。【０００５】
第１背景技術では、並列演算装置に複数のオブジェクトコードを搭載し、それらのオブジェクトコードに含まれる構成情報の格納位置が重なる場合、それらが重ならないようにオブジェクトコードを合成し直す必要がある。また、並列演算装置に複数のオブジェクトコードあるいは大規模なオブジェクトコードを搭載する場合、並列演算装置で保持可能な構成情報数を超えると、並列演算装置は、処理の停止、オブジェクトコードの入れ替え、処理の再開等の処理を実行する必要がある。また、このような処理のために外部にＣＰＵ等の処理装置が必要になる。その際、第１背景技術の並列演算装置では、オブジェクトコードの合成時に決定した格納位置にしか構成情報を格納できないため、同じ機能の構成情報から成るオブジェクトコードであっても、それらを決められた格納位置にそれぞれ格納する必要がある。すなわち、並列演算装置は同じ構成情報を複数保持しなければならず、同一の構成情報どうしで書き換える等の無駄な処理が発生する問題がある。【０００６】
そこで、本出願人は構成情報の格納先の制限を無くすと共に構成情報を共有することが可能な並列演算装置を提案している（特願２００７−０６１９３４号：以下、これを第３背景技術と称す)。【０００７】
上記第３背景技術を第１背景技術の並列演算装置に適用した場合の要部の構成例を図１に示す。また、図１に示した並列演算装置の動作を図２のタイミングチャートで示す。【０００８】
図１に示す構成では、演算部がイベント信号を出力すると、状態管理部は該イベント信号に基づいて現状態実番号を次状態論理番号に変換し、構成番号変換部は次状態論理番号を次状態実番号に変換する。これらの処理は逐次行う必要があるため、パイプライン処理で実行できない。【０００９】
したがって、図１に示す構成では、状態管理部における状態遷移の遅延が大きいため高速に処理することが困難であるという問題がある。これは、状態管理部における状態遷移処理が１クロックサイクル以内で完了するように、クロックサイクルを長くしなければならないためである。状態遷移を複数クロックサイクルで処理するように構成すれば、クロックサイクルを長くする必要はなくなる。しかしながら、演算部は1クロックサイクルで処理を完了した後、状態遷移処理の完了を待つ必要があるため、処理性能が低下してしまう。【００１０】
このような問題を解決するため、第３背景技術では並列演算装置に状態管理部及び補助制御部を備え、該状態管理部及び補助制御部による多階層の状態遷移の制御を可能にした構成も提案している。しかしながら、並列演算装置は、通常のＣＰＵ等と構造及び動作の両方が根本的に相違しているため、このような多階層の状態遷移あるいはそれを利用した並列演算処理のためのオブジェクトコードを適切に生成する技術は確立されていない。【００１１】
すなわち、第１背景技術の並列演算装置のオブジェクトコードは、第２背景技術によってソースコードから生成できるが、第２背景技術で得られるオブジェクトコード（以下、これを初期オブジェクトコードと称す）に基づいて、第３背景技術の並列演算装置で実現する並列演算装置を良好に動作させるためのオブジェクトコードを生成する技術は確立していない。
【発明の開示】
【００１２】
そこで、本発明は、多階層の状態遷移の制御が可能な構成の並列演算装置のためのオブジェクトコードを生成できるデータ処理装置および方法を提供することを目的とする。
【００１３】
上記目的を達成するため本発明のデータ処理装置は、複数の演算器及び前記演算器の接続を切り換える相互接続部を備え、前記演算器に対する演算命令及び前記演算器の接続関係を示す情報を含む少なくとも一つの構成情報から成るオブジェクトコードにしたがって複数の処理を並列に実行する並列演算装置に対して供給する前記オブジェクトコードを生成するデータ処理装置であって、
前記並列演算装置の物理構造及び物理特性に対応した制約条件を保持する条件記憶手段と、
単一階層の状態遷移で構成される前記オブジェクトコードから、前記制約条件に基づいて多階層の状態遷移で構成されるオブジェクトコードを生成するオブジェクトコード変換手段と、
を有する。
【００１４】
一方、本発明のデータ処理方法は、複数の演算器及び前記演算器の接続を切り換える相互接続部を備え、前記演算器に対する演算命令及び前記演算器の接続関係を示す情報を含む少なくとも一つの構成情報から成るオブジェクトコードにしたがって複数の処理を並列に実行する並列演算装置に対して供給する前記オブジェクトコードを生成するためのデータ処理方法であって、
前記並列演算装置の物理構造及び物理特性に対応した制約条件を条件記憶手段に保持しておき、
単一階層の状態遷移で構成される前記オブジェクトコードから、前記制約条件に基づいて多階層の状態遷移で構成されるオブジェクトコードを生成する方法である。
【図面の簡単な説明】
【００１５】
【図１】図１は、第３背景技術の並列演算装置の要部の構成を示すブロック図である。
【図２】図２は、図１に示した並列演算装置の動作を示すタイミングチャートである。
【図３】図３は、本発明のデータ処理システムの構成例を示すブロック図である。
【図４】図４は、図３に示した並列演算装置の構成例を示すブロック図である。
【図５】図５は、図３に示したデータ処理装置の一構成例を示すブロック図である。
【図６】図６は、図３に示したオブジェクトコード変換手段の第１の実施の形態の構成を示すブロック図である。
【図７】図７は、図６に示したグループ候補抽出手段の処理手順を示すフローチャートである。
【図８】図８は、図６に示したマクロ状態遷移生成手段の処理手順を示すフローチャートである。
【図９】図９は、図３に示したオブジェクトコード変換手段の第２の実施の形態の構成を示すブロック図である。
【図１０】図１０は、図９に示したプリロード情報生成手段の処理手順を示すフローチャートである。
【図１１】図１１は、初期オブジェクトコードに含まれる初期状態遷移グラフの一例を示す状態遷移図である。
【図１２】図１２は、初期オブジェクトコードに含まれる状態遷移リストの一例を示す模式図である。
【図１３】図１３は、図１２に示す状態遷移リストから抽出したループリスト及びループ情報の一例を示す表である。
【図１４】図１４は、図１１に示した初期状態遷移グラフ及び状態遷移確率から生成したループリスト及び疑似的なループ情報の一例を示す表である。
【図１５】図１５は、図１３に示したループリストから生成された優先順付けされたループリストの一例を示す表である。
【図１６】図１６は、図１５に示したループリストから生成した状態毎のグループリストの一例を示す表である。
【図１７】図１７は、マクロ状態遷移グラフの生成過程を例示した状態遷移図である。
【図１８】図１８は、図１６に示したグループリストから生成したマクロ状態遷移グラフの一例を示す状態遷移図である。
【図１９】図１９は、図１６に示した状態毎のグループリストと図１８に示したマクロ状態遷移グラフから生成したプリロード情報の一例を示す表である。
【図２０】図２０は、図３に示した並列演算装置１４０の動作の様子を示すタイミングチャートである。
【発明を実施するための最良の形態】
【００１６】
次に本発明について図面を参照して説明する。
(第１の実施の形態)
図３は本発明のデータ処理システムの構成例を示すブロック図であり、図４は図３に示した並列演算装置の構成例を示すブロック図である。【００１７】
図３に示すデータ処理システム１００は、データ供給手段１１０、データ処理装置１２０、オブジェクトコード供給手段１３０、並列演算装置１４０及び外部入出力装置１５０を備えている。【００１８】
図４に示すように、並列演算装置１４０は、制御部３１０、演算部３２０、書換決定部３３０及び外部記憶手段３４０を備えている。【００１９】
制御部３１０は、状態管理部３１１、構成番号変換部３１２、構成情報記憶部３１３及び構成書換部３１４を備えている。【００２０】
演算部３２０は、補助制御部３２１、複数の演算器３２２及び各演算器３２２の接続を切替える相互接続部３２３を備えている。【００２１】
演算器３２２及び相互接続部３２３は、演算器３２２に対する演算命令及び相互接続部３２３の接続関係を示す情報を含む少なくとも一つの構成情報から成るオブジェクトコードにしたがって動作する。【００２２】
構成情報記憶部３１３は、オブジェクトコードの構成情報および次に遷移する状態の候補群の情報の少なくとも一部を保持し、保持した情報を補助制御部３２１及び状態管理部３１１に供給する。【００２３】
外部記憶手段３４０は、オブジェクトコードを保持すると共に、並列演算装置１４０で実行する処理で必要な情報を保持する。【００２４】
状態管理部３１１は、現在の動作状態、次に遷移する状態の候補群及び演算器３２２で発行されるイベント情報に基づき、次の動作状態で用いる構成情報のうち、オブジェクトコードに含まれる各構成情報の相互関係を示す情報である論理番号を指定する。【００２５】
補助制御部３２１は、演算器３２２及び相互接続部３２３と状態管理部３１１間に挿入され、状態管理部３１１で制御可能な状態遷移よりも規模の小さい状態遷移を制御する。【００２６】
構成番号変換部３１２は、論理番号に対応する構成情報が実際に保存されている格納位置を示す実番号に変換する。このとき、論理番号に対応する構成情報が構成情報記憶部３１３に保持されていない場合は、該論理番号に対応する構成情報への書き換えを構成書換部３１４に要求する。【００２７】
構成書換部３１４は、構成番号変換部３１２または書換決定部３３０からの要求に応じて、外部記憶手段３４０からオブジェクトコード等の情報を読み出し、構成情報記憶部３１３あるいは構成番号変換部３１２で保持している情報を書き換える。【００２８】
書換決定部３３０は、制御部３１０が備える構成番号変換部３１２、構成情報記憶部３１３及び構成書換部３１４の現在の状態を参照し、次に遷移する状態以降の状態で必要となる構成情報を予測し、該構成情報への書き換えを構成書換部３１４に要求する。【００２９】
本実施形態の並列演算装置１４０は、外部記憶手段３４０に格納されたオブジェクトコードに対応して、補助制御部３２１及び状態管理部３１１により動作サイクル毎に状態遷移を行い、この状態遷移に対応する個々の演算器３２２の処理及び相互接続部３２３の接続関係を構成情報記憶部３１３から指定されることで複数の処理を並列に実行する。【００３０】
本実施形態のデータ処理装置１２０は、例えば図５に示すように、ＣＰＵ６０１、バスライン６２０を介してＣＰＵ６０１に接続されたＲＡＭ６０２、ＲＯＭ６０３、ＨＤＤ６０４、ＦＤ６１１が交換自在に装填されるＦＤＤ（FD  Drive）６０６、ＣＤ−ＲＯＭ６１２が交換自在に装填されるＣＤドライブ６０７、ディスプレイ６０８、キーボード６０９、マウス６１０、Ｉ／Ｆユニット６０５等を備えたコンピュータで実現できる。【００３１】
本実施形態のデータ処理装置１２０では、ＲＡＭ６０２、ＲＯＭ６０３、ＨＤＤ６０４、ＦＤ６１１、ＣＤ−ＲＯＭ６１２等が記録媒体に相当し、これらの少なくとも一つにＣＰＵ６０１で処理を実行するためのプログラムや各種データが格納されている。【００３２】
例えば、ＣＰＵ６０１に各種の処理を実行させるためのプログラムは、ＦＤ６１１やＣＤ−ＲＯＭ６１２に事前に格納されている。このようなプログラムは、ＨＤＤ６０４に事前にインストールされ、データ処理装置１２０の起動時にＲＡＭ６０２に複写されてＣＰＵ６０１に読み出される。【００３３】
このようにＣＰＵ６０１が適正なプログラムを読み出して各種の処理を実行することにより、本実施形態のデータ処理装置１２０は、図３に示したデータ入力手段１２１、条件記憶手段１２２、オブジェクト変換手段１２３およびデータ出力手段１２４として動作する。【００３４】
データ処理システム１００のデータ供給手段１１０は、例えば初期オブジェクトコード及び状態遷移に関する情報が格納されたＦＤ６１１からなり、並列演算装置１４０の初期オブジェクトコード及び状態遷移に関する情報をデータ処理装置１２０に供給する。ここで、状態遷移に関する情報としては、状態の分岐における発生確率等がある。初期オブジェクトコードは単一階層の状態遷移で構成される。【００３５】
データ処理装置１２０のデータ入力手段１２１は、ＲＡＭ６０２に格納されたプログラムにしたがってＣＰＵ６０１によりＦＤＤ６０６を制御することで実現される。データ入力手段１２１は、データ供給手段１１０に格納された初期オブジェクトコード及び状態遷移に関する情報を取得する。【００３６】
条件記憶手段１２２は、プログラムにしたがってＣＰＵ６０１が認識するＨＤＤ６０４等の記憶領域で実現される。条件記憶手段１２２には、並列演算装置１４０の物理構造や物理特性等に対応した各種の制約条件が事前に登録されている。【００３７】
オブジェクトコード変換手段１２３は、プログラムにしたがってＣＰＵ６０１が処理を実行することで実現される。オブジェクトコード変換手段１２３は、データ入力手段１２１で取得した初期オブジェクトコード及び状態遷移に関する情報を、条件記憶手段１２２に格納された制約条件に基づいて、並列演算装置１４０がより効率的に動作するための多階層の状態遷移で構成されるオブジェクトコードに変換する。【００３８】
データ出力手段１２４は、プログラムにしたがってＣＰＵ６０１がＩ／Ｆユニット６０５のデータ出力を制御することで実現される。データ出力手段１２４は、オブジェクトコード変換手段１２３で変換されたオブジェクトコードをオブジェクトコード供給手段１３０に出力する。【００３９】
オブジェクトコード供給手段１３０は、データ出力手段１２４のＩ／Ｆユニット６０５と並列演算装置１４０の外部記憶手段３４０とを接続するコネクタ（不図示）等に相当し、データ処理装置１２０から出力されるオブジェクトコードを並列演算装置１４０の外部記憶手段３４０に格納する。【００４０】
本実施形態のデータ処理装置１２０が備えるオブジェクトコード変換手段１２３は、図６に示すようにループ抽出手段２０１、ループ優先順位付け手段２０２、グループ候補抽出手段２０３及びマクロ状態遷移生成手段２０４を備えている。【００４１】
ループ抽出手段２０１は、入力された初期オブジェクトコードに含まれる初期状態遷移グラフと状態遷移に関する情報を解析し、状態のループ構造を抽出し、そのループ構造のリスト（ループリスト）を生成する。上記状態遷移に関する情報としては、例えば並列演算装置１４０や並列演算装置１４０と同様に動作するシミュレータ等で初期オブジェクトコードを動作させることで得られる状態遷移リストや状態毎の遷移確率等の情報である。このような状態遷移に関する情報が得られない場合は、初期状態遷移グラフの構造に基づいて、例えばある状態からの遷移は全て同じ確率にする等、予め遷移確率を適切に設定しておいてもよい。【００４２】
上記ループリストには、個々のループに関する、例えばループに含まれる状態数、ループに沿った状態の組合せあるいは順列、ループ内で発生した、または発生すると予測される平均値、最大値または最小値の動作サイクル数、もしくは遷移確率等のループ情報が少なくとも1つ含まれる。【００４３】
ループ優先順位付け手段２０２は、ループ情報に基づいてループ抽出手段２０１で生成された各ループリストに優先順位を付与し、優先順位付けされたループリストを生成する。【００４４】
上記優先順位は、ループ情報に含まれる、ループ内の状態数、ループ内で発生した、もしくは発生すると予測される動作サイクル数の平均値、最大値もしくは最小値の情報を少なくとも1つを用いて付与する。【００４５】
グループ候補抽出手段２０３は、初期オブジェクトコードに含まれる初期状態遷移グラフ及び制約条件に基づいて、上記優先順位付けされたループリストから状態毎のグループリストを生成する。【００４６】
上記制約条件には、並列演算装置１４０の物理構造や物理特性等に応じて、例えば並列演算装置１４０の構成情報記憶部３１３で保持できる構成情報のデータ量、補助制御部３２１や状態管理部３１１で保持できる状態数、構成番号変換部３１２で保持できる変換表の数、構成書換部３１４が構成情報や変換表を書換える時間、補助制御部３２１、状態管理部３１１、構成番号変換部３１２等の内部処理またはそれらの間の制御等で発生する時間等がある。【００４７】
グループ候補抽出手段２０３で生成された状態毎のグループリストには、初期状態遷移グラフのノード毎（状態毎）にその状態を含む状態番号が列挙されている。【００４８】
グループ候補抽出手段２０３によるグループリストを生成するための処理手順を図７のフローチャートで示す。【００４９】
図７に示すように、グループ候補抽出手段２０３は、初期状態遷移グラフのノード（状態）全てに対してグループリストを生成する。グループ候補抽出手段２０３は、まず初期状態遷移グラフから選択した全ての状態について、その状態番号を含み、かつ制約条件を満たすループを、優先順位付けされたループリストの上位から検索する。ここでの制約条件には補助制御部３２１で保持できる状態数等を用いる。例えば、補助制御部３２１で保持できる状態数がループに含まれる状態数を越えている場合は補助制御部３２１で状態遷移を制御できないため、この数以下の状態数からなるループを検索する必要がある。このとき、例えばループに含まれる状態数ができるだけ少なく、かつ後述する制約条件である、構成書換部３１４にて構成情報を書き換える時間がそのループ内で発生した、または発生すると予測される平均動作サイクル数よりも大きいループを選択することが好ましい。そのようなループが存在する場合は、そのループの状態遷移順に状態番号をグループリストに登録し、そのようなループが存在しない場合は選択している状態番号をグループリストに登録する。【００５０】
次に、グループ候補抽出手段２０３は、グループリストに含まれている全ての状態に対応して算出される値、例えば選択している状態のグループリストに含まれるループ内で発生した、または発生すると予測される平均動作サイクル数、グループリストに含まれる総状態数等が、制約条件を満たしているか否かを判断する。満たしている場合はこの状態のグループリストの登録を終了し、グループリストに抽出されていない状態について上記処理を繰り返す。満たしていない場合は、選択している状態のグループリストに含まれる全て状態と初期状態遷移グラフとを参照し、次に遷移すると予測される、このグループリストに含まれない状態を一つ選択し、該選択した状態に対して上記のループ検索から処理を繰り返し、検索された状態番号をこのグループリストに追加登録する。【００５１】
本実施形態のグループ候補抽出手段２０３は、ここでの制約条件として次の２つの条件を用いる。
（１）グループリストに含まれる総状態数が、補助制御部３２１で保持できる状態数以下でなるべく小さい。
（２）選択している状態のグループリストに含まれるループ内で発生した、または発生すると予測される平均動作サイクル数が所定の値より大きい。【００５２】
これは、構成書換部３１４が構成情報を書き換える時間が、選択している状態のグループリストに含まれるループ内で発生した、または発生すると予測される平均動作サイクル数よりも大きい場合、並列演算装置１４０の書換決定部３３０で予測した構成情報を構成書換部３１４が書き込む期間は、演算部３２０が動作不可となり、並列演算装置１４０の処理性能が低下する原因となるからである。【００５３】
なお、上記の２つの条件のうち、（１）の条件が優先される。【００５４】
マクロ状態遷移生成手段２０４は、入力された初期オブジェクトコードに含まれる初期状態遷移グラフを基にして、上記状態毎のグループリストから並列演算装置１４０がより効率的に動作するための多階層の状態遷移（マクロ状態遷移グラフ、マイクロ状態遷移グラフ）で構成されるオブジェクトコードを生成する。【００５５】
なお、マクロ状態とは並列演算装置１４０の制御部で順次遷移させる状態を指し、マイクロ状態とは並列演算装置１４０の補助制御部で順次遷移する状態を指す。【００５６】
マイクロ状態遷移グラフは、主に上記状態毎のグループリストに登録された状態から構成される初期状態遷移グラフ内の部分グラフであり、１つ以上存在する。マクロ状態遷移グラフは、マイクロ状態遷移グラフ間の遷移を示すグラフであり、1つだけ存在する。【００５７】
マクロ状態遷移生成手段２０４は、グループリストを用いて初期状態遷移グラフのカバーリングを行い、並列演算装置のためのより効率的に動作する多階層の状態遷移（マクロ状態遷移グラフ、マイクロ状態遷移グラフ）で構成されるオブジェクトコードを生成する。【００５８】
カバーリングとは、あるグラフをその部分グラフの組合せで実現することを指し、マクロ状態遷移生成手段は、初期状態遷移グラフをマイクロ状態遷移グラフでカバーリングを行い、マクロ状態遷移グラフを生成する。このとき、マクロ状態遷移グラフのノードはマイクロ状態遷移グラフとなる。【００５９】
マクロ状態遷移生成手段２０４により上記マクロ状態遷移グラフ及びマイクロ状態遷移グラフを生成するための処理手順を図８のフローチャートで示す。【００６０】
図８に示すように、マクロ状態遷移生成手段２０４は、まず初期状態遷移グラフの開始状態を選択し、この選択した状態のグループリストを参照し、参照したグループリストに含まれる複数の状態で初期状態遷移グラフの部分グラフを生成する。マクロ状態遷移生成手段２０４は、この部分グラフを1つのマイクロ状態遷移グラフとする。【００６１】
次に、マクロ状態遷移生成手段２０４は、これまでに生成したマイクロ状態遷移グラフについて、初期状態遷移グラフの一部でも包含できていない箇所があるか否かを判定する。初期状態遷移グラフの一部でも包含できていない箇所がある場合、マクロ状態遷移生成手段２０４は、初期状態遷移グラフを参照して生成したマイクロ状態遷移グラフをノードとみなしたとき、次の分岐先となる状態を選択し、マイクロ状態遷移グラフが初期状態遷移グラフを全て包含するまで上記処理を繰り返す。ここで、マイクロ状態遷移グラフをノードとみなしたときに次の分岐先となる状態は複数存在することがあるため、上記の処理は再帰的な処理となる。【００６２】
マクロ状態遷移生成手段２０４は、マイクロ状態遷移グラフで初期状態遷移グラフを全て包含したら、マイクロ状態遷移グラフをノードとみなして、そのノード間の遷移構造を、初期状態遷移グラフを参照して生成し、それをマクロ状態遷移グラフとする。【００６３】
本実施形態のデータ処理システム１００によれば、オブジェクトコード変換手段１２３によって初期オブジェクトコードから抽出し、優先順位付けされたループ構造を含むマイクロ状態遷移グラフが、並列演算装置１４０の補助制御部３２１で制御され、そのマイクロ状態遷移グラフ間の遷移情報であるマクロ状態遷移グラフが制御部３１０の状態管理部３１１で制御される。そのため、並列演算装置１４０が初期オブジェクトコードで動作する場合と比べて補助制御部３２１の動作サイクル数が増加し、状態管理部３１１を経由することに伴う演算部３２０の動作停止時間の割合を相対的に低下させることができる。そのため、並列演算装置１４０の処理性能が向上する。【００６４】
(第２の実施の形態)
図９は図３に示したオブジェクトコード変換手段１２３の第２の実施の形態の構成を示すブロック図である。【００６５】
第２の実施の形態のオブジェクトコード変換手段１２３は、第１の実施の形態のオブジェクトコード変換手段１２３が備えるマクロ状態遷移生成手段２０４の後段にプリロード情報生成手段２０５を追加した構成である。その他の構成は第１の実施の形態と同様であるため、その説明は省略する。【００６６】
プリロード情報生成手段２０５は、初期状態遷移グラフと、グループ候補抽出手段２０３から出力された状態毎のグループリストと、マクロ状態遷移生成手段２０４から出力されたマクロ状態遷移グラフ及びマイクロ状態遷移グラフと、制約条件とを基にして、プリロード情報を生成する。プリロードとは、並列演算装置１４０の状態管理部３１１が決定した、次に遷移する状態番号に対応する構成情報が構成情報記憶部３１３に無い場合に、次に遷移する状態以降の状態で必要となる構成情報を並列演算装置１４０の構成書換部３１４に通知する処理を指す。【００６７】
プリロード情報には、各マクロ状態遷移のノード毎に、並列演算装置１４０の動作状態に応じて補助制御部３２１や状態管理部３１１が次に遷移する状態以降の状態で必要となる構成情報の指示が含まれる。【００６８】
プリロード情報生成手段２０５がプリロード情報を生成する処理手順を図１０のフローチャートに示す。【００６９】
プリロード情報生成手段２０５は、マクロ状態遷移グラフの全てのノードに対応したプリロード情報を生成する。プリロード情報生成手段２０５は、制約条件と、注目しているマクロ状態遷移グラフのノードの遷移確率の情報を用いて、そのノード（状態）の遷移先である状態番号を1つ選択し、その選択した状態番号のグループリスト及びマイクロ状態遷移グラフを参照して状態遷移順にプリロード情報として登録する。ここで、マクロ状態遷移グラフのノードの遷移確率の情報とは、例えば、そのノードが分岐する状態に対応する初期状態遷移グラフの状態の遷移確率等を意味する。【００７０】
また、ここでの制約条件としては補助制御部３２１で保持できる状態数等を用いる。例えば、この制約条件の場合、マイクロ状態遷移グラフに含まれる状態数とプリロード情報に登録する状態数の合計は、補助制御部３２１で保持できる状態数を越えることはできない。【００７１】
本実施形態のオブジェクトコード変換手段１２３によって生成されたプリロード情報には、マクロ状態遷移グラフの各ノードの付加情報として、次に遷移すると予測されたノードの構成情報に対応する状態番号が含まれる。そのため、このプリロード情報を並列演算装置１４０の書換決定部３３０に入力することで、第１の実施の形態の並列演算装置１４０と比べて、補助制御部３２１による動作サイクル中に、状態管理部３１１の状態の次の状態以降で必要となる構成情報を演算部３２０からのイベント信号に先行して書換決定部３３０から構成書換部３１４に対して構成情報を要求できる。したがって、並列演算装置１４０の処理性能をさらに向上させることができる。
（実施例）
次に本発明のデータ処理装置１２０の実施例について図面を用いて説明する。【００７２】
図１１は、データ供給手段１１０から供給される初期オブジェクトコードに含まれる初期状態遷移グラフの例を示している。図１１の初期状態遷移グラフの各ノードに記載されている番号は状態番号を示し、枝の番号はイベント番号を示し、枝の横に記載された分数値はその分岐の発生確率を示している。初期状態遷移グラフの初期状態は状態「０」である。【００７３】
なお、図１１に示す分岐の発生確率は、データ供給手段１１０から供給される状態遷移に関する情報である。状態遷移に関する別の情報としては、例えば図１２に示すような状態遷移リストがある。この状態遷移リストは、例えば並列演算装置１４０や並列演算装置１４０と同様に動作するシミュレータ等を用いて初期オブジェクトコードを動作させることで得られる状態遷移のリストである。【００７４】
ループ抽出手段２０１は、上記初期状態遷移グラフと上記状態遷移に関する情報とに基づいてループリストを生成する。【００７５】
図１２に示すような状態遷移リストからループ抽出手段２０１が抽出したループリスト及びループ情報の例を図１３に示す。【００７６】
図１３に示す表には、ループに含まれる状態数、ループに含まれる状態番号をループに沿った順列で表記した状態番号列、ループの動作サイクル数の平均値、最大値及び最小値、発生したループの回数が含まれている。なお、図１３には、状態「０」，「１」，「４」からなるループが記載されていないが、これは状態遷移リストにそのようなループが含まれていないことを意味する。状態遷移リストが利用できない場合は状態遷移確率から疑似的なループ情報を生成してもよい。【００７７】
図１１に示した初期状態遷移グラフ及び状態遷移確率から生成したループリストと疑似的なループ情報の例を図１４に示す。【００７８】
図１４は、初期状態遷移グラフ及び状態遷移確率から状態毎の滞在確率を計算し、ループ情報としてループに含まれる状態の滞在確率の和を用いた例を示している。状態遷移リスト及び遷移確率のどちらも利用できない場合は、初期状態遷移グラフの各状態における遷移確率を、その状態の分岐数で割った値にしてもよい。そのようにして生成された状態遷移確率は、上述したように疑似的なループ情報に変換できる。【００７９】
ループ優先順位付け手段２０２は、ループリストに含まれるループ情報に基づいて各ループリストに優先順位を付与し、優先順位付けされたループリストを生成する。【００８０】
図１５は、図１３に示したループリストから生成された優先順付けされたループリストの一例を示している。図１５に示す優先順付けされたループリストでは、ループ情報のうち、ループの動作サイクル数の平均値に基づいて各ループリストに優先順位が付与されている。【００８１】
グループ候補抽出手段２０３は、上記優先順位付けされたループリストを用いて初期オブジェクトコードに含まれる初期状態遷移グラフ及び制約条件に基づいて状態毎のグループリストを生成する。【００８２】
図１６に図１５に示したループリストから生成した状態毎のグループリストの一例を示す。図１６に示すグループリストは、制約条件として、補助制御部３２１で保持できる状態数を「４」とし、構成書換部３１４による構成情報の書換時間に相当する、ループ内で発生した、または発生すると予測される平均動作サイクル数を「２０」として生成した例である。【００８３】
図１６に示す状態毎のグループリストは、グループリストに含まれる状態が、制約条件である「４」以下のできるだけ大きい数で構成され、かつそのグループリストに含まれる全ての状態で発生した、または発生すると予測される平均動作サイクル数が、制約条件である「２０」以上である。【００８４】
マクロ状態遷移生成手段２０４は、入力された初期オブジェクトコードに含まれる初期状態遷移グラフを基にして、上記状態毎のグループリストから、並列演算装置１４０で用いる多階層の状態遷移（マクロ状態遷移グラフ、マイクロ状態遷移グラフ）で構成されるオブジェクトコードを生成する。【００８５】
図１７の（ａ）〜（ｃ）はマクロ状態遷移グラフの生成過程を例示した状態遷移図である。図１８は図１６に示したグループリストから生成したマクロ状態遷移グラフの一例を示す状態遷移図である。【００８６】
図１７の（ａ）は、最初に初期状態である状態「０」に注目し、グループリストの状態番号「０」を参照して、状態番号「０」と「１」からなる状態のグループを抽出し、この状態番号「０」と「１」からなる部分グラフをマクロ状態番号「０」のマイクロ状態遷移グラフとした例を示している。【００８７】
図１７の（ｂ）は、マクロ状態番号「０」から分岐する状態番号が「２」と「４」であるため、まずは状態番号「２」に対して上記と同様の処理を行って状態番号「２」と「３」からなる状態のグループを抽出し、この状態番号「２」と「３」からなる部分グラフをマクロ状態番号「１」のマイクロ状態遷移グラフとした例を示している。【００８８】
図１７の（ｃ）は、マクロ状態番号「０」から分岐する状態番号「４」に対して上記と同様の処理を行って状態番号「４」、「５」、「３」からなるグループを抽出し、この状態番号「４」、「５」、「３」からなる部分グラフをマクロ状態番号「２」のマイクロ状態遷移グラフとした例を示している。【００８９】
以上示したマイクロ状態遷移グラフの組合せで初期状態遷移を全て含むようになったため、マクロ状態遷移生成手段２０４は、これまでに生成したマイクロ状態遷移グラフをノードとし、マイクロ状態遷移グラフ間の遷移を枝とするようなマクロ状態遷移グラフを生成する。【００９０】
プリロード情報生成手段２０５は、初期状態遷移グラフと、グループ候補抽出手段２０３から出力された状態毎のグループリストと、マクロ状態遷移生成手段２０４から出力されたマクロ状態遷移グラフ及びマイクロ状態遷移グラフと、制約条件とからプリロード情報を生成する。【００９１】
図１９に、図１６に示した状態毎のグループリストと図１８に示したマクロ状態遷移グラフから生成したプリロード情報の一例を示す。【００９２】
図１９において、マクロ状態番号「２」がプリロード情報として状態番号「０」しか持たないのは、マクロ状態番号「２」に含まれる状態数が「３」であるためである。これにより、制約条件である「４」を満たすために、プリロードする状態数が１つに制約される。【００９３】
データ出力手段１２４は、これらの出力データをオブジェクトコードとして出力する。【００９４】
次に、本発明のデータ処理装置１２０で生成したオブジェクトコードが並列演算装置１４０で動作したときの様子について、初期オブジェクトコードで動作させたときの並列演算装置１４０の動作と対比させて説明する。【００９５】
図２０は図３に示した並列演算装置１４０の動作の様子を示すタイミングチャートである。【００９６】
図２０の（ａ）は、図１１に示した初期オブジェクトコードで並列演算装置１４０を動作させたときの様子を示し。図２０の（ｂ）は本発明のデータ処理装置１２０で生成したオブジェクトコード（図１８のマクロ状態遷移グラフ）で並列演算装置１４０を動作させたときの様子を示している。また、図２０の（ｃ）は本発明のデータ処理装置１２０で生成したオブジェクトコードで並列演算装置１４０を動作させるに際して、本発明のデータ処理装置１２０で生成したプリロード情報を書換決定部３３０に入力して並列演算装置１４０を動作させたときの様子を示している。【００９７】
なお、図２０の（ａ）〜（ｃ）は、並列演算装置１４０が備える補助制御部３２１、状態管理部３１１及び構成書換部３１４の動作状態を示している。また、図２０の（ａ）〜（ｃ）に示す補助制御部３２１及び状態管理部３１１はそれぞれ制御状態の論理番号を示し、構成書換部３１４は書き換えを行っている構成情報に対応する状態の論理番号を示す。但し、図２０の（ｂ）及び図２０の（ｃ）に示す状態管理部３１１が制御している番号はマクロ状態番号である。ここでは、状態の論理番号とマクロ状態番号とを区別するためにマクロ状態番号を括弧で示している。【００９８】
図２０の（ａ）に示すように、初期オブジェクトコードで並列演算装置１４０が動作している場合、補助制御部３２１で管理している状態と状態管理部３１１で管理している状態は同一であるため、補助制御部３２１にて異なる状態への遷移が発生すると、補助制御部３２１を含む演算部３２０は一時停止して状態管理部３１１に制御を移す（Ｔ１０１）。同一状態への遷移の場合は、この一時停止が発生しない（Ｔ１０４）。【００９９】
また、状態管理部３１１にて状態遷移が発生し、構成情報記憶部３１３に遷移先の状態に対応する構成情報が格納されていない場合、構成番号変換部３１２は構成書換部３１４に構成情報を要求し、状態管理部３１１は構成書換部３１４が構成情報の書き換えを終了するまで一時停止する（Ｔ１０２）。【０１００】
構成情報記憶部３１３に遷移先の状態に対応する構成情報が格納されている場合は一時停止が発生しない（Ｔ１０３）。【０１０１】
図２０の（ｂ）に示すように、本発明のデータ処理装置１２０で生成したオブジェクトコードで並列演算装置１４０が動作している場合、補助制御部３２１で管理している状態はマイクロ状態番号であり、状態管理部３１１で管理している状態はマクロ状態番号であるため、補助制御部３２１はマイクロ状態遷移に含まれない状態遷移のときのみ、状態管理部３１１に制御を移す。そのため、Ｔ１０１で発生していた、補助制御部３２１の状態遷移に伴う一時停止が発生しなくなる（Ｔ２０１）。【０１０２】
さらに、図２０の（ｃ）に示すように、本発明のデータ処理装置１２０で生成したオブジェクトコード及びプリロード情報で並列演算装置１４０が動作している場合は、プリロード情報に基づいて書換決定部３３０が適宜プリロードを行う（Ｔ３０５）。そのため、状態管理部３１１にて状態遷移が発生したとき、構成情報記憶部３１３に遷移先の状態に対応する構成情報が格納されていない場合は、書換決定部３３０にて構成番号変換部３１２から構成書換部３１４に発行する構成情報の要求に先行して構成情報を要求する。したがって、Ｔ１０２やＴ２０２で発生していた状態管理部３１１の構成書き込み終了待ちによる一時停止が発生しない（Ｔ３０２）。【０１０３】
本発明のデータ処理装置１２０は、並列演算装置の物理構造や物理特性に対応した制約条件が事前に登録されており、並列演算装置１４０に入力される初期状態遷移グラフからなる初期オブジェクトコード及びその状態遷移に関する情報から制約条件に基づいて並列演算装置１４０がより効率的に動作するためのオブジェクトコードを生成し、この生成されたオブジェクトコードを出力する。したがって、多階層の状態遷移の制御が可能な構成の並列演算装置のためのオブジェクトコードを生成できる。【０１０４】
本発明の並列演算装置１４０では、本発明のデータ処理装置で生成されたオブジェクトコードが外部記憶手段３４０に格納されており、そのオブジェクトコードのマイクロ状態遷移に対応して演算部３２２が動作し、そのオブジェクトコードのマクロ状態遷移に対応して制御部３１０が動作する。そのため、並列演算装置１４０では、データ処理装置１２０で生成されたオブジェクトコードにしたがって動作サイクル毎に複数の処理回路が並列に動作できる。【０１０５】
また、本発明の他の並列演算装置１４０では、データ処理装置１２０で生成されたオブジェクトコード及びプリロード情報が外部記憶手段３４０に格納されており、そのオブジェクトコードのマイクロ状態遷移に対応して演算部３２２が動作し、そのオブジェクトコードのマクロ状態遷移に対応して制御部３１０が動作し、そのプリロード情報に対応して書換決定部３３０が動作する。そのため、並列演算装置１４０では、データ処理装置１２０で生成されたオブジェクトコードにしたがって動作サイクル毎に複数の処理回路が並列に動作できる。【０１０６】
さらに、本発明の他の並列演算装置１４０では、データ処理装置１２０で生成されたオブジェクトコード及びプリロード情報が供給され、そのオブジェクトコードのマイクロ状態遷移に対応して演算部３２２が動作し、そのオブジェクトコードのマクロ状態遷移に対応して制御部３１０が動作し、そのプリロード情報に対応して書換決定部が動作する。そのため、並列演算装置では、データ処理装置で生成されたオブジェクトコードにしたがって動作サイクル毎に複数の処理回路が並列に動作できる。【０１０７】
また、本発明のデータ処理システムでは、データ処理装置１２０で生成されたオブジェクトコード及びプリロード情報の少なくとも一つが並列演算装置１４０に供給され、データ処理装置１２０に入力される初期オブジェクトコードに対応して並列演算装置１４０が備える演算器３２２が順次切り換わることで並列演算を複数サイクル毎に実行できる。【０１０８】
なお、本発明のデータ処理システムが備える各種手段は、その機能を実現するように形成されていればよく、例えば所定の機能を実現する専用のハードウェア、プログラムにしたがって処理を実行することで所定の機能を実現するデータ処理装置、プログラムによりデータ処理装置の内部で実現される所定の機能、及びこれらの組み合わせ等を許容する。また、本発明のデータ処理システムが備える各種手段は、個々に独立した存在である必要もなく、ある手段が他の手段の一部である構成も許容する。【０１０９】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されものではない。本願発明の構成や詳細は本願発明のスコープ内で当業者が理解し得る様々な変更が可能である。【０１１０】
この出願は、２００７年１０月３日に出願された特願２００７−２５９８８９号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2009044635.tif 000003
【図２】
2009044635.tif 000004
【図３】
2009044635.tif 000005
【図４】
2009044635.tif 000006
【図５】
2009044635.tif 000007
【図６】
2009044635.tif 000008
【図７】
2009044635.tif 000009
【図８】
2009044635.tif 000010
【図９】
2009044635.tif 000011
【図１０】
2009044635.tif 000012
【図１１】
2009044635.tif 000013
【図１２】
2009044635.tif 000014
【図１３】
2009044635.tif 000015
【図１４】
2009044635.tif 000016
【図１５】
2009044635.tif 000017
【図１６】
2009044635.tif 000018
【図１７】
2009044635.tif 000019
【図１８】
2009044635.tif 000020
【図１９】
2009044635.tif 000021
【図２０】
2009044635.tif 000022
【手続補正書】
【提出日】平成21年2月5日(2009.2.5)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の演算器及び前記演算器の接続を切り換える相互接続部を備え、
前記演算器に対する演算命令及び前記演算器の接続関係を示す情報を含む少なくとも一つの構成情報から成るオブジェクトコードにしたがって前記演算器及び前記相互接続部から成る回路の構成を変更して各種の処理を実行する並列演算装置に対して供給する前記オブジェクトコードを生成するためのデータ処理装置であって、
前記並列演算装置の物理構造及び物理特性に対応した制約条件を保持する条件記憶手段と、
単一階層の状態遷移で構成される前記オブジェクトコードを取得するためのデータ入力手段と、
前記データ入力手段によって取得したオブジェクトコードから、前記制約条件に基づいて多階層の状態遷移で構成されるオブジェクトコードを生成するオブジェクトコード変換手段と、
前記オブジェクトコード変換手段で生成された前記多階層の状態遷移で構成されたオブジェクトコードを出力するデータ出力手段と、
を有し、
前記並列演算装置は、
前記構成情報間の遷移関係である状態遷移に基づいて前記演算器及び前記相互接続部から成る回路の構成を変更する制御部と、
前記演算器及び前記相互接続部と前記制御部との間に挿入される、前記制御部で制御可能な状態遷移よりも規模の小さい状態遷移を制御する補助制御部を備え、
前記オブジェクトコード変換手段は、
前記単一階層の状態遷移で構成されるオブジェクトコードの状態遷移を、より小さい規模の状態遷移に重複を許して分割し、
前記状態遷移の分割は、分割された状態遷移間の遷移が少なくなるような分割であるデータ処理装置。
【請求項２】
前記オブジェクトコード変換手段は、
単一階層の状態遷移で構成される前記オブジェクトコードに含まれる状態遷移グラフ及び状態遷移に関する情報からループ構造となる状態遷移を抽出するループ抽出手段と、
前記ループ抽出手段で抽出された状態遷移に対してループ構造の特性に応じた優先順位を付与するループ優先順位付け手段と、
前記優先順位付けされたループ構造から前記制約条件に対応するループ構造を選択し、別階層の状態遷移グラフであるグループリストを抽出するグループ候補抽出手段と、
前記グループリストを用いて単一階層の状態遷移で構成される前記オブジェクトコードに含まれる状態遷移グラフをカバーリングし、多階層の状態遷移で構成されるオブジェクトコードを生成するマクロ状態遷移生成手段と、
を有する請求項１記載のデータ処理装置。
【請求項３】
前記オブジェクトコード変換手段は、
前記単一階層の状態遷移で構成されるオブジェクトコードに含まれる状態遷移グラフと前記多階層の状態遷移で構成されるオブジェクトコードに含まれる多階層の状態遷移グラフを用いて、前記並列演算装置が次に遷移する状態以降に遷移すると予測される状態に対応する構成情報を要求するためのプリロード情報を生成するプリロード情報生成手段を有する請求項２記載のデータ処理装置。
【請求項４】
複数の演算器及び前記演算器の接続を切り換える相互接続部を備え、
前記演算器に対する演算命令及び前記演算器の接続関係を示す情報を含む少なくとも一つの構成情報から成るオブジェクトコードにしたがって前記演算器及び前記相互接続部から成る回路の構成を変更して各種の処理を実行する並列演算装置に対して供給する前記オブジェクトコードを生成するためのデータ処理方法であって、
前記並列演算装置の物理構造及び物理特性に対応した制約条件を条件記憶手段で保持しておき、
単一階層の状態遷移で構成される前記オブジェクトコードを取得し、
該取得したオブジェクトコードから、前記制約条件に基づいて多階層の状態遷移で構成されるオブジェクトコードを生成して出力し、
前記並列演算装置は、
前記構成情報間の遷移関係である状態遷移に基づいて前記演算器及び前記相互接続部から成る回路の構成を変更する制御部と、
前記演算器及び前記相互接続部と前記制御部との間に挿入される、前記制御部で制御可能な状態遷移よりも規模の小さい状態遷移を制御する補助制御部を備え、
前記単一階層の状態遷移で構成されるオブジェクトコードの状態遷移をより小さい規模の状態遷移に重複を許して分割し、
前記状態遷移の分割は、分割された状態遷移間の遷移が少なくなるような分割であるデータ処理方法。
【請求項５】
前記単一階層の状態遷移で構成されるオブジェクトコードに含まれる状態遷移グラフ及び状態遷移に関する情報からループ構造となる状態遷移を抽出し、
該抽出した状態遷移に対してループ構造の特性に応じた優先順位を付与し、
前記優先順位付けされたループ構造から前記制約条件に対応するループ構造を選択し、別階層の状態遷移グラフであるグループリストを抽出し、
前記グループリストを用いて前記単一階層の状態遷移で構成されるオブジェクトコードに含まれる状態遷移グラフをカバーリングし、多階層の状態遷移で構成されるオブジェクトコードを生成する請求項４記載のデータ処理方法。
【請求項６】
前記単一階層の状態遷移で構成されるオブジェクトコードに含まれる状態遷移グラフと前記多階層の状態遷移で構成されるオブジェクトコードに含まれる多階層の状態遷移グラフを用いて、前記並列演算装置が次に遷移する状態以降に遷移すると予測される状態に対応する構成情報を要求するためのプリロード情報を生成する請求項５記載のデータ処理方法。
【請求項７】
複数の演算器及び前記演算器の接続を切り換える相互接続部を備え、
前記演算器に対する演算命令及び前記演算器の接続関係を示す情報を含む少なくとも一つの構成情報から成るオブジェクトコードにしたがって前記演算器及び前記相互接続部から成る回路の構成を変更して各種の処理を実行する並列演算装置に対して供給する前記オブジェクトコードをデータ処理装置に生成させるためのプログラムであって、
前記並列演算装置の物理構造及び物理特性に対応した制約条件を条件記憶手段に保持させ、
単一階層の状態遷移で構成される前記オブジェクトコードを取得させ、
該取得したオブジェクトコードから、前記制約条件に基づいて多階層の状態遷移で構成されるオブジェクトコードを生成して出力させ、
前記並列演算装置は、
前記構成情報間の遷移関係である状態遷移に基づいて前記演算器及び前記相互接続部から成る回路の構成を変更する制御部と、
前記演算器及び前記相互接続部と前記制御部との間に挿入される、前記制御部で制御可能な状態遷移よりも規模の小さい状態遷移を制御する補助制御部を備え、
前記単一階層の状態遷移で構成されるオブジェクトコードの状態遷移をより小さい規模の状態遷移に重複を許して分割し、
前記状態遷移の分割は、分割された状態遷移間の遷移が少なくなるような分割であるプログラム。
【請求項８】
前記単一階層の状態遷移で構成されるオブジェクトコードに含まれる状態遷移グラフ及び状態遷移に関する情報からループ構造となる状態遷移を抽出し、
該抽出した状態遷移に対してループ構造の特性に応じた優先順位を付与し、
前記優先順位付けされたループ構造から前記制約条件に対応するループ構造を選択し、別階層の状態遷移グラフであるグループリストを抽出し、
前記グループリストを用いて前記単一階層の状態遷移で構成されるオブジェクトコードに含まれる状態遷移グラフをカバーリングし、多階層の状態遷移で構成されるオブジェクトコードを生成するための請求項７記載のプログラム。
【請求項９】
前記単一階層の状態遷移で構成されるオブジェクトコードに含まれる状態遷移グラフと前記多階層の状態遷移で構成されるオブジェクトコードに含まれる多階層の状態遷移グラフを用いて、前記並列演算装置が次に遷移する状態以降に遷移すると予測される状態に対応する構成情報を要求するためのプリロード情報を生成するための請求項８記載のプログラム。
【請求項１０】
請求項７から９のいずれか１項記載のプログラムが格納された記録媒体。
【請求項１１】
複数の演算器、前記演算器の接続を切り換える相互接続部及び請求項１から３のいずれか１項記載のデータ処理装置で生成された前記オブジェクトコードを格納するための外部記憶手段を備え、
前記演算器に対する演算命令及び前記演算器の接続関係を示す情報を含む少なくとも一つの構成情報から成るオブジェクトコードにしたがって各種の処理を実行する並列演算装置。
【請求項１２】
複数の演算器及び前記演算器の接続を切り換える相互接続部を備え、
請求項１から３のいずれか１項記載のデータ処理装置で生成されたオブジェクトコードが入力される、前記演算器に対する演算命令及び前記演算器の接続関係を示す情報を含む少なくとも一つの構成情報から成るオブジェクトコードにしたがって各種の処理を実行する並列演算装置。
【請求項１３】
請求項１から３のいずれか１項記載のデータ処理装置と、
前記データ処理装置で生成されたオブジェクトコードが入力される請求項１２に記載の並列演算装置と、
を有するデータ処理システム。
【国際調査報告】
2009044635.tif 000023
2009044635.tif 000024
2009044635.tif 000025
2009044635.tif 000026