(57)【要約】【課題】複数の入力命令をベクトル化する効果的な方法及び装置を提供すること。【解決手段】本発明の一特徴は、トレースの共通のオペレーションコードを有する２以上の命令を検索し、前記２以上の命令が、トレース依存性ツリーにおいて同一のレベルを有する場合、前記２以上の命令を１つのＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令にマージする最適化ユニットを有する装置であって、前記トレース依存性ツリーは、各レベルが同一の高さの命令を有する複数のレベルにおける命令を有し、前記トレースの命令は、メモリに格納されることを特徴とする装置に関する。【選択図】図１
2011165216.tif 000002
【特許請求の範囲】
【請求項１】
トレースの共通のオペレーションコードを有する２以上の命令を検索し、前記２以上の命令が、トレース依存性ツリーにおいて同一のレベルを有する場合、前記２以上の命令を１つのＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令にマージする最適化ユニットを有する装置であって、
前記トレース依存性ツリーは、各レベルが同一の高さの命令を有する複数のレベルにおける命令を有し、
前記トレースの命令は、メモリに格納されることを特徴とする装置。
【請求項２】
請求項１記載の装置であって、
前記共通のオペレーションコードは、メモリオペレーションコード又は算術オペレーションコードから構成されることを特徴とする装置。
【請求項３】
請求項１記載の装置であって、
前記最適化ユニットは、
前記２以上の命令を前記トレース依存性ツリーに配置することによって、シーケンサから受け付けた命令のトレースから前記２以上の命令を検索する第１ステージと、
前記命令を前記トレース依存性ツリーに格納するキャッシュメモリと、
前記１つのＳＩＭＤ命令を生成するため、前記キャッシュメモリの前記２以上の命令を検索する第２ステージと、
を有することを特徴とする装置。
【請求項４】
請求項１記載の装置であって、
前記最適化ユニットは、連続するメモリアドレスにアクセスする前記２以上の命令を前記１つのＳＩＭＤ命令に合成することが可能であることを特徴とする装置。
【請求項５】
請求項１記載の装置であって、
前記最適化ユニットは、入力された命令をＳＳＡ（Ｓｉｎｇｌｅ  Ｓｔａｔｉｃ  Ａｓｓｉｇｎｍｅｎｔ）形式に変換可能であることを特徴とする装置。
【請求項６】
トレースの共通のオペレーションコードを有する２以上の命令を検索するステップと、
前記２以上の命令が、トレース依存性ツリーにおいて同一のレベルを有する場合、前記２以上の命令を１つのＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令にマージするステップと、
を有する方法であって、
前記トレース依存性ツリーは、各レベルが同一の高さの命令を有する複数のレベルを有することを特徴とする方法。
【請求項７】
請求項６記載の方法であって、
メモリ処理オペレーションコード又は算術オペレーションコードから構成される前記共通のオペレーションコードを選択するステップを有することを特徴とする方法。
【請求項８】
請求項６記載の方法であって、
連続するメモリアドレスにアクセスする前記２以上の命令を前記１つのＳＩＭＤ命令に合成するステップを有することを特徴とする方法。
【請求項９】
請求項６記載の方法であって、
前記マージするステップは、前記トレースの入力された命令をＳＳＡ（Ｓｉｎｇｌｅ  Ｓｔａｔｉｃ  Ａｓｓｉｇｎｍｅｎｔ）形式に変換することから構成されることを特徴とする方法。
【請求項１０】
バスと、
バスに接続される記憶装置と、
トレースの共通のオペレーションコードを有する２以上の命令を検索し、前記２以上の命令が、トレース依存性ツリーにおいて同一のレベルを有する場合、前記２以上の命令を１つのＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令にマージする最適化ユニットを有するプロセッサと、
から構成されるシステムであって、
前記トレース依存性ツリーは、各レベルが同一の高さの命令を有する複数のレベルにおける命令を有し、
前記トレースの命令は、前記記憶装置に格納されることを特徴とするシステム。
【請求項１１】
請求項１０記載のシステムであって、
前記共通のオペレーションコードは、メモリオペレーションコード又は算術オペレーションコードから構成されることを特徴とするシステム。
【請求項１２】
請求項１０記載のシステムであって、
前記最適化ユニットは、
前記２以上の命令を前記トレース依存性ツリーに配置することによって、シーケンサから受け付けた命令のトレースから前記２以上の命令を検索する第１ステージと、
前記命令を前記トレース依存性ツリーに格納するキャッシュメモリと、
前記１つのＳＩＭＤ命令を生成するため、前記キャッシュメモリの前記２以上の命令を検索する第２ステージと、
を有することを特徴とするシステム。
【請求項１３】
請求項１０記載のシステムであって、
前記最適化ユニットは、連続するメモリアドレスにアクセスする前記２以上の命令を前記１つのＳＩＭＤ命令に合成することが可能であることを特徴とするシステム。
【請求項１４】
請求項１０記載のシステムであって、
前記最適化ユニットは、入力された命令をＳＳＡ（Ｓｉｎｇｌｅ  Ｓｔａｔｉｃ  Ａｓｓｉｇｎｍｅｎｔ）形式に変換可能であることを特徴とするシステム。
【請求項１５】
トレースの共通のオペレーションコードを有する２以上の命令を検索するステップと、
前記２以上の命令が、トレース依存性ツリーにおいて同一のレベルを有する場合、前記２以上の命令を１つのＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令にマージするステップと、
をコンピュータに実行させるプログラムであって、
前記トレース依存性ツリーは、各レベルが同一の高さの命令を有する複数のレベルを有することを特徴とするプログラム。
【請求項１６】
請求項１５記載のプログラムであって、
メモリ処理オペレーションコード又は算術オペレーションコードから構成される前記共通のオペレーションコードを選択するステップを前記コンピュータに実行させるプログラム。
【請求項１７】
請求項１５記載のプログラムであって、
連続するメモリアドレスにアクセスする前記２以上の命令を前記１つのＳＩＭＤ命令に合成するステップを前記コンピュータに実行させるプログラム。
【請求項１８】
請求項１５記載のプログラムであって、
入力された命令をＳＳＡ（Ｓｉｎｇｌｅ  Ｓｔａｔｉｃ  Ａｓｓｉｇｎｍｅｎｔ）形式に変換するステップを前記コンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の入力命令をベクトル化する方法及び装置に関する。
【背景技術】
【０００２】
コンピュータシステムの中央処理ユニット（ＣＰＵ）は、命令をパラレルに処理する複数の機能実行ユニットを含むかもしれない。これらの命令は、ＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令を含むかもしれない。ＳＩＭＤ命令は、複数のデータに対する共通の処理をパラレルに実行することが可能である。従って、ＳＩＭＤ命令は、ＣＰＵが全体の実行時間を低減するため、複数の繰り返しの計算を同時に実行することを可能にするかもしれない。ＳＩＭＤ処理の使用は、音声及び画像処理などのマルチメディアアプリケーションにおいて特に有効であるかもしれない。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
本発明の課題は、複数の入力命令をベクトル化する効果的な方法及び装置を提供することである。
【課題を解決するための手段】
【０００４】
上記課題を解決するため、本発明の一特徴は、トレースの共通のオペレーションコードを有する２以上の命令を検索し、前記２以上の命令が、トレース依存性ツリーにおいて同一のレベルを有する場合、前記２以上の命令を１つのＳＩＭＤ（Ｓｉｎｇｌｅ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ｄａｔａ）命令にマージする最適化ユニットを有する装置であって、前記トレース依存性ツリーは、各レベルが同一の高さの命令を有する複数のレベルにおける命令を有し、前記トレースの命令は、メモリに格納されることを特徴とする装置に関する。
【発明の効果】
【０００５】
本発明によると、複数の入力命令をベクトル化する効果的な方法及び装置を提供することができる。
【図面の簡単な説明】
【０００６】
【図１】図１は、本発明の一実施例によるコンピュータシステムのブロック図である。
【図２】図２は、本発明の一実施例による最適化ユニットのブロック図である。
【図３】図３は、本発明の一実施例による命令をＳＩＭＤ命令に変換する方法を説明するのに有用な一例となる依存性ツリーの図である。
【図４】図４は、本発明の一実施例によるベクトル化処理の説明に有用なテーブルの図である。
【図５】図５は、本発明の他の実施例によるベクトル化処理の説明に有用なテーブルの図である。
【発明を実施するための形態】
【０００７】
以下の詳細な説明では、本発明の完全なる理解を提供するため、多数の具体的詳細が提供される。しかしながら、本発明がこれらの具体的詳細なく実現可能であるということは、当業者には理解されるであろう。他の例では、本発明を不明りょうにしないように、周知の方法、処理、構成要素及び回路は、詳細には説明されない。
【０００８】
以下の詳細な説明の一部は、コンピュータメモリ内のデータビット又はバイナリデジタル信号に対する記号表現及びアルゴリズムに関して提供される。これらのアルゴリズム的な記載及び表現は、データ処理分野の当業者によって他の当業者に自らの研究の本質を伝えるのに利用される技術であるかもしれない。
【０００９】
以下の説明から明らかなように、具体的に説明されない場合、本明細書の全体を通じて、「処理」、「計算」、「決定」などの用語の使用は、計算システムのレジスタ及び／又はメモリ内の電子量などの物理量として表されるデータを、計算システムのメモリ、レジスタ又は他のこのような情報ストレージ、送信若しくは表示装置内の物理量として同様に表される他のデータに操作及び／又は変換するコンピュータ、計算システム又は同様の電子計算装置のアクション及び／又は処理を表すことが理解される。さらに、「複数の」という用語は、２以上の構成要素、装置、要素、パラメータなどを説明するのに本明細書を通じて使用されるかもしれない。例えば、「複数の命令」とは、２以上の命令を表す。
【００１０】
「ＳＩＭＤ化」又は「ベクトル化」という用語は、実行のためスケジューリングされるものであって、レジスタや機能ユニットなどの同様の実行リソースを要求する処理を単一のＳＩＭＤ命令にマージする処理を表す等価な用語であるということが理解されるべきである。本発明の範囲はこれに限定されるものではないが、説明の簡単化のため、「ベクトル化」という用語は、実行のためにスケジューリングされ、同様の実行リソースを必要とする処理をマージする処理を説明するのに使用される。
【００１１】
本発明は、様々な用途に利用可能であるということが理解されるべきである。本発明はこれに限定されるものではないが、ここで開示される回路及び技術は、コンピュータシステム、プロセッサ、ＣＰＵなどの多数の装置において利用可能である。本発明の範囲内に含まれるべきプロセッサは、単なる一例ではあるが、ＲＩＳＣ（Ｒｅｄｕｃｅｄ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｓｅｔ  Ｃｏｍｐｕｔｅｒ）、パイプラインを有するプロセッサ、ＣＩＳＣ（Ｃｏｍｐｌｅｘ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｓｅｔ  Ｃｏｍｐｕｔｅｒ）などを含む。
【００１２】
本発明の一部の実施例は、例えば、マシーンにより実行される場合（例えば、プロセッサ及び／又は他の適切なマシーンによって）、当該マシーンに本発明の実施例による方法及び／又は処理を実行させる命令又は命令セットを格納可能なマシーン可読媒体又は物品を利用して実現されるかもしれない。このようなマシーンは、例えば、任意の適切な処理プラットフォーム、計算プラットフォーム、計算装置、処理装置、計算システム、処理システム、コンピュータ、プロセッサなどを含むものであってもよく、ハードウェア及び／又はソフトウェアの任意の適切な組み合わせを用いて実現されるようにしてもよい。マシーン可読媒体又は物品は、例えば、任意の適切なタイプのメモリユニット、記憶装置、メモリ物品、記憶媒体、ストレージ装置、ストレージ物品、ストレージ媒体及び／又はユニットを含むものであってもよく、例えば、メモリ、着脱可能又は着脱不可な媒体、消去可能又は消去不可な媒体、書き込み可能又は書き換え可能な媒体、デジタル又はアナログ媒体、ハードディスク、フロッピー（登録商標）ディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＣＤ−Ｒ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅｃｏｒｄａｂｌｅ）、ＣＤ−ＲＷ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅｗｒｉｔａｂｌｅ）、光ディスク、磁気媒体、各種タイプのＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）、テープ、カセットなどを含むものであってもよい。命令は、ソースコード、コンパイルされたコード、インタープリットされたコード、実行可能コード、静的コード、動的コードなどの任意の適切なタイプのコードを含むものであってもよく、例えば、Ｃ、Ｃ＋＋、Ｊａｖａ（登録商標）、ＢＡＳＩＣ、Ｐａｓｃａｌ、Ｆｏｒｔｒａｎ、Ｃｏｂｏｌ、アセンブリ言語、機械コードなどの任意の適切な高レベル、低レベル、オブジェクト指向、ビジュアル、コンパイル及び／又はインタープリットプログラミング言語を含むものであってもよい。
【００１３】
図１を参照するに、本発明の一実施例によるコンピュータシステム１００のブロック図が示される。本発明の範囲はこれに限定されるものではないが、コンピュータシステム１００は、パーソナルコンピュータ（ＰＣ）、携帯情報端末（ＰＤＡ）、インターネット装置、携帯電話又は他の任意の計算装置であってもよい。一例では、コンピュータシステム１００は、電源１２０によって駆動されるメイン処理ユニット１１０を有するかもしれない。本発明の実施例では、メイン処理ユニット１１０は、システムインターコネクト１３５により記憶装置１４０及び１以上のインタフェース回路１５０に電気的に接続されるマルチ処理ユニット１３０を有するものであってもよい。例えば、システムインターコネクト１３５は、所望される場合には、アドレス／データバスであってもよい。バス以外のインターコネクトがマルチ処理ユニット１３０を記憶装置１４０に接続するのに利用可能であるということが理解されるべきである。例えば、１以上の専用線及び／又はクロスバーが、マルチ処理ユニット１３０を記憶装置１４０に接続するのに利用可能である。
【００１４】
本発明の一部の実施例によると、マルチ処理ユニット１３０は、Ｉｎｔｅｌ（登録商標）Ｐｅｎｔｉｕｍ（登録商標）ＴＭ系のマイクロプロセッサ、Ｉｎｔｅｌ（登録商標）ＩｔａｎｉｕｍＴＭ系のマイクロプロセッサ、及び／又はＩｎｔｅｌ（登録商標）系のＸＳｃａｌｅＴＭ系のプロセッサなど任意のタイプの処理ユニットを有するものであってもよい。さらに、マルチ処理ユニット１３０は、ＳＲＡＭ（Ｓｔａｔｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）などの任意のタイプのキャッシュメモリを有するものであってもよい。記憶装置１４０は、ＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、不揮発性メモリなどを有するものであってもよい。一例として、記憶装置１４０は、所望される場合には、マルチ処理ユニット１３０により実行可能なソフトウェアプログラムを格納するものであってもよい。
【００１５】
本発明の範囲はこれに限定されるものではないが、インタフェース回路１１０は、イーサネット（登録商標）インタフェース、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）インタフェースなどを有するものであってもよい。本発明の実施例では、１以上の入力装置１６０が、データ及びコマンドをメイン処理ユニット１１０に入力するため、インタフェース回路１５０に接続可能である。例えば、入力装置１６０は、キーボード、マウス、タッチ画面、トラックパッド、トラックボール、イソポイント（ｉｓｏｐｏｉｎｔ）、音声認識システムなどを含むものであってもよい。
【００１６】
本発明の範囲はこれに限定されるものではないが、出力装置１７０は、１以上のインタフェース回路１６０を介しメイン処理ユニット１１０に動作可能に接続可能であり、所望される場合には、１以上のディスプレイ、プリンタ、スピーカー及び／又は他の出力装置を含むものであってもよい。例えば、出力装置の１つはディスプレイであるかもしれない。ディスプレイは、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）、ＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）又は他の任意のタイプのディスプレイであってもよい。
【００１７】
本発明の範囲はこれに限定されるものではないが、コンピュータシステム１００は、１以上のストレージ装置１８０を有するものであってもよい。例えば、コンピュータシステム１００は、所望される場合、１以上のハードドライブ、１以上のＣＤドライブ、１以上のＤＶＤドライブ及び／又は他のコンピュータメディア入出力（Ｉ／Ｏ）装置を含むものであってもよい。
【００１８】
本発明の範囲はこれに限定されるものではないが、コンピュータシステム１００は、ネットワーク１９０との接続を介し他の装置とデータを交換することが可能である。ネットワーク接続は、イーサネット（登録商標）接続、デジタル加入者線（ＤＳＬ）、電話線、同軸ケーブルなどの任意のタイプのネットワーク接続であってもよい。ネットワーク１９０は、インターネット、電話ネットワーク、ケーブルネットワーク、無線ネットワークなどの任意のタイプのネットワークであってもよい。
【００１９】
本発明の範囲は本実施例に限定されるものではないが、本発明の当該実施例では、マルチ処理ユニット１３０は、最適化ユニット２００を含むものであってもよい。本発明の実施例によると、最適化ユニット２００は、トレースの２以上の候補命令を検索する処理を実行するものであってもよい。さらに、最適化ユニット２００は、トレース依存性ツリー（ｔｒａｃｅ  ｄｅｐｅｎｄｅｃｙ  ｔｒｅｅ）の深さに従って２以上の候補命令をＳＩＭＤ命令にマージするようにしてもよい。本発明の一部の実施例では、候補命令は、ＳＩＭＤ命令に含まれる同様の及び／又は同一のタイプのオペレーションコードを含むものであってもよい。例えば、最適化ユニット２００は、候補命令の依存性の深さに基づき、同様の処理を実行する候補命令を検索するようにしてもよい。本発明の実施例によると、最適化ユニット２００は、所望される場合、候補命令の少なくとも一部をＳＩＭＤ命令にマージするようにしてもよい。本発明の範囲はこれに限定されるものではないが、最適化ユニット２００は、ソフトウェア、ハードウェア又はソフトウェアとハードウェアの任意の適切な組み合わせにより実現可能であるということが理解されるべきである。
【００２０】
図２を参照するに、本発明の一実施例による図１の最適化ユニット２００のブロック図が示される。本発明の範囲はこれに限定されるものではないが、最適化ユニット２００は、入力トレースバッファ２１０と、シーケンサ２２０と、ベクトル化ユニット２３０と、出力トレースバッファ２４０とを有するものであってもよい。本発明の範囲はこれに限定されるものではないが、本発明の一部の実施例では、ベクトル化ユニット２３０は、第１ステージ２３２と、第２ステージ２３４と、キャッシュメモリなどのメモリ２３６とを有するものであってもよい。
【００２１】
本発明の範囲はこれに限定されるものではないが、入力トレースバッファ２１０は、オペレーションコード（オペ）コードを有する命令トレースを受け付けるようにしてもよい。本発明の一部の実施例では、シーケンサ２２０は、入力トレースバッファ２１０から命令を受け取り、オペレーションコード及び／又は命令トレース（シーケンスなど）をベクトル化ユニット２３０に提供するかもしれない。例えば、命令は、ＬＯＡＤ、ＳＴＯＲＥなどのメモリ処理と、ＡＤＤ、ＳＵＢＴＲＡＣＴ、ＭＵＬＴ、ＳＨＩＦＴ、ＡＮＤなどの算術処理の少なくとも２つのタイプの処理を有するものであるかもしれない。さらに、命令は、レジスタ、定数などの入力値及び出力値を含むものであってもよい。
【００２２】
本発明の実施例によると、ベクトル化ユニット２３０は、シーケンサ２２０からトレースを受け取り、トレース依存性に従って候補命令を検索するようにしてもよい。本発明の一部の実施例では、第１ステージ２３２は、シーケンサ２２０から受け付けたオペコード命令を処理する。例えば、トレースの命令及び／又はオペコードは、ＳＳＡ（Ｓｉｎｇｌｅ  Ｓｔａｔｉｃ  Ａｓｓｉｇｎｍｅｎｔ）形式に変換されるかもしれない。ＳＳＡ形式では、レジスタはトレースに１回のみ書き込み可能であり、残りの処理は、ＳＳＡ条件を満足するため、「バーチャル」レジスタ名を導入するかもしれない。従来のＩＳＡ（Ｉｎｓｔｒｕｃｔｉｏｎ  Ｓｅｔ  Ａｒｃｈｉｔｅｃｔｕｒｅ）により記述されるプログラムコードなどのプログラムコードは、本発明の範囲がこれに限定されるものではないが、同一のレジスタと同一の名前を有する２つのソースレジスタを提供するかもしれない。
【００２３】
本発明の範囲はこれに限定されるものではないが、第１ステージ２３２は、命令を依存性ツリーに配置することによって、ベクトル化のための候補を検索するようにしてもよい。
【００２４】
図３を参照するに、本発明の一実施例によるＳＩＭＤ命令を生成する方法を説明するのに有用な一例となる依存性ツリー３００が示される。本発明の範囲はこれに限定されるものではないが、依存性ツリー３００は、異なる高さの命令を含むものであってもよい。本発明の範囲はこれに限定されるものではないが、依存性ツリー３００のレベルは、同一の高さの命令を含むものであってもよい。第１レベル３１０は命令３１２及び３１４を、第２レベル３２０は命令３２２を、第３レベル３３０は命令３３２及び３３４を、第４レベル３４０は命令３４２を含むものであってもよい。さらに、依存性ツリー３００の深さは、依存性ツリー３００の最初の高さ３１０から最後の高さ３４０までの距離（例えば、当該距離は、レベル間の矢印によって示されるかもしれない）に従って計算されてもよい。
【００２５】
図２を参照するに、本発明の範囲はこれに限定されるものではないが、第１ステージ２３２は、ベクトル化のための候補命令をメモリ２３６に格納する。本発明の実施例によると、第２ステージ２３４は、同一又は同様のレベルを有する同様のオペコードをメモリ２３６から検索し、ＳＩＭＤ命令を生成するようにしてもよい。さらに、第２ステージ２３２は、元のトレース命令をＳＩＭＤ命令に置換してもよく、ＳＩＭＤ命令を出力トレースバッファ２４０に格納するようにしてもよい。
【００２６】
本発明の範囲はこれに限定されるものではないが、最適化ユニット２００の第１ステージ２３２と第２ステージの処理が、一例となるＣ言語を模した擬似コードアルゴリズムにより記述可能である。
【００２７】
本発明の範囲はこれに限定されるものではないが、Ｃ言語を模した擬似コードアルゴリズムの第１部分は、定数、変数構造などを定義するものである。
【００２８】
例えば、トレースの最大命令数は、
【００２９】
【表１】
2011165216.tif 000003
として定義される。
【００３０】
命令の最大ソース数は、
【００３１】
【表２】
2011165216.tif 000004
として定義される。
【００３２】
命令の最大デスティネーション数は、
【００３３】
【表３】
2011165216.tif 000005
として定義される。
【００３４】
トレース範囲及び内部バッファサイズは、
【００３５】
【表４】
2011165216.tif 000006
として定義される。
【００３６】
Ｃ言語を模した擬似コードアルゴリズムによると、命令構造は、当該命令がベクトル化に適しているか示すブール変数、デスティネーションレジスタ、オペコード、ソースレジスタを有するかもしれない。この命令構造は、
【００３７】
【表５】
2011165216.tif 000007
として定義される。
【００３８】
Ｃ言語を模した擬似コードアルゴリズムによると、トレースは、ＭＡＸ＿ＴＲＡＣＥ＿ＳＩＺＥのエントリのベクトルによって表される高々ＭＡＸ＿ＴＲＡＣＥ＿ＳＩＺＥの命令のシーケンスとして定義される。さらに、ツー・デミニュション（ｔｗｏ  ｄｉｍｉｎｕｔｉｏｎｓ）（２Ｄ））トレース依存ビットマップが、トレースの命令の有効性を示すのに利用可能である。トレースの実際の命令数はＩＮＩＴＩＡＬ＿ＴＲＡＣＥ＿ＳＩＺＥであるかもしれない場合、最初のＩＮＩＴＩＡＬ＿ＴＲＡＣＥ＿ＳＩＺＥのエントリのみが有効であるかもしれない。
【００３９】
【表６】
2011165216.tif 000008
Ｃ言語を模した擬似コードアルゴリズムによると、メモリ２３６に格納されるＳＩＭＤマトリックスは、オペレーションコードを有し、Ｍ個のオペコード位置のＮ本のラインを保持するかもしれない（例えば、合計でＮｘＭｘｌｏｇ（ＭＡＸ＿ＴＲＡＣＥ＿ＳＩＺＥ）ビットなど）。
【００４０】
【表７】
2011165216.tif 000009
本発明の範囲はこれに限定されるものではないが、本実施例のアルゴリズムでは、最適化ユニット２３０の第１ステージ２３２は、昇順にトレースの命令を繰り返すことによってトレースの候補命令を検索する。第１ステージ２３２は、リネーミング処理中に構成されるトレース［ｉ］のすべてのプレデセッサ（ｐｒｅｄｅｃｅｓｓｏｒ）を比較する。さらに、第１ステージ２３２は、トレース［ｉ］の依存性の高さ（レベルなど）と、それの可能性のある最先のスケジューリング位置を計算することによって、依存性ツリー（依存性ツリー３００など）における命令の高さ（レベルなど）をタグ付けするようにしてもよい。
【００４１】
【表８】
2011165216.tif 000010
本発明の範囲はこれに限定されるものではないが、本例のＣ言語を模した擬似コードアルゴリズムでは、第２ステージ２３４は、ベクトル化に適した命令（マトリックスＳＩＭＤなど）をメモリ２３６から検索する。例えば、適切な命令は、同じ依存性ツリーの高さ（レベルなど）におけるより以前の命令トレース［ｊ］であるかもしれない。さらに、第２ステージ２３６は、ＳＩＭＤ命令を生成し、以下に示すように、元の命令をＳＩＭＤ命令と置換するかもしれない。
【００４２】
【表９】
2011165216.tif 000011
本発明の一部の実施例によると、最適化ユニット２００は、メモリにアクセスする２つの命令が、連続するメモリアドレスにアクセスする場合、単一のＳＩＭＤ命令に合成されるというルールに従って、ＳＩＭＤ命令を生成するようにしてもよい。すなわち、これら２つの命令によってアクセスされるデータが（少なくともバーチャルメモリ空間において）隣接することは、それらのメモリアドレスと対応するデータ長から計算することが可能である。例えば、以下の命令を含むトレースでは、すなわち、
１．ＥＳＰ＋４から４バイトをＬＯＡＤする。
２．ＥＳＰ＋１２から４バイトをＬＯＡＤする。
３．ＥＳＰ＋８から４バイトをＬＯＡＤする。
では、命令は、所望される場合には、単一のＳＩＭＤ命令である「ＥＳＰ＋４から１２バイトをＬＯＡＤする」に合成されるかもしれない。
【００４３】
図４を参照するに、テーブル４００が示される。本発明の範囲はこれに限定されるものではないが、テーブル４００は、依存性ツリー（依存性ツリー３００など）における当該命令のレベルを示すレベルカラムと、入力トレースバッファ２１０及びシーケンサ２２０によって提供される元の命令を示す元のトレースカラムと、出力トレースバッファ２４０における命令を示すベクトル化後のトレースとを含む。テーブル４００の行は、命令のレベルと、元の命令とベクトル化後の命令とを示すかもしれない。
【００４４】
本発明の範囲はこれに限定されるものではないが、最適化ユニット２００は、トレース依存性グラフの深さ（トレース命令の高さなど）をタグ付けするものであってもよい。さらに例えば、テーブル４００によると、最適化ユニット２００は、ベクトル化のための候補と同一のレベル（レベル２など）にある命令「ＥＡＸ←ＬＯＡＤ（ＥＳＰ，４）」と「ＥＢＸ←ＬＯＡＤ（ＥＳＰ，８）を特定し、所望される場合には、これらの命令をＳＩＭＤ命令「ＥＡＸ，ＥＢＸ←ＳＩＭＤ＿ＬＯＡＤ（ＥＳＰ，４）」に合成するようにしてもよい。本発明の範囲はこれに限定されるものではないが、最適化ユニット２００は、共通の処理（ＬＯＡＤなど）によるものであって、トレース依存性グラフの同じ深さ（高さなど）にある２つの命令が、それらの一定でないすべてのソース（レジスタなど）が同様のものである場合、及び／又は一定又は直接的なソースが異なる場合、単一のＳＩＭＤ命令（ＳＩＭＤ＿ＬＯＡＤなど）に合成されるというルールに従うことによって、ＳＩＭＤ命令を生成するようにしてもよい。
【００４５】
図５を参照するに、本発明の他の実施例によるテーブル５００が示される。本発明の範囲はこれに限定されるものではないが、テーブル５００は、依存性ツリー（依存性ツリー３００など）における元の命令のレベルを示すレベルカラムと、入力トレースバッファ２１０及びシーケンサ２２０によって提供される元の命令を示す元のトレースカラムと、ＳＳＡなどの基本的変換後の命令のレベルを示すレベルカラムと、変換後の命令を示すカラムと、出力トレースバッファ２４０におけるベクトル化後のトレースの命令を示すカラムとを有するものであってもよい。テーブル５００の行は、命令のレベルと、基本的変換後の命令の元の命令レベルと、基本的変換後の命令と、ベクトル化後の命令とを示すものであってもよい。
【００４６】
本発明の範囲はこれに限定されるものではないが、一例となるテーブル５００によると、最適化ユニット２００は、トレースにおける元の命令の高さをタグ付けする。最適化ユニット２００は、トレースの命令をＳＳＡ形式に変換するかもしれない。最適化ユニット２００は、トレースがＳＳＡ形式に変換されることを利用することによって、トレースの命令を変換してもよい。最適化ユニット２００は、
例えば、
【００４７】
【表１０】
2011165216.tif 000012
などのベクトル化のための候補命令と同一レベルの変換された命令をタグ付けし、それらをＳＩＭＤ命令
【００４８】
【表１１】
2011165216.tif 000013
にそれぞれ合成するようにしてもよい。
【００４９】
本発明の特徴がここで図示及び説明されたが、当業者には、多数の改良、置換、変更及び均等が想起するであろう。従って、添付した請求項が、本発明の真の趣旨に属するこのようなすべての改良及び変更をカバーするものであるということは理解されるべきである。
【符号の説明】
【００５０】
１００  コンピュータシステム
１１０  メイン処理ユニット
１２０  電源
１３０  マルチ処理ユニット
１４０  記憶装置
【図１】
2011165216.tif 000014
【図２】
2011165216.tif 000015
【図３】
2011165216.tif 000016
【図４】
2011165216.tif 000017
【図５】
2011165216.tif 000018