(57)【要約】  コンピュータにより、予め決められたタイミングで途中結果を出力すると共に時系列的に処理されるソフトウェアのコンパイルを行うコンパイル方法は、ソフトウェアのソースコードに含まれる処理シーケンスから並列性及び条件分岐に関する処理ブロックを抽出する抽出ステップと、抽出された処理ブロックのリストラクチャリングを行い実行コードを自動的に生成する生成ステップとを含む。
2008072334.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータにより、予め決められたタイミングで途中結果を出力すると共に時系列的に処理されるソフトウェアのコンパイルを行うコンパイル方法であって、
該コンピュータにより、該ソフトウェアのソースコードに含まれる処理シーケンスから並列性及び条件分岐に関する処理ブロックを抽出する抽出ステップと、
該コンピュータにより、抽出された処理ブロックのリストラクチャリングを行い実行コードを自動的に生成する生成ステップとを含むことを特徴とする、コンパイル方法。
【請求項２】
該抽出ステップは、演算及び該コンピュータのメモリ及びレジスタに演算結果の代入を行う演算代入処理の処理ブロックに対して、ステートメント間の依存方程式に基づく並べ替えを行い中間言語レベルで整理されたステートメント列を求める第一段階と、該整理されたステートメント列に対してステートメントのグループの結合及び再定義を行う第二段階を有することを特徴とする、請求項１記載のコンパイル方法。
【請求項３】
該生成ステップは、該第二段階でグループ化を行ったスケジューラ化処理ブロック及びスレッド化処理ブロックに制御ステートメントを付加し、スレッドとスケジューラとして最終的な中間言語を生成する第三段階を有し、
該スケジューラ化処理ブロックは、後続の処理ブロックが条件分岐処理であると処理ブロックと結合されて再定義されたものであり、
該スレッド化処理ブロックは、呼び出し元の処理ブロックが条件分岐処理であると条件分岐の従属節が再定義されたものであることを特徴とする、請求項２記載のコンパイル方法。
【請求項４】
該第一段階は、全ての制御ステートメントで区切られた演算代入ステートメントのグループに対して行われ、定義及び参照される変数の抽出、各ステートメントの依存関係を表現した依存グラフの定義、不要なステートメントの削除、及び該依存グラフに基づくステートメントのソートからなることを特徴とする、請求項２又は３記載のコンパイル方法。
【請求項５】
該第二段階は、ネスト又は入れ子構造にある最も内側の階層の処理ブロックから順に該ステートメントのグループの結合及び再定義を行うことを特徴とする、請求項２〜４のいずれか1項記載のコンパイル方法。
【請求項６】
該第二段階は、該第一段階のソートの結果に対して行われ、処理ブロック化を対象とするプログラムのコードに対して、呼び出し元の処理ブロックが条件分岐処理であると条件分岐の従属節をスレッド化処理ブロックとして再定義し、該条件分岐処理ではなく、且つ、後続の処理ブロックが条件分岐処理に続くものであるとこれらの処理ブロックを結合してスケジューラ化処理ブロックとして再定義することを特徴とする、請求項５記載のコンパイル方法。
【請求項７】
該第三段階は、該第二段階でグループ化を行ったスケジューラ化処理ブロック及びスレッド化処理ブロックに対して行われ、
処理の対象となる処理ブロックがスレッド化処理ブロックの場合はスレッド化処理ブロックへステートメントを追加する処理を行い、
処理対象となる処理ブロックがスケジュール化処理ブロックの場合はスケジューラ化処理ブロックへステートメントを追加する処理を行うことを特徴とする、請求項３〜６のいずれか1項記載のコンパイル方法。
【請求項８】
該スケジューラ化処理ブロックはスレッドのコンテキストスイッチ機能を有し、該スレッド化処理ブロックはスケジューラの要求時にのみ動作する仕組みを有することを特徴とする、請求項３記載のコンパイル方法。
【請求項９】
該第三段階は、最外郭ループに囲まれたスケジューラ化処理ブロックについては、該コンピュータのＯＳのタイマ機能を用いて周期的にシグナルを送信して自動起動させるタイマハンドラの仕組みを組み込むことを特徴とする、請求項３記載のコンパイル方法。
【請求項１０】
該第三段階は、演算処理が不要な期間において該コンピュータを解放する機構を有する制御ステートメントを付加することを特徴とする、請求項３記載のコンパイル方法。
【請求項１１】
コンピュータにより、予め決められたタイミングで途中結果を出力すると共に時系列的に処理されるソフトウェアのコンパイルを行うコンパイラであって、
該コンピュータにより、該ソフトウェアのソースコードを第１の中間言語に翻訳して記憶部に保存するフロントエンドと、
該コンピュータにより、該記憶部に保存された該第１の中間言語に基づいて該ソースコードに含まれる処理シーケンスから並列性及び条件分岐に関する処理ブロックを抽出し、抽出された処理ブロックのリストラクチャリングを行い第２の中間言語を生成して記憶部に保存するミドルパスと、
該コンピュータにより、該記憶部に保存された該第２の中間言語に基づいて実行コードを自動的に生成するバックエンドとを備えたことを特徴とする、コンパイラ。
【請求項１２】
該ミドルパスは、演算及び該記憶部に演算結果の代入を行う演算代入処理の処理ブロックに対して、ステートメント間の依存方程式に基づく並べ替えを行い該第１の中間言語レベルで整理されたステートメント列を求める第一段階と、該整理されたステートメント列に対してステートメントのグループの結合及び再定義を行う第二段階を有することを特徴とする、請求項１１記載のコンパイラ。
【請求項１３】
該ミドルパスは、該第二段階でグループ化を行ったスケジューラ化処理ブロック及びスレッド化処理ブロックに制御ステートメントを付加し、スレッドとスケジューラとして該第２の中間言語を生成する第三段階を有し、
該スケジューラ化処理ブロックは、後続の処理ブロックが条件分岐処理であると処理ブロックと結合されて再定義されたものであり、
該スレッド化処理ブロックは、呼び出し元の処理ブロックが条件分岐処理であると条件分岐の従属節が再定義されたものであることを特徴とする、請求項１２記載のコンパイラ。
【請求項１４】
該第一段階は、全ての制御ステートメントで区切られた演算代入ステートメントのグループに対して行われ、定義及び参照される変数の抽出、各ステートメントの依存関係を表現した依存グラフの定義、不要なステートメントの削除、及び該依存グラフに基づくステートメントのソートからなることを特徴とする、請求項１２又は１３記載のコンパイラ。
【請求項１５】
該第二段階は、ネスト又は入れ子構造にある最も内側の階層の処理ブロックから順に該ステートメントのグループの結合及び再定義を行うことを特徴とする、請求項１２〜１４のいずれか1項記載のコンパイラ。
【請求項１６】
該第二段階は、該第一段階のソートの結果に対して行われ、処理ブロック化を対象とするプログラムのコードに対して、呼び出し元の処理ブロックが条件分岐処理であると条件分岐の従属節をスレッド化処理ブロックとして再定義し、該条件分岐処理ではなく、且つ、後続の処理ブロックが条件分岐処理に続くものであるとこれらの処理ブロックを結合してスケジューラ化処理ブロックとして再定義することを特徴とする、請求項１５記載のコンパイラ。
【請求項１７】
該第三段階は、該第二段階でグループ化を行ったスケジューラ化処理ブロック及びスレッド化処理ブロックに対して行われ、
処理の対象となる処理ブロックがスレッド化処理ブロックの場合はスレッド化処理ブロックへステートメントを追加する処理を行い、
処理対象となる処理ブロックがスケジュール化処理ブロックの場合はスケジューラ化処理ブロックへステートメントを追加する処理を行うことを特徴とする、請求項１３〜１６のいずれか1項記載のコンパイラ。
【請求項１８】
該スケジューラ化処理ブロックはスレッドのコンテキストスイッチ機能を有し、該スレッド化処理ブロックはスケジューラの要求時にのみ動作する仕組みを有することを特徴とする、請求項１３記載のコンパイラ。
【請求項１９】
該第三段階は、最外郭ループに囲まれたスケジューラ化処理ブロックについては、該コンピュータのＯＳのタイマ機能を用いて周期的にシグナルを送信して自動起動させるタイマハンドラの仕組みを組み込むことを特徴とする、請求項１３記載のコンパイラ。
【請求項２０】
該第三段階は、演算処理が不要な期間において該コンピュータを解放する機構を有する制御ステートメントを付加することを特徴とする、請求項１３記載のコンパイラ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンパイル方法及びコンパイラに係り、特に組み込み機器上におけるソフトウェアの実行コードを自動的に生成するコンパイル方法及びコンパイラに関する。
【背景技術】
【０００２】
図１は、組み込み機器上におけるソフトウェアの実行コードを生成する従来のコンパイラの構成を示す図である。図１に示すコンパイラは、組み込み機器のソフトウェアを単一のアプリケーションとして効率的に実行するために、実行コードの最適化を行う。図１に示すコンパイラは、翻訳装置（フロントエンド）２、最適化装置（ミドルパス）４及びコード生成装置（バックエンド）５を有する。フロントエンド２はソースコード１から中間言語３−１を生成し、ミドルパス４は中間言語３−１から中間言語３−２を生成する。バックエンド５は、中間言語３−２から最適化された実行コード６を生成する。コンパイルによる翻訳作業の過程で、ミドルパス４において不要な変数の削除や命令のパッキング、呼び出し関数のインライン展開等の単純な再構築（リストラクチャリング）を行う。【０００３】
このような実行コードの最適化のためのリストラクチャリングでは、命令コードの削除や単純置換を行い、ソースコード１に記述された処理シーケンスの構造そのものを変更するようなリストラクチャリングは行わない。【０００４】
動画処理や通信処理等の処理の実行を開始した後は、CPUの処理能力に関係なく予め決められた時刻において周期的に途中の演算結果を出力するような時系列処理のソフトウェアがある。このような時系列的（シーケンシャル）に記述されたソフトウェアを図１に示すコンパイラでコンパイルして実行コードを生成した場合、処理の開始から終了までのトータルの演算量がCPUの処理能力に見合ってる場合においても、図２に示す例のように処理P3,P4が開始される順番によっては、処理が間に合わず遅延を生じることがある。図２は、時系列処理（シーケンシャル処理）の遅延を説明する図である。図２において、P1〜P4は処理を示し、t1は開始条件判断時刻、t2は処理P3の実際の終了時刻、t3は処理P4の期待終了時刻、t4は処理P4の実際の終了時刻、t5は処理P3の期待終了時刻を示す。この場合、処理P4の実際の終了時刻t4は、処理P4の期待終了時刻t3より遅く、遅延D1が生じている。【０００５】
一般的には、上記のように平均的なCPUの処理能力が十分であっても、局所的な処理の観点ではCPUの処理能力が不十分な状態が起こり得ると想定される場合、ソフトウェアは図３で示すように設計段階でバッファ８を定義することにより処理遅延の問題を回避する。図３は、時系列処理の遅延の回避を説明する図である。図３中、図２と同一部分には同一符号を付し、その説明は省略する。図３において、P3ｙ,P4ｙは夫々ｙ番目に実行される処理P3,P4、P4ｚはｚ番目に実行される処理P4、t2yは処理P3ｙの実際の終了時刻、t3yは処理P4ｙの期待終了時刻、t5yは処理P3ｙの期待終了時刻である。【０００６】
図４は、従来の動的スケジューラのイメージを示す図である。同図中、１１はタスク又はスレッド、１２はタスク又はスレッド１１から報告される実行情報テーブル、１３は情報テーブルに基づいてスケジューリングを行う動的スケジューラ、１４はオペレーティングシステム（ＯＳ）１６内のコンテキストスイッチ・プロセス管理機能、１５は動的スケジューラ１３の指示によるスイッチを示す。従来の組み込み機器で効率的に複数のタスク又はスレッド１１を並列（同時）に実行する場合、図４に示す動的スケジューラ１３では、アプリケーションに動的なプロファイリング機能を持たせ、メモリやCPU使用量を随時ＯＳ１６に報告する。動的スケジューラ１３は、常時収集された情報の情報テーブル１２を参照して動的にタスク又はスレッド１１の優先度を定義し、ＯＳ１６のコンテキストスイッチ・プロセス管理機能１４によりタスク又はスレッド１１のスイッチ１５を行う。【０００７】
このように複数のタスク又はスレッド１１を効率的に実行するための動的スケジューラ１３は、ＯＳ１６と連動したアプリケーションとは別動作をするソフトウェア、即ち、外部（又は、外付けの）スケジューラである。このため、対象とするソフトウェアが必要とするCPUの演算量の観点からは、このような動的スケジューラ１３は純粋なオーバーヘッドとみなされる。【０００８】
そこで、情報テーブル１２を参照して優先度を定義する動的スケジューラ１３によるオーバーヘッドを発生させないために、一般的にはラウンドロビン、或いは、予め固定的に設定された優先度に従って能動的に動作しないオーバーヘッドの小さいスケジューラを用いる手法があるが、全てのソフトウェアを効率的に実行することはできない。【０００９】
処理時間を最短にする実行コードを生成し、且つ、動的スケジューラ１３によるオーバーヘッドを回避するためには、実行コード中に実行開始を定義する静的スケジューラ機構を埋め込む手法が用いられることがある。【００１０】
静的スケジューラは、メモリやCPUの使用量を動的に報告しない代替手段として、コンパイル時に分岐命令に着目し、分岐命令からジャンプする従属処理のメモリやCPUの使用量に対して、分岐予測の係数を乗じた見込みの情報テーブルに基づいてコンパイル時にスケジューリングを決定する。【００１１】
静的スケジューラは、動的に最適な処理を行う動的スケジューラに対して、実行時のスケジューリングに対するオーバーヘッドは小さいが、特に実行毎に演算量や取り扱うデータ量が変化するような構造のソフトウェアでは、スケジューリング精度が落ち、処理時間を最短に行えるとは限らない。このため、静的スケジューラは、一般的にはCPU上で処理を行いたい演算量が予めわかっているソフトウェアに用いられる。【００１２】
従来のコンパイラは、コードレベルの最適化や時系列的に記述されたソースコードのコンパイル時にデータ依存や制御依存の解析を行い、並列実行可能な処理を分割し、並列に配置されたCPUに対する実行コードを生成する。このようにして、時系列的に記述されたソースコードからより多くの並列性を抽出し、実行開始から終了までの処理時間を最短に行える実行コードを生成する。【００１３】
動的スケジューラは、例えば特許文献１や特許文献２にて提案されている。又、多重レベルスケジューラは、例えば特許文献２にて提案されている。
【特許文献１】特開平６−１１０６８８号公報
【特許文献２】特開２００３−８４９８９号公報
【特許文献３】特開平８−２１２０７０号公報
【発明の開示】
【発明が解決しようとする課題】
【００１４】
組み込み機器のソフトウェア実行環境は、高度化するＯＳやコンパイル環境により変化しており、パーソナルコンピュータ（ＰＣ）やワークステーション等で動作していた汎用のソフトウェアが組み込み機器で動作するようになってきている。一方、組み込み機器では、CPUやメモリ等の限られたリソースを用いて、対象とするソフトウェアを効率的に実行することが望まれている。【００１５】
従来の組み込み機器では、リストラクチャリングを伴わないコード最適化レベルのコンパイラが起動されるか、或いは、複数のタスク又はスレッドが起動するようなソフトウェア構成の場合にはスケジューラが起動される。【００１６】
一方で、ソフトウェアをより効率的に動作させためには、ソフトウェアの実装者により対象となる組み込み機器に適した移植作業を手動で行う必要があった。【００１７】
このように、組み込み機器の限られたソフトウェア実行環境では、ソフトウェア、特に時系列的に記述されたソースコードで、且つ、予め決められた時刻に周期的に途中の演算結果を出力するような時系列処理を行うアプリケーションを実行する際に、低いオーバーヘッド、高いスケジューリング精度、CPUやメモリ等のリソースの効率的な利用を可能とする実行コードをコンパイラにより自動的に生成することが求められている。【００１８】
そこで、本発明は、限られたソフトウェア実行環境でもソフトウェアの実行コードを効率的に生成することが可能なコンパイル方法及びコンパイラを実現することを目的とする。
【課題を解決するための手段】
【００１９】
上記の課題は、コンピュータにより、予め決められたタイミングで途中結果を出力すると共に時系列的に処理されるソフトウェアのコンパイルを行うコンパイル方法であって、該コンピュータにより、該ソフトウェアのソースコードに含まれる処理シーケンスから並列性及び条件分岐に関する処理ブロックを抽出する抽出ステップと、該コンピュータにより、抽出された処理ブロックのリストラクチャリングを行い実行コードを自動的に生成する生成ステップとを含むことを特徴とするコンパイル方法によって達成できる。【００２０】
上記の課題は、コンピュータにより、予め決められたタイミングで途中結果を出力すると共に時系列的に処理されるソフトウェアのコンパイルを行うコンパイラであって、該コンピュータにより、該ソフトウェアのソースコードを第１の中間言語に翻訳して記憶部に保存するフロントエンドと、該コンピュータにより、該記憶部に保存された該第１の中間言語に基づいて該ソースコードに含まれる処理シーケンスから並列性及び条件分岐に関する処理ブロックを抽出し、抽出された処理ブロックのリストラクチャリングを行い第２の中間言語を生成して記憶部に保存するミドルパスと、該コンピュータにより、該記憶部に保存された該第２の中間言語に基づいて実行コードを自動的に生成するバックエンドとを備えたことを特徴とするコンパイラによって達成できる。
【発明の効果】
【００２１】
本発明によれば、限られたソフトウェア実行環境でもソフトウェアの実行コードを効率的に生成することが可能なコンパイル方法及びコンパイラを実現することができる。
【図面の簡単な説明】
【００２２】
【図１】従来のコンパイラの構成を示す図である。
【図２】時系列処理の遅延を説明する図である。
【図３】時系列処理の遅延の回避を説明する図である。
【図４】従来の動的スケジューラのイメージを示す図である。
【図５】本発明のコンパイラの一実施例の構成を示す図である。
【図６】ソフトウェアを構成するソースコードの分類を説明する図である。
【図７】ステートメントの依存関係を表現した依存グラフの一例を示す図である。
【図８】図７の依存グラフを元に処理順序を入れ替えた例を示す図である。
【図９】ソフトウェアのフロー構成例を示す図である。
【図１０】実施例の第一段階の処理を示すフローチャートである。
【図１１】無条件ジャンプ及びループ処理のブロックの演算代入処理ブロックとしての再定義を説明する図である。
【図１２】演算代入処理ブロック同士の再定義を説明する図である。
【図１３】スレッド化処理ブロック及びスケジューラ化処理ブロックの再定義を説明する図である。
【図１４】スレッド化処理ブロック及びスケジューラ化処理ブロックを説明する図である。
【図１５】実施例の第二段階の処理を示すフローチャートである。
【図１６】スレッド化処理ブロックへのステートメントの追加方法を説明する図である。
【図１７】スケジューラ化処理ブロックへのステートメントの追加方法を説明する図である。
【図１８】最外郭スケジューラ化処理ブロックのタイマ処理を説明する図である。
【図１９】実施例の第三段階の処理を説明するフローチャートである。
【図２０】実施例の動作時のタイミングチャートのイメージを示す図である。
【図２１】図２の従来手法と実施例のタイミングチャートのイメージを比較する図である。
【図２２】実施例のスケジューラ化処理ブロックのイメージを示す図である。
【図２３】実際のプログラムに対してコンパイルを行った場合のリソースの利用効率の測定結果を従来手法と実施例について示す図である。
【符号の説明】
【００２３】
３１      ソースコード
３２      フロントエンド
３３−１，３３−２      中間言語
３４      ミドルパス
３５      バックエンド
３６      実行コード
８１      タスク又はスレッド
８３      動的スケジューラ
８４      コンテキストスイッチ・プロセス管理機能
８６      ＯＳ
８８      タイマ機能
【発明を実施するための最良の形態】
【００２４】
本発明のコンパイル方法及びコンパイラでは、組み込み機器上で動作するソフトウェアのうち、時系列的に記述されたソフトウェアのソースコードを、コンパイル時における中間言語のプリプロセッシングでタスク又はスレッド化し、スケジューリングコードを生成するリストラクチャリングを行うことにより、小さいオーバーヘッドの実現とCPU等のリソースの利用効率の向上を可能とすることができる実行コードを生成する。【００２５】
つまり、組み込み機器上で動作するアプリケーションのうち、動画処理や通信処理等の時系列処理を行うようなループ構成のアプリケーションにおいて、コンパイルの初期段階で構造解析の終わった中間言語（中間コード）上でステートメントレベルで分類された処理ブロックから、条件分岐の処理ブロックで構成されるスケジューラの構築、タイマハンドラ化、及び条件分岐後に実行される演算代入処理の処理ブロックの抽出、スレッド化を行い、ウェイトによるCPUの解放（リリース）、シグナルに応答するウェイクアップ（Wake-Up）機構を挿入するような再構築（リストラクチャリング）を行うことで、実行時に必要なタイミングで必要な演算処理を行い、不要なときはCPUを解放するような仕組みによりCPUを含むリソースの利用効率を向上させる。【００２６】
このように、本発明では、実行対象のソフトウェアの元となるソースコードをコンパイル過程の中間言語レベルで解析、分類し、抽出された処理ブロックから並列（同時）に処理可能な処理ブロック及び、スケジューリングに関する処理ブロックとして再定義し、必要最低限のステートメントを挿入する。これにより、不要な外部ステートメント（コード）を削除し、対象とするソフトウェアの専用スケジューラをリストラクチャリングにより実現することができる。
【実施例】
【００２７】
図５は、本発明のコンパイラの一実施例の構成を示す図である。コンパイラの本実施例は、本発明のコンパイル方法の一実施例を採用する。本実施例では、本発明が組み込み機器上におけるソフトウェアの実行コードを生成する場合に適用されている。組み込み機器は、CPU等のプロセッサとメモリ等の記憶部を備え、プロセッサが記憶部に格納されたプログラムを実行する周知のハードウェア構成を有するコンピュータ（又はコンピュータシステム）である。【００２８】
図５に示すコンパイラは、組み込み機器のソフトウェアを単一のアプリケーションとして効率的に実行するために、実行コードの最適化を行う。図５に示すコンパイラは、翻訳装置（フロントエンド）３２、最適化装置（ミドルパス）３４及びコード生成装置（バックエンド）３５を有する。フロントエンド３２はソースコード３１から中間言語３３−１を生成して記憶部に保存し、ミドルパス３４は記憶部に保存された中間言語３３−１から中間言語３３−２を生成して記憶部に保存する。バックエンド３５は、記憶部に保存された中間言語３３−２から最適化された実行コード３６を生成し、必要に応じて記憶部に保存する。コンパイルによる翻訳作業の過程で、ミドルパス３４において不要な変数の削除や命令のパッキング、呼び出し関数のインライン展開等の単純なリストラクチャリングを行う。フロントエンド３２やバックエンド３５は単純な翻訳装置であり、能動的に実行コードの最適化を行うことはない。実行コードの最適化を行わない場合には、フロントエンド３２が生成した中間言語３３−１を直接バックエンド３５が解読し、実行コードを生成するため、ミドルパス３４は使用されない。【００２９】
一般的に、コンパイル処理は、ソースコードで示された処理シーケンスを対象とするCPU等の演算装置（プロセッサ）が解読できる実行コードに変換する。又、ミドルパスでは、伝播しない変数及び数式文の削除やサブルーチンのインライン展開、或いは、ループをイタレーション単位で展開するアンローリング処理等の汎用的な最適化手法により、より効率的な実行コードを生成する。【００３０】
これに対し、本実施例は、ミドルパス３４に組み込まれる効率的な実行コードの生成手法に特徴がある。図５に示すミドルパス３４は、中間言語３３−１を入力とし、以下に示す手順によりリストラクチャリングを行い、中間言語３３−２を生成する。中間言語３３−１のレベルでリストラクチャリングを行う。このため、フロントエンド３２及びバックエンド３５については従来と同様のものを変更することなく使用可能であり、ミドルパス３４は既存のコンパイラに汎用的に組み込むことが可能である。【００３１】
図６は、ソフトウェアを構成するソースコード３１の分類を説明する図である。図６は、ソフトウェアを構成するソースコード３１をステートメントレベルで分類した場合を示し、全てのソースコード３１は中間言語３３−１に翻訳された後、以下のいずれかの処理区分ｐｓ１〜ｐｓ４に分類することができる。処理区分ｐｓ１は、演算及びメモリやレジスタ等の記憶部に演算結果の代入を行う演算代入処理であることを示す。処理区分ｐｓ２は、バックエッジを含むジャンプ命令で示されるループ処理、即ち、バックエッジジャンプであることを示す。処理区分ｐｓ３は、条件分岐或いは条件付きジャンプ命令で示される分岐処理であることを示す。処理区分ｐｓ４は、サブルーチンや関数コール等を示し、無条件ジャンプ命令であることを示す。【００３２】
本実施例では、任意の構成の中間言語３３−１に着目してリストラクチャリングを行うので、汎用的な最適化処理がどこで行われても構わないが、ループ構造をそのまま使用するため、リストラクチャリングを行う前にアンローリング手法等のループ最適化手法は適用しないものとする。【００３３】
コンパイラは、中間言語３３−２を生成する際に必ず変数テーブルを内部に持ち、中間言語３３−２の各ステートメントは昇順で採番されており、参照する変数（式の右辺）と、定義する変数（式の左辺）を持つ。x番目のステートメントをSxで表した場合、Sxの参照変数の集合体を（式１）、Sxの定義変数の集合を（式２）で表す。
Use(Sx)                                        （式１）
Def(Sx)                                         （式２）
（式１）及び（式２）は、集合化されたステートメントグループSGにも適用され、y番目のステートメントグループSGyに対して同様に（式３）及び（式４）を定義する。
Use(SGx)                                       （式３）
Def(SGx)                                        （式４）
又、定義及び参照される変数が存在しない場合の表現として、空集合をΦ用いる。【００３４】
ステートメントSxが条件分岐文の場合、条件を判定するための参照変数のみが存在するため、（式５）が成立する。
Def(Sx) = Φ、Use(Sx) ≠ Φ                 （式５）
ステートメントSxがサブルーチンコールに因る無条件ジャンプ文の場合、（式６）が成立する。
Def(Sx) = Use(Sy) = Φ                        （式６）
ステートメント間の依存関係は、互いに定義及び参照する変数集合に対して同一の要素が含まれるか否かで定義される。m番目及びn番目のステートメントに関して、（式１）及び（式２）から導かれる変数の集合体において、ｍ<ｎの関係で（式７）が成立する場合、正方向依存が存在する。
Def(Sm) ∩ Use(Sn) ≠ Φ                     （式７）
ここで、SmとSnが正方向依存δであることを表現する式として（式８）を定義する。
Sm δ Sn                                          （式８）
ｍ>ｎの関係で（式７）が成立する場合、逆方向依存が存在する。SmとSnが逆方向依存δiであることを表現する式として、（式９）を定義する。
Sm δi Sn                                            （式９）
又、（式１０）が成立する場合、出力依存が存在する。
Def(Sm) ＝ Def(Sn)                                 （式１０）
SmとSnが出力依存δoであることを表現する式として、（式１１）を定義する。
Sm δo Sn                                            （式１１）
（式１１）が成立するSm, Sn について、ｍ<ｋ<ｎの関係を満たす任意のｋに対して（式１２）が成り立つ場合、Smで定義される変数はどこでも参照されることなく、Snにおいて上書きされることから、Smを削除することが可能である。
(Def(Sm) = Def(Sn))  ∩ Use(Sk) ＝ Φ          （式１２）
（式８）、（式９）及び（式１１）を一般的には依存方程式と呼び、全てのステートメントに対して（式１）及び（式２）を導くことで、各ステートメントの依存関係を表現した依存グラフを作成することができる。【００３５】
図７は、ステートメントの依存関係を表現した依存グラフの一例を示す図である。同図中、Sa〜Sfは、ステートメントを示す。図７に示す例では、ステートメントSaの定義結果をステートメントSdが参照し、ステートメントSdが参照している変数をステートメントSfで定義することを表している。又、ステートメントSbの定義変数はどこでも使用されることなく、ステートメントSfにおいて再定義されることから（式１２）が成立するとみなされ、ステートメントSbはコード中から削除されることになる。【００３６】
原則として（式８）、（式９）及び（式１１）の関係にあるステートメントは、何らかの依存関係にあるステートメントであり、処理順序を入れ替えることはできない。言い換えると、（式８）、（式９）及び（式１１）のいずれの関係も成立しないステートメント同士は、処理順序の入れ替えを行うことができる。【００３７】
上記の観点から、図７において、（式１３）に示すようにステートメントSaとステートメントSdから構成されるグループをSGx、ステートメントScとステートメントSeから構成されるグループをSGyとした場合、これらは（式１４）から依存関係にないため、互いに処理順序を入れ替えることが可能である。（式１４）において、「¬δ」は依存関係がないことを示す。又、上述のようにステートメントSbは削除可能なため、図７で示す依存グラフは図８に示すグラフと等価となる。図８は、図７の依存グラフを元にステートメントの処理順序を入れ替えた、即ち、ソートされた例を示す図である。
SGx = (Sa, Sd), SGy = (Sc, Se)                    （式１３）
つまり、
Def(SGx) = Def(Sa) ∪ Def(Sd), Use(SGx) = Use(Sa) ∪ Use(Sd)
Def(SGy) = Def(Sc) ∪ Def(Se), Use(SGy) = Use(Sc) ∪ Use(Se)
且つ、
（Def(Sa)或いはDef(Sd) ∩ （Use(Se) 或いは Use(Se)） ＝ Φ
（Use(Sa)或いはUse(Sd)  ∩ (Def(Se)  或いは Def(Se)) = Φ
（Def(Sa)或いはDef(Sd)  ∩ (Def(Se)  或いは Def(Se)) = Φ
が成立するため、（式１４）が得られる。
SGx ¬δ  SGy                                        （式１４）
図９は、ソフトウェアのフロー構成例を示す図である。図９中、ｐｓ１〜ｐｓ４は、夫々図６に示す処理区分ｐｓ１〜ｐｓ４の処理に対応する処理ブロックを示す。中間言語に展開されたステートメントの列は、図９で示すように、複数代入処理の処理ブロックｐｓ１の間に条件分岐の処理ブロックｐｓ３或いは無条件ジャンプの処理ブロックｐｓ４が挟まった形態を取る。条件分岐の処理ブロックｐｓ３及び無条件ジャンプの処理ブロックｐｓ４は、データ依存ではなく制御構造を示すものであり、処理フローが一旦途切れるとみなされるため、図５に示すミドルパス３４の処理単位を、条件分岐の処理ブロックｐｓ３及び無条件ジャンプの処理ブロックｐｓ４のステートメントで区切られた演算代入処理の処理ブロックｐｓ１、即ち、代入ステートメントの集合と考える。【００３８】
本実施例では、第一段階の処理として、図９に示す演算代入処理の処理ブロックｐｓ１に対して、上記ステートメント間の依存方程式に基づく並べ替えを行うものとする。図１０は、本実施例の第一段階を示すフローチャートである。図１０において、入力は中間言語３３−１であり、出力も中間言語３３−１である。【００３９】
図１０に示す第一段階は、全ての制御ステートメントで区切られた演算代入ステートメントのグループに対して行われる。先ず、ステップSt1で定義及び参照される変数の抽出が行われ、ステップSt2で依存グラフの定義が行われる。又、ステップSt3で不要なステートメントの削除が行われ、ステップSt4で依存グラフに基づくステートメントのソートが行われる。【００４０】
第一段階の依存解析において、従来はコンパイル段階でポインタ変数等の依存関係を明確に抽出できない場合があった。本実施例の第一段階は、第二段階以降の操作をより簡便に行うための前処理であるため、必ずしも全ての依存関係を抽出できる必要はない。【００４１】
本実施例の第二段階では、上記の中間言語レベルで整理されたステートメント列に対し、後述する方式に従ってステートメントのグループの結合及び再定義を行う。又、第二段階では、上記処理区分で分類された処理ブロックを結合する作業を行うが、一般的なソフトウェアは、ネスト構造のループ、入れ子構成の条件分岐、サブルーチン配下のループ、条件分岐等の階層構造を有する。このため、本実施例の第二段階で行う操作は、ネスト又は入れ子構造にある最も内側の階層の処理ブロックから順に行っていくものとする。【００４２】
ネスト又は入れ子構造の最も内側の処理ブロックは、必ず演算代入処理の処理ブロックになっている。第一段階において、最も内側の処理ブロックに存在したステートメントが依存方程式の解により削除された場合には、該当する入れ子構造も削除される。【００４３】
ネスト又は入れ子構造の最も内側の処理ブロックの処理にあたっては、呼び出し元の処理ブロックが無条件ジャンプ、即ち、コールされるサブルーチンの本体である場合には、これを前段処理区分の無条件ジャンプの処理ブロックと結合して再グループ化し、演算代入処理ブロックとして再定義する。【００４４】
一般的なコード最適化において、ステートメントがインライン展開されていれば、この操作は第一段階の処理において通常の演算代入処理ブロックの整理と共に処理されるが、本実施例においては、ステートメントがインライン展開される必要はなく、単にステートメントのグループ化が行われるだけで良い。【００４５】
ネスト又は入れ子構造の最も内側の処理ブロックの処理にあたっては、呼び出し元の処理ブロックがループ処理（バックエッジジャンプ）の処理ブロック、即ち、ループ内部に条件分岐等の制御構造を伴わない単純ループの本体である場合には、これを再グループ化し、演算代入処理ブロックとして再定義する。【００４６】
図１１は、無条件ジャンプ及びループ処理（バックエッジジャンプ）の処理ブロックの演算代入処理ブロックとしての再定義を説明する図である。図１１に示すように、呼び出し元の処理ブロックが無条件ジャンプの処理ブロックである場合には、これを前段処理区分の無条件ジャンプの処理ブロックと結合して再グループ化し、演算代入処理ブロックとして再定義する。又、図１１に示すように、呼び出し元の処理ブロックがループ処理（バックエッジジャンプ）の処理ブロックである場合には、これを再グループ化し、演算代入処理ブロックとして再定義する。【００４７】
上記の如き演算代入処理ブロックの再定義を行った結果、ネスト又は入れ子の同一階層に演算代入処理ブロックが縦列に並ぶことがある。この場合、縦列に並んだ演算代入処理ブロックは結合され、再び演算代入処理ブロックとして再定義される。【００４８】
図１２は、演算代入処理ブロック同士の再定義を説明する図である。図１２において、「代入演算」は代入演算処理ブロックを示し、破線で囲まれた処理ブロックは結合された処理ブロックを示す。【００４９】
次に、呼び出し元の処理ブロックが条件分岐処理の処理ブロックの場合、即ち、条件分岐の真偽いずれかの従属節にあたる場合、特に処理ブロック間の結合処理を行うことなく、これをスレッド化処理ブロックとして再定義する。【００５０】
図１３は、スレッド化処理ブロック及びスケジューラ化処理ブロックの再定義を説明する図である。ネスト又は入れ子構造の階層的な解析により、スレッド化処理ブロックの構成要素は必ずしも１つの処理ブロックとは限らず、又、スレッド化処理ブロックの構成要素は演算代入処理ブロックだけとは限らない。【００５１】
又、ある処理ブロックの後続の処理ブロックが条件分岐処理である場合、これらの処理ブロックを結合し、スケジューラ化処理ブロックとして再定義する。【００５２】
スレッド化処理ブロックとスケジューラ化処理ブロックには密接な関係があり、スレッド化処理ブロックは条件分岐からの従属節であるため、必ず該当する条件分岐を含んだスケジューラ化処理ブロックと連携することになる。【００５３】
上記の処理ブロック化を対象とするコードに対して、ネストや入れ子構造も考慮してスレッド化処理ブロック及びスケジューラ化処理ブロックを再定義する。図１４は、スレッド化処理ブロック及びスケジューラ化処理ブロックを説明する図である。図１４に示すプログラム中、４１は図１４において階層の最も上位に属するスケジューラ化処理ブロック、４２はスケジューラ化処理ブロック４１に従属するスレッド化処理ブロック、４３はスケジューラ化処理ブロック４１の一階層下に含まれるスケジューラ化処理ブロック、４４はスケジューラ化処理ブロック４３に従属するスレッド化処理ブロック、４５はスレッド化処理ブロック４２の一階層下に含まれるスケジューラ化処理ブロック、４６はスケジューラ化処理ブロック４５に従属するスレッド化処理ブロックを夫々示す。【００５４】
図１５は、本実施例の第二段階の処理を示すフローチャートである。図１５において、入力は中間言語３３−１であり、出力も中間言語３３−１である。【００５５】
図１５に示す第二段階は、上記第一段階で行った依存グラフに基づくステートメントのソートの結果に対して行われる。先ず、ステップSt11は、処理ブロック化を対象とするプログラムのコードに対して、ネスト又は入れ子構造にある最も内側の階層の処理ブロックから順に処理を開始する。ステップSt12は、呼び出し元の処理ブロックが条件分岐処理であるか否かを判定する。ステップSt12の判定結果がYESであると、ステップSt13は、条件分岐の従属節をスレッド化処理ブロックとして再定義し、処理はステップSt11へ戻り、ネスト又は入れ子構造にある最も内側の階層の次の階層の処理ブロックの処理を開始する。他方、ステップSt12の判定結果がNOであると、ステップSt14は、後続の処理ブロックが条件分岐処理に続くものであるか否かを判定し、判定結果がNOであると、処理はステップSt11へ戻り、ネスト又は入れ子構造にある最も内側の階層の更に次の階層の処理ブロックの処理を開始する。又、後続の処理ブロックが条件分岐処理でありステップSt14の判定結果がYESであると、ステップSt15は、これらの処理ブロックと後続の処理ブロックを結合してスケジューラ化処理ブロックとして再定義する。ステップSt15の後、処理はステップSt11へ戻り、ネスト又は入れ子構造にある最も内側の階層の次の階層の処理ブロックの処理を開始する。【００５６】
本実施例の第二段階では、上記の中間言語レベルで整理されたステートメント列に対し、後述する方式に従ってステートメントのグループの結合及び再定義を行う。又、第二段階では、上記処理区分で分類された処理ブロックを結合する作業を行うが、一般的なソフトウェアは、ネスト構造のループ、入れ子構成の条件分岐、サブルーチン配下のループ、条件分岐等の階層構造を有する。このため、本実施例の第二段階で行う操作は、ネスト又は入れ子構造にある最も内側の階層の処理ブロックから順に行っていくものとする。【００５７】
本実施例の第三段階では、第二段階でグループ化を行ったスケジューラ化処理ブロック及びスレッド化処理ブロックに制御ステートメントを付加し、スレッドとスケジューラとして最終的な中間言語（中間コード）を生成する。【００５８】
条件分岐及び条件を算出する演算と、それに従属する処理ブロックの呼び出しは、動的スケジューラとスケジューリングされるスレッドの関係と等価である。本実施例では、外部（又は、外付けの）スケジューラを使用しない構造とするため、スケジューラ化処理ブロックの構造にスレッドのコンテキストスイッチ機能と同様の動きをする仕組みを設ける。又、スレッド化処理ブロックには、スケジューラの要求時にのみ動作する仕組みを設ける。【００５９】
そこで、本実施例の第三段階では、スケジューラ化処理ブロックとそれに従属するスレッド化処理ブロックに対して次のような操作を行う。【００６０】
図１６は、スレッド化処理ブロックへのステートメントの追加方法を説明する図である。先ず、図１６に５１で示すようにスレッド化処理ブロック５５をループで囲み、５２で示すようにループの入口部分（先頭部分）にシグナルを受信待ちし、シグナルを受信するまではCPUを解放（リリース）するウェイト（wait）機構のようなＯＳのサービスコールを挿入する。又、５３，５４で示すように、スレッド化された処理ブロック同士が並列動作することも考慮し、並列実行（同時実行）する処理ブロックを（式８）、（式９）及び（式１１）で導かれる依存方程式に基づいて解析し、依存関係にある場合、セマフォ（Semaphore）やミューテックス（Mutex）による排他制御コードを挿入する。つまり、５３で示すように排他ロックをかけると共に、５４で示すように排他ロックを解除する。上記の操作により、構造を変更されたスレッド化処理ブロック５５をイベント処理スレッド５９として定義して起動するようなコードをプログラム本体に追加することができる。【００６１】
上記の操作により、処理動作を行わなくても良いタイミングでは、イベント処理スレッド５９はCPUを解放しているため、不要なCPUリソースを使用することがない。【００６２】
図１７は、スケジューラ化処理ブロックへのステートメントの追加方法を説明する図である。スケジューラ化処理ブロックには条件分岐処理が含まれており、その条件分岐が発生するタイミングが上記のイベント処理スレッド５９を起動するタイミング（スケジューリングする）であると考えられる。そこで、条件分岐後の従属節に、図１７に６１で示すように従属するイベント処理スレッド５９が期待するシグナル（即ち、条件A又はBが成立すると動作させるイベントに対するシグナル）を発行するステートメント（コード）を挿入し、これをスケジューラ化処理ブロック６９として定義する。【００６３】
元となるソースコード３１中、スケジューラ化処理ブロック６５が入れ子構造の内部にある場合、そのスケジューラ化処理ブロック６５を起動するのはその親階層にあるスケジューラ化処理ブロックである。図１４の例では、シグナルに応答するウェイクアップ機構が挿入されたようなリストラクチャリングにより、４５で示す入れ子の内側のスケジューラ化処理ブロックは、４１で示す上位階層のスケジューラ化処理ブロックからのシグナル発信を契機に、ダイナミックに起動されることになる。【００６４】
本実施例では、主に時系列処理、即ち、予め決められたタイミングで途中の演算結果を出力するような汎用的なプログラミング言語で記述されたプログラムを想定しており、このようなプログラムは、一般的にはプログラムの最も上位の階層でループ構造を取る。本実施例の第二段階の処理を行うと、必ず最外郭ループに囲まれたスケジューラ化処理ブロック、即ち、最外郭スケジューラ化処理ブロックが存在することになる。【００６５】
上記最外郭スケジューラ化処理ブロックを起動する動的シグナル発生装置はないため、最外郭スケジューラ化処理ブロックについては、図１８に示すように、ＯＳのタイマ機能を用い、周期的にＯＳからシグナル（タイマ信号）を送信し、自動起動させるようなタイマハンドラのような仕組みを組み込む。図１８は、最外郭スケジューラ化処理ブロックのタイマ処理を説明する図である。図１８中、図１７と同一部分には同一符号を付し、その説明は省略する。図１８において、６４はＯＳから周期的に送信されるシグナル（タイマ信号）、６５Aは最外郭スケジューラ化処理ブロック、６９Aは６１で示すように従属するイベント処理スレッド５９が期待するシグナル（即ち、条件A又はBが成立すると動作させるイベントに対するシグナル）を発行するステートメント（コード）が挿入されて定義されたスケジューラ化処理ブロックを示す。【００６６】
図１９は、本実施例の第三段階の処理を説明するフローチャートである。図１９において、入力は中間言語３３−１であり、出力は中間言語３３−２である。【００６７】
図１９に示す第三段階は、上記第二段階でグループ化を行ったスケジューラ化処理ブロック及びスレッド化処理ブロックに対して行われる。先ず、ステップSt21は、処理の対象となる処理ブロックがスレッド化処理ブロックであるか、或いは、スケジューラ化処理ブロックであるかを判定する。処理対象となる処理ブロックがスレッド化処理ブロックの場合、ステップSt22〜St25のスレッド化処理ブロックへステートメントを追加する処理が行われる。他方、処理対象となる処理ブロックがスケジュール化処理ブロックの場合、ステップSt26〜St28のスケジューラ化処理ブロックへステートメントを追加する処理が行われる。【００６８】
ステップSt22は、図１６に５１で示すようにスレッド化処理ブロック５５をループで囲む。ステップSt23は、図１６に５２で示すようにループの入口部分にシグナルを受信待ちし、シグナルを受信するまではCPUを解放（リリース）するウェイト（wait）機構のようなＯＳのサービスコールを挿入する。ステップSt24は、図１６に５３，５４で示すようにスレッド化された処理ブロック同士が並列動作することも考慮し、並列実行（同時実行）する処理ブロックを（式８）、（式９）及び（式１１）で導かれる依存方程式に基づいて解析し、依存関係にあるか否かを判定する。ステップS２４の判定結果がYESの場合、ステップS２５は、セマフォ（Semaphore）やミューテックス（Mutex）による排他制御コードを挿入し、処理は終了する。他方、ステップSt24の判定結果がNOであると処理は終了する。【００６９】
ステップSt26は、条件分岐後の従属節に図１７に６１で示すように従属するイベント処理スレッド５９が期待するシグナル（即ち、条件A又はBが成立すると動作させるイベントに対するシグナル）を発行する送信機構（ステートメント）を挿入し、これをスケジューラ化処理ブロック６９として定義する。ステップSt27は、スケジューラ化処理ブロックが最外郭スケジューラ化処理ブロックであるか否かを判定する。ステップSt27の判定結果がYESであると、ステップSt28は、タイマハンドラを組み込み、処理は終了する。他方、ステップSt27の判定結果がNOであると、処理は終了する。【００７０】
上記第三段階の操作を行うことにより、ソースコード３１中に含まれた処理シーケンスから動的スケジューラ機能を導き出すことができ、外部スケジューラを用いる場合のようなオーバーヘッドが発生しない。又、不要なバッファリングを行う必要がないため、メモリの利用効率が高くなる。更に、各処理ブロックは、必要時にCPUを使用するような仕組み、即ち、処理動作が不要な時にはCPUを解放する仕組みも同時に組み込まれるため、CPUのリソースも効率的に使用することが可能になる。【００７１】
図２０は、本実施例の動作時のタイミングチャートのイメージを示す図である。図２０は、ＯＳのタイマ機能を用いて得られる周期的なシグナル（タイマ信号）、スケジューラ化処理ブロックにより実現される動的スケジューラ、及びイベント処理スレッドET1，ET2のタイミングを示す。【００７２】
ネスト又は入れ子構造になっているコードのうち、同一階層にあるスケジューラがあり、且つ、上記（式１４）で導出されるステートメント（又は処理ブロック）の順序の入れ替えが可能な場合、スケジューラ化処理ブロックの処理順序を入れ替えることで、動的スケジューリングにおける割付優先度の制御の考え方を導入することが可能である。一般的に、動的スケジューラの割付優先度の決定は、ヒューリスティック（heuristic）なアルゴリズムに従って行われ、CPUの使用量（処理ブロックのクリティカルパス）、メモリの使用量（データ使用量）等をアルゴリズムが判断に用いるパラメータ（又は係数）として使用する。優先度のソートの鍵となるパラメータを決定するに当たり、最良の解を得るには対象とするソフトウェアの性質に依存することが大きい。【００７３】
本実施例では、上記第一段階〜第三段階の処理をコンパイラのミドルパス３４に組み込むため、一般的なコンパイラによる最適化の手法として２パスコンパイルの考えを導入することができる。一般的な２パスコンパイラでは、１回目のコンパイルで生成された実行コードに基づいて実際に組み込み機器等を動作させてプロファイリングを行い、プロファイリングの結果に基づいて２回目のコンパイルを行う。【００７４】
プロファイリングを用いる２パスコンパイルを許すコンパイラに本実施例を適用した場合、スケジューラ化処理ブロックの優先度によるソートを、このプロファイリング結果に基づいて行うことが可能である。従って、本手法を用いることで、より精度の高いスケジューリング結果を得ることが可能になる。【００７５】
このようにして、ミドルパス３４は、図５のバックエンド３５が解読可能な中間言語３３−２を生成し、コンパイラは実行コード３６を生成する。【００７６】
図２１は、図２の従来手法と本実施例のタイミングチャートのイメージを比較する図である。図２１中、図２及び図２０と同一部分には同一符号を付し、その説明は省略する。図２１の上部は本実施例の動作タイミングを示し、下部は図２の従来手法の動作タイミングを示す。図２１において、OH1は本実施例における複数スレッド化により生じるオーバーヘッドを示し、R1は本実施例におけるCPU解放期間を示す。本実施例によれば、処理P3の実際の終了時間は従来手法における終了時間ｔ２より多少遅くなるが、処理P4を確実に期待終了時間ｔ３までに終了することができる。このため、本実施例では、時系列処理することで定期的に途中演算結果を出力するようなソフトウェアにおいて、従来手法において生じていた分岐タイミングの逸脱による処理完了時間の遅延を回避することができる。又、本実施例では、図３の従来手法のようなバッファリングを行う必要がないため、メモリの利用効率が高くなる。【００７７】
図２２は、本実施例のスケジューラ化処理ブロック、即ち、動的スケジューラのイメージを示す図である。同図中、８１はタスク又はスレッド、８２はCPUのアイドル状態、８３はコンテキストスイッチ機能を有すると共にスケジューリングを行う動的スケジューラ、８４はＯＳ８６内のプロセス管理機能、８５は動的スケジューラ８３の指示によるスイッチ、８８はＯＳ８６内のタイマ機能を示す。組み込み機器で効率的に複数のタスク又はスレッド８１を並列（同時）に実行する場合、図２２に示す動的スケジューラ８３は、ＯＳ８６のタイマ機能８８からのシグナルに基づいて動的にタスク又はスレッド８１の優先度を定義すると共に、そのコンテキストスイッチ機能及びＯＳ８６のプロセス管理機能８４によりタスク又はスレッド８１のスイッチ８５を行う。本実施例によれば、スレッドとタイマハンドラに分解されたソースコード３１は、能動的にCPUを解放しアイドル状態８２にするため、不要なCPUのリソースを使用することがない。又、動的スケジューラ８３を構成するスケジューラ化処理ブロックは、元々ソースコード３１中に存在するコードであるため、複数スレッド化により生じるオーバーヘッドも極めて小さい。【００７８】
図２３は、実際のプログラムに対してコンパイルを行った場合のリソースの利用効率の測定結果を上記従来手法と実施例について示す図である。図２３に示すように、プログラムPAは動画プレーヤのソフトウェアであり、プログラムPBは通信処理のソフトウェアである。プログラムPA，PBは、いずれも時系列処理を基本とし、予め決められたタイミングで途中結果を出力するソフトウェアである。プログラムPCは静止画処理のソフトウェアであり、プログラムPDは算術演算のソフトウェアである。プログラムPCは、XGAの圧縮画像の伸張を行うソフトウェアである。プログラムPDは、既にプログラマによりソースコードレベルで最適化が行われた流体計算用のソフトウェアである。【００７９】
図２３からもわかるように、本実施例によれば、全てのプログラムPA〜PDについて、CPU負荷が上記従来手法の場合と比べて低減されることが確認された。又、本実施例によれば、プログラムPA，PB，PCについては、メモリ使用量が上記従来手法の場合と比べて低減されることが確認された。更に、本実施例によれば、プログラムPA，PB，PCについては、CPUの消費電力をピーク時の消費電力より低減できることが確認された。尚、本実施例によれば、プログラムPCについては、スレッド化の効果は少ないものの、第一段階のステートメント調整による効果が見られた。【００８０】
このように、主に時系列処理型のプログラムの完成度にもよるが、本実施例によれば、CPU及びメモリ、即ち、リソースの使用量は、従来手法を用いる場合と比べて３０％前後低減することが確認できた。又、副次効果としてCPUのアイドル状態を生成することができるため、CPUの消費電力を低減する効果もあることが確認された。
【産業上の利用可能性】
【００８１】
本発明は、CPUやメモリ等のリソースを有する各種電子機器に適用可能であり、特にリソースが限られた組み込み機器に好適である。【００８２】
以上、本発明を実施例により説明したが、本発明は上記実施例に限定されるものではなく、本発明の範囲内で種々の変形及び改良が可能であることは言うまでもない。
【図１】
2008072334.tif 000003
【図２】
2008072334.tif 000004
【図３】
2008072334.tif 000005
【図４】
2008072334.tif 000006
【図５】
2008072334.tif 000007
【図６】
2008072334.tif 000008
【図７】
2008072334.tif 000009
【図８】
2008072334.tif 000010
【図９】
2008072334.tif 000011
【図１０】
2008072334.tif 000012
【図１１】
2008072334.tif 000013
【図１２】
2008072334.tif 000014
【図１３】
2008072334.tif 000015
【図１４】
2008072334.tif 000016
【図１５】
2008072334.tif 000017
【図１６】
2008072334.tif 000018
【図１７】
2008072334.tif 000019
【図１８】
2008072334.tif 000020
【図１９】
2008072334.tif 000021
【図２０】
2008072334.tif 000022
【図２１】
2008072334.tif 000023
【図２２】
2008072334.tif 000024
【図２３】
2008072334.tif 000025
【手続補正書】
【提出日】平成21年6月8日(2009.6.8)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
コンピュータにより、予め決められたタイミングで途中結果を出力すると共に時系列的に処理されるソフトウェアのコンパイルを行うコンパイル方法であって、
該コンピュータにより、該ソフトウェアのソースコードに含まれる処理シーケンスから並列性及び条件分岐に関する処理ブロックを抽出する抽出ステップと、
該コンピュータにより、抽出された処理ブロックのリストラクチャリングを行い実行コードを自動的に生成する生成ステップとを含むことを特徴とする、コンパイル方法。
【請求項２】
該抽出ステップは、演算及び該コンピュータのメモリ及びレジスタに演算結果の代入を行う演算代入処理の処理ブロックに対して、ステートメント間の依存方程式に基づく並べ替えを行い中間言語レベルで整理されたステートメント列を求める第一段階と、該整理されたステートメント列に対してステートメントのグループの結合及び再定義を行う第二段階を有することを特徴とする、請求項１記載のコンパイル方法。
【請求項３】
該生成ステップは、該第二段階でグループ化を行ったスケジューラ化処理ブロック及びスレッド化処理ブロックに制御ステートメントを付加し、スレッドとスケジューラとして最終的な中間言語を生成する第三段階を有し、
該スケジューラ化処理ブロックは、後続の処理ブロックが条件分岐処理であると処理ブロックと結合されて再定義されたものであり、
該スレッド化処理ブロックは、呼び出し元の処理ブロックが条件分岐処理であると条件分岐の従属節が再定義されたものであることを特徴とする、請求項２記載のコンパイル方法。
【請求項４】
該第三段階は、該第二段階でグループ化を行ったスケジューラ化処理ブロック及びスレッド化処理ブロックに対して行われ、
処理の対象となる処理ブロックがスレッド化処理ブロックの場合はスレッド化処理ブロックへステートメントを追加する処理を行い、
処理対象となる処理ブロックがスケジュール化処理ブロックの場合はスケジューラ化処理ブロックへステートメントを追加する処理を行うことを特徴とする、請求項３記載のコンパイル方法。
【請求項５】
該第三段階は、演算処理が不要な期間において該コンピュータを解放する機構を有する制御ステートメントを付加することを特徴とする、請求項３記載のコンパイル方法。
【請求項６】
コンピュータにより、予め決められたタイミングで途中結果を出力すると共に時系列的に処理されるソフトウェアのコンパイルを行うコンパイラであって、
該コンピュータにより、該ソフトウェアのソースコードを第１の中間言語に翻訳して記憶部に保存するフロントエンドと、
該コンピュータにより、該記憶部に保存された該第１の中間言語に基づいて該ソースコードに含まれる処理シーケンスから並列性及び条件分岐に関する処理ブロックを抽出し、抽出された処理ブロックのリストラクチャリングを行い第２の中間言語を生成して記憶部に保存するミドルパスと、
該コンピュータにより、該記憶部に保存された該第２の中間言語に基づいて実行コードを自動的に生成するバックエンドとを備えたことを特徴とする、コンパイラ。
【請求項７】
該ミドルパスは、演算及び該記憶部に演算結果の代入を行う演算代入処理の処理ブロックに対して、ステートメント間の依存方程式に基づく並べ替えを行い該第１の中間言語レベルで整理されたステートメント列を求める第一段階と、該整理されたステートメント列に対してステートメントのグループの結合及び再定義を行う第二段階を有することを特徴とする、請求項６記載のコンパイラ。
【請求項８】
該ミドルパスは、該第二段階でグループ化を行ったスケジューラ化処理ブロック及びスレッド化処理ブロックに制御ステートメントを付加し、スレッドとスケジューラとして該第２の中間言語を生成する第三段階を有し、
該スケジューラ化処理ブロックは、後続の処理ブロックが条件分岐処理であると処理ブロックと結合されて再定義されたものであり、
該スレッド化処理ブロックは、呼び出し元の処理ブロックが条件分岐処理であると条件分岐の従属節が再定義されたものであることを特徴とする、請求項７記載のコンパイラ。
【請求項９】
該スケジューラ化処理ブロックはスレッドのコンテキストスイッチ機能を有し、該スレッド化処理ブロックはスケジューラの要求時にのみ動作する仕組みを有することを特徴とする、請求項８記載のコンパイラ。
【請求項１０】
該第三段階は、最外郭ループに囲まれたスケジューラ化処理ブロックについては、該コンピュータのＯＳのタイマ機能を用いて周期的にシグナルを送信して自動起動させるタイマハンドラの仕組みを組み込むことを特徴とする、請求項８記載のコンパイラ。
【国際調査報告】
2008072334.tif 000026
2008072334.tif 000027
2008072334.tif 000028
2008072334.tif 000029
2008072334.tif 000030
2008072334.tif 000031