JP5518087B2 - 範囲検出を行うための命令及びロジック - Google Patents

Description

本発明は、概して、情報処理の分野に関し、特に、コンピュータシステム及びマイクロプロセッサにおける範囲検出を実行する分野に関する。

例えば、マイクロプロセッサのような、コンピュータハードウェアにおける数学的関数の性能は、キャッシュ又はメインメモリ等のロケーションに格納されたルックアップテーブル（ＬＵＴ）の使用に依存する。ハードウェアにおいて数学的関数が実行されるときには、単一命令複数データ（ＳＩＭＤ）命令は、複数のメモリオペレーションを実行して、ＬＵＴにアクセスする場合がある。例えば、複数の入力オペランドに基づく関数を実行するＳＩＭＤ命令は、ＳＩＭＤ関数に出力される結果を取得するために、入力オペランド各々について、ＬＵＴにアクセスをする。一部のプロセッサアーキテクチャでは、複数のＬＵＴに対する並列アクセス機能が提供されず、１以上のＬＵＴにアクセスするのに、同じメモリアクセスロジックが使用されているため、これら複数のＬＵＴアクセスは、並列的にではなく、順次的に発生し、その結果、ＳＩＭＤ演算の実行性能が制限されてしまっていた。

あるアルゴリズムでは、数学的関数を、スプライン又はその他の多項式による手法を使用して評価してもよい。従来技術の幾つかの例では、数学的関数を評価するのに使用するスプライン関数は、範囲検出、係数照合及び多項式計算のような処理を実行する複数のソフトウェアオペレーションを必要とする。したがって、数学的関数を評価するのにスプラインを使用すると、計算量が非常に多くなり性能が相対的に低くなってしまうことから、コンピュータプログラムにおけるスプライン計算の実用性は限定されてしまっていた。

本発明の実施形態は例示を目的として記載されており、限定することを意図しておらず、添付の図面において使用されている同様な参照番号は、同様な要素を示している。

本発明の実施形態の少なくとも一つが使用されてもよいマイクロプロセッサのブロック図である。 本発明の実施形態の少なくとも一つが使用されてもよい共有バスコンピュータシステムのブロック図である。 本発明の実施形態の少なくとも一つが使用されてもよいポイント・ツー・ポイント相互接続コンピュータシステムのブロック図である。 一実施形態に係る、複数の領域に分割されたスプラインを示した図である。 一実施形態に係る、領域検出命令に応答してスプライン内での領域検出を加速させるのに使用してもよいロジックを示した図である。 一実施形態に係る、領域検出命令に応答してスプライン内での領域検出を加速させるのに使用してもよいロジックを示した図である。 本発明の実施形態の少なくとも１つを実行するのに使用されてもよいオペレーションのフロー図である。

本発明の実施形態は、マイクロプロセッサ及びコンピュータにおける数学的計算性能を改善するのに使用されてもよい。幾つかの実施形態では、スプライン計算は、従来のスプライン計算よりも、高い性能レベルでの様々な数学的オペレーションを実行するのに使用される。少なくとも１つの実施形態において、スプライン計算を実行するのに伴う、複数の最も時間を消費する及び最もリソースを消費するオペレーションのうちの少なくとも１つの速度を高めることにより、スプライン計算性能の改善を図る。また、一実施形態において、スプライン計算で使用される様々な多項式に対応するスプライン内の範囲検出を加速させるために、範囲検出命令及び対応するハードウェアロジックが提供される。

図１は、本発明の実施形態の少なくとも一つが使用されてもよいマイクロプロセッサのブロック図である。具体的には、図１には、１以上のプロセッサコア１０５、１１０を有するマイクロプロセッサ１００が示され、プロセッサコアはそれぞれ、ローカルキャッシュ１０７、１１３と関連付けられている。また、図１には、各ローカルキャッシュ１０７、１１３に格納されている少なくとも一部の情報のバージョンが記憶されていてもよい共有キャッシュメモリ１１５が示されている。幾つかの実施形態では、マイクロプロセッサ１００は、図１に示されていないその他のロジックを含んでもよく、コンピュータシステム内でＩ／Ｏ制御のようなその他の機能を実行するロジックと共に、例えば、集積メモリコントローラ、集積グラフィックスコントローラを含んでもよい。一実施形態において、マルチプロセッサシステムにおける各マイクロプロセッサ、又はマルチコアプロセッサにおける各プロセッサコアは、一実施形態に係る命令に応答して範囲検出を実行するべく、ロジック１１９を含む又はロジック１１９と関連付けられていてもよい。

図２は、本発明の実施形態の少なくとも一つが使用されてもよい、例えば、フロントサイドバス（ＦＳＢ）コンピュータシステムを示している。プロセッサ２０１、２０５、２１０又は２１５のいずれも、プロセッサコア２２３、２２７、２３３、２３７、２４３、２４７、２５３、２５７のうちの１つ内に存在する、又は関連付けられたローカルレベル１（Ｌ１）キャッシュメモリ２２０、２２５、２３０、２３５、２４０、２４５、２５０、２５５のうちのいずれかから、情報にアクセスすることができる。また、プロセッサ２０１、２０５、２１０又は２１５のいずれも、チップセット２６５を介して、共有レベル２（Ｌ２）キャッシュ２０３、２０７、２１３、２１７のうちのいずれか１つ、又はシステムメモリ２６０から、情報にアクセスすることができる。図２に示されている１以上のプロセッサは、一実施形態に係る範囲検出命令を実行するべく、ロジック２１９を含む、又はロジック２１９と関連付けられていてもよい。

図２に示したＦＳＢコンピュータシステムに加えて、本発明の様々な実施形態と併せてその他のシステム構成を使用してもよく、例えば、ポイント・ツー・ポイント（Ｐ２Ｐ）相互接続システム及び環状相互接続システムを使用してもよい。例えば、図示した例の図３のＰ２Ｐシステムは、プロセッサ３７０、３８０の２つしか含んでいないが、これより多い数のプロセッサが含まれていてもよい。プロセッサ３７０、３８０はそれぞれ、メモリ３２、３４と接続するためのローカルメモリ制御ハブ（ＭＣＨ）３７２、３８２を含んでもよい。プロセッサ３７０、３８０は、ポイント・ツー・ポイント（ＰｔＰ）インターフェース回路３７８、３８８を使用したＰｔＰインターフェース３５０を介して、データを交換してもよい。プロセッサ３７０、３８０はそれぞれ、ポイント・ツー・ポイント回路３７６、３９４、３８６、３９８を使用したＰｔＰインターフェース３５２、３５４を介して、チップセット３９０内のデータを交換してもよい。また、チップセット３９０は、高性能グラフィックスインターフェース３３９を介して高性能グラフィックス回路３３８とデータを交換してもよい。本発明の実施形態は、１以上のプロセッサコアを有するあらゆるプロセッサ内、又は図３の各ＰｔＰバスエージェント内に位置してもよい。一実施形態において、いずれのプロセッサコアも、（図示しない）ローカルキャッシュメモリを含む、又はローカルキャッシュメモリと関連付けられていてもよい。共有キャッシュ（図示せず）は、プロセッサのうちのどちらか１つに含まれていてもよいし、２つのプロセッサの外側に設けられていてもよく、また、プロセッサが低電力モードに入った場合に、プロセッサのいずれか又は両方のローカルキャッシュ情報が共有キャッシュメモリに格納されるように、ｐ２ｐ相互接続を介して共有キャッシュはプロセッサと接続される。図３の複数のプロセッサ又はコアのうちの１以上が、一実施形態に係る範囲検出命令を実行するべく、ロジック３１９を含む、又はロジック３１９と関連付けられていてもよい。

スプライン計算における、ルックアップテーブル（ＬＵＴ）の使用、及び関連するコストのかかるメモリアクセスの使用の必要性を除外することができる。図４は、例えば、１次スプライン関数を示している。図４において、"Ｘ"は、データが含まれている８個の要素からなる入力ベクトルであり、"Ｘｉｎ"は、それぞれが３２ビットで表され、ベクトルＸにおいて全部で２５６ビットになるようになっている。ベクトルＹの要素"Ｙｏｕｔ"は、所与の入力"Ｘｉｎ"に対するスプライン関数のベクトルＹｎｏ要素であり、Ｗ＝Ｙ（Ｘ）となる。範囲検出、係数照合及び多項式計算を含むスプライン計算オペレーションを使用して、ベクトルＷの要素の値を求めてもよい。少なくとも１つの実施形態は、スプライン関数の計算において範囲検出を実行する命令及びロジックを含む。幾つかの実施形態では、ベクトルＸの要素の大きさは８ビットであるが、別の実施形態では、１６ビット、３２ビット、６４ビット、１２８ビット等であってもよい。また、幾つかの実施形態では、Ｘの要素は、整数、浮動小数点、１倍又は２倍精度浮動小数点等であってもよい。

一実施形態では、範囲検出ロジックは、範囲検出命令を実行するデコードロジック及び実行ロジックを含み、範囲検出命令は、式、"範囲ベクトル（Ｒ）＝範囲＿検出（入力ベクトル（Ｘ）、範囲限定ベクトル（ＲＬ））"を実行するための命令フォーマット及び制御フィールドを有する。ここで、Ｒは図５に記載されるロジックにより生成される範囲ベクトル、Ｘは入力ベクトル、ＲＬは、スプライン関数各々の最初のＸｉｎを含むベクトルである。例えば、一実施形態において、ベクトルＲＬは、図４の各範囲の最初のＸｉｎ（０、１０、３０、５０、７０、８０、２５５）を含む。

一実施形態において、範囲検出は、入力ベクトルＸ内に提供される各入力点に従って、図４に示されているスプライン関数の特定の範囲を照合し、結果をＳＩＭＤレジスタに格納する。次に記載する例では、入力ベクトルＸ、及び図４に示したスプラインに対応する範囲検出ベクトルが示されている。以下の例では、１６ビットの固定小数点入力に対してのオペレーションが記載されているが、同様の手法が、８ビット及び３２ビット固定小数点及び浮動小数点にも適用することができ、現在の及び将来のベクトル拡張で使用される様々な種類のデータにも適用可能である。

図４のｘ軸に沿ったＸｉｎの値をそれぞれ含む要素からなる入力ベクトルＸが、次のような入力ベクトルであるとする。

上記の入力ベクトルＸ、及び図４に示されたスプラインに基づく範囲検出ベクトルは、次のようになる。

一実施形態において、図４のスプラインに従って入力ベクトルを演算することにより、上記の範囲検出ベクトルを生成すべく、命令が実行される。一実施形態において、命令は、入力ベクトル要素を、範囲限界の各要素と比較する（図４においては、０、１０、３０、５０、７０、８０）。一実施形態において、範囲限界の各々は、ＳＩＭＤレジスタに伝達され、入力ベクトルＸとの比較を行ってもよい。一実施形態において、比較オペレーションの結果が０又は−１となった場合には、比較結果、すなわち、比較結果の引き算及び足し算によって、入力ベクトルＸにおける各入力点が含まれたスプラインの範囲が生成されることを表している。比較オペレーションを実行するロジックが図５に示されており、ｘ_ｉは、入力ベクトルＸ内の入力点を表し、ｔ_iは、図４のスプラインの範囲限界を表し、ｒ_ｉは、入力点ｘ_ｉに対する範囲検出ベクトルＲ内の結果の範囲を表す。他の実施形態において、比較オペレーションを別の値（例えば、１及び０）を用いて結果を表してもよく、比較、加算又は減算、及び比較された値の蓄積を使用して比較オペレーションが実行され、範囲検出レジスタＲが生成される。

図５Ａは、一実施形態に係る範囲検出命令を実行するのに応答して、範囲検出ベクトルＲを生成するのに使用されてもよいロジックを示している。一実施形態において、ロジック５００ａは、比較ロジック５０５ａによって範囲限界ベクトル５１０ａと比較される入力ベクトルＸ５０１ａを含み、範囲限界ベクトル５１０ａは各要素に、入力ベクトルＸのｉ番目の要素に対応するスプライン範囲の範囲限界値を含む。一実施形態において、入力ベクトル５０１ａの要素は、比較ロジック５０５ａによって、範囲限界レジスタ５１０ａの対応する要素と比較される。一実施形態において、ゼロベクトル５１５ａの要素は、入力ベクトル５０１ａと範囲限界ベクトル５１０ａとの比較結果の負の値に加算（５１７ａ）され、比較結果の加算結果の要素のそれぞれにおいて、０又は−１が生成される。次に、入力ベクトル５０１ａは、範囲限界ベクトル５２０ａの対応する要素と比較されて、比較結果の負の値が、１つ前の比較結果に加算される。このようなプロセスを、範囲限界ベクトル５１０ａの各要素について行い、最終的に範囲検出ベクトル５２５ａを得る。

一実施形態において、図５Ａのロジックを、少なくとも１つの命令セットアーキテクチャを使用したプログラムと共に利用してもよく、命令セットアーキテクチャは、以下のような疑似コードで例示できる。

別の実施形態では、範囲検出ベクトルＲを決定する他の手法を使用してもよく、例えば、範囲限界ベクトル要素に対して、二分探索を実行するロジックを含んでもよい。図５Ｂは、範囲検出ベクトルＲを生成するのに使用してもよい、一実施形態に係る二分探索木を示した図である。図５Ｂの二分探索木５００ｂでは、入力ベクトルＸ５０１ｂの各要素は、範囲限界ベクトルの各要素５１０ｂと比較され、真ん中のベクトル要素（Ｔ４、入力及び範囲限界ベクトルが８つの要素で構成されている場合）から開始して、ベクトルの前半部分及び後半部分（Ｔ５‐Ｔ８及びＴ３‐１）へと続く。一実施形態において、次に示すような疑似コードにより、１つの命令セットアーキテクチャからの命令を使用して、図５Ｂの二分探索木の機能を例示できる。

上記の疑似コードにおいて、Ｔは、範囲限界ベクトルを表し、Ｉは、入力ベクトルＸ及び範囲限界ベクトルＴのｉ番目の要素を表す。

一実施形態において、命令及び対応するロジックが、範囲検出ベクトルＲを生成するのに使用される。範囲検出ベクトルＲが決定されると、問題となっている特定の数学的オペレーションに関連付けられたスプライン関数の値をもとめる計算に関連する、係数照合及び多項式計算オペレーションを含む別のオペレーションを実行できるようになる。

一実施形態において、図４のスプラインの範囲それぞれに対応する多項式の各々は、対応する係数を有する。係数照合では、係数ベクトル要素と、本発明の一実施形態で生成された範囲検出ベクトル要素とを照合する。図４に示した例では、６つの範囲が存在し、次のような多項式で表されてもよい。

係数照合は、範囲検出段階の結果に基づく。得られた係数ベクトルの数は、最も高次の多項式の次数＋１と等しい。上述の例に戻り、図４で記載された入力ベクトルＸに対して得られた係数ベクトルＣ_１及びＣ_２は、次のように例示される。

上記の例の全ての多項式の次数は、１であり、得られる係数ベクトルの数は２になる。一実施形態において、Ｃ_１及びＣ_２ベクトルは、シャッフル命令を使用して計算され、図５Ａ及び図５Ｂに示された範囲検出段階の出力に基づいて、２つの係数ベクトルＣ_１及びＣ_２の対応する要素に、適切な係数を格納する。

入力ベクトルＸに対応する多項式の係数を計算した後、入力ベクトルＸにおける各入力値に対して、多項式評価計算を実行してもよい。一実施形態において、多項式計算は、２つの主要なオペレーションに分割できる。第１のオペレーションは、スプラインの範囲の開始点からの各入力値のオフセットを求めることを含む。一実施形態において、例えば、シャッフル命令を使用して、各範囲の開始点と、各入力点とを照合することにより、オフセットを見つける段階を実現してもよい。図４のスプラインの各範囲の開始点からのオフセットは、対応する入力ベクトル要素から、各範囲の開始点の値を引き算することによって計算される。例えば、図４のスプラインにおける点７７は、範囲５に割り当てられる。範囲５の開始点は、７０であるから、割り当てられた範囲の開始点からのオフセットは７となる。第２のオペレーションは、各入力ベクトル要素に対して、出力ベクトル要素を計算することを含む。最終的な出力ベクトルを計算するために、範囲の開始点でのオフセットを見つけ、これを、関係する多項式の入力要素として設定する。例えば、範囲５の多項式は、ｙ＝２＊ｘ−２０で表される。入力ベクトル要素７７に対しては、オフセット７を得ることから、点７７に対する最終的な値は、Ｙ＝２＊（オフセット）−２０＝２＊（７）−２０＝−６となる。入力ベクトル要素に対応する残りの多項式を計算した後、計算結果が、結果ベクトルに格納される。開始範囲値がＢ、オフセットベクトル値がＯ、及び出力ベクトル値がＹであるベクトル値を、以下に例示する。

出力ベクトルＹは、一実施形態によれば、式によって表すことができ、この例の場合には、出力ベクトルＹは、Ｙ＝Ｏ＊Ｃ１＋Ｃ２で計算される。

図６は、本発明の実施形態の少なくとも１つに関連して使用されてもよいオペレーションのフロー図である。一実施形態において、オペレーション６０１では、範囲検出ベクトルが生成される。一実施形態において、二分探索及び本明細書に例示されたその他のロジックのようなプロセスに従って、入力ベクトル要素の各々に対して、範囲検出ベクトルが生成される。オペレーション６０５では、係数照合が行われ、入力ベクトル要素に応じた、スプラインの各範囲に対応する多項式の係数が生成される。オペレーション６１０において、多項式計算は、入力ベクトルの要素それぞれに対して行われ、計算結果が結果ベクトルに格納される。

少なくとも１つの実施形態の１以上の側面を、プロセッサ内の様々なロジックを表現する機械可読媒体に格納された代表的なデータによって実装してもよく、機械によって読み込まれると機械に、本明細書に記載した手法を実行するロジックを作成させる。このような代表的なものとして知られる"ＩＰコア"を、有形の機械可読媒体（テープ）に格納し、様々な顧客又は製造設備に供給し、ロジック又はプロセッサを実際に作成する作成機械に取り込んでもよい。

マイクロアーキテクチャメモリ領域アクセスに関する方法及び装置について説明した。上記の説明は、例示することを目的としており、制限することを意図していない。上述の説明を読み理解することにより、多くの別の実施形態が当業者に明らかとなる。したがって、添付の特許請求の範囲、及び特許請求の範囲に記載される均等物の全てを参照することにより、本発明の範囲が決定されるべきである。

Claims (17)

1. 複数の入力ベクトル要素のそれぞれと、スプライン関数の複数の範囲を表す複数の範囲限界ベクトル要素のうちの対応する範囲限界ベクトル要素とを比較して、それぞれの入力ベクトル要素が含まれるスプライン多項式の範囲を比較結果に基づき検出して範囲値を決定する範囲検出命令を実行するロジックを備える装置。
2. 前記ロジックは、入力ベクトルの要素それぞれと、スプライン関数の複数の範囲を表す複数の範囲限界ベクトル要素のうち、対応する範囲限界ベクトル要素とを比較する二分探索ロジックを含む請求項１に記載の装置。
3. 前記ロジックは、前記範囲値を含む範囲値ベクトルを格納する範囲ベクトルストレージを含む請求項１または２に記載の装置。
4. 前記ロジックは、前記複数の入力ベクトル要素を格納する入力ベクトルストレージを含む請求項１から３のいずれか一項に記載の装置。
5. 前記ロジックは、前記複数の入力ベクトル要素に対応する複数の係数ベクトル要素を格納する、少なくとも１つの係数ベクトルストレージを含む請求項１から４のいずれか一項に記載の装置。
6. 前記ロジックは、前記複数の入力ベクトル要素に対応する複数のオフセットベクトル要素を格納する、少なくとも１つのオフセットベクトルストレージを含む請求項１から５のいずれか一項に記載の装置。
7. 前記ロジックは、前記複数の入力ベクトル要素に対応する複数の出力ベクトル要素を格納する、少なくとも１つの出力ベクトルストレージを含む請求項１から６のいずれか一項に記載の装置。
8. コンピュータに設けられた範囲検出ロジックが、スプライン関数の複数の入力値のそれぞれと、スプライン関数の複数の範囲を表す複数の範囲限界ベクトル要素のうちの対応する範囲限界ベクトル要素とを比較して、複数の入力値のそれぞれが含まれる複数の範囲値のそれぞれを含む範囲ベクトルを比較結果に基づき生成する、範囲検出命令を実行する段階と、
   コンピュータが、前記スプライン関数の前記複数の入力値に対応した複数の多項式に対応する複数の係数を生成する係数照合オペレーションを実行する段階と、
   コンピュータが、前記複数の入力値に対応する複数の出力値を生成する多項式の値を求める計算を実行する段階と
   を備える方法。
9. 前記範囲検出ロジックは、前記複数の入力値のそれぞれと、スプライン関数の複数の範囲を表す複数の範囲限界ベクトル要素のうち、対応する範囲限界ベクトル要素とを比較する二分探索ロジックを含む請求項８に記載の方法。
10. 範囲検出命令を格納するストレージと、
    前記範囲検出命令の実行に応答して、複数の入力ベクトル要素のそれぞれと、スプライン関数の複数の範囲を表す複数の範囲限界ベクトル要素のうちの対応する範囲限界ベクトル要素とを比較して、それぞれの入力ベクトル要素が含まれるスプライン多項式の範囲を比較結果に基づき検出して範囲値を決定するプロセッサと
    を備えるシステム。
11. 前記プロセッサは、入力ベクトルの要素それぞれと、スプライン関数の複数の範囲を表す複数の範囲限界ベクトル要素のうち、対応する範囲限界ベクトル要素とを比較する二分探索ロジックを含む請求項１０に記載のシステム。
12. 前記プロセッサは、前記範囲値を含む範囲値ベクトルを格納する範囲ベクトルストレージを含む請求項１０または１１に記載のシステム。
13. 前記プロセッサは、前記複数の入力ベクトル要素を格納する入力ベクトルストレージを含む請求項１０から１２のいずれか一項に記載のシステム。
14. 前記プロセッサは、前記複数の入力ベクトル要素に対応する複数の係数ベクトル要素を格納する、少なくとも１つの係数ベクトルストレージを含む請求項１０から１３のいずれか一項に記載のシステム。
15. 前記プロセッサは、前記複数の入力ベクトル要素に対応する複数のオフセットベクトル要素を格納する、少なくとも１つのオフセットベクトルストレージを含む請求項１０から１４のいずれか一項に記載のシステム。
16. スプライン関数の複数の入力値のそれぞれと、スプライン関数の複数の範囲を表す複数の範囲限界ベクトル要素のうちの対応する範囲限界ベクトル要素とを比較して、複数の入力値のそれぞれが含まれる複数の範囲値のそれぞれを含む範囲ベクトルを比較結果に基づき生成する、範囲検出命令を実行する第１ロジックと、
    前記スプライン関数の前記複数の入力値に対応した複数の多項式に対応する複数の係数を生成する係数照合オペレーションを実行する第２ロジックと、
    前記複数の入力値に対応する複数の出力値を生成する多項式の値を求める計算を実行する第３ロジックと
    を備えるプロセッサ。
17. 前記第１ロジックは、前記複数の入力値のそれぞれと、スプライン関数の複数の範囲を表す複数の範囲限界ベクトル要素のうち、対応する範囲限界ベクトル要素とを比較する二分探索ロジックを含む請求項１６に記載のプロセッサ。

Images