(57)【特許請求の範囲】
【請求項１】
複数種類のプロセッサユニットを複数個有するヘテロジニアスマルチプロセッサに実行させる出力コードを入力プログラムから生成するヘテロジニアスマルチプロセッサ向けグローバルコンパイラにおいて、
前記複数種類のプロセッサユニットは、汎用プロセッサユニットと専用プロセッサユニットを含んで構成され、
前記入力プログラムを、前記ヘテロジニアスマルチプロセッサが有する前記専用プロセッサユニットと汎用プロセッサユニットの種別毎に予め用意した前記各プロセッサユニット専用のコード生成コンパイラにて、前記入力プログラムを解析することで前記各プロセッサユニット毎に実行可能なプログラム部分の処理コストを算出し、当該プログラム部分の処理コストを各プロセッサユニット毎に対象プロセッサ情報として生成する第１の処理と、
前記入力プログラムの解析を行って、前記入力プログラムを複数の粒度のタスクに分割し、前記タスク間の制御依存性及びデータ依存性を解析することで前記タスク間の並列性を抽出し、前記対象プロセッサ情報の処理コストを用いて前記各タスクを割り当てるプロセッサユニットを決定する第２の処理と、
前記タスクを割り当てた前記プロセッサユニット毎の出力コードを出力する第３の処理と、
を計算機に実行させ、
前記第１の処理は、
前記専用プロセッサユニットと汎用プロセッサユニットの種別毎に前記入力プログラムの実行可能な部分を前記各プロセッサユニットで処理を行う実行時間を見積もった実行時間情報を前記処理コストとして生成する
ことを特徴とするヘテロジニアスマルチプロセッサ向けグローバルコンパイラ。
【請求項２】
請求項１に記載のヘテロジニアスマルチプロセッサ向けグローバルコンパイラにおいて、
前記第１の処理は、
前記実行時間情報の実行時間に加え、前記各プロセッサユニット毎に必要となるデータの共有メモリとプロセッサユニット内のローカルメモリ間のデータ転送時間を算出し、データ時間転送時間情報を生成する処理を含むことを特徴とするヘテロジニアスマルチプロセッサ向けグローバルコンパイラ。
【請求項３】
請求項１に記載のヘテロジニアスマルチプロセッサ向けグローバルコンパイラにおいて、
前記第１の処理は、
前記実行時間情報を生成する際に、
さらに前記対象となるプロセッサユニットのハードウェアアーキテクチャに基づき、プログラムロード時間、並びに前記プロセッサユニット内の演算器制御時間を算出し、プログラムロード時間情報並びに演算器制御時間情報を生成することを特徴とするヘテロジニアスマルチプロセッサ向けグローバルコンパイラ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の異種プロセッサユニットで構成されるマルチプロセッサシステムにおいて、当該複数プロセッサユニットを効率よく動作させることを可能とする実行プログラムを生成するコンパイル方法及びコンパイラに関する。
【背景技術】
【０００２】
半導体製造技術の進歩による素子の微細化により、膨大な数のトランジスタを集積することが可能となっている。それと同時にプロセッサの高周波数化も進むが、動作時電力の増加、またリーク電流に起因する待機時電力の増加により、従来のプロセッサが歩んできた動作周波数の向上と論理方式の改善により達成してきた性能向上に限界が見え始めている。一方で、自動車のナビゲーションシステム、携帯電話、デジタルテレビなど、画像、音声、データベース情報など多様なデータを同時に扱うデジタル民生機器が登場し、特性の異なる膨大なデータを短時間にかつ低電力に処理することが強く求められている。
【０００３】
そこで現在、性能改善と低電力化を実現する手段として、従来の単一チップで提供された汎用プロセッサ（ＣＰＵ）を複数個単一チップ上に集積し、処理を並列で行うことで、動作周波数を向上させなくとも、高い演算性能を得ることが可能な、マルチプロセッサシステムが有望となっている。将来、微細化がさらに進むことで、ＰＵをオンチップで１００個〜１０００個積載することも可能となると予測される。また、特に組み込み機器向けシステムにおいては、無線や画像、音声など定型的なデジタル信号処理を扱うことも多く、性能改善と低電力化を両立する手段として、同一の汎用プロセッサ（ＣＰＵ）、つまり同一の命令セットで構成及び演算性能が同一な汎用プロセッサを複数個集積したホモジニアスなマルチプロセッサシステム以外に、複数個のＣＰＵに加えある特定の処理を非常に効率良く（高速にかつ低電力に）処理可能な専用プロセッサ、アクセラレータ、といった命令セットが異種である、様々な種類のＰＵを複数個単一チップで搭載し、特に一定のアプリケーションを対象とし、高い演算効率を目指したヘテロジニアスマルチプロセッサシステム（ＨＣＭＰ）が現在提案されている。専用プロセッサの一例として、非特許文献１のような動的再構成可能プロセッサ（ＤＲＰ）がある。
【０００４】
このようなマルチプロセッサシステムにおいて、ＰＵの数に比例した演算性能を得るためには、搭載されたＰＵを同時に稼動させプログラムを処理する必要がある。しかしながら、通常の入力プログラムは処理が時系列で逐次的に記述されているため、複数のＰＵを搭載するにも関わらず、当該複数ＰＵに比例して期待される演算性能を得ることができない。この問題点を解決するための一つの方法として、プログラム開発者が自らプログラムの並列性を考慮し、当該プログラムを実行させるマルチプロセッサシステムの構成に基づいて、当該プログラムを複数のＰＵで実行させるための並列化コードを付加する必要がある。しかしながら、本手法はＰＵが数個のシステムにおいては有効であるが、将来の数十〜数千といった数のＰＵが積載されたシステムにおいては、また特にＰＵが異種で構成されるＨＣＭＰの場合は、開発時間、実効性能の点で実用的ではない。
【０００５】
＜公知例：マルチグレイン並列化コンパイラ＞
そこで、ホモジニアスマルチプロセッサにおいては、プログラムの並列性を自動で抽出し、複数のＰＵに処理を分散し処理性能を向上させる自動並列化コンパイラが提案されている。つまり、入力プログラムを解析し、当該プログラム中から並列に動作可能な部分を抽出し、当該部分を複数のＰＵに割り当て同時に実行することを可能とする、自動並列化コンパイラの研究がすでに行われている。例えば、入力ソースプログラムを解析し、当該プログラムをサブルーチンやループなどさまざまな粒度のブロック（タスク）に分割し、当該複数タスク間の並列性を解析すると共に、タスクとそれらがアクセスするデータをキャッシュあるいはローカルメモリに適合するサイズに分割し、それらを各ＰＵに対して当該タスクを最適割り当てすることによって、マルチプロセッサシステムを効率よく動かす目的プログラムを生成するコンパイル方式が、で特許文献１に開示されている。またマルチグレイン並列処理の機能をサポートするチップマルチプロセッサのアーキテクチャが、特許文献２で開示されている。
【０００６】
＜公知例：非対称マルチプロセッサ、電力スケジューリング＞
また、ヘテロジニアスマルチプロセッサ（ＨＣＭＰ）においては、その異種構成のプロセッサ群の性能を引き出すためのタスク割り当て手段として、画像処理など予め処理の手順が判明しているアプリケーションにおいて、各処理の特性に合わせてＣＰＵやＤＳＰなどの種類の異なる複数のプロセッサを組み合わせ、当該プロセッサ上での処理時間や消費電力情報を予め測定し与えておくことで、当該情報により動的に一連の処理を当該各プロセッサに割り当てる手法が、特許文献３で開示されている。
【０００７】
＜公知例：自動ベクトルコンパイラ＞
また、ＨＣＭＰではプロセッサの種類前に専用の実行コードを生成する必要があるが、その生成手段として、例えば専用プロセッサがベクトル演算器である場合は、プログラムよりベクトル演算可能な部分（ループ）をデータ依存解析より抽出し、ベクトル演算命令を生成する自動ベクトルコンパイラが非特許文献２及び非特許文献３で開示されている。
【特許文献１】特開２００４−２５２７２８
【特許文献２】特開２００１−１７５６１９
【特許文献３】特開２００４−２５２９００
【非特許文献１】津野田、他、「デジタルメディア向け再構成型プロセッサＦＥ−ＧＡの概要」、電気電子情報通信学会技術報告、ＲＥＣＯＮＦ−６５
【非特許文献２】田中、岩澤、「ベクトル計算機のためのコンパイル技術」、情報処理、第３１巻、第６号、平成２年６月５日発行
【非特許文献３】Ｋｕｃｋ，Ｄ．Ｊ．，ｅｔ．ａｌ．，：Ｄｅｐｅｎｄｅｎｃｅ  Ｇｒａｐｈｓ  ａｎｄ  Ｃｏｍｐｉｌｅｒ  Ｏｐｔｉｍｉｚａｔｉｏｎｓ，  Ｐｒｏｃ．  ８ｔｈ  Ａｎｎｕａｌ  ＡＣＭ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｐｒｉｎｃｉｐｌｅｓ  ｏｆ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｌａｎｇｕａｇｅｓ，ｐｐ．１７７−１８９（１９８１）
【発明の開示】
【発明が解決しようとする課題】
【０００８】
現在、自動車のナビゲーションシステム、携帯電話、デジタルテレビなどといった、画像、音声、データベース情報など多様なデータを同時に扱う新アプリケーションが生まれる中で、様々な種類の入力データを、当該データ夫々に最適な方法で同時に処理をするために、プロセッサは複数種類のＰＵを搭載するＨＣＭＰが有望となると考えられる。従来のマルチプロセッサシステムでは、特許文献２で開示されているように同じ構成のＰＵを複数搭載したホモジニアスなプロセッサシステムであった。しかしながらこのように、多様なアプリケーションが同時に多種のＰＵ上で処理される将来のヘテロジニアスマルチプロセッサシステムにおいて、搭載するＰＵの種類と数に比例して処理性能を得るためには、ＰＵの種類を考慮したプログラムの並列化と配置が必須となることに発明者は気づいた。
【０００９】
また従来、複数のＰＵ上でプログラムを効率よく実行するためには、小規模なプログラムや処理シーケンスが常に固定的に決定できる応用に対しスケジューリングを行うための実行時間などのスケジュール情報を得るために、一度プログラムを当該システム上で実行し測定することが必要となり、当該測定値を元に開発者が予め当該スケジュール情報を手動で生成する必要があった。この場合、事前に処理の内容やシーケンスが不明な一般のプログラムの場合、特に規模が大きな場合は、当該情報を事前に手動で生成することが困難となる。またＰＵの種類や数が増加した場合も同じく、当該情報を手動で生成することが困難となる。そこで発明者は、プログラムをコンパイルする時、ＰＵの構成に基づきコンパイラが予め事前の処理時間を見積もり、コンパイル時に処理順序を静的に決定できる部分に関しては事前に処理手順を決定しておき、また実行時にならないと処理順序が決定できない部分に関しては、コンパイラが実行時間を含んだ処理情報に基づいたスケジューリングを動的に行うプログラムを生成することで、一般のプログラムを多様なＰＵで構成されるマルチプロセッサシステム上で効率よく処理できることに気づいた。
【００１０】
そこで本発明の目的は、多様なＰＵを積載するＨＣＭＰにおいて、処理対象となる入力プログラムから当該ＨＣＭＰが持つ専用プロセッサ（またはアクセラレータ）で処理が可能なプログラム部分をユーザの指定に基づき、または当該専用プロセッサ向けの実行コードを生成するコンパイラが当該専用プロセッサにて効率良く実行可能な部分を抽出することにより、その当該指定並びに当該抽出されたタスクを含む形で、並列化コンパイラが自動的に並列性を持つタスクを抽出し、各ＰＵの特性に合わせて当該タスクを配置することで当該ＰＵを効率よく動かし、さらに当該ＰＵの処理量を見積もることで動作周波数や電源電圧を最適化する、コードを生成し目的プログラムに付加するコンパイラ及びその最適化を可能とするヘテロジニアスマルチプロセッサ向け並列化コンパイラシステムを提供することで、ユーザがＨＣＭＰにあわせた並列化を意識することなく、短期間にＨＣＭＰの性能を最大限引き出すことを可能とすることにある。
【課題を解決するための手段】
【００１１】
本発明は、ヘテロジニアスマルチプロセッサ上で、プログラムを当該プロセッサが積載する各種プロセッサユニットの処理特性に合わせたプログラム分割手段となるグローバルコンパイラを提供する。またさらに、分割したプログラムを各種プロセッサユニットの性能を最大限活用できるよう、また当該複数プロセッサユニットを同時に並行して動作させることで、効率よく処理ができるよう、前記分割プログラムをスケジューリングする手段となるグローバルコンパイラを提供する。
【００１２】
その具体的な方法としては、複数種類のプロセッサユニットを複数個有するヘテロジニアスマルチプロセッサに実行させる出力コードを入力プログラムから生成するヘテロジニアスマルチプロセッサ向けグローバルコンパイラにおいて、前記複数種類のプロセッサユニットは、汎用プロセッサユニットと専用プロセッサユニットを含んで構成され、前記入力プログラムを、前記ヘテロジニアスマルチプロセッサが有する前記専用プロセッサユニットと汎用プロセッサユニットの種別毎に予め用意した前記各プロセッサユニット専用のコード生成コンパイラにて、前記入力プログラムを解析することで前記各プロセッサユニット毎に実行可能なプログラム部分の処理コストを算出し、当該プログラム部分の処理コストを各プロセッサユニット毎に対象プロセッサ情報として生成する第１の処理と、前記入力プログラムの解析を行って、前記入力プログラムを複数の粒度のタスクに分割し、前記タスク間の制御依存性及びデータ依存性を解析することで前記タスク間の並列性を抽出し、前記対象プロセッサ情報の処理コストを用いて前記各タスクを割り当てるプロセッサユニットを決定する第２の処理と、前記タスクを割り当てた前記プロセッサユニット毎の出力コードを出力する第３の処理と、を計算機に実行させ、前記第１の処理は、前記専用プロセッサユニットと汎用プロセッサユニットの種別毎に前記入力プログラムの実行可能な部分を前記各プロセッサユニットで処理を行う実行時間を見積もった実行時間情報を前記処理コストとして生成する。
【００１３】
また、前記グローバルコンパイラにおいて、プログラムの部分を実行すべきプロセッサを指定する前記プロセッサ情報を指示文として入力プログラムに挿入する処理を行うことで、課題を解決する。
【００１４】
また、前記グローバルコンパイラにおいて、前記プロセッサ情報に加え、前記プロセッサにて実行した際の実行時間、データ転送時間、制御時間等をコスト情報として生成する処理を行うことで、課題を解決する。
【００１５】
またさらに、前記コスト情報を指示文として入力プログラムに挿入する処理を行うことで、課題を解決する。
【発明の効果】
【００１６】
本発明により、多様なＰＵを集積するマルチプロセッサシステムにおいて、当該ＰＵを効率よく動作させるプログラムの分割配置および制御コードを生成する複数コンパイラ連携プログラム並列化手法により、当該プロセッサシステムの性能を最大限活用しつつ、低電力にて効率よく処理することが可能となる。また、さらにはソフトウェア開発者がプロセッサの構成を意識することなく、短時間で効率良いプログラム作成が可能となる。
【発明を実施するための最良の形態】
【００１７】
以下、本発明の一実施形態を添付図面に基づいて説明する。
＜実施形態の全体構成＞
本発明の実施形態として、まず本発明で提供する並列化コンパイル方式の適用対象となるヘテロジニアスマルチプロセッサシステム（以下、ＨＣＭＰ）１の構成を図１のブロック図を参照しながら説明する。ＨＣＭＰ１では、複数の異種のプロセッサユニット（ＰＵ）、共有メモリ（ＣＳＭ）で構成する。当該各ＰＵは、インタコネクション・ネットワーク（ＬＢＵＳ）に接続される。また、当該ＳＭはＬＢＵＳに接続される。当該各ＰＵは、当該ＰＵのプロセッサコア、メモリ等の各部位に対し電源電圧及び動作クロックを供給する、電源電圧・クロック周波数制御回路が接続される。本実施形態ではＰＵの種類と個数を、２個の汎用処理プロセッサ（ＣＰＵ）、１個の信号処理プロセッサ（ＤＳＰ）、２個の動的再構成可能プロセッサ（ＤＲＰ）で構成したが、ＰＵの種類や数は本実施形態で示した限りではなく、さまざまな構成を取り得る。
【００１８】
各ＰＵは当該ＰＵで処理されるプログラムやデータを一時的に保存するローカルメモリ（またはキャッシュ）（ＬＭ）及び、当該ＰＵに対する電源電圧や動作周波数を決定する周波数・電源電圧制御レジスタ（ＦＶＲ）、を具備する。なお、ローカルメモリ（ＬＭ）２４は、他のＰＵ及び当該ＬＭを持つ自ＰＵからアクセス可能なグローバルアドレスがマッピングされている空間と、当該自ＰＵのみアクセス可能なプライベートアドレスがマッピングされている空間に分割される。なお、ＬＢＵＳに接続された共有メモリ（ＣＳＭ）はグローバルアドレスがマッピングされており、全ＰＵからアクセス可能である。なお以上は本発明における適用構成の一例に過ぎず、実施方法としてはこの限りでない。例えば図１では表現されていないが、ＬＢＵＳには入出力処理、割り込み処理、タイマ、デバッグ回路、等の周辺回路を必要に応じて接続することとなる。また、バスブリッジを介して、同種類または異種類のバスを階層的に接続することも考えられる。
【００１９】
このように、複数の種類のＰＵが持つ性能を引き出すためには、各ＰＵを並行して動作させること、また特に専用プロセッサであるＤＲＰやＤＳＰには当該プロセッサを効率良く稼動させることが可能な処理を割り振ることが必要となる。
【００２０】
＜グローバルコンパイラの構成＞
ＨＣＭＰ１向けプログラム並列化並びに実行コード生成の処理の一例を示すフローチャートを図２ａに図示する。入力されるプログラム２００（以下、入力プログラム）は通常、逐次的に記述されるが、本フローチャートによりＨＣＭＰ１が持つＰＵを最大限活用できるように、入力プログラム２００のタスク分割と並列性解析、並びにスケジューリングが実施される。本発明では図２ａで示したフローチャートによる処理手順を、グローバルコンパイラ２と呼ぶこととする。以下図２ａに示すグローバルコンパイラ２の全体のフローチャートをまず簡単に説明し、次に各コンパイル段階におけるフローを詳細に説明する。なお、図２ａに示す処理は、予め用意したコンピュータによって実行されるものである。
【００２１】
グローバルコンパイラ２への入力は、ユーザがＣ言語やＦＯＲＴＲＡＮなどの高級言語を用いて処理ステップを逐次的に記述した入力プログラム２００となる。また、さらにグローバルコンパイラ２がターゲットとするＨＣＭＰ１の構成情報２０４もあわせて入力する。図３に入力プログラム２００の一例を示す。入力プログラム２００はこのようにループやサブルーチン、条件分岐などの制御構造を持ち、ＨＣＭＰ１並列化コンパイラではこの構造を手がかりに構造単位でタスク分割を行うことになる。
【００２２】
＜ＨＣＭＰアーキテクチャ構成情報＞
続いてＨＣＭＰ１の構成情報の例を図４に示す。図２ａに示したアーキテクチャ構成情報２０４には、図１に示したＨＣＭＰ１の構成のアーキテクチャ情報を、グローバルコンパイラによる並列化に必要なパラメータ情報として予め入力する。アーキテクチャ構成情報２０４へ入力する通常パラメータ情報としては、ＰＵの種類、数、ＰＵの対バス動作速度比、各ＰＵが持つメモリの種類、メモリサイズ、及びメモリアクセスレイテンシ、ＨＣＭＰ１が持つメモリ種類、サイズ、レイテンシ、等が定義される。例えば、図４の１行目、「ｐｕ  ０  ｃｐｕ  ｃｌｏｃｋ＝２  ｌｄｍ＝１２８ＫＢ，２ｃｙｃ  ｄｓｍ＝１６ＫＢ，１ｃｙｃ  ｉｃａｃｈｅ＝８ＫＢ，２ｗａｙ」は、先頭よりその意味を説明すると、「ＰＵ」はパラメータの種別を示しここではプロセッサユニットに関する属性を表現する。「０」はＰＵ番号をあらわし、「ｃｐｕ」はプロセッサ種別としてＣＰＵであることを示す。次に「ｃｌｏｃｋ＝２」は当該ＰＵのバスに対する速度比が２倍であることを、「ｌｄｍ＝１２８ＫＢ、２ｃｙｃ」はローカル・データ・メモリ（ＬＤＭ）を保持しそのサイズが１２８ＫＢ、アクセスレイテンシが２サイクルであることを表現する。
【００２３】
さらに「ｄｓｍ＝１６ＫＢ、１ｃｙｃ」は分散共有メモリを保持しそのサイズが１６ＫＢ、アクセスレイテンシが１サイクル、「ｉｃａｃｈｅ＝８ＫＢ、２ｗａｙ」は８ＫＢの２ウェイ命令キャッシュを持つことを示している。また９行目はＨＣＭＰ１が持つ集中共有メモリ（ＣＳＭ）を示し、「ｏｎｃｈｉｐ」はチップ上に搭載されたことを意味している。
【００２４】
つまり、この構成情報より、ＨＣＭＰ１が図１で示すように、汎用プロセッサＣＰＵ×４、信号処理プロセッサＤＳＰ×２、及び動的再構成可能プロセッサ（ＤＲＰ）×２で構成され、各ＰＵはローカルメモリを保持することになる。なお、構成情報としては、図４に示した以外にも、例えばバスの構成、各ＰＵが持つ電力モードの種別、等を指定することも考えられる。例えば、バスのネットワーク構成としては、双方向の１本バスや３本バス、リング状のバス、クロスバ接続、等が表現できる。またバストランザクション方式（アトミックトランザクションか、バスの要求と返答を分離できるスプリットトランザクションか）の指定がある。また各PEがどのバスに接続されているか、またはクラスタ構造がとられた場合どのドメインのバスに属しているか、等も指定できる。
【００２５】
また電力モードの種別としては、クロック停止や電源遮断などの電力制御モードの定義や各モードにおける電力制御時の効果の記述も考えられる。本構成情報は、グローバルコンパイラが並列化スケジューリングする際に必要となる処理時間や電力といったコストを導出するために必要となる。また並列化のためのプログラム分割を行う際も、ＰＵが持つメモリ容量を考慮する必要があるため、本構成ファイルの情報を用いることとなる。
【００２６】
＜グローバルコンパイラの処理フロー＞
次に、各プロセッサ向けコード生成コンパイラ２１０と並列化コンパイラ２１１を連携させ、入力プログラム２００をヘテロジニアスマルチプロセッサ（ＨＣＭＰ）１上で並列実行する実行コード２０６に変換する、グローバルコンパイラ２の処理フローを説明する。まず、入力プログラム２００はＨＣＭＰ１が持つプロセッサの種類毎に用意された複数の各種プロセッサ向けコード生成コンパイラＡＣＣＰＬ２１０にて順次処理される。特にＨＣＭＰ１が持つ専用プロセッサは通常のＣＰＵとは命令セットが異なるため、並列化スケジューリング時に必要な処理コストを別途見積もる必要があり、またＰＵの種別によっては効率的に処理可能なプログラム構造が限られていることが多くあるため、ＨＣＭＰ１が持つプロセッサ種類毎に用意された各種プロセッサ向けのコード生成コンパイラＡＣＣＰＬ２１０で処理を行うことで、次段の並列化コンパイラ２１１が必要とする情報を生成する。
【００２７】
なお、ヘテロジニアスマルチプロセッサ１では、命令セットが異なる汎用プロセッサが複数持つこともできる。この際も、汎用プロセッサといえどもアーキテクチャの違いで効率良く処理可能なプログラム構造が異なるため、プログラム構造に対する実行時間等の各種情報を生成することもできる。
【００２８】
つまり、ＡＣＣＰＬ２１０は入力プログラム２００に対し、各種プロセッサでの最適処理部の指定、並びに当該処理部の当該各種プロセッサで処理を行った際の処理時間（処理コスト＝実行サイクル数）を求め、対象プロセッサ情報として当該入力プログラム２００に付加する。なお、当該処理段階でのＡＣＣＰＬ２１０の出力は、入力プログラム２００に上述した情報を付加したプログラム２０１となる。また、前記対象プロセッサ情報は入力プログラム２００に付加するのではなく、前記情報に加え、当該情報に対する当該入力プログラム２００の位置を示す情報を別途ファイル等（２０９）で生成しておくことも考えられる。また、予めユーザによる処理プロセッサ指定などで、予め固定的に処理プロセッサが決められているプログラム部分に対しては、この段階で当該プロセッサ向け実行コード２０５を別に生成しておいて、並列化スケジューリング後に当該実行コードをリンクしてＨＣＭＰ１向け実行コードとすることも可能である。
【００２９】
次に、ＡＣＣＰＬ２１０における処理結果（対象プロセッサ情報付加プログラム）２０１を利用して並列化コンパイラ（ＰＲＬＣＰＬ）はプログラム構造を解析し、プログラムの分割と分割したプログラム単位（タスク）の並列性を抽出し、通常ＣＰＵで処理した際のコストを求め、並列性を元に同時に実行できる処理を複数のＰＵに全体の処理時間が短くなるようタスクの割り当てを行う。このとき、ＨＣＭＰ１上の専用プロセッサで処理できる部位に関しては、入力プログラム２００に付加された情報を活用して、専用プロセッサに処理を割り当てることで全体の終了時間が早くなると判断できる場合は、当該専用プロセッサにタスク割り当てを行うこととなる。
【００３０】
また、専用プロセッサ資源の制約により当該専用プロセッサが混雑している場合で、通常のＣＰＵで処理したほうが早くなると判断できる場合は、汎用プロセッサにタスクを割り当てる。スケジューリングの結果、分割されたタスク毎に対応する入力プログラム２０１に対し、タスクの目印となる指示文、処理対象となるＰＵを示す指示文（並列化情報）が並列コンパイラにより挿入・付加される。また、各タスクに対応するプログラムで用いるデータの、ＨＣＭＰ１上でのメモリ配置を示す指示文も併せて挿入されることとなる。
【００３１】
続いてこのタスク分割、配置を示す指示文が付加された入力プログラム２０２は、再度汎用プロセッサＣＰＵ及び専用プロセッサを含むＰＵ種別毎の専用プロセッサ向けコンパイラＡＣＣＰＬ２１０で処理することにより、各ＰＵの実行コードを生成する。ＡＣＣＰＬ２１０に入力されるプログラムには、処理対象となるＰＵが明記されているため、各ＰＵ向けコード生成コンパイラは各コンパイラが対象とするＰＵでの処理が指定された部分のみを解析し、実行コード２０３に変換すれば良い。
【００３２】
なお、スケジューリング全体の最適化をさらに行うために、並列化コンパイラＰＲＬＣＰＬ２１１で生成されたスケジューリング情報等のコンパイラ情報２０８、またＡＣＣＰＬ２１０で並列化コンパイラＰＲＬＣＰＬ２１１によるスケジューリングに基づく実行コード生成の結果得た、より正確なコスト情報を含むコンパイラ情報２０７を、並列化コンパイラＰＲＬＣＰＬ２１１に入力し（２２１）、再度スケジューリングを実行することも可能である。ＨＣＭＰ１における実行コードの最適化をより深く行いたいときは、この処理（２１０）を繰り返すことで、プログラム全体の最適化が実行される。
【００３３】
なお、図２ｂに示す通り、当該コンパイラ情報２０７、２０８をグローバルコンパイラ２の処理の初段に位置する各種プロセッサ向けコード生成コンパイラ２１０に入力し（２２３）、再度コード生成コンパイラ２１０による各種プロセッサ向けタスク抽出と実行時間評価を行うこともできる。
【００３４】
ＡＣＣＰＬ２１０で生成された実行コード２０３は、リンカ２１２にて各プログラムやデータのＨＣＭＰ１上でのメモリ位置を指定し、また第１段階の専用プロセッサ向けコンパイラＡＣＣＰＬ２１０で生成された実行コードを使用することが並列化コンパイラ２１１の出力プログラム２０２に指定されていた場合は当該実行コードを含め、単一のＨＣＭＰ１向けの実行コード（オブジェクト）２０６としてマージする。実行オブジェクト２０６はディスク装置やオフチップ共有メモリ（ＣＳＭ）上に置かれ、実行時にオブジェクトコードをロードすることにより、ＰＵ毎のプログラムが各ＰＵに読み込まれ、実行を開始することとなる。
【００３５】
なお、実際にＨＣＭＰ１チップまたはＨＣＭＰシミュレータ上で実行し、その結果得られたタスク実行時間、データ転送時間、バス利用時間、電力制御効果、キャッシュミス率、等の情報を実行プロファイル情報２３１として収集し、次回のコンパイルに活用することもできる。つまり、当該実行プロファイル情報を並列化コンパイラＰＲＬＣＰＬ２１１に入力して、実行時間をより短縮する、また消費電力をより低減することを目的として、スケジューリング全体の最適化を行うこともできる。なお、図２ｂに示す通り、当該コンパイラ情報プロファイル情報２３１をグローバルコンパイラフローの初段に位置する各種プロセッサ向けコード生成コンパイラ２１０に入力し（２２２）、コード生成コンパイラ２１０による各種プロセッサ向けタスク抽出と実行時間評価に活用することもできる。
【００３６】
＜各種プロセッサ向けライブラリを用いたコンパイルフロー＞
各種専用プロセッサは、記述されたプログラムを各プロセッサ向けコード生成コンパイラ２１０にて各プロセッサ毎の実行コードに変換し、当該実行コードを処理するが、専用プロセッサによっては必ずしも実行コードに変換するコード生成コンパイラが用意されているとは限らない。例えば、信号処理プロセッサ（ＤＳＰ）のようなプロセッサでは、通常のＣ言語の形で書かれたプログラムをＤＳＰ向け実行コードに変換することは難しい。
【００３７】
一般的には、ある機能を実現する実行コードを予めコンパイラを用いずアセンブリ等でライブラリとして記述しておき、ユーザが当該プロセッサを用いる場合は当該ライブラリを呼び出す形が取られる。また、通常プログラムを解釈しない、動作をハードウェア的に定義した専用処理回路は、当該回路に対しデータを与え処理を起動する、といった制御動作をライブラリとして定義することになる。
【００３８】
このようにライブラリベースで各種プロセッサを用いる場合も、グローバルコンパイラ２は対応する。具体的には、図２ｃに示すように、各種プロセッサライブラリ２３０を導入する。当該ライブラリ２３０は各種プロセッサ向けの実行コードや制御コード、並びに当該処理の実行時間といったコスト情報２３２が格納されている。ユーザはプログラム２００においてサブルーチンコールの形でライブラリ２３０を呼び出すことができる。例えば、図３の入力プログラム例で「ｆｕｎｃ３」のサブルーチンコール３０１と同様に記述できる。この際、コスト情報２３２を図３の「#pramga hcmp assign dsp」（３００）のように指示文でプログラム中に明示するか、後段の並列化コンパイラＰＲＬＣＰＬ２１１が各種プロセッサライブラリのコスト情報２３２を参照する。並列化コンパイラ２１１以下の処理は、図２ａ、図２ｂで示したフローと同様である。
【００３９】
＜各種プロセッサ向けコンパイラの処理フロー＞
以上が、ＨＣＭＰ１向けグローバルコンパイラ２の処理フローとなる。次に、各種専用プロセッサ向けコンパイラＡＣＣＰＬ２１０の処理手順を説明する。まず、並列化コンパイラＰＲＬＣＰＬ２１１に入力するため、ＡＣＣＰＬ２１０の出力プログラム２０１を生成する処理フローを図５ａに図示する。
【００４０】
以下では、プロセッサとしてＤＲＰ等の専用処理プロセッサを例に説明する。ＡＣＣＰＬ２１０はまずプログラム２００の構造の解析を行い、コンパイラ内部で変数や演算、制御構造単位に分割した中間コードを生成する（２１０１）。続いて解析されたプログラム構造、特にループといった制御構造に着目し、ループ内の演算データフローやループのイタレーション間の依存性解析を行い、当該ループを連続的に効率良く対象となるＰＵ上で処理可能かを判定する（２１０２、２１０３）。例えば、非特許文献１にあるようなＤＲＰの場合は、例えば８×４のＡＬＵアレイで構成されており、８×４の演算器を縦方向で並列的に、また横方向でパイプライン処理的に用いることで効率良く処理できる。つまり、ループのイタレーション間で並列性があれば、ＡＬＵアレイを縦方向に分割してＡＬＵアレイの１面で複数イタレーション分を一度に処理することができる。また、ループ内の代入文といったステートメントレベルで並列性がある場合には、ステートメント単位で演算器を縦方向に並列的に分割することで、複数ステートメントを一度に処理することができる。また、ステートメント間でデータ依存がある場合には、ＡＬＵアレイの横方向をパイプライン的に活用するよう演算をマッピングすることで、命令とデータを１ないし数個ずつ処理を進めていくＣＰＵに対し、大きな速度向上を得ることができる。このように、ステップ２１０２、２１０３、２１０４では専用プロセッサのアーキテクチャに合わせた最適化が行われる。
【００４１】
なお、入力プログラム２００内にユーザによる指示文が存在する場合はそれも合わせて解析する。指示文としては、ユーザがＨＣＭＰ１上のある特定の専用プロセッサで処理すべきことを示す指示文がある。つまり、もしＡＣＣＰＬ２１０が例えばＤＲＰ用のコード生成コンパイラであり、指示文としてあるプログラム・ブロックがユーザによってＤＲＰ上での処理を指定していたとすると、そのブロックはＤＲＰ処理部として扱う。つまり、指示文で指定された箇所（ループやサブルーチンなどのプログラム構造単位で指定される場合もあれば、当該ＤＲＰ向け処理部のその前後に指示文で指定される場合もある）においては、ＤＲＰにて処理できるものとして扱い、当該部分の処理コストや実行コードを生成することになる。
【００４２】
続いて、当該ＰＵで処理可能と判定されたブロックに対して、当該ＰＵのアーキテクチャに中間コードレベルで最適化された結果より、当該ブロックを当該ＰＵで処理を行った際の処理コストを算出する（２１０５）。なお、この処理コストは対象となるＰＵのアーキテクチャにより導出方法は異なるが、通常のプロセッサタイプではプログラムの命令を実行する際に消費される平均のクロック数を元に算出される。また、ＤＲＰなどの信号処理プロセッサでは、処理対象となるデータ量がわかればデータパス上の演算器に流すデータ供給のサイクル数より、正確なクロック数を算出できる。また、専用プロセッサがベクトル演算器である場合は、非特許文献２で開示されている自動ベクトル化コンパイラによるプログラムのベクトル化技術を用いることができる。ベクトル化技術は、ループ構造のデータ依存解析を行うことでループのベクトル化判定を行い、ベクトル化可能な部位に対してはベクトル演算命令を挿入する。ベクトル化のためのプログラム変換が可能かを決定する方法は、非特許文献３で開示されているようにデータ依存グラフを用いることで可能である。また、処理コストはベクトル命令及び演算対象となるデータ数より、ベクトル演算クロック数として得られる。
【００４３】
なお、専用プロセッサは上述したように、通常複数の演算器群とデータを連続的に供給するパスを持ち、演算器制御やデータ供給制御は別に設けたシーケンサや制御用プロセッサが行うことになる。つまり、当該プロセッサ上のメモリにＣＳＭや他のプロセッサのローカルメモリ等、専用プロセッサ外部のメモリからデータを転送する、専用プロセッサ内のメモリから演算器へのデータの供給、または演算器の機能を決定するプログラム供給、演算器の機能やデータを供給するタイミングを決定する制御を行う時間も必要となり、コード生成コンパイラ２１０は例えばＣＳＭから当該ＰＵ内のローカルメモリに対するデータロード時間、当該ＰＵ上の演算器機能を設定するために必要な制御時間等も含めて、処理コストを決定することになる。算出された処理コストは、入力プログラムに対し指示文として付加する（２１０６）。
【００４４】
なお、以上で算出された処理コストをコンパイル情報２０７として別途出力しても良い。図５ｂのステップ２１１１〜２１１６にコンパイラ情報２０７を生成する処理フローを示す。前記コンパイラ情報２０７は、前述したように再度並列化コンパイラＰＲＬＣＰＬ２１１で処理（２２０）することによりプログラム全体を最適化するために用いられる。
【００４５】
また、コード生成コンパイラ２１１はコスト等の情報を入力プログラム２００に付加する以外にも、当該プロセッサ実行コード及び、データ転送・専用プロセッサ制御コードを生成する。図５ｃのステップ２１２１〜２１２６に実行コード生成する各種プロセッサ向けコード生成コンパイラ処理フローを示す。
【００４６】
＜各種プロセッサ向けコンパイラが出力するプログラム＞
図３に示した、各種プロセッサ向けコード生成コンパイラ２１０に入力し、上述した処理手順にしたがって解析する入力プログラムについてまず説明する。図３の入力プログラム上では一部ユーザによる指示文が存在する。指示文は、「＃ｐｒａｇｍａ  ＨＣＭＰ１」というキーワードで始まる行がそれである。３００の「＃ｐｒａｇｍａ  ＨＣＭＰ１  ａｓｓｉｇｎ  ｄｓｐ」は、当該指示文の直後のサブルーチン「ｆｕｎｃ３（ｄ、ｅ、ｆ）」（３０１）はＤＳＰに処理を割り当てることを指定している。つまり、前記サブルーチンはＤＳＰ上での処理が可能なことを示すとともに、ＤＳＰでの処理をユーザが指定している。なお、本指示があっても並列化コンパイラが、例えばＤＳＰが他のタスクを処理中で通常ＣＰＵで処理したほうが、終了時間が早いと判定される場合は、結果的にＣＰＵで処理されることもあり、必ずしも強制的に当該指示文による指定プロセッサで処理が行われるとは限らない。また、図３の３０２「＃ｐｒａｇｍａ  ＨＣＭＰ１  ａｓｓｉｇｎ  ｄｒｐ  ｐｒｏｃｅｓｓ＿ａ＿０１」及び３０３の「＃ｐｒａｇｍａ  ａｓｓｉｇｎ  ｐｒｏｃｅｓｓ＿ａ＿０１」で囲まれた部分がＤＲＰに処理を割り当てることを指定している。指示文の最後尾はユーザが指定する一意のＩＤとなっており、前例のようにループやサブルーチンに対する構造単位で指定する方式、並びにまた指示文で開始点と終了点を指定する方式がある。
【００４７】
次に前記入力プログラム２００をまずＤＳＰ向けコード生成コンパイラにて処理を行った結果を図６に示す。ＤＳＰ向けコード生成コンパイラでは、プログラム構造によりＤＳＰにて処理可能なブロックを特定すると共に、ＤＳＰで当該ブロックを処理した際のコストを入力プログラムに挿入する。例えば、図６の３１０「＃ｐｒａｇｍａ  ＨＣＭＰ１  ｅｘｅｃ  ｄｓｐ  ｅｘｅｃ＿ｃｙｃ＝７００、０００  ｄａｔａ＝２０、０００」は次行３１１の「＃ｐｒａｇｍａ  ＨＣＭＰ１  ａｓｓｉｇｎ  ｄｓｐ」で指定されたＤＳＰ処理ブロックに対する、ＤＳＰ向けコード生成コンパイラにより算出された処理コストを示す。「ｅｘｅｃ＿ｃｙｃ＝７００、０００」は実行時間が７００Ｋサイクル、また「ｄａｔａ＿ｃｙｃ＝２０、０００」はデータ転送時間が２０Ｋサイクル、かかることを示している。
【００４８】
続いてＤＳＰ向けコード生成コンパイラ２１０による出力プログラムを、ＤＲＰ向けコード生成コンパイラに入力し、処理（２０１）した結果を図７に示す。例えば、図７の３２０「＃ｐｒａｇｍａ  ＨＣＭＰ１  ｅｘｅｃ  ｄｒｐ  ｅｘｅｃ＿ｃｙｃ＝２００、０００  ｄａｔａ＿ｃｙｃ＝１０、０００  ｃｏｎｆｉｇ＿ｃｙｃ＝３、０００」は３２１「＃ｐｒａｇｍａ  ＨＣＭＰ１  ａｓｓｉｇｎ  ｄｒｐ」で指定されたＤＲＰ処理ブロックに対する、ＤＲＰ向けコード生成コンパイラにより算出された処理コストを示す。「ｅｘｅｃ＿ｃｙｃ＝２００、０００」は実行時間が２００Ｋサイクル、「ｄａｔａ＿ｃｙｃ＝１０、０００」はデータ転送時間が１０Ｋサイクル、「ｃｏｎｆｉｇ＿ｃｙｃ＝３、０００」はＤＲＰ用のプログラム情報（コンフィギュレーション）のロードに３Ｋサイクル、かかることを示している。また、あるブロックが複数の専用プロセッサで処理可能と判定された場合には、処理可能なそれぞれの専用プロセッサ向けのコストが複数行で挿入される。例えば、図７の３２２「＃ｐｒａｇｍａ  ＨＣＭＰ１  ｅｘｅｃ  ｄｒｐ」及び３２３「＃ｐｒａｇｍａ  ＨＣＭＰ１  ｅｘｅｃ  ｄｓｐ」が連続して挿入されているが、これは次行のループがＤＲＰ及びＤＳＰ双方で実行可能なことを示している。並列化コンパイラ２１１は双方の実行コスト並びに、スケジューリング時の各ＰＵの状況により、最終的に当該ループを割り当てるＰＵを決定することになる。
【００４９】
また、グローバルコンパイラオプションの指定により、ユーザが「＃ｐｒａｇｍａ  ＨＣＭＰ１  ａｓｓｉｇｎ  ＊＊＊」で明示的に処理プロセッサを指定し、当該処理プロセッサのみコストを求め、指示文を挿入する使い方もできる。本方法により図３の入力プログラムを処理した結果（コスト情報２０９）を図８に示す。
【００５０】
＜並列化コンパイラの処理フロー＞
次にグローバルコンパイラ２における並列化コンパイラ２１１の処理フローを説明する。図９に並列化コンパイラ２１１の処理フローを示す。
【００５１】
＜マクロタスクの生成＞
Ｃ言語やＦｏｒｔｒａｎ等の高級言語で記述された逐次構造の入力プログラム２０１はまず、並列化コンパイラ２１１が当該プログラムの構造を解析することで、繰り返しブロック（ＲＢ：Ｒｅｐｅｔｉｔｉｏｎ  Ｂｌｏｃｋ）、サブルーチン（ＳＢ：Ｓｕｂ  Ｒｏｕｔｉｎｅ）、擬似代入文ブロック（ＢＰＡ：Ｂｌｏｃｋ  ｏｆ  Ｐｓｅｕｄｏ  Ａｓｓｉｇｎｍｅｎｔ  ｓｔａｔｅｍｅｎｔｓ）の３種類の粒度が大きなマクロタスク（ＭＴ）に分割、生成する（４０１）。ＲＢはループブロックで各階層での最も外側のループであり、ＢＰＡはスケジューリングオーバーヘッドあるいは並列性を考慮し、代入文からなる複数の基本ブロックを融合あるいは分割したブロックである。図３の「＃ｐｒａｇｍａ  ＨＣＭＰ１  ａｓｓｉｇｎ  ＊＊＊」のように、専用プロセッサでの処理を指定されたブロックは、一つのマクロタスクとして扱うことになる。
【００５２】
＜データ依存・制御フロー解析＞
続いて、並列化コンパイラ２１１は、分割生成された当該マクロタスク間の制御フロー及びデータ依存性を解析し、ＭＴの実行順序関係を抽出する（４０２）。入力プログラムは逐次的に記述されているため、通常のコンパイラによる実行コードは、当該プログラムの構造と同様に逐次的な順序で実行されるが、ＭＴ間で見ると必ずしも記述された順序で実行する必要がないことが多い。つまり、ＭＴ間において制御またはデータ参照の依存性がない場合、特にマルチプロセッサシステムにおいては、複数のＰＵに複数のＭＴを配置して同時にまたは順序を変更して、全体の実行時間が短くなるようスケジューリングすることが重要となる。このようなスケジューリングを行うためには、ＭＴ間の並列性を解析する必要がある。そこでこれに向けた準備として、データ依存・制御フロー解析処理４０２により、ＭＴ間の実行順序関係を抽出する。
【００５３】
＜ループレベル並列性解析＞
続いて並列化コンパイラ２１１は、マクロタスク内の中粒度レベルの並列性解析として、ループレベル並列化を行う（４０３）。ループレベル並列化４０３では、ループの繰り返し（イタレーション）単位間のデータ依存性を解析して、各イタレーションが独立に処理できるかを判断し、可能な場合は各イタレーションを複数のＰＵに割り当てて並列処理を行う。また、単一のループを複数のループに分割し並列性を高めたり、データのコピーや配列変数の拡張によりループ間のデータ依存性を削除することで並列したり、また複数のループを単一のループに融合することでループ制御に必要なオーバーヘッドを軽減したり、といった様々な手法によりループの並列化を実現する。
【００５４】
＜処理コスト解析＞
次に並列化コンパイラ２１１は、生成されたマクロタスクＭＴを各ＰＵで実行した際に必要となる処理サイクルを、予め付加されたディレクティブ情報より求める。なお、ＣＰＵの処理サイクルに関しては、通常並列化コンパイラ内のＣＰＵ命令コストテーブルを参照することによってもとめる（４０４）。ＣＰＵ処理コストの見積もり方法としては、例えばＣＰＵなどに関しては乗算や加算など命令レベルで必要とするサイクル数をテーブル４２０に保持しておき、当該テーブル４２０を参照することでＭＴを当該ＰＵで実行する際の逐次処理サイクル数を見積もることができる。
【００５５】
なお、コンパイル時にコストを決定できない要素が存在する場合、例えばＭＴが分岐を含む場合は、分岐確率を５０％としてコスト算出を行う。また例えばループや配列のサイズが定まらない場合は、ループを固定回数とする、配列宣言時の最大サイズとする、等の方法を適用する。
【００５６】
＜マクロタスク間並列性解析＝最早実行条件解析＞
コンパイラ２１１はマクロタスクＭＴの処理コストが決定した後、データ依存・制御フロー解析処理４０２で抽出したＭＴ間の制御フローとデータ依存性を同時に解析結果から、ＭＴ間の並列性、つまり各ＭＴの実行を最も早く実行してよい条件（最早実行条件）を決定する（４０５）。この最早実行条件をグラフで可視的に示したものがマクロタスクグラフ（ＭＴＧ）である。図３の入力プログラム２００を解析して生成されたＭＴＧを、図１０に示す。なお、マクロタスク間並列性解析結果は、マクロタスクグラフテーブル４２１として外部記憶装置に保持され、後段のコンパイル処理で使用される。
【００５７】
＜マクロタスクグラフの説明＞
以下、マクロタスクグラフＭＴＧについて説明する。本グラフ中の各ノードはマクロタスクＭＴを示し、ノード間の実線はマクロタスク間のデータ依存関係を、ノード間の破線はマクロタスク間の制御依存関係を、ノード内の小円が条件分岐を表している。
例えば、ＭＴ１＿１（５０１）からＭＴ１＿２（５０２）及びＭＴ１＿３（５０３）に対して実線が伸びているが、これはＭＴ１＿２及びＭＴ１＿３がＭＴ１＿１を実行した結果生じたデータを入力データとして用い処理を実行しているという依存関係があることを示している。そのため、実行順序として、ＭＴ１＿２及びＭＴ１＿３はＭＴ１＿１タスク終了後、実行できることを示す。
【００５８】
また、入力プログラム２００よりＭＴ１＿２（５０２）は複数のループやサブルーチンで構成されたブロックなので、コンパイラは当該ＭＴをさらに複数のＭＴに階層的に分割する。よって、当該ＭＴＧではＭＴ１＿２中に、別階層でＭＴＧを構成する。ＭＴＧ１＿３（５０３）も同様である。
【００５９】
ＭＴ１＿２（５０２）内のＭＴＧ（５１０）を見ると、ＭＴ１＿２＿１（５１１）からはＭＴ１＿２＿２（５１２）、ＭＴ１＿２＿３（５１３）、ＭＴ１＿２＿４（５１４）に実線が延びているため、ＭＴ１＿２＿１（５１１）終了後同時にこれら３つのタスク５１２、５１４、５１５を並行して実行することが可能である。また、ＭＴ１＿２＿３（５１３）及びＭＴ１＿２＿４（５１４）からＭＴ１＿２＿５（５１５）に対して実線が延びているため、ＭＴ１＿２＿３（５１３）及びＭＴ１＿２＿４（５１４）双方の実行が終了した時点でＭＴ１＿２＿５（５１５）が実行できる。以上のように、ＭＴ１＿２は実行前に並列順序関係は確定されており、コンパイル時にスタティックにスケジューリング可能である。つまり、タスクのＰＵ上での実行順序はコンパイル時に決定される。
【００６０】
続いて、ＭＴ１＿３（５０３）内のＭＴＧ（５２０）を見ると、ＭＴ１＿３＿１（５２１）には小円が存在するが、これはタスクＭＴ１＿３＿１（５２１）が分岐条件を含むことを示している。小円からＭＴ１＿３＿２（５２３）、ＭＴ１＿３＿３（５２４）へは矢印のある破線が伸びており、また制御依存のＯＲ条件を表す点線のアーク５２２が重なっているため、当該条件がＭＴ１＿３＿２またはＭＴ＿１＿３＿３の何れかに分岐することを示している。なお、破線はタスクの実行が確定される制御依存関係と、データ依存しているタスクが実行されない場合の条件を表している。また、矢印がついた破線は、データ依存・制御フロー解析（４０２）で求めた制御手順と同一（つまり、オリジナル）であることを表す。なお、ＭＴ１＿３＿１（５２１）の分岐条件は、当該タスクＭＴ１＿３＿１を実行しないと分岐方向が確定しないため、実行時の状況に応じたスケジューリングを行う必要がある。
【００６１】
＜プロセッサグルーピング＞
次にコンパイラは、生成されたＭＴＧテーブル４２１を参照し、ＨＣＭＰ１のＰＵ資源を勘案した上で、マクロタスクグラフの形状や並列性に応じた、またはユーザからの指定に応じたプロセッサのグループ化を、汎用プロセッサＣＰＵを対象に行う（４０６）。ＤＳＰ、ＤＲＰ等の専用プロセッサ群はグループには含めずに、各グループでの処理で必要なときに随時タスクが専用プロセッサ群に割り当てられる。
【００６２】
つまり、ＭＴＧで表現された上位階層のＭＴ、例えばＭＴ１＿２（５０２）、ＭＴ１＿３（５０３）の形状、並列性を解析し、当該ＭＴの処理に必要となるＰＵをグループ化し、当該グループにＭＴを割り当てる。なお、１つのグループは、当該グループ内の特定用途プロセッサ（ＤＳＰ、ＤＲＰ、ＢＭＰ）を制御するための汎用プロセッサ（ＣＰＵ）を含む集合となる。例えば図１に示したＨＣＭＰ１構成上でスケジュールする場合、ＣＰＵは２個であるので、ＭＴ１＿２とＭＴ１＿３をそれぞれ各ＣＰＵ１個にグルーピングする。前記ＭＴ１＿２及びＭＴ１＿３内の階層のタスク群は基本的にグルーピングされたＣＰＵに対してタスクの割り当てが行われる。そのとき、専用プロセッサ指定がある場合で、専用プロセッサでタスクを処理したときに当該タスクの終了時間がＣＰＵで行うよりも早いと判定され、なおかつ当該グループ内タスク全体の処理時間が最短となると判定できる場合には、指定された専用プロセッサに処理を割り当てる。
【００６３】
＜スタティックスケジュールとダイナミックスケジュール＞
コンパイラ２１１は次にスケジューリング方法として、スタティックスケジュールかダイナミックスケジュールかを判断する（４０７）。夫々のスケジューリング方法の詳細は後述するが、以下簡単に説明する。まずもし、ＭＴに条件分岐がなく最早実行条件が予め決定できるＭＴフローであれば、前者のスタティックスケジュールを適用し、コンパイラが予めＭＴのスケジューリングを行い、コンパイル時に同期コードをタスク間に挿入する。またもし、ＭＴに条件分岐がある、またＭＴの処理時間が実行時に変動するなど、コンパイラ時に予測できないＭＴフローであれば、後者のダイナミックスケジュールを適用し、コンパイラは、分岐などの状況に応じた制御を実行時に行うスケジューリングプログラムを生成しＣＰＵにて実行することで、実行時にタスクの割り当てを行う。
【００６４】
＜スタティックスケジューリング＞
まず、スタティックスケジューリングの処理フローについて説明する。スタティックスケジューリングでは、コンパイル時にＭＴの割り当てと実行順序がすでに決定しているため、まずマクロタスクスケジューリング処理４０８により、マクロタスクテーブル４２１及びプロセッサグルーピングテーブル４２２情報を参照し、ＰＵ間における実行タスク間の同期や他タスクの起動等を行う制御情報を生成し、当該情報の挿入箇所を決定する。またさらに、タスクプログラムまたはタスクが必要とするデータを、他ＰＵのＬＭや共有メモリＳＭより当該ＰＵのローカルメモリＬＭにロードするといったデータ転送情報も併せて生成する。このような、データローカライゼーション手法により、ローカルメモリＬＭを有効に活用し、データの転送量を最小化する。以上の処理により生成されたスケジュール情報は、マクロタスクスケジュールテーブル４２３として、外部記憶装置に保持される。
【００６５】
続いて、コンパイラはスタティックＦＶスケジューリング処理４０９を行う。本処理では、タスクの並列スケジューリングの結果、ＰＵがアイドル状態となる部分に対して、電源を遮断する、クロックを停止する、またはクロックを低減し電源電圧を降下させる、等の電源制御コードを生成する。
【００６６】
＜ダイナミックスケジューリング＞
次に、ダイナミックスケジューリングの処理フローについて説明する。ダイナミックスケジューリング時は、ＭＴ内の分岐条件等の不確定要素によりコンパイル時にスケジューリング内容を決定することができない。このためコンパイラは、ＭＴの処理結果に基づきプログラム実行時に動的にスケジューリングを行うスケジューリングプログラムを生成する（４１０）。本プログラムは、処理結果に基づきＭＴの起動や同期、及び当該ＭＴが必要とするデータのロードを行う。また、さらに図１８で説明したタスク並列処理実行時のＦＶ制御概念に基づき、ＰＵの動作周波数・供給電圧を決定する動作モードを設定する。生成したスケジューリングプログラムは、電源・ＦＶ制御スケジュールテーブル４２４として、外部記憶装置に保持される。
【００６７】
＜スケジューリングコードの生成＞
コンパイラは以上の処理により、入力プログラムのＰＵへのスケジューリングを完了する。これまでの処理で生成したスケジューリング情報は外部記憶装置にテーブル（４２１〜４２４）として保持されている。コンパイラは、当該テーブル（４２１〜４２４）にアクセスし、タスクの実行順序やデータ転送情報、及びＦＶ制御情報を読み込み、入力プログラムに対してスタティックスケジュール部には制御コード（スケジューリングコード）を、またダイナミックスケジュール部にはスケジューリングプログラムを付加する（４１１）。
【００６８】
＜スケジューリングの結果＞
本スケジューリング結果の例を図１１に示す。図１１は、ＭＴのスケジューリング結果をＰＵ毎に時間軸で示している。図中斜線のハッチングは、スタティックスケジューリングで埋め込まれた同期コードを示し、図中縦線のハッチングは、タスク割り当てようダイナミックスケジューラで生成されたスケジューリングコードを示す。本例ではＣＰＵ０がタスクの起動や同期、ＦＶ電力制御などの管理を行うため、最初にＣＰＵ０上にコンパイラが生成した制御コード５５０がロードされる。制御コードは初めにＭＴ１＿１をＣＰＵ０上で起動する。ＭＴ１＿１処理終了後、コンパイラが生成した制御コード５５１を実行し、次に処理すべきタスクは、ＭＴ１＿２及びＭＴ１＿３の下位層のＭＴＧで指定されたＭＴ１＿２＿１及びＭＴ１＿３＿１であり、前者はＣＰＵ０にて、後者はＤＲＰ０にて実行される。
【００６９】
なお、前述した通り、ＭＴＧ１＿２は分岐条件を含まないためコンパイル時のすでにスケジューリングが行われており（スタティックスケジューリング）、コンパイル時にすでにＣＰＵ０、ＤＲＰ０、ＤＲＰ１、ＤＳＰ０へＭＴがスケジュールされている。またＭＴＧ１＿３は分岐条件を含むため、実行時にスケジューリングを行うプログラムを付加し、実行結果によってＣＰＵ１、及び必要であればＤＲＰ、ＤＳＰの専用プロセッサ群へＭＴを割り振る。
【００７０】
続いてＭＴＧ１＿２のＭＴグループのスケジューリングについて説明する。ＭＴ１＿２＿１の実行がＤＲＰ０において終了すると同時にＣＰＵ０にＭＴ１＿２＿１の処理終了を通知する。ＣＰＵ０の制御コードは、ＤＲＰ０上でＭＴ１＿２＿２、ＤＲＰ１上でＭＴ１＿２＿３、ＤＳＰ上で１＿２＿４を起動する。各ＰＵ上のタスクは処理終了と同時に、ＣＰＵ０にその終了を通知する。この時点で未処理のタスクはＭＴ１＿２＿５であるが、ＭＴ１＿２＿５はＤＳＰ処理タスクであり、ＭＴ１＿２＿４終了後ＣＰＵ０にてＭＴ１＿２＿２は起動される。
【００７１】
続いてＭＴＧ１＿３のＭＴグループについて説明する。ＭＴ１＿３は内部に分岐を持つため、タスクを実行しないと分岐方向がわからない。従って、実行時の状況によりタスク、データのロード、タスクの起動、同期及び電力制御コードの管理を行うダイナミックスケジューラ５５２を、ＣＰＵ１において実行する。当該スケジューラ５５２は、まずＣＰＵ１上でＭＴ１＿３＿１を起動し実行する。本例では、ＭＴ１＿３＿１の実行結果よりＭＴ１＿３＿２に分岐したとすると、ＭＴ１＿３＿２はＤＲＰ実行タスクのため本来はＤＲＰで実行したほうが効率良く処理できるが、ＭＴ１＿３＿１の割り当て時、ＤＲＰ０、ＤＲＰ１はＭＴ１＿３のタスクを実行しているため、当該タスク終了後にＤＲＰ０またはＤＲＰ１上で実行するか、それとも効率は下がるがＣＰＵ１上で実行するかを、予想終了時間を求めることで決定する。本例では、ＤＲＰがタスク実行中のためにＣＰＵ１で実行したほうが終了時刻が早いと判定され、ＣＰＵ１にタスクが割り当てられる。
【産業上の利用可能性】
【００７２】
本発明により、多様なＰＵを集積するマルチプロセッサシステムにおいて、当該ＰＵを効率よく動作させるプログラムの分割配置および制御コードを生成するコンパイラにより、当該プロセッサシステムの性能を最大限活用しつつ、低電力にて効率よく処理することが可能となる。また、さらにはソフトウェア開発者がプロセッサの構成を意識することなく、短時間で効率良いプログラム作成が可能となる。その結果、高い演算性能を持ちかつ低電力に処理することが強く望まれる、カーナビや形態電話、情報家電向けのＬＳＩに本発明を適用することができ、高品質の動画像や音声処理、また画像認識や音声認識といった機能を実現することが可能となる。また、自動車における情報系、制御系システム向けＬＳＩに対しても適用することができ、自動運転や安全運転システム等を実現することが可能となる。またさらには、将来非常に高い演算性能を有しつつ低電力化が必須となる、スーパーコンピュータへの応用も可能である。
【図面の簡単な説明】
【００７３】
【図１】実行コードの生成対象となるヘテロジニアスマルチプロセッサ（ＨＣＭＰ１）のアーキテクチャを説明するブロック図である。
【図２ａ】ＨＣＭＰ１グローバルコンパイラの処理手順の一例を示すフローチャートである。
【図２ｂ】ＨＣＭＰ１グローバルコンパイラの処理手順の他の一例を示すフローチャートである。
【図２ｃ】ＨＣＭＰ１グローバルコンパイラの処理手順の他の一例を示すフローチャート図である。
【図３】入力プログラム例を示した図である。
【図４】ＨＣＭＰ１ハードウェア構成情報を説明するブロック図である。
【図５ａ】各種プロセッサ向けコード生成コンパイラを説明する図である。
【図５ｂ】各種プロセッサ向けコード生成コンパイラを説明する図である。
【図５ｃ】各種プロセッサ向けコード生成コンパイラを説明する図である。
【図６】ＤＳＰ向けコード生成コンパイラ出力結果を示した図である。
【図７】ＤＲＰ向けコード生成コンパイラ出力結果を示した図である。
【図８】ユーザ指定ブロックに対するコスト情報の指定結果を示した図である。
【図９】並列化コンパイラの処理手順の一例を示すフローチャートである。
【図１０】コンパイラが生成したタスク間依存関係図を示したマクロタスクグラフである。
【図１１】ＨＣＭＰタスクスケジューリングの結果を示したタイムチャートである。
【符号の説明】
【００７４】
２００〜２０２  プログラム
２０３、２０５、２０６  実行コード
２０４  アーキテクチャ構成情報
２０７、２０８コンパイル情報
２３１  実行プロファイル情報
２１０〜２１２、２２０  処理
２３０  各種プロセッサ向けライブラリ
２３１コスト情報
３００〜３０３、３１０、３１１、３２０〜３２３  指示文
４００  入力プログラム
４０１〜４１１  処理
４１２  出力コード
４１３  処理
４２０〜４２４  テーブル
５００、５１０、５２０  マクロタスクグラフ
５０１〜５０３、５１１〜５１５、５２１〜５２５、５５１  マクロタスク
５２２  ＯＲ条件
５５０  タスク間同期制御コード
５５２  タスク同期制御用ダイナミックスケジューラコード
【図１】
0004784827.tif 000002
【図２ａ】
0004784827.tif 000003
【図２ｂ】
0004784827.tif 000004
【図２ｃ】
0004784827.tif 000005
【図３】
0004784827.tif 000006
【図４】
0004784827.tif 000007
【図５ａ】
0004784827.tif 000008
【図５ｂ】
0004784827.tif 000009
【図５ｃ】
0004784827.tif 000010
【図６】
0004784827.tif 000011
【図７】
0004784827.tif 000012
【図８】
0004784827.tif 000013
【図９】
0004784827.tif 000014
【図１０】
0004784827.tif 000015
【図１１】
0004784827.tif 000016