(57)【要約】【課題】　複数の制御フローパスを有するソフトウェアパイプライン化ループのシステムおよび方法を提供する。【解決手段】　本発明にかかるソフトウェアパイプライン化方法は、パイプラインオペレーションを開始すること（１１０）と、フロー制御条件が有効である場合、分岐オペレーションを行うこと（１２０）と、該分岐オペレーションを行う判定が開始された前記パイプラインオペレーションのポイントで前記パイプラインオペレーションにリターンすること（１３０）とを含む。【選択図】図１
2004062909.tif 000002
【特許請求の範囲】
【請求項１】
　パイプラインオペレーションを開始すること（１１０）と、
　フロー制御条件が有効である場合、分岐オペレーションを行うこと（１２０）と、
　該分岐オペレーションを行う判定が開始された前記パイプラインオペレーションのポイントで前記パイプラインオペレーションにリターンすること（１３０）と
　を含むソフトウェアパイプライン化方法。
【請求項２】
　前記パイプラインオペレーションはループ命令を実行する
　請求項１記載のソフトウェアパイプライン化方法。
【請求項３】
　前記リターンすることは、反復内において制御フローの正しい順序を維持するように実行される（１３０）
　請求項２記載のソフトウェアパイプライン化方法。
【請求項４】
　プレディケート命令プロセスを実行すること（１３０）をさらに含む
　請求項１記載のソフトウェアパイプライン化方法。
【請求項５】
　前記プレディケート命令プロセスは、プレディケートの有効性をチェックすること（１３０）と、
　前記プレディケートが有効ではない場合、前記プレディケート命令プロセスの残りの部分をスキップすること（１３０）と、
　プレディケート命令に対応するオペレーションを含め、前記プレディケートが有効である場合、前記プレディケート命令プロセスの残りの部分を実行すること（１３０）と、
を含む
　請求項４記載のソフトウェアパイプライン化方法。
【請求項６】
　前記プレディケート（１３０）および前記条件（１１０）は相補的なものである
　請求項４記載のソフトウェアパイプライン化方法。
【請求項７】
　前記分岐オペレーション（１２０）の実行頻度は前記プレディケートオペレーションの実行頻度よりも低い
　請求項１記載のソフトウェアパイプライン化方法。
【請求項８】
　プロセッサオペレーションを指示する命令を格納するコンピュータ可読記憶媒体であって、前記プロセッサオペレーションは、
　ソフトウェアパイプライン中のループ反復のフロー制御条件をテストすること（１１０）と、
　前記ループフロー制御条件が真の場合、前記ループ反復の代替パス上の命令を処理するように、サイクル境界において前記ソフトウェアパイプラインから分岐すること（１２０）と、
　前記サイクル境界に再び併合して、ソフトウェアパイプラインオペレーションを継続すること（１３０）と、
　プレディケート命令に基づいて、前記ソフトウェアパイプラインの前記ループ反復のプレディケート命令の処理を行うこと（１３０）と
　を含む記憶媒体。
【請求項９】
　モジュロスケジュールカーネルの実行は、対応する頻繁に実行されないパスオペレーションからの情報を待つ（１２０）間、ループ反復の分岐ポイントにおいて延期される（１１０）
　請求項８記載の記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
　本発明は記憶装置に関する。
　特に、本発明は磁気記憶装置に関する。
【背景技術】
【０００２】
　電子システムおよび回路は近代社会の発展に著しい貢献をなし、有益な結果を達成するために多くの用途に利用されている。
　デジタルコンピュータ、計算機、オーディオ装置、映像機器、および電話システム等多くの電子技術は、生産性の増大を促進し、商業、科学、教育、および娯楽という大半の分野におけるデータ、アイディア、およびトレンドの解析および通信のコストを低減してきた。
　頻繁に、これら活動は情報の処理を含み、さらに高いパフォーマンスおよび機能性に対する需要により、より高速の処理能力への望みが生じている。
【０００３】
　多くの電子装置は、一連の命令を含むプログラムを実行することで動作するプロセッサを備える。
　これらプログラムおよびそれぞれの一連の命令は、ソフトウェアと通常呼ばれる。
　ソフトウェア命令は、有用なタスクの実行においてプロセッサ装置の機能をガイドする指示を含む。
【０００４】
　たとえば、ソフトウェアコードはしばしば、命令セットが所定数の反復の間、または特定の条件がエグジットするまで、繰り返し行われる「ループ」を含む。
　ループは通常、アルゴリズムの複数反復を実行する便利かつ効率的なソフトウェア符号化技法を提供する。
【０００５】
　プロセッサ装置が提供する有用性は、ソフトウェアプログラムに含まれる命令が実行される速度および効率によって決まることが多い。
　従来、タスクはシリアル方式で行われ、この方式では次々と直線的に、１つのオペレーションが行われてから次のオペレーションが行われる。
　純粋な逐次システムでは通常、あるオペレーションが、前のオペレーションが完了するまで行われないため、一連のオペレーションが完了するまでにかなり長い時間をかける必要がある。
　従来のシステムによっては、ソフトウェアパイプライン化により高速化しようとするものがある。
【０００６】
　ソフトウェアパイプライン化とは、時間の短縮および資源利用最大化の促進を含め、パフォーマンスを大幅に向上する可能性をしばしば提供する技法である。
　ソフトウェアパイプライン化は、通常、ある反復からの命令が、前の反復からの命令が完了する前に開始されるデータの並列処理を可能にしようとして、命令処理を「オーバーラップ」させることを含む。
【０００７】
　単一ループの複数の反復のオペレーションをｓステージに分ける。
　最初のｓ−１反復についてパイプラインを埋めるための開始コードおよび最後のｓ−１反復のパイプラインを排出するためのクリーンアップコードを挿入する必要があり得る変換後、変換されたコードの単一反復で、変換前の反復ｉからのステージ１および変換前の反復ｉ−１からのステージ２等々を行う。
　かかる単一反復は、変換コードのカーネルとして知られている。
【０００８】
　非特許文献１に記載されるように、ソフトウェアパイプライン化を達成するアルゴリズムの特定の既知のクラスは、一般に「モジュロスケジューリング」と呼ばれる。
　モジュロスケジューリングは、以下の非特許文献２にも記載されている。
　モジュロスケジューリングは、開始間隔（ＩＩ）と呼ばれる一定のレートでループ反復を開始する。
【０００９】
　ソフトウェアパイプライン化は潜在的に有益な特徴を有するが、従来的に状況によっては適用が困難である。
　たとえば、制御フローを異なる制御フローパス間で渡す分岐、または制御フローをループの外へ渡す分岐を含むループでは、ソフトウェアパイプライン化に準拠するように変換する必要がある。
【００１０】
　非特許文献３に記載の階層低減、非特許文献４に記載のｉｆ変換、ならびに非特許文献５に記載のエンハンストモジュロスケジューリング等の技法を使用して、かかるループをソフトウェアパイプライン化しようとするいくつかの試みがあった。
　しかし、これら技法はしばしば、資源要件と、あまり頻繁に実行されないパスからの命令がパイプラインカーネルに包含されてループ長が増大するため、ループを通して頻繁に実行されるパスにペナルティが課されるカーネルへの依存の高さを増大させる。
　複数の制御フローパスを含むループを、「早い」エグジットを有するループに変換する別の手法ではしばしば、「早い」エグジットに対処する時に困難さに直面し、非特許文献６に記載のようにコードサイズを増大させる末尾重複（tail duplication）を通常利用する。
【非特許文献１】James C.DehnertおよびRoss A. Towle著「Compiling for the Cydra 5」The Journal of Supercomputing, volume 7,（Kluwer Academic Publishers, Boston、１９９３年）
【非特許文献２】B. R. Rau著「Iterative Modulo Scheduling」The International Journal of Parallel Processing, volume 24, no.1（１９９６年２月）
【非特許文献３】M. S. Lam著「Software pipelining: An effective scheduling technique for VLIW machines」Proceedings of ACM SIGPLAN 1988 Conference on Programming Language Design and Implementation, pp318-328, June 1988
【非特許文献４】J. C. Dehnhert、P. Y. Hsu、およびJ. P. Bratt著「Overlapped loop support in the Cydra 5」Proceedings of the Third International Conference on Architectural Support for Programming languages and Operating Systems, pp26-38, April 1989
【非特許文献５】N. J. Warter、G. E. Haab、Ｋ． Subramanian、およびJ. W. Bockhhaus著「Enhanced modulo scheduling for loops with conditional branches」Proceedings of the 25th Annual International Symposium on Microarchitecture, pp170-179, Dec 1992
【非特許文献６】D. M. Lavery著「Modulo Scheduling for Control-Intensive General-Purpose Programs」PhD thesis, Department of Electrical and Computer Engineering, University of Illinois, Urbana, IL, May 1997
【発明の開示】
【発明が解決しようとする課題】
【００１１】
　本発明の目的は、複数の制御フローパスを有するソフトウェアパイプライン化ループのシステムおよび方法を提供することである。
【課題を解決するための手段】
【００１２】
　一実施形態では、ソフトウェアパイプライン方法がパイプラインオペレーションを開始する。
　フロー制御条件が有効である場合、分岐オペレーションが行われる。
　ソフトウェアパイプラインを休止した後、制御フローは、休止が開始されたパイプラインオペレーション中の同じポイントにおけるソフトウェアパイプラインオペレーションにリターンする。
【００１３】
　ループの主パス（たとえば、頻繁に実行されるパス）中のループオペレーションは第１のスケジュール（たとえば、モジュロスケジュール）に従って処理し、代替パス（たとえば、頻繁に実行されないパス）オペレーションは第２のスケジュール（たとえば、有効リストスケジュール）に従って処理することができる。
　主パス（たとえば、分岐オペレーションと同じサイクル境界）へのリターンは、反復内の適切な逐次順序、およびループの複数の反復にわたるステージ実行の並列コヒーレンシを維持するように行われる。
　例示的な一実施態様では、頻繁に実行されるパスのモジュロスケジューリングおよびモジュロスケジュールからあまり頻繁に実行されないパスへの分岐により、頻繁に実行されるパスが、あまり頻繁に実行されない分岐パスからの追加命令によってペナルティが課されないようにする。
【発明の効果】
【００１４】
　本発明によれば、複数の制御フローパスを有するソフトウェアパイプライン化ループのシステムおよび方法が提供される。
【発明を実施するための最良の形態】
【００１５】
　本明細書に組み込まれ本明細書の一部をなす添付図面は、本発明の実施形態を示し、説明と併せて本発明の原理を説明する役割を果たす。
　本明細書において参照する図面は、特記されない場合一定の比率で拡大縮小したものではないものと理解されたい。
【００１６】
　これより、例を添付図面に示す本発明の好ましい実施形態を詳細に参照する。
　本発明について好ましい実施形態と併せて説明するが、本発明をこれら実施形態に限定する意図はないことが理解されよう。
　反対に、本発明は、併記の特許請求項によって定義される本発明の精神および範囲内に包含し得る代替、変更、および等価物をカバーするよう意図される。
【００１７】
　さらに、以下の本発明の詳細な説明では、本発明の完全な理解を提供するために多くの特定の詳細について述べる。
　しかし、本発明はこういった特定の詳細なしでも実施し得ることが分かる。
　他の例では、容易に理解される方法、手順、構成要素、および回路によっては、本発明の態様を不必要に曖昧にしないように、詳細に説明しないものがある。
【００１８】
　以下の詳細な説明のいくつかの部分は、手順、ロジックブロック、処理、およびコンピュータメモリ内のデータビットに対するオペレーションの他の象徴的な表現に関して提示される。
　これら説明および表現は、それぞれの研究内容を他の当業者に効率的に伝えるためにデータ処理分野における当業者によって一般に使用される手段である。
　本明細書では、手順、ロジックブロック、プロセス等は、システムの動作を所望の結果に導く一連のステップまたは命令であると一般に解釈される。
【００１９】
　ステップは、物理量の物理的な処理を含む。
　通常、これら量は、格納、転送、結合、比較、またそうでなければ処理システムにおいて処理することが可能な電気信号、磁気信号、光信号、または量子信号の形を採るが、必ずしもそうである必要はない。
　主として慣用の理由により、これら信号をビット、値、要素、記号、キャラクタ、用語、番号等として言及することが時に便利であることが証明されている。
【００２０】
　しかし、これらおよび同様の用語にはすべて適切な物理量が関連付けられ、こういった量に適用される便利なラベルにすぎないことを念頭に置かれたい。
　特記しない限り、または以下の説明から明白なように、本出願全体を通して、「処理」、「コンピューティング」、「計算」、「判定」、「表示」等の用語を利用する説明は、物理（たとえば、電子）量として表現されるデータを処理し変換するコンピュータシステムまたは同様の処理装置（たとえば、電気的、光学的、または量子的なコンピューティング装置）のアクションおよびプロセスを指すことがわかる。
　システムのコンポーネント（たとえば、レジスタ、メモリ、他のかかる情報記憶装置、伝送装置、または表示装置等）内の物理量を、同じまたは他のコンポーネント内の物理量として同様に表される他のデータに処理または変換する処理装置のアクションおよびプロセスを指す。
【００２１】
　図１は、本発明の一実施形態であるソフトウェアパイプライン化方法１００のフローチャートである。
　ソフトウェアパイプライン化方法１００は、条件付制御フローを有するループの処理を含むソフトウェア命令の効率的な実施に役立つ。
　本方法では、ループ内に条件付分岐が存在する場合であっても、異なる反復からの命令を、反復内の制御フローの正しい順序を維持しながら並列に処理することができる。
【００２２】
　ステップ１１０において、ソフトウェアパイプラインオペレーションが開始される。
　ソフトウェアパイプラインオペレーションは、ソフトウェアパイプラインシーケンスの一部としてループ反復を実行することを含む。
　たとえば、これは、ループ反復中のあるポイントにおける条件をテストすることを含むことができ、ループオペレーションは、第１のスケジュール（たとえば、モジュロスケジュール）に従って行われる。
【００２３】
　ステップ１２０において、フロー制御条件が有効な場合には分岐オペレーションが行われる。
　一実施形態では、分岐オペレーションは、サイクル境界（たとえば、２つのプロセッササイクル間のポイント）においてパイプラインから分岐して、条件が真の場合には代替パス（たとえばループ内の頻繁に実行されない制御フローパス）上の第１の命令を実行することを含む。
　ループの主パスにおけるループオペレーションは第１のスケジュール（たとえば、モジュロスケジュール）に従って処理することができ、代替パス（たとえば、頻繁に実行されないパス）のオペレーションは、頻繁に実行されないパスの制御フローについての条件が真の場合に第２のスケジュール（たとえば、有効リストスケジュール）に従って処理することができる。
　パイプラインオペレーションは、対応する頻繁に実行されないパスのオペレーションからの情報を待つ間、ループ反復の分岐ポイントにおいて延期させることができる（たとえば、モジュロスケジュールカーネルの実行が延期される）。
【００２４】
　ステップ１３０において、パイプラインオペレーションは、ステップ１２０における分岐オペレーションを行う判定が開始された、パイプラインオペレーション中のポイントにリターンする。
　このリターンは、反復内の適切な逐次順序、およびループの複数の反復にわたるステージ実行の並列コヒーレンシを維持するように行われる。
　一実施形態では、パイプラインから分岐が行われたポイントと同じ分岐ポイント（たとえば、サイクル境界）への再併合が行われる。
　条件付分岐ポイントにおけるループオペレーションは、第１のスケジュールに従って続けられる。
【００２５】
　一実施形態では、プレディケートオペレーションがループ反復のパイプライン処理に含められる。
　プレディケートオペレーションは、一実施において適切な順序を維持するために利用される。
　たとえば、パイプラインステージの実行は、プレディケートインジケーションに基づいて処理される。
【００２６】
　プレディケート値（たとえば、条件の補完）が真の場合にパイプライン中のプレディケートオペレーションが実行される。
　たとえば、制御フローの主パス上にあるが、代替パスがその分岐ポイントからとられる場合には実行すべきではない条件付分岐ポイント後のオペレーションが、上記条件の補完後にプレディケートされる。
　一実施形態では、パイプライン中のプレディケート命令プロセスの実行は、いくつかのオペレーションを含む。
【００２７】
　プレディケートの有効性がチェックされる。
　たとえば、プレディケートレジスタ中の値の有効性または真偽が解析される。
　プレディケートが有効ではない場合、プレディケートパイプラインオペレーションの残りの部分はスキップされる。
　プレディケートパイプラインオペレーションの残りの部分は、プレディケート値が有効な場合に行われる。
【００２８】
　図２は、モジュロスケジューリングを適用しない状態でのループ２００中の例示的な条件付制御を示すブロック図である。
　ループ２００は、様々な命令またはオペレーションを含み得るブロック２１０、２２０、２３０、および２４０を含む。
　図２は、条件ｑが真の場合には命令２２５を実行し、条件ｐが真の場合には命令２３５を実行し、双方の命令の後に命令２４５が続く基本的な反復を示す。
【００２９】
　例示的な一実施態様では、ループ２００を１０００回反復してブロック２２０を実行し、ループ２００を１０回反復してブロック２３０を実行する。
　本発明の一実施形態によるモジュロスケジューリング技法を行う準備を整えながらのループ２００に適した制御フローの達成を図３に示す。
【００３０】
　図３は、ソフトウェアパイプライン化方法１００の例示的な実施態様の場合に準備したループ２００の制御フローを示すブロック図である。
　ループ２００は、ブロック２１０、２２０、および２４０の主実行パスを有する。
　ブロック２１０は、フロー制御条件をテストする命令２１５を含む。
【００３１】
　たとえば、テストにより、プレディケートｐまたはプレディケートｑが真かどうかを判定することができる。
　例示的な一実施態様では、プレディケートｐおよびｑは相補的なものである。
　プレディケートｑが真の場合、ループ２００の実行はブロック２２０に進み、命令２２５を実行してからブロック２４０において命令２４５を実行する。
　プレディケートｐが真の場合、ループ２００の実行はステップ１２０におけるブロック２３０に分岐し、命令２２５を実行してからブロック２２０にリターンするが、プレディケートｑが真ではないため命令２２５をスキップする。
　ループ実行２００は、ブロック２４０（たとえば、命令２４５を含む）を実行し、ブロック２４０において命令を実行した後にブロック２１０にリターンする。
【００３２】
　本発明では、ループを増長単一基本ブロックループ（たとえば、ｉｆ変換を介して）に変換することに頼ることなく、複数の制御フローを含むループをモジュロスケジューリングするようにプログラムすることが可能である。
　たとえば、図３では、ループを通して最も頻繁に実行されるパスに沿ったブロック（たとえば、ブロック２１０、２２０、および２４０）は、モジュロスケジューリングされるが、あまり頻繁に実行されないブロック（たとえば、ブロック２３０）はモジュロスケジューリングされない。
　ループの異なる反復からのこの頻繁に実行されるパスからの命令はパイプライン化される。
【００３３】
　しかし、あまり頻繁に実行されないブロック（たとえば、ブロック２３０）からの命令はパイプライン化されない。
　その代わり、ブロック２３０が実行される（たとえば、フロー制御条件が真）ときの反復では、プロセスはループのモジュロスケジューリングされたカーネルからブロック２３０に分岐する。
　ブロック２３０中の命令が実行され、プロセスはループのモジュロスケジューリングされた部分に分岐してリターンする。
　ブロック２３０への条件付分岐は、残りの頻繁に実行されるパスに沿ってパイプライン化される。
【００３４】
　本発明の一実施形態では、ブロック２２０のある反復からの命令が、ループの他の反復からの命令とともにパイプライン化される。
　本発明は、適切な逐次順序が維持されるように保証する。
　たとえば、ブロック２３０への分岐が実行される場合、その反復のブロック２２０からの命令は実行されない。
　そのため、ブロック２２０からの命令が、異なる反復からの命令（たとえば、２１０、２４０等）とともにパイプライン化される場合、ブロック２３０の実行からパイプラインにリターンすると他の反復からの命令が実行されるが、ブロック２２０の命令は実行されない。
　同じ反復におけるブロック２２０からの命令の実行を回避するために、ブロック２２０の命令は、ブロック２２０への分岐が開始されるフロー制御条件の補完であるプレディケートによって保護される。
　ソフトウェアパイプライン化方法１００は、ブロック２３０に分岐した直後のポイントでモジュロスケジュールに分岐してリターンする。
　実施態様に応じて行うことのできる様々なスケジューリング実施態様がある。
【００３５】
　図４は、多重パイプライン化ループ反復オペレーションの実行を示すブロック図である。
　本例では、ループ命令Ａ、Ｂ、ＣおよびＤが図３の命令２１５、２２５、２３５、および２４５それぞれに対応する。
　ループ反復３０１〜３０５は、パイプラインステージ３９１〜３９７中に実行される。
　たとえば、ソフトウェアパイプラインプロローグはステージ３９１および３９２を含み、ソフトウェアパイプラインカーネルはステージ３９３〜３９５を含み、エピローグはステージ３９６および３９７を含む。
　したがって、反復３０１、３０２、および３０３の命令Ｄ、Ｂ、およびＡの命令実行インスタンス化３３１、３３２、および３３３は、それぞれ同じパイプラインステージ３９３中にモジュロスケジュールに従って行われる。
【００３６】
　例示的な本実施態様は、命令Ａに従って行われる条件テストにより、フロー制御条件が反復３０３について有効であると判定されることを示す。
　ループ命令の適切な逐次実行および並列実行の維持に利用し得る様々なスケジューリング実施態様がある。
　図４では、ソフトウェアパイプライン化オペレーションのモジュロスケジューリングは、反復３０３について命令Ｃのインスタンス化３９９を実行するように分岐が行われるため、ステージ３３０と３４０との間で休止する。
　したがって、モジュロスケジューリングされたソフトウェアパイプラインオペレーションは、期間３７７に含まれるサイクル中に延期される。
【００３７】
　再び図２を参照すると、モジュロスケジューリングはブロック２３０中の命令には適用されないため、ブロック２３０の命令は、ループのモジュロスケジューリング前に有効リストスケジュール（直線コードスケジュール）にスケジューリングされる。
　スケジューリング中、命令間の依存がスケジューリング依存グラフに表される。
【００３８】
　グラフ中の各エッジは、エッジの元にある命令からエッジの先にある命令への依存を示す。
　エッジには、２つの命令の実行間に経過するサイクル数を表す依存距離が注釈付けられる。
　例示的な一実施態様では、依存グラフは、ループがモジュロスケジューリングされる場合のそのループ内の命令を含む。
【００３９】
　一実施形態では、複数の制御フローを含むループを通る頻繁に実行されるパスをモジュロスケジューリングする場合、依存グラフは、モジュロスケジューリングされることのないループ反復中の命令（たとえば、本例ではブロック２３０）を含まない。
　コードがモジュロスケジューリングされる実施態様によっては、頻繁に実行されないパスオペレーションからの命令（たとえば、ブロック２３０）は、頻繁に実行されるパス上の命令との依存性を有する。
【００４０】
　たとえば、ブロック２４０からの命令２４５がブロック２３０中の命令２３５に依存する場合、コンパイラは、命令２４５の、スケジューリングに対する「準備」がいつ整うかを知る必要がある。
　本実施態様では、命令２４５の準備は、ブロック２３０実行後にプロセスがモジュロスケジュールに分岐してリターンするポイントにおいて整う。
　本発明は、上述したように、ブロック２３５に分岐した直後にモジュロスケジュールに分岐してリターンするため、命令２４５の準備は、ブロック２３０に分岐した「直」後に整う（たとえば、プレディケート判定が行われてこの反復ではブロック２２０中の命令をスキップすると）。
【００４１】
　したがって、命令２３５から命令２４５への依存は、ブロック２１０中の条件付フロー制御オペレーションから命令２４５に、依存グラフ中のエッジで表すことができる。
　一実施形態では、この新しいエッジには、頻繁に実行されるパスに沿った命令のスケジューリングを最適化するために、依存距離０と注釈付けられる。
【００４２】
　変更した依存グラフの一部を図５に示す。
　結果として、ブロック２３０中の命令２３５後、ｎサイクル未満で命令２４５をスケジューリングすることができる。
　但し、ｎは命令２３０から命令２４５までの当初の依存距離である。
【００４３】
　これにより、ブロック２３０への分岐を含む反復中の命令２４５を実行するとき、スコアボードマシン（scoreboarded machine）（たとえば、Ｉｔａｎｉｕｍ）のストールが発生する可能性がある。
　ブロック２３０は頻繁に実行されないため、これはまれにしか発生しないはずである。
　したがって、ループオペレーションは、条件付分岐とパイプライン化命令の間のエッジに割り当てられた動作サイクル持続期間がゼロであり、パイプライン化命令が、第２のスケジュールに従って行われる頻繁に実行されないパスオペレーションの結果に依存するソフトウェアパイプラインスケジューリング依存グラフに従ってスケジューリングされる。
【００４４】
　同様に、ブロック２１０中の命令からブロック２３０中の命令へのエッジは、ブロック２１０中の命令からブロック２３０への条件付分岐までの新しいエッジで表される。
　ここでも、このエッジは、頻繁に実行されるパスを積極的に最適化するために、サイクル依存距離０を有することができる。
　依存グラフ中のブロック２３０の命令への／からの依存エッジが、ブロック２３０への分岐への／からの新しいエッジで表されると、ブロック２３０からの命令は、それぞれ関連するエッジとともに依存グラフから除去される。
【００４５】
　本発明の一実施形態では、回転レジスタ（rotating register）を使用してモジュロスケジューリングをサポートする。
　ソフトウェアパイプライン中の命令によって使用され定義される値に割り当てられる回転レジスタは、命令がスケジューリングされているパイプラインステージに依存する。
　ブロック２３０中の命令はモジュロスケジューリングされないが、適切な回転レジスタが、ソフトウェアパイプラインによって生成される頻繁に実行されないパス上の命令によって消費される値に割り当てられる。
【００４６】
　同様に、適切な回転レジスタが、ソフトウェアパイプライン中の命令によって消費される頻繁に実行されないパス上の命令により生成される値に割り当てられる。
　たとえば、代替パス上（たとえば、頻繁に実行されないパス上）の命令は、回転レジスタ割り当て目的のために、主（たとえば、頻繁に実行される）パイプライン化パスからの対応する分岐と同じステージに属するものとして処理される。
【００４７】
　ソフトウェアパイプライン化方法１００は、コンピュータシステムで実施することができる。
　図６は、本発明を実施し得るコンピュータシステムの一実施形態であるコンピュータシステム５００のブロック図である。
　コンピュータシステム５００は、通信バス５０７、プロセッサ５０１、メモリ５０２、入力コンポーネント５０３、およびオプションのディスプレイモジュール５０５を備える。
　通信バス５０７は、中央処理装置５０１、メモリ５０２、入力コンポーネント５０３、およびオプションのディスプレイモジュール５０５に接続される。
【００４８】
　コンピュータシステム５００のコンポーネントは協働して機能して、本発明のソフトウェアパイプライン化方法（たとえば、ソフトウェアパイプライン化方法１００）に従ったループ命令の実行を含む様々な機能を提供する。
　通信バス５０７は情報を通信し、プロセッサ５０１は情報および命令を処理し、メモリ５０２は情報および命令を格納し、入力コンポーネント５０３は、コンピュータシステム５００への情報の通信を促進し、オプションのディスプレイモジュール５０５はコンピュータユーザに情報を表示する。
【００４９】
　本発明は、様々な実施態様に容易に適合することができる。
　図７は、本発明の一実施形態による条件付分岐およびプレディケート命令を利用する複数の制御フローを含むループのモジュロスケジューリングを示す。
　一実施形態では、あまり頻繁に実行されない各パスに、頻繁に実行されるパス上の単一条件付分岐から入り、頻繁に実行されるパス上の単一ポイントで再度入る。
【００５０】
　たとえば、頻繁に実行されるパスはブロック５１０〜５５０を含む。
　第１の分岐はブロック５７１〜５７４を含み、第２の分岐はブロック５９１〜５９３を含む。
　ブロック５２０および５３０は、ブロック５１０中の条件付フロー制御値を補完するプレディケートオペレーションを含む。
【００５１】
　ブロック５４０は、ブロック５３０中の条件付フロー制御値を補完するプレディケートオペレーションを含む。
　スケジューリング依存グラフは、パイプライン中の対応するステージに適切な回転レジスタを割り当てた状態で複数の頻繁に実行されないパス上の命令からの依存性を考慮して、頻繁に実行されるパスが正しくモジュロスケジューリングされるように更新される。
　複数の制御フローをそれ自体が含むあまり頻繁に実行されないパスもまた処理される。
　たとえば、第１の分岐５７０は、ブロック５７２あるいはブロック５７４に反復パスを向ける条件付制御フローをブロック５７１に含む。
【００５２】
　本発明の一実施形態では、頻繁に実行されるパスのみがモジュロスケジューリングされる。
　頻繁に実行されないパスの実行のために、モジュロスケジュールから出る分岐およびモジュロスケジュールにリターンする分岐が行われる。
　頻繁に実行されるパスのみをモジュロスケジューリングし、モジュロスケジュールからあまり頻繁に実行されないパスに出る分岐をとることにより、頻繁に実行されるパスが、あまり頻繁に実行されない分岐パスからの付加的な命令により不利にならない。
【００５３】
　これにより、ループを通して頻繁に実行されるモジュロスケジューリングされたパスのスケジュール長が低減するため、ループオペレーションの実行にかかる時間が短縮される。
　本例の殆どの反復は、ループのモジュロスケジューリングされた部分から頻繁に実行されないパスに分岐しない。
　本例の反復がループのモジュロスケジューリングされた部分から頻繁に実行されないパスに分岐する比較的少ない回数の間、分岐および関連するリストスケジュールを実行するための追加時間は、より頻繁に実行されるパスオペレーションとともに頻繁に実行されないパスオペレーションを行う（たとえば、ｉｆ変換のように）累積時間よりも短い。
【００５４】
　したがって、本発明は、複数の制御フローパスを含むループの高速パイプライン処理に役立つ。
　頻繁に実行されないパスオペレーションへのパイプラインからの分岐、およびパイプライン中の同じポイントでのパイプラインへの続くリターンを有する頻繁に実行される主パスのパイプライン化は、反復内の逐次オペレーションおよび異なる反復にわたる並列オペレーションの維持に役立つ。
【００５５】
　本発明の特定の実施形態の上記説明は、例示および説明を目的として提示されたものである。
　網羅的、すなわち本発明を開示した厳密な形態に制限する意図はなく、明らかに、上記教示に鑑みて多くの変更および変形が可能である。
　実施形態は、当業者が意図する特定の使用に合うように本発明および各種変更形態を最もよく利用できるように、本発明の原理およびその実際の応用を最もよく説明するために選択し記載した。
　本発明の範囲は、併記の特許請求項およびその等価物によって定義されることが意図される。
【産業上の利用可能性】
【００５６】
　本発明は、記憶装置、特に、磁気記憶装置に利用可能である。
【図面の簡単な説明】
【００５７】
【図１】本発明の一実施形態であるソフトウェアパイプライン化方法のフローチャートである。
【図２】モジュロスケジューリングを適用しない状態における、ループ中の例示的な条件付制御の制御フローを示すブロック図であり、
【図３】本発明の一実施形態によるモジュロスケジューリング技法を使用する間の制御フローの達成を示す。
【図４】多重パイプライン化ループ反復オペレーションの実行を示すブロック図である。
【図５】本発明の一実施形態による変更された依存グラフの一部を示す。
【図６】本発明を実施し得るコンピュータシステムの一実施形態であるコンピュータシステム５００のブロック図である。
【図７】本発明の一実施形態による条件付分岐およびプレディケート命令を利用する複数の制御フローを含むループのモジュロスケジューリングを示す。
【符号の説明】
【００５８】
２００・・・ループ、
２１０，２２０，２３０，２４０・・・ブロック、
２１５，２２５，２３５，２４５・・・命令、
３０１〜３０５・・・ループ反復、
３３１，３３２，３３３・・・命令実行インスタンス化、
３７７・・・期間、
３９１〜３９７・・・パイプラインステージ、
３９９・・・インスタンス化、
５００・・・コンピュータシステム、
５０１・・・プロセッサ、
５０２・・・メモリ
５０３・・・入力コンポーネント、
５０５・・・ディスプレイ、
５０７・・・通信バス、
５１０〜５９３・・・ブロック、
【図１】
2004062909.tif 000003
【図２】
2004062909.tif 000004
【図３】
2004062909.tif 000005
【図４】
2004062909.tif 000006
【図５】
2004062909.tif 000007
【図６】
2004062909.tif 000008
【図７】
2004062909.tif 000009