(57)【要約】【課題】パイプラインでブロックをスケジュールするコンパイル方法及び装置を提供する。【解決手段】プログラムコードによる制御流れのブロックに対するアクセスカウントを、プロセッサを用いてプロファイルするステップと、ブロックに入るエッジの前記アクセスカウントに含まれる、エッジカウントが予め決定した値以上である場合、ブロックを重要ブロックとして判断するステップと、レジスタライトバックコンフリクトが防止されるように重要ブロックをアクセスカウントに応じてスケジュールするステップとを含む。【選択図】      図６
2014146311.tif 000002
【特許請求の範囲】
【請求項１】
プログラムコードによる制御流れのブロックに対するアクセスカウントを、プロセッサを用いてプロファイルするステップと、
前記ブロックに入るエッジの前記アクセスカウントに含まれる、エッジカウントが予め決定した値以上である場合、前記ブロックを重要ブロックとして判断するステップと、
レジスタライトバックコンフリクトが防止されるように前記重要ブロックを前記アクセスカウントに応じてスケジュールするステップと、
を含むことを特徴とするパイプラインでブロックをスケジュールするコンパイル方法。
【請求項２】
前記ブロックに入るエッジの前記アクセスカウントに含まれる、エッジカウントが予め決定した値以上である場合、前記ブロックを重要ブロックとして判断するステップは、
前記エッジカウントが予め決定した重要限界値以上であるエッジを重要エッジとしてマークするステップと、
前記重要エッジが入るブロックを前記重要ブロックとして判断するステップと、
を含むことを特徴とする請求項１に記載のパイプラインでブロックをスケジュールするコンパイル方法。
【請求項３】
前記エッジカウントが予め決定した重要限界値以上であるエッジを重要エッジとしてマークするステップは、スケジュールされないブロックから入る前記重要エッジをノーマルエッジとしてマークするステップを含むことを特徴とする請求項２に記載のパイプラインでブロックをスケジュールするコンパイル方法。
【請求項４】
前記レジスタライトバックコンフリクトが防止されるように前記重要ブロックを前記アクセスカウントに応じてスケジュールするステップは、
前記アクセスカウントによる優先順位で前記ブロックを整列するステップと、
前記優先順位で整列した順序に応じて順次前記ブロックをスケジュールするステップと、
を含むことを特徴とする請求項１乃至３のいずれか一項に記載のパイプラインでブロックをスケジュールするコンパイル方法。
【請求項５】
前記ブロックに入るエッジの前記アクセスカウントに含まれる、エッジカウントが予め決定した値以上である場合、前記ブロックを重要ブロックとして判断するステップは、前記アクセスカウントに応じて前記ブロックからスーパーブロックを形成するステップを含むことを特徴とする請求項１乃至４のいずれか一項に記載のパイプラインでブロックをスケジュールするコンパイル方法。
【請求項６】
前記レジスタライトバックコンフリクトが防止されるように前記重要ブロックを前記アクセスカウントに応じてスケジュールするステップは、前記重要ブロックで前記レジスタライトバックコンフリクトが予想されるサイクルにライトバックの実行されないオペレーションをスケジュールするステップを含むことを特徴とする請求項１乃至５のいずれか一項に記載のパイプラインでブロックをスケジュールするコンパイル方法。
【請求項７】
前記重要ブロックで前記レジスタライトバックコンフリクトが予想されるサイクルにライトバックの実行されないオペレーションをスケジュールするステップは、前記レジスタライトバックコンフリクトが予想されるサイクルにＮＯＰ（Ｎｏ  ＯＰｅｒａｔｉｏｎ）をスケジュールするステップを含むことを特徴とする請求項６に記載のパイプラインでブロックをスケジュールするコンパイル方法。
【請求項８】
前記重要ブロックで前記レジスタライトバックコンフリクトが予想されるサイクルにライトバックの実行されないオペレーションをスケジュールするステップは、前記レジスタライトバックコンフリクトが予想されるサイクルに格納オペレーションをスケジュールするステップを含むことを特徴とする請求項６又は７に記載のパイプラインでブロックをスケジュールするコンパイル方法。
【請求項９】
前記レジスタライトバックコンフリクトが防止されるように前記重要ブロックを前記アクセスカウントに応じてスケジュールするステップは、前記重要ブロック内部または前記重要ブロックとエッジによって接続されるブロックでライトバックが行われるように前記重要ブロックのオペレーションをスケジュールするステップを含むことを特徴とする請求項１乃至８のいずれか一項に記載のパイプラインでブロックをスケジュールするコンパイル方法。
【請求項１０】
前記重要ブロックとして判断されていない非重要ブロックでライトバックを無視してスケジュールするステップを含むことを特徴とする請求項１乃至９のいずれか一項に記載のパイプラインでブロックをスケジュールするコンパイル方法。
【請求項１１】
前記重要ブロックとして判断されていない非重要ブロックでライトバックを無視してスケジュールするステップは、前記非重要ブロックで前記レジスタライトバックコンフリクトが予想されるサイクルにハードウェア的にストールサイクルを適用するステップを含むことを特徴とする請求項１０に記載のパイプラインでブロックをスケジュールするコンパイル方法。
【請求項１２】
すでにスケジュールされたブロックに出て行くエッジがある場合、前記重要ブロックとして判断されていない非重要ブロックを、前記非重要ブロック内でオペレーションのライトバックが行われるようにスケジュールするステップを含むことを特徴とする請求項１乃至１１のいずれか一項に記載のパイプラインでブロックをスケジュールするコンパイル方法。
【請求項１３】
プログラムコードによる制御流れのブロックに対するアクセスカウントをプロファイルするブロックプロファイル部と、
前記ブロックに入るエッジの前記アクセスカウントに含まれるエッジカウントが予め決定した値以上である場合、前記ブロックを重要ブロックとして判断するブロック判断部と、
レジスタライトバックコンフリクトが防止されるように前記重要ブロックを前記アクセスカウントに応じてスケジュールするブロックスケジュール部と、
を備えることを特徴とするパイプラインでブロックをスケジュールするコンパイル装置。
【請求項１４】
前記アクセスカウントに応じて前記ブロックからスーパーブロックを形成するスーパーブロック形成部を備え、
前記ブロックスケジュール部は、前記アクセスカウントによる優先順位で前記ブロック及び前記スーパーブロックを整列して整列した順序に応じて順次前記ブロック及び前記スーパーブロックをスケジュールすることを特徴とする請求項１３に記載のパイプラインでブロックをスケジュールするコンパイル装置。
【請求項１５】
前記ブロック判断部は、前記ブロックで前記エッジカウントが予め決定した重要限界値以上であるエッジを重要エッジとしてマークし、スケジュールされないブロックから入る前記重要エッジをノーマルエッジとしてマークするエッジマーク部を備え、
前記重要エッジが入るブロックを前記重要ブロックとして判断することを特徴とする請求項１３又は１４に記載のパイプラインでブロックをスケジュールするコンパイル装置。
【請求項１６】
前記ブロックスケジュール部は、前記重要ブロックで前記レジスタライトバックコンフリクトが予想されるサイクルにライトバックの実行されないオペレーションをスケジュールし、前記重要ブロックとして判断されていない非重要ブロックですでにスケジュールされたブロックに出て行くエッジがある場合、前記非重要ブロック内でオペレーションのライトバックが行われるようにスケジュールすることを特徴とする請求項１３乃至１５のいずれか一項に記載のパイプラインでブロックをスケジュールするコンパイル装置。
【請求項１７】
前記重要ブロックとして判断されていないブロックでレジスタライトバックコンフリクトが予想されるサイクルにストールサイクルを適用するストール適用部を備えることを特徴とする請求項１３乃至１６のいずれか一項に記載のパイプラインでブロックをスケジュールするコンパイル装置。
【請求項１８】
請求項１〜請求項１２のいずれか一項に記載のコンパイル方法をコンパイル装置に実行させるコンピュータプログラム。
【請求項１９】
パイプラインでブロックをスケジューリングするコンパイル方法において、
プロセッサを用いて前記ブロックが重要ブロックであるか前記ブロックのアクセスカウントを用いて判断するステップと、
前記ブロックを重要ブロックとして判断した場合、前記ブロックでレジスタライトバックコンフリクトが発生することを防止するように前記ブロックをスケジューリングするステップと、
を含むことを特徴とする方法。
【請求項２０】
前記ブロックの前記アクセスカウントは、少なくとも１つの動作命令の結果としてコンパイルされたプログラムコードの総アクセス数に対する前記ブロックの使用回数の比率であることを特徴とする請求項１９に記載の方法。
【請求項２１】
前記ブロックを非重要ブロックとして判断した場合、前記ブロックでレジスタライトバックコンフリクトの発生を許容するように前記ブロックをスケジューリングするステップをさらに含むことを特徴とする請求項１９又は２０に記載の方法。
【請求項２２】
前記ブロックにレジスタライトバックコンフリクトの発生を許容するように前記ブロックをスケジューリングする場合、前記ブロックがレジスタライトバックコンフリクトを発生すると予測されるかを判断し、前記ブロックがレジスタライトバックコンフリクトを発生させるものとして予測されると判断された場合、ストールサイクルを適用するステップをさらに含むことを特徴とする請求項２１に記載の方法。
【請求項２３】
パイプラインでブロックをスケジューリングするコンパイル装置において、
前記ブロックが重要または非重要であるか前記ブロックに入るエッジのエッジカウントを予め決定した値と比較して判断するブロック判断部と、
前記ブロックが重要である場合、前記ブロックでレジスタライトバックコンフリクト発生を防止するように前記ブロックがスケジューリングされ、前記ブロックが非重要である場合、前記ブロックでレジスタライトバックコンフリクト発生を許容するように前記ブロックがスケジューリングされるよう前記ブロックをスケジューリングするブロックスケジューリング部と、
を備えることを特徴とするコンパイル装置。
【請求項２４】
前記ブロックスケジューリング部は、前記ブロックが重要ではない場合、前記ブロックが前記レジスタライトバックコンフリクトを発生させると予測されるかを判断し、前記ブロックが前記レジスタライトバックコンフリクトを発生させるものと予測されると判断した場合、前記レジスタライトバックコンフリクトが予測されるサイクルにストールサイクルを適用することを特徴とする請求項２３に記載のコンパイル装置。
【発明の詳細な説明】
【技術分野】
【０００１】
プログラムコードによるパイプラインでブロックをスケジュールするコンパイル方法及び装置が開示される。
【背景技術】
【０００２】
複数のパイプラインを有するコンピュータ構造において、ライトバック（ｗｒｉｔｅ−ｂａｃｋ）はオペレーションにより磁気ディスクなどに記録するデータを一時的レジスタに格納するものである。物理的な作動に伴う記録は電気的処理に比べて遅いため、ライトバックによってデータをレジスタに記録し、システム全体の待ち時間（ｌａｔｅｎｃｙ）を減少させる。
【０００３】
ここで、各オペレーションの待ち時間が異なると、他のサイクルに開始されたオペレーションが同時にレジスタに書き込む場合が発生し、これをレジスタライトバックコンフリクト（ｒｅｇｉｓｔｅｒ  ｗｒｉｔｅ−ｂａｃｋ  ｃｏｎｆｌｉｃｔ）という。
【０００４】
したがって、レジスタライトバックコンフリクトを発生させずにも待ち時間を最小化することのできるコンパイラ技術が求められている。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、プログラムコードによるパイプラインでレジスタライトバックコンフリクトが防止されるようにブロックをスケジュールするコンパイル方法及び装置提供することにある。
【課題を解決するための手段】
【０００６】
一実施形態によると、プログラムコードによる制御流れのブロックに対するアクセスカウントを、プロセッサを用いてプロファイルするステップと、ブロックに入るエッジのアクセスカウントに含まれる、エッジカウントが予め決定した値以上である場合、ブロックを重要ブロックとして判断するステップと、レジスタライトバックコンフリクトが防止されるように重要ブロックをアクセスカウントに応じてスケジュールするステップとを含むパイプラインでブロックをスケジュールするコンパイル方法が提供される。
【０００７】
他の一実施形態によると、ブロックに入るエッジのアクセスカウントに含まれる、エッジカウントが予め決定した値以上である場合、ブロックを重要ブロックとして判断するステップは、エッジカウントが予め決定した重要限界値以上であるエッジを重要エッジとしてマークするステップと、重要エッジが入るブロックを重要ブロックとして判断するステップとを含むパイプラインでブロックをスケジュールするコンパイル方法が提供されてもよい。
【０００８】
他の一実施形態によると、エッジカウントが予め決定した重要限界値以上であるエッジを重要エッジとしてマークするステップは、スケジュールされないブロックから入る重要エッジをノーマルエッジとしてマークするステップを含むパイプラインでブロックをスケジュールするコンパイル方法が提供されてもよい。
【０００９】
他の一実施形態によると、レジスタライトバックコンフリクトが防止されるように重要ブロックをアクセスカウントに応じてスケジュールするステップは、アクセスカウントによる優先順位でブロックを整列するステップと、優先順位で整列した順序に応じて順次ブロックをスケジュールするステップとを含むパイプラインでブロックをスケジュールするコンパイル方法が提供されてもよい。
【００１０】
他の一実施形態によると、ブロックに入るエッジのアクセスカウントに含まれる、エッジカウントが予め決定した値以上である場合、ブロックを重要ブロックとして判断するステップは、アクセスカウントに応じてブロックからスーパーブロックを形成するステップを含むパイプラインでブロックをスケジュールするコンパイル方法が提供されてもよい。
【００１１】
他の一実施形態によると、レジスタライトバックコンフリクトが防止されるように重要ブロックをアクセスカウントに応じてスケジュールするステップは、重要ブロックでレジスタライトバックコンフリクトが予想されるサイクルにライトバックの実行されないオペレーションをスケジュールするステップを含むパイプラインでブロックをスケジュールするコンパイル方法が提供されてもよい。
【００１２】
他の一実施形態によると、重要ブロックでレジスタライトバックコンフリクトが予想されるサイクルにライトバックの実行されないオペレーションをスケジュールするステップは、レジスタライトバックコンフリクトが予想されるサイクルにＮＯＰ（Ｎｏ  ＯＰｅｒａｔｉｏｎ）をスケジュールするステップを含むパイプラインでブロックをスケジュールするコンパイル方法が提供されてもよい。
【００１３】
他の一実施形態によると、重要ブロックでレジスタライトバックコンフリクトが予想されるサイクルにライトバックの実行されないオペレーションをスケジュールするステップは、レジスタライトバックコンフリクトが予想されるサイクルに格納オペレーションをスケジュールするステップを含むパイプラインでブロックをスケジュールするコンパイル方法が提供されてもよい。
【００１４】
他の一実施形態によると、レジスタライトバックコンフリクトが防止されるように重要ブロックをアクセスカウントに応じてスケジュールするステップは、重要ブロック内部または重要ブロックとエッジによって接続されるブロックでライトバックが行われるように重要ブロックのオペレーションをスケジュールするステップを含むパイプラインでブロックをスケジュールするコンパイル方法が提供されてもよい。
【００１５】
他の一実施形態によると、重要ブロックとして判断されていない非重要ブロックでライトバックを無視してスケジュールするステップを含むパイプラインでブロックをスケジュールするコンパイル方法が提供されてもよい。
【００１６】
他の一実施形態によると、重要ブロックとして判断されていない非重要ブロックでライトバックを無視してスケジュールするステップは、非重要ブロックでレジスタライトバックコンフリクトが予想されるサイクルにハードウェア的にストールサイクルを適用するステップを含むパイプラインでブロックをスケジュールするコンパイル方法が提供されてもよい。
【００１７】
他の一実施形態によると、重要ブロックとして判断されていない非重要ブロックは、すでにスケジュールされたブロックに出て行くエッジがある場合、非重要ブロック内でオペレーションのライトバックが行われるようにスケジュールするステップを含むパイプラインでブロックをスケジュールするコンパイル方法が提供されてもよい。
【００１８】
一実施形態によると、プログラムコードによる制御流れのブロックに対するアクセスカウントをプロファイルするブロックプロファイル部と、ブロックに入るエッジのアクセスカウントに含まれるエッジカウントが予め決定した値以上である場合、ブロックを重要ブロックとして判断するブロック判断部と、レジスタライトバックコンフリクトが防止されるように重要ブロックをアクセスカウントに応じてスケジュールするブロックスケジュール部とを備えるパイプラインでブロックをスケジュールするコンパイル装置が提供される。
【００１９】
他の一実施形態によると、アクセスカウントに応じてブロックからスーパーブロックを形成するスーパーブロック形成部を備え、ブロックスケジュール部は、アクセスカウントによる優先順位でブロック及びスーパーブロックを整列して整列した順序に応じて順次ブロック及びスーパーブロックをスケジュールするパイプラインでブロックをスケジュールするコンパイル装置が提供されてもよい。
【００２０】
他の一実施形態によると、ブロック判断部は、ブロックでエッジカウントが予め決定した重要限界値以上であるエッジを重要エッジとしてマークし、スケジュールされないブロックから入る重要エッジをノーマルエッジとしてマークするエッジマーク部を備え、重要エッジが入るブロックを重要ブロックとして判断するパイプラインでブロックをスケジュールするコンパイル装置が提供されてもよい。
【００２１】
他の一実施形態によると、ブロックスケジュール部は、重要ブロックでレジスタライトバックコンフリクトが予想されるサイクルにライトバックの実行されないオペレーションをスケジュールし、重要ブロックとして判断されていない非重要ブロックですでにスケジュールされたブロックに出て行くエッジがある場合、非重要ブロック内でオペレーションのライトバックが行われるようにスケジュールするパイプラインでブロックをスケジュールするコンパイル装置が提供されてもよい。
【００２２】
他の一実施形態によると、重要ブロックとして判断されていないブロックでレジスタライトバックコンフリクトが予想されるサイクルにストールサイクルを適用するストール適用部を備えるパイプラインでブロックをスケジュールするコンパイル装置が提供されてもよい。
【００２３】
一実施形態に係る方法を行うようにする命令語を含む１つ以上のプログラムを格納したコンピュータで読み出し可能な格納媒体が提供される。
【００２４】
一実施形態によると、パイプラインでブロックをスケジューリングするコンパイル方法において、プロセッサを用いてブロックが重要ブロックであるかブロックのアクセスカウントを用いて判断するステップと、ブロックを重要ブロックとして判断した場合、ブロックでレジスタライトバックコンフリクトが発生することを防止するようにブロックをスケジューリングするステップとを含む方法が提供される。
【００２５】
他の一実施形態によると、ブロックのアクセスカウントは、少なくとも１つの動作命令の結果としてコンパイルされたプログラムコードの総アクセス数に対するブロックの使用回数の比率である方法が提供されてもよい。
【００２６】
他の一実施形態によると、ブロックを非重要ブロックとして判断した場合、ブロックでレジスタライトバックコンフリクトの発生を許容するようにブロックをスケジューリングするステップをさらに含む方法が提供されてもよい。
【００２７】
他の一実施形態によると、ブロックにレジスタライトバックコンフリクトの発生を許容するようにブロックをスケジューリングする場合、ブロックがレジスタライトバックコンフリクトを発生すると予測されるかを判断し、ブロックがレジスタライトバックコンフリクトを発生させるものとして予測されると判断された場合、ストールサイクルを適用するステップをさらに含む方法が提供されてもよい。
【００２８】
一実施形態によると、パイプラインでブロックをスケジューリングするコンパイル装置において、ブロックが重要または非重要であるかブロックに入るエッジのエッジカウントを予め決定した値と比較して判断するブロック判断部と、ブロックが重要である場合、ブロックでレジスタライトバックコンフリクト発生を防止するようにブロックがスケジューリングされ、ブロックが非重要である場合、ブロックでレジスタライトバックコンフリクト発生を許容するようにブロックがスケジューリングされるようブロックをスケジューリングするブロックスケジューリング部とを備えるコンパイル装置が提供される。
【００２９】
他の一実施形態によると、ブロックスケジューリング部は、ブロックが重要ではない場合、ブロックがレジスタライトバックコンフリクトを発生させると予測されるかを判断し、ブロックがレジスタライトバックコンフリクトを発生させるものと予測されると判断した場合、レジスタライトバックコンフリクトが予測されるサイクルにストールサイクルを適用するコンパイル装置が提供されてもよい。
【発明の効果】
【００３０】
本発明によると、一実施形態に係るパイプラインでブロックをスケジュールするコンパイル装置は、レジスタライトバックが基本ブロックの境界を越えるようにオペレーションをスケジュールしてパフォーマンスを向上させることができる。また、プロファイル結果のエッジカウントから判断された重要ブロックをストールが発生しないようにスケジュールして性能を極大化し、非重要ブロックについてはストールサイクルを適用してコードサイズを最小化することができる。そして、アクセスカウントによる優先順位で整列されたブロックをスケジュールすることにより、バックトラッキングをなくしコンパイル時間を最小化することができる。
【図面の簡単な説明】
【００３１】
【図１】パイプラインで待ち時間が同一であるか、他のオペレーションにより発生するライトバックの状況を示す図である。
【図２】パイプラインでレジスタライトバックコンフリクトに対してストールサイクルを適用した状況を示す図である。
【図３】パイプラインでレジスタライトバックコンフリクトに対してＮＯＰ（Ｎｏ  ＯＰｅｒａｔｉｏｎ）を適用した状況を示す図である。
【図４】スーパーブロックにスペキュレーションが適用された制御流れを示す図である。
【図５】パイプラインで基本ブロックにＮＯＰが適用された制御流れを示す図である。
【図６】一実施形態に係るパイプラインでブロックをスケジュールするコンパイル方法を示すフローチャートである。
【図７】一実施形態に係るプログラムコードがプロファイルされた制御流れを示す図である。
【図８】一実施形態に係るプロファイルの結果に応じてスーパーブロックが形成された制御流れを示す図である。
【図９】一実施形態に係るプロファイルの結果に応じてブロックが整列された制御流れを示す図である。
【図１０】一実施形態に係るプロファイルの結果に応じて重要エッジがマークされた制御流れを示す図である。
【図１１】一実施形態に係る重要エッジが入るブロックがスケジュールされた制御流れを示す図である。
【図１２】一実施形態に係る重要エッジを考慮してブロックがスケジュールされた制御流れを示す図である。
【図１３】一実施形態に係るブロックが整列した順序に応じて順次スケジュールされた制御流れを示す図である。
【図１４】一実施形態に係るパイプラインでブロックをスケジューリングするためのコンパイラ装置を示す図である。
【発明を実施するための形態】
【００３２】
本明細書で全般的に用いられる用語は次のように示してもよい。
【００３３】
パイプラインは、１つのプロセッサを互いに異なる機能を有する数個のサブプロセッサに分けて各サブプロセッサが同時に他のデータを処理するようシステムを設計する方式である。ここで、１つの命令語が数段階を経てオペレーションを完了するために所要される時間を待ち時間といい、各ステップに所要する時間をサイクルという。
【００３４】
制御流れ又は制御フローは、プロセス処理をするための入出力装置の指定、使用プログラムの名称などをハードウェアと接続する一種の制御カードグループとして、フローチャートに表現して１つのプログラム実行順序におけるすべての可能な経路を抽象化したものである。
【００３５】
制御流れに示す略語のうち、それぞれｄｉｖはｄｉｖｉｓｉｏｎとして割り算オペレーション、ｍｕｌはｍｕｌｔｉｐｌｉｃａｔｉｏｎとして掛け算オペレーション、ａｄｄはたし算オペレーション、ｓｕｂはｓｕｂｔｒａｃｔｉｏｎとして引き算オペレーション、ｓｈｉｆｔはレジスタでビット値を左側や右側に移動させる演算オペレーション、ｊｕｍｐは条件なしでループを繰り返すオペレーション、ｂｒａｎｃｈは条件に応じてループを繰り返すオペレーション、ｌｏａｄはメモリから値を呼び出すオペレーション、ｎｏｐまたはＮＯＰはＮｏ  ＯＰｅｒａｔｉｏｎを意味する。ここで、各略語の右側に記載の数字はブロックに指定された番号として、例えば、ａｄｄ３は第３ブロックでたし算オペレーションするものとして示される。
【００３６】
ここで、制御流れは、プログラムコードによる複数のブロックを示し、それぞれのブロックで行方向はオペレーションが実行されるサイクル順序を示すものである。例えば、図４に示す最初のブロック４９１でｄｉｖ１が最初に実行され、４サイクルのｎｏｐ以後にｂｒａｎｃｈが実行される。一実施形態によると、プログラムコードは、Ｃ、Ｃ＋＋、ＪＡＶＡ（登録商標）などの言語がコンパイラ内で変換されたＩＲコードを含んでもよい。例えば、コンパイラはプロセッサによって高級言語を機械語に変換してもよい。
【００３７】
図１は、パイプラインで待ち時間が異なるオペレーションにより発生するレジスタライトバックコンフリクト（ｒｅｇｉｓｔｅｒ  ｗｒｉｔｅ−ｂａｃｋ  ｃｏｎｆｌｉｃｔ）の状況を示す図である。ここで、図１（ａ）及び図１（ｂ）は、一実施形態によりパイプラインで同一の又は異なる待ち時間を有する各オペレーションに起因して発生するライトバックを示している。
【００３８】
ここで、図１に示された略語のうち、それぞれＩＦ（Ｉｎｓｔｒｕｃｔｉｏｎ  Ｆｅｔｃｈ）は、プロセッサが命令語の実行を終わらせて次に実行される命令語を記憶装置から取り出すまでのオペレーション、ＩＤ（Ｉｎｓｔｒｕｃｔｉｏｎ  Ｄｅｃｏｄｅ）は、命令語の実行のために命令語を記憶装置から読み出した後に命令語の種類を判断するオペレーション、ＥＸ（ＥＸｅｃｕｔｉｏｎ）は、ＩＤで判断された種類により命令語を実行するオペレーション、ＷＢは、オペレーションにより磁気ディスクなどに記録するデータを一時的にレジスタに格納するオペレーションである。
【００３９】
以下、図１（ａ）及び図１（ｂ）に示す横軸はサイクル、縦軸はオペレーションを示す。
【００４０】
図１（ａ）に示すように、オペレーション待ち時間を同一にして各オペレーションのＷＢがそれぞれ異なるサイクルに行われるようにしてもよい。ここで、各オペレーションに付与される同じ待ち時間は、最も長い待ち時間を有するオペレーションの待ち時間を基準としてもよい。ただし、短い待ち時間を有するオペレーションは、結果が出てもレジスタライトバックが不可能な場合が生じ得る。したがって、データフォワーディングが必要であるものの、ＶＬＩＷ（Ｖｅｒｙ  Ｌｏｎｇ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｗｏｒｄ）では多くのイシュー幅、最近のプロセッサでは高いクロック周波数と長いパイプラインによりデータフォワーディングできない場合もある。
【００４１】
図１（ｂ）は、待ち時間が異なる各オペレーションが同一のサイクルにＷＢ１０１が発生した場合を示す。例えば、図１Ｂに示すように、第１オペレーションｏｐ１及び第２オペレーションｏｐ２はそれぞれＩＦからＷＢまで必要とされるサイクルが４サイクル及び３サイクルとして異なり、サイクル１に第１オペレーション、サイクル２に第２オペレーションが実行される場合、サイクル５に第１オペレーション及び第２オペレーションのＷＢが行われることになる。したがって、異なるオペレーションが同時にレジスタに書き込むレジスタライトバックコンフリクトが発生する。
【００４２】
ここで、レジスタライトバックコンフリクトは、上述した図１（ａ）のように複雑なフォワーディングロジックを用いて同じ待ち時間を同一にするか、ハードウェア的な方式としてレジスタライトバッファ、または下記の図２に示すようにパイプラインストールを適用して防止することができる。ソフトウェア的な方式として、図３〜図５に示すようにブロックをスケジュールして防止できる。
【００４３】
図２は、パイプラインでレジスタライトバックコンフリクトに対してストールサイクルを適用した状況を示す図である。図１と類似に、横軸はサイクル、縦軸は各オペレーションを示す。
【００４４】
ここで、レジスタライトバックコンフリクトが発生したときパイプラインをストールし、そのうちの１つを先ずライトバックしながら、続いてストールを解いて残りのレジスタを書き込んでもよい。例えば、図２に示すように、第１オペレーション及び第２オペレーションでレジスタライトバックコンフリクトが発生することがあり、サイクル５に第２オペレーションないし第５オペレーションにストールサイクル２０１を適用してもよい。このようなパイプラインストール方式は、全体のパイプラインを中止するため頻繁に発生することになると性能が低下してしまう恐れがある。
【００４５】
上述した図２に示すストールサイクルの適用とは異なるハードウェア方式として、レジスタライトバッファを用いてもよい。具体的に、レジスタライトバックコンフリクトが発生すると、そのうちの１つをレジスタライトバッファに置き、次のサイクルに書き込んでもよい。この場合、次のサイクルに再びレジスタライトバックコンフリクトが発生すると回避できず、待ち時間が１だけ差のあるパイプラインにのみ適用され、最近の長い待ち時間と短い待ち時間が共存する場合には適用し難いこともある。
【００４６】
図３は、一実施形態に係るパイプラインでレジスタライトバックコンフリクトに対してＮＯＰ（Ｎｏ  ＯＰｅｒａｔｉｏｎ）３０２を適用した状況を示す図である。ここで、ソフトウェア方式の１つであるオペレーションスケジューリングによってレジスタライトバックコンフリクトを予め認知し、レジスタライトバックコンフリクトが発生しないようスケジュールしてもよい。
【００４７】
具体的に、スケジュールしたいサイクルにすでに他のレジスタが書き込んでいると、レジスタを書き込む作業の必要ないオペレーションをスケジュールしてもよい。例えば、レジスタ書き込みが必要でないオペレーションは、格納またはＮＯＰ３０２を含んでもよい。例えば、図３に示すように、第１オペレーションと第２オペレーションがサイクル５にレジスタライトバックコンフリクトが発生し、ストールサイクル３０１が必要なこともある。図３では、ストールサイクルを適用する代わりに、ＮＯＰ３０２を適用したものである。ここで、スケジュールに誤りが発生する場合、多くのＮＯＰ３０２が追加されてその性能が低下する場合がある。
【００４８】
図４は、スーパーブロックにスペキュレーション（ｓｐｅｃｕｌａｔｉｏｎ）が適用された制御流れを示す図である。ここで、図３とは異なって、ソフトウェア方式として、グローバルスケジューリング（ｇｌｏｂａｌ  ｓｃｈｅｄｕｌｉｎｇ）を考慮してもよい。グローバルスケジューリングは、オペレーションスケジューリングを基本ブロック（ＢＢ：Ｂａｓｉｃ  Ｂｌｏｃｋ）内で行うものではなく、複数の基本ブロックを集めて共にスケジュールしてもよい。例えば、スーパーブロックは、グローバルスケジューリングの代表的な方式として、ブロック間にインエッジ（ｉｎ−ｅｄｇｅ）がなくアウトエッジ（ｏｕｔ−ｅｄｇｅ）のみがある。ここで、エッジは、アクセスによりオペレーションがこのブロックから他のブロックへ行く方向を意味する。例えば、オペレーションの順序である。
【００４９】
このようなブロックをスケジュールするとき、普通はレジスタライトバックを考慮せずに同じ長さ待ち時間を用いるか、そうでなければ、レジスタライトバックが基本ブロック内で終わるようにスケジュールしてもよい。この場合、レジスタライトバックコンフリクトによって性能が低下することがある。より詳しくは、アクセスは、コンパイルされたプログラムコードに対する付加的な動作命令を通したシミュレーションを行う過程で付加的な動作命令を行うため各ブロックを通過するものと理解されてもよい。
【００５０】
例えば、図４（ａ）に示すように、最初のブロック４９１及び２番目のブロック４９２がスーパーブロック４１０として第１ブロックを形成してもよく、プログラムコードにより第２ブロック、第３ブロック、第４ブロックが制御流れ上に示されてもよい。第１ブロック４１０の２番目のブロック４９２のｍｕｌ１オペレーションがスペキュレーション４９０によって最初のブロック４９１にスケジュールされてもよい。図４（ｂ）に示すように、スケジュールされたｍｕｌ１オペレーションにより第１ブロック４１０の最初のブロック４９１及び２番目のブロック４９２でｎｏｐが減少する。
【００５１】
図５は、パイプラインで基本ブロックにＮＯＰが適用された制御流れを示す図である。ここで、第１ブロック５１０は、最初のブロック５９１及び２番目のブロック５９２から形成されるスーパーブロックであってもよく、第１ブロック５１０で各オペレーションのライトバックが発生するサイクル５１３は、第１ブロック５１０の右側に点線のように図示される。ここで、第１ブロック５１０で各オペレーションが実行され、１ないし２サイクルの後が右側に点線のように図示されるライトバックが現れるサイクル５１３であってもよい。
【００５２】
一実施形態によると、上述した第１ブロック５１０と類似に、第２ブロック５２０の各オペレーションのライトバックが発生するサイクル５２３、第３ブロック５３０の各オペレーションのライトバックが発生するサイクル５３３、第４ブロック５４０の各オペレーションのライトバックが発生するサイクル５４３が図示される。
【００５３】
図５は、スーパーブロック及び基本ブロック内のみで各オペレーションがスケジュールされたものとして、オペレーションがブロックの内部で終了するように複数のｎｏｐが各ブロックに発生してシステムの性能が低下することがある。
【００５４】
以下、実施形態を添付する図面を参照しながら詳細に説明する。
【００５５】
図６は、一実施形態に係るパイプラインでブロックをスケジュールするコンパイル方法を示すフローチャートである。
【００５６】
ステップＳ６１０において、コンパイラがプログラムコードをプロファイルする。具体的に、プログラムコードによる制御流れでブロックに対するアクセスカウントをプロファイルしてもよい。ここで、アクセスカウントをプロファイルして又は求めて、各ブロックのエッジカウントを算出してもよい。例えば、エッジカウントは、各ブロックに入るエッジのインエッジをシミュレーションによりカウントしたものである。アウトエッジは、各ブロックから他のブロックに出て行くエッジを意味する。エッジは、プログラムコードに対するシミュレーションを行う過程で動作されるために通過する付加的な動作命令を通したブロック間の経路であると理解されてもよい。さらに、エッジカウントは、動作命令の予め決定した回数が与えられた場合、総アクセス回数（予め決定した回数）との関係で対応経路の使用比率または対応経路の使用比率であると考慮されてもよい。
【００５７】
一実施形態によると、アクセスカウント及びエッジカウントは、一定回数の全体アクセスをプログラムコードに対して与えるシミュレーションによって算出されてもよい。例えば、アクセスカウント及びエッジカウントは、全体アクセス回数対比ブロックに対するアクセス及びエッジの比率として示されてもよい。したがって、エッジカウントは、少なくとも１つの動作命令をシミュレーションした結果として、コンパイルされたプログラムコードに対する総アクセス回数に対するブロックの使用回数の比率、または、各ブロックの使用回数の比率として理解されてもよい。また、アクセスカウントは、エッジカウントの総和であると考慮されてもよい。
【００５８】
そして、ステップＳ６２０において、コンパイラがアクセスカウントに応じてスーパーブロックを形成する。具体的に、アクセスカウントに応じて少なくとも２以上のブロックをグルーピングしてスーパーブロックを形成してもよい。一実施形態によると、少なくとも２以上のブロックの各アクセスカウントが多くてエッジに互いに接続される場合、スーパーブロックを形成してもよい。
【００５９】
続いて、ステップＳ６３０において、コンパイラがアクセスカウントによる優先順位でブロックを整列する。ここで、全体アクセス対比アクセスカウントの比率が高いブロックであるほどはやい優先順位を有する。一実施形態によると、スーパーブロックで形成されるブロックが最も高いアクセスカウントを有するため、最優先順位で整列されてもよい。
【００６０】
そして、ステップＳ６４０において、コンパイラがエッジカウントが予め決定した重要限界値よりも高いかを判断する。ここで、予め決定した重要限界値は、プログラムコードをコンパイルするときユーザによって任意に定められてもよい。一実施形態によると、エッジカウントに対して予め決定した重要限界値は１０％であってもよいが、これに限定されることはない。すなわち、１０％は単なる例示に過ぎず、ユーザによって任意的に設定されたエッジカウントに対して予め決定した重要限界値に限定することはない。
【００６１】
続いて、ステップＳ６５０において、コンパイラは、エッジカウントが予め決定した重要限界値以上であるエッジを重要エッジとしてマークする。ここで、重要エッジとしてマークされた場合でも、重要エッジをインエッジとして受けるブロックが重要エッジをアウトエッジとして送りだすブロックよりも早い優先順位を有する場合、当該エッジをノーマルエッジとしてマークしてもよい。例えば、重要エッジがまだスケジュールされないブロックから出た場合、当該の重要エッジをノーマルエッジとしてマークしてもよい。
【００６２】
そして、ステップＳ６６０において、コンパイラが重要ブロックをアクセスカウントによって整列した順序に応じてスケジュールする。具体的に、アクセスカウントによる優先順位でブロック及びスーパーブロックを整列し、優先順位で整列した順序に応じて順次ブロックをスケジュールしてもよい。ここで、重要エッジに伝えられるレジスタライトバックは基本ブロックを渡ってスケジュールされてもよい。または、システム複雑性を低くするために基本ブロック内でライトバックが完了するようにスケジュールしてもよい。
【００６３】
関連技術分野において、基本ブロックで動作をスケジューリングすることは基本ブロックにＮＯＰを追加することで完了される。したがって、追加されたＮＯＰによりサイクルが増加されることで、全体の実行時間が長くなり得る。これとは異なって、図示するように基本ブロックを渡って動作をスケジューリングしてもよい。したがって、動作は、関連する技術分野よりも短い実行時間を示すように、基本ブロックに最小限のＮＯＰを追加することで他の基本ブロックで動作が完了される。図５及び図１３（ａ）で追加されたＮＯＰの個数による差から理解される。言い換えれば、基本ブロックを渡ってスケジューリングする場合、基本ブロック内でスケジューリングする場合に比べて少ないＮＯＰが追加される。また、このような特徴は、図５に示すスーパーブロック５１０及び図１３に示すスーパーブロック間の比較に基づいて理解される。
【００６４】
続いて、重要ブロックではない非重要ブロックについてはライトバックを無視してスケジュールしてもよい。具体的に、非重要ブロックでレジスタライトバックコンフリクトが予想されるサイクルにストールサイクルを適用し、その後、オペレーションしたサイクルずつ遅延させてもよい。一実施形態によると、非重要ブロックは、アクセスカウントが低くて実行される確率が低いことから、性能に及ぼす影響を小さくすることができる。
【００６５】
上述した各ステップは、以下の図７ないし図１３を参照して詳細に説明する。
【００６６】
図７は、一実施形態に係るプログラムコードがプロファイルされた制御流れを示す図である。ここで、上述した図６に示すステップＳ６１０が詳細に説明されてもよい。具体的に、プログラムコードによる制御流れの各ブロック７９１、７９２、７２０、７３０、７４０が図示される。
【００６７】
一実施形態によると、図７（ａ）は、各ブロックに対するプロファイルが行われず、まだエッジカウントが算出されていない状態である。図７（ｂ）は、各ブロックに対するプロファイルが行われ、全体アクセスに対するシミュレーションを介してエッジカウントが算出された状態である。例えば、第１ブロックの最初のブロック７９１に入るエッジ７６１は８５％、第１ブロックの２番目のブロック７９２に入るエッジ７１１は８０％、第１ブロックの最初のブロック７９１から第２ブロック７２０に入るエッジ７１２は５％、第２ブロック７２０に入るエッジ７６２は１０％、第３ブロック７３０に入るエッジ７６３は５％、第３ブロック７３０から第２ブロック７２０に入るエッジ７３２は２％、第３ブロック７３０から第４ブロック７４０に入るエッジ７３４は３％に、エッジカウントが算出されたと仮定する。
【００６８】
図８は、一実施形態に係るプロファイルの結果に応じてスーパーブロックが形成された制御流れを示す図である。ここで、図６に示すステップＳ６２０が詳細に説明される。各ブロック８９１、８９２、８１０、８２０、８３０、８４０のエッジカウント及びエッジカウントの和で算出されるアクセスカウントは上述した図７に示すとおりである。
【００６９】
一実施形態によると、図８（ａ）に示すように、第１ブロック８１０の最初のブロック８９１に入るエッジ８６１と、第１ブロック８１０の２番目のブロック８９２に入るエッジ８１１に対するエッジカウントはそれぞれ８５％と８０％である。ここで、図８（ｂ）に示すように、アクセスカウントが多い、例えば、一定値以上である最初のブロック８９１及び２番目のブロック８９２をグルーピングして第１ブロック８１０をスーパーブロックとして形成してもよい。
【００７０】
図９は、一実施形態に係るプロファイルの結果に応じてブロックが整列された制御流れを示す図である。ここで、上述した図６に示すステップＳ６３０が詳細に説明される。例えば、各ブロックに対するアクセスカウント及び各ブロックのエッジに対するエッジカウントは上述した図７に示すとおりである。
【００７１】
具体的に、図９（ａ）に示す各ブロックを図９（ｂ）に示すように、アクセスカウントが８５％で最も高い第１ブロック９１０を最優先順位ブロック９６０、１７％として次に高い第２ブロック９２０を次の優先順位ブロック９７０、５％としてその次に高い第３ブロック９３０をその次優先順位ブロック９８０、そして、３％である第４ブロック９４０を最後の優先順位ブロック９９０に整列してもよい。
【００７２】
図１０は、一実施形態に係るプロファイルの結果に応じて重要エッジがマークされた制御流れを示す図である。ここで、上述した図６のステップＳ６４０、６５０が詳細に説明されている。
【００７３】
一実施形態によると、図１０（ａ）に示すような各ブロックのエッジ１０６１、１０６２、１０６３、１０１１、１０１２、１０３２、１０３４のうち予め決定した重要限界値以上であるエッジを重要エッジとしてマークしてもよい。例えば、重要限界値がコンパイルするときユーザによって１０％と設定されると仮定すると、図１０（ｂ）に示すように、エッジのうちエッジカウントが８５％である第１ブロックに入る重要エッジ１００１、８０％である第１ブロック内部の重要エッジ１００２、１０％である第２ブロックに入る重要エッジ１００３をマークしてもよい。
【００７４】
図１１は、一実施形態に係る重要エッジが入るブロックがスケジュールされた制御流れを示す図である。ここで、上述した図６のステップＳ６６０で最優先順位ブロック１１６０をスケジュールしてもよい。
【００７５】
一実施形態によると、第１ブロック１１１０で最初のブロック１１１１と２番目のブロック１１１２の右側に点線のように表示された部分１１１３は、実行されたオペレーションのライトバックが発生するサイクル順序を示すものである。例えば、最優先順位ブロック１１６０の第１ブロック１１１０で各オペレーションが実行が完了するために必要とされる待ち時間はｄｉｖ１が６サイクル、ｍｕｌ１が２サイクル、ｌｏａｄ１が５サイクルであってもよい。ここで、ライトバックは、各オペレーションの実行が完了した後１ないし２サイクルの後で発生するが、同じシステムでは同じサイクルであってもよい。
【００７６】
具体的に、図１１（ａ）に示すように、マークされた重要エッジ１１０１、１１０２が入る最優先順位ブロック１１６０は重要ブロックである。重要ブロックは、レジスタライトバックコンフリクトが予想されるサイクルにライトバックの実行されないオペレーションをスケジュールしてもよく、各オペレーションは、基本ブロックの向かい側または基本ブロック内でライトバックが完了するようにスケジュールしてもよい。ここで、ライトバックの実行されないオペレーションは、ＮＯＰ（Ｎｏ  ＯＰｅｒａｔｉｏｎ）または格納オペレーションを含んでもよい。
【００７７】
例えば、図１１（ｂ）に示すように、各オペレーションがスケジュールされてもよい。スーパーブロックで形成された第１ブロック１１１０の最初のブロック１１１１でｄｉｖ１が実行され、次のサイクルにｍｕｌ１が実行されてもよい。ここで、ｍｕｌ１は待ち時間が２サイクルであるため、図１１（ｂ）に示すようにライトバックが発生する。
【００７８】
続いて、第１ブロック１１１０の２番目のブロック１１１２でｌｏａｄ１の待ち時間が５サイクルであるため、３つのｎｏｐをスケジュールしてスーパーブロック内でｌｏａｄ１のライトバックが完了するようにスケジュールしてもよい。
【００７９】
そして、ｄｉｖ１は、上述した図７で算出されたエッジカウントに応じて８０％の確率で２番目のブロック１１１２に伝えられる。一実施形態によると、ｄｉｖ１の待ち時間は６サイクルであるため、ライトバックがないｎｏｐがスケジュールされてレジスタライトバックコンフリクトが防止される。ここで、ｄｉｖ１は、図７に示すエッジカウントに応じて５％の確率で第２ブロックに伝えられるところ、下記の図１２を参照して詳細に説明する。
【００８０】
図１２は、一実施形態に係る重要エッジを考慮してブロックがスケジュールされた制御流れを示す図である。ここで、上述した図６のステップＳ６６０で次の優先順位ブロック１２７０をスケジュールしてもよい。
【００８１】
図１２（ａ）に示すように、次の優先順位ブロック１２７０は、第１ブロック１２１０からのエッジ、第５ブロック１２５０からのエッジ１２５２、及びその次優先順位ブロック１２８０からのエッジが重要エッジであるか否かを考慮する。
【００８２】
ここで、第５ブロック１２５０からのエッジ１２５２は図７に示すように重要エッジであるが、第５ブロック１２５０がまだスケジュールされていない状態であるためスケジュールに使用し難い。したがって、相対的に重要性が落ちるため第５ブロック１２５０からのエッジ１２５２はエッジカウントが予め決定した重要限界値以上であるにもかかわらずノーマルエッジとしてマークする。例えば、当該エッジ１２５２がノーマルエッジであり、残りのエッジはエッジカウントが重要閾値以下として重要エッジではないため、次の優先順位ブロック１２７０は非重要ブロックとしてライトバックを無視してスケジュールされてもよい。
【００８３】
一実施形態によると、第２ブロック１２２０で右側点線で表示した部分１２２３は、実行されたオペレーションのライトバックが発生するサイクル順序を示すものである。例えば、次の優先順位で整列されたブロック１２７０で各オペレーションの待ち時間はｌｏａｄ２が５サイクル、ｓｈｉｆｔ２が１サイクル、ａｄｄ２が１サイクル、ｓｕｂ２が１サイクルである。
【００８４】
具体的に、第２ブロックは、図１２（ｂ）に示すように、重要エッジがノーマルエッジとしてマークされて非重要ブロックであるためライトバックを無視し、スケジュールした後ハードウェア方式でレジスタライトバックコンフリクトを防止することができる。
【００８５】
例えば、第２ブロックでｌｏａｄ２は、待ち時間が５サイクルであるため図１２（ｂ）に示すサイクルにライトバックされてもよい。ここで、ライトバックは、ｌｏａｄ２の実行が完了した後１ないし２サイクル後で発生する。続いて、ｓｈｉｆｔ２、ａｄｄ２、ｓｕｂ２はそれぞれ待ち時間が１サイクルであるため、直ちにライトバックされる。
【００８６】
図１１において、上述したように第１ブロックから伝えられたｄｉｖ１の待ち時間が６サイクルであるため、ａｄｄ２のようなサイクルにライトバックが発生する。この場合、ｄｉｖ１がａｄｄ２のようなサイクルにライトバックが発生する確率は図７に示すように５％に過ぎないことから、ハードウェア的にストールサイクルを適用してもよい。一実施形態によると、全体的な性能に大きい影響を及ぼすことなく、コードサイズの増加を抑えることができる。
【００８７】
図１３は、一実施形態に係るブロックが整列した順序に応じて順次スケジュールされた制御流れを示す図である。ここで、上述した図６のステップＳ６６０で整列された残りのブロック１３８０、１３９０が重要ブロックとして判断されるとスケジュールする。
【００８８】
一実施形態によると、図１３（ｂ）に示すように、実線で囲まれた命令は動作を実行するシーケンスを示し、各ブロック１３２０、１３３０、１３４０の右側に示す点線部分１３２３、１３３３、１３４３は、第３ブロック１３３０及び第４ブロック１３４０で実行されたオペレーションがライトバックされるサイクル順序を示す。例えば、各オペレーションの待ち時間はｌｏａｄ３及びｌｏａｄ４が５サイクル、ａｄｄ３が１サイクルであってもよい。また、命令が重なった命令、例えば、ｓｈｉｆｔ２及びｌｏａｄ３は同じサイクルに重なった命令のレジスタライトバックコンフリクトが発生することを示す。
【００８９】
具体的に、その次優先順位ブロック１３８０は、入るエッジのうち重要エッジがなくて非重要ブロックであってもよい。最後の優先順位ブロック１３９０は入る重要エッジがないが、出て行くエッジがあり、当該のエッジを受けるブロックがまだスケジュールさていないと仮定する。この場合、最後の優先順位ブロック１３９０の次のブロックがスケジュールさていないため状態を考慮することができず、最後の優先順位ブロック１３９０の各オペレーションが基本ブロック内でライトバックが完了するように重要ブロックと類似にスケジュールしてもよい。
【００９０】
例えば、その次優先順位ブロック１３８０でｌｏａｄ３は、図７に示すエッジカウントに応じて２％の確率で第２ブロック１３２０、３％の確率で第４ブロック１３４０に伝えられてもよい。第２ブロックでｓｈｉｆｔ２のようなサイクルにライトバックが発生１３２３することもあるが、その確率は低いことから、ストールサイクルを適用してレジスタライトバックコンフリクトを防止することができる。ａｄｄ３は、待ち時間が１サイクルであるため、直ちにライトバックが発生する。
【００９１】
そして、第４ブロック１３４０でｌｏａｄ４は待ち時間が５サイクルであるため、３つのｎｏｐをスケジュールしてｌｏａｄ４のライトバックが図１３（ｂ）に示すように、基本ブロック内で発生するようにしてもよい。ここで、第３ブロック１３３０から伝えられたｌｏａｄ３は、図７に示されたエッジカウントに応じて３％の確率でライトバックのないｎｏｐサイクルにライトバックが発生する。
【００９２】
一実施形態によると、合わせて１００回アクセスする場合、図５に示す方法は１０３５サイクルを実行し、図１３に示す方法では７７０サイクルと７ストールサイクルが発生し、合わせて７７７サイクルを実行する。例えば、総２４％の実行時間が節減され、コードサイズは図５に示す方法が２６命令である一方、提案する発明では２１命令であるため、合わせて１９％が減少した。
【００９３】
一実施形態によると、図１４に示すように、パイプラインでブロックをスケジュールするコンパイル装置は、ブロックプロファイル部１４１０、ブロック判断部１４２０、ブロックスケジュール部１４３０、スーパーブロック形成部１４４０、ストール適用部１４５０を備える。
【００９４】
ブロックプロファイル部１４１０は、プログラムコードによる制御流れのブロックに対するアクセスカウントをプロファイルする。ここで、ブロックに対するアクセスカウントは、シミュレーションにより得られるエッジカウントを算出してプロファイルされる。
【００９５】
ブロック判断部１４２０は、ブロックでエッジカウントを含むアクセスカウントが予め決定した値以上であるブロックを重要ブロックとして判断する。具体的に、ブロック判断部１４２０は、ブロックでエッジカウントが予め決定した重要限界値以上であるエッジを重要エッジとしてマークし、スケジュールされないブロックから入る重要エッジをノーマルエッジとしてマークするエッジマーク部１４２５を備え、ブロック判断部１４２０は、重要エッジが入るブロックを重要ブロックとして判断する。
【００９６】
ブロックスケジュール部１４３０は、重要ブロックをアクセスカウントに応じてスケジュールしてもよい。具体的に、ブロックスケジュール部１４３０は、重要ブロックでレジスタライトバックコンフリクトが予想されるサイクルにライトバックの実行されないオペレーションをスケジュールし、重要ブロックと判断されていない非重要ブロックですでにスケジュールされたブロックに出て行くエッジがある場合、非重要ブロック内でライトバックが行われるようにスケジュールしてもよい。
【００９７】
一実施形態によると、ブロックスケジュール部１４３０は、アクセスカウントによる優先順位でブロック及びスーパーブロックを整列し、整列された順序に応じて順次ブロック及びスーパーブロックをスケジュールしてもよい。
【００９８】
スーパーブロック形成部１４４０は、アクセスカウントに応じてブロックからスーパーブロックを形成する。例えば、スーパーブロック形成部１４４０は、アクセスカウントが多いエッジに接続される少なくとも２つ以上のブロックをグルーピングしてスーパーブロックを形成してもよい。
【００９９】
ストール適用部１４５０は、重要ブロックと判断されないブロックでレジスタライトバックコンフリクトが予想されるサイクルにストールサイクルを適用してもよい。
【０１００】
一実施形態に係るパイプラインでブロックをスケジュールするコンパイル装置は、レジスタライトバックが基本ブロックの境界を越えるようにオペレーションをスケジュールしてパフォーマンスを向上させることができる。また、プロファイル結果のエッジカウントから判断された重要ブロックをストールが発生しないようにスケジュールして性能を極大化し、非重要ブロックについてはストールサイクルを適用してコードサイズを最小化することができる。そして、アクセスカウントによる優先順位で整列されたブロックをスケジュールすることにより、バックトラッキングをなくしコンパイル時間を最小化することができる。
【０１０１】
以上で説明した装置は、ハードウェア構成要素、ソフトウェア構成要素、及び／またはハードウェア構成要素及びソフトウェア構成要素の組合で実現されてもよい。例えば、実施形態で説明された装置及び構成要素は、例えば、プロセッサ、パイプラインプロセッサ（ｐｉｐｅｌｉｎｅ  ｐｒｏｃｅｓｓｏｒ）、コントローラ、ＡＬＵ（ａｒｉｔｈｍｅｔｉｃ  ｌｏｇｉｃ  ｕｎｉｔ）、デジタル信号プロセッサ（ｄｉｇｉｔａｌ  ｓｉｇｎａｌ  ｐｒｏｃｅｓｓｏｒ）、マイクロコンピュータ、ＦＰＡ（ｆｉｅｌｄ  ｐｒｏｇｒａｍｍａｂｌｅ  ａｒｒａｙ）、ＰＬＵ（ｐｒｏｇｒａｍｍａｂｌｅ  ｌｏｇｉｃ  ｕｎｉｔ）、マイクロプロセッサー、または、命令（ｉｎｓｔｒｕｃｔｉｏｎ）を実行して応答できる異なる装置のように、１つ以上の汎用コンピュータまたは特殊目的コンピュータを用いて実現されてもよい。処理装置は、オペレーティングシステム（ＯＳ）及びオペレーティングシステム上で行われる１つ以上のソフトウェアアプリケーションを実行できる。また、処理装置はソフトウェアの実行に応答して、データをアクセス、格納、操作、処理及び生成してもよい。理解の便宜のために、処理装置は１つが使用されるものと説明する場合もあるが、当該の技術分野で通常の知識を有する者は、処理装置が複数の処理要素（ｐｒｏｃｅｓｓｉｎｇ  ｅｌｅｍｅｎｔ）及び／または複数類型の処理要素を含んでいることが分かる。例えば、処理装置は、複数のプロセッサまたは１つのプロセッサ及び１つのコントローラを含んでもよい。また、並列プロセッサ（ｐａｒａｌｌｅｌ  ｐｒｏｃｅｓｓｏｒ）のような、他の処理構成（ｐｒｏｃｅｓｓｉｎｇ  ｃｏｎｆｉｇｕｒａｔｉｏｎ）も可能である。
【０１０２】
ソフトウェアは、コンピュータプログラム、コード、命令、または、このうちの１つ以上の組合を含んでもよく、希望のとおりに動作するよう処理装置を構成したり独立的または結合的に処理装置を命令してもよい。ソフトウェア及び／またはデータは、処理装置によって解釈されたり処理装置に命令またはデータを提供するため、どのような類型の機械、構成要素、物理的装置、仮想装置、コンピュータ格納媒体または装置、または送信される信号波に永久的、または、一時的に具体化される。ソフトウェアは、ネットワークに接続されたコンピュータシステム上に分散し、分散された方法で格納されたり実行されてもよい。ソフトウェア及びデータは１つ以上のコンピュータ読み出し可能な記録媒体に格納されてもよい。
【０１０３】
実施形態に係る方法は、様々なコンピュータ手段によって実行されることができるプログラム命令形態で実現され、コンピュータで読み取り可能な媒体に記録されることができる。コンピュータで読み取り可能な媒体は、プログラム命令、データファイル、データ構造などを単独または組み合わせて含むことができる。媒体に記録されるプログラム命令は、本発明のために特別に設計されて構成されたものであってもよく、コンピュータソフトウェア当業者に公示されて使用可能なものであってもよい。
【０１０４】
上述したように、本発明は限定された実施形態と図面によって説明されたが、本発明が上述した実施形態に限定されるものではなく、本発明が属する分野において通常の知識を有する者であれば、このような記載から多様な修正および変形が可能である。
【０１０５】
したがって、本発明の範囲は上述した実施形態に限定されて定められてはならず、添付の特許請求の範囲だけではなく、この特許請求の範囲と均等なものによって定められなければならない。
【符号の説明】
【０１０６】
１０１：レジスタライトバックコンフリクト（ｒｅｇｉｓｔｅｒ  ｗｒｉｔｅ−ｂａｃｋ  ｃｏｎｆｌｉｃｔ）
２０１、３０１：ストールサイクル
３０２：ＮＯＰ
４９１、５９１：最初のブロック
４９２、５９２：２番目のブロック
４１０：スーパーブロック
４９０：スペキュレーション
５１０：第１ブロック
５２０：第２ブロック
５３０：第３ブロック
５４０：第４ブロック
５１３：第１ブロック５１０で各オペレーションのライトバックが発生するサイクル
５２３：第２ブロック５２０の各オペレーションのライトバックが発生するサイクル
５３３：第３ブロック５３０の各オペレーションのライトバックが発生するサイクル
５４３：第４ブロック５４０の各オペレーションのライトバックが発生するサイクル
７９１：第１ブロックの最初のブロック
７９２：第１ブロックの２番目のブロック
７２０：第２ブロック
７３０：第３ブロック
７４０：第４ブロック
７６１：第１ブロックの最初のブロック７９１に入るエッジ
７１１：第１ブロックの２番目のブロック７９２に入るエッジ
７１２：第１ブロックの最初のブロック７９１から第２ブロック７２０に入るエッジ
７６２：第２ブロック７２０に入るエッジ
７６３：第３ブロック７３０に入るエッジ
７３２：第３ブロック７３０から第２ブロック７２０に入るエッジ
７３４：第３ブロック７３０から第４ブロック７４０に入るエッジ
８１０：第１ブロック
８９１：第１ブロック８１０の最初のブロック
８９２：第１ブロック８１０の２番目のブロック
８２０、８３０、８４０：ブロック
８６１：第１ブロック８１０の最初のブロック８９１に入るエッジ
８１１：第１ブロック８１０の２番目のブロック８９２に入るエッジ
９１０：第１ブロック
９２０：第２ブロック
９３０：第３ブロック
９４０：第４ブロック
９６０：最優先順位ブロック
９７０：次の優先順位ブロック
９８０：その次優先順位ブロック
９９０：最後の優先順位ブロック
１０６１、１０６２、１０６３、１０１１、１０１２、１０３２、１０３４：エッジ
１００１：第１ブロックに入る重要エッジ
１００２：第１ブロック内部の重要エッジ
１００３：第２ブロックに入る重要エッジ
１１１０：第１ブロック
１１１１：最初のブロック
１１１２：２番目のブロック
１１１３：実行されたオペレーションのライトバックが発生するサイクル順序
１１０１、１１０２：重要エッジ
１１６０：重要エッジ１１０１、１１０２が入る最優先順位ブロック
１２１０：第１ブロック
１２５０：第５ブロック
１２７０：次の優先順位ブロック
１２８０：その次優先順位ブロック
１２５２：第５ブロック１２５０からのエッジ
１２２０：第２ブロック
１２２３：実行されたオペレーションのライトバックが発生するサイクル順序
１３２０：第２ブロック
１３３０：第３ブロック
１３４０：第４ブロック
１３２３、１３３３、１３４３：第３ブロック１３３０及び第４ブロック１３４０で実行されたオペレーションがライトバックされるサイクル順序
１３８０：その次優先順位ブロック
１３９０：最後の優先順位ブロック
１４１０：ブロックプロファイル部
１４２０：ブロック判断部
１４２５：エッジマーク部
１４３０：ブロックスケジュール部
１４４０：スーパーブロック形成部
１４５０：ストール適用部
【図１４】
2014146311.tif 000003
【図１】
2014146311.tif 000004
【図２】
2014146311.tif 000005
【図３】
2014146311.tif 000006
【図４】
2014146311.tif 000007
【図５】
2014146311.tif 000008
【図６】
2014146311.tif 000009
【図７】
2014146311.tif 000010
【図８】
2014146311.tif 000011
【図９】
2014146311.tif 000012
【図１０】
2014146311.tif 000013
【図１１】
2014146311.tif 000014
【図１２】
2014146311.tif 000015
【図１３】
2014146311.tif 000016