(57)【要約】  システムおよび方法は、テーブルのエントリを検索することに関する。プロセッサが、インデックスの第1のサブセットを指定する第1の単一命令複数データ(SIMD)命令を含む、1つまたは複数のSIMD命令を受け取る。テーブルエントリの第1のサブセットが、クロスバーを使用して、インデックスの第1のサブセットを用いて検索される。第1のSIMD命令の第1のベクトル出力は、クロスバーの出力がテーブルエントリの所望のサブセットに属するかどうかに基づくものである。同様に、第2、第3、および第4のSIMD命令が、クロスバーを使用して残りのテーブルエントリを検索するためにインデックスの対応する第2、第3、および第4のサブセットを指定する。クロスバーのサイズは、テーブルエントリを検索するために使用されるインデックスのサブセットにおけるインデックスの数に基づくものである。
2018523245.tif 000002
【特許請求の範囲】
【請求項１】
メモリに記憶されたテーブルエントリをプロセッサによって検索する方法であって、
インデックスの第1のサブセットを指定する第1の単一命令複数データ(SIMD)命令を受け取るステップと、
前記プロセッサによって実装されるクロスバーにおいて、インデックスの前記第1のサブセットを用いてテーブルエントリの第1のサブセットを検索するステップと、
前記クロスバーの出力に基づいて前記第1のSIMD命令の第1のベクトル出力を生成するステップと
を含む、方法。
【請求項２】
前記クロスバーの前記出力が、テーブルエントリの所望のサブセットに属する場合、前記クロスバーの前記出力に等しいものとして前記第1のベクトル出力を生成するステップをさらに含む、請求項1に記載の方法。
【請求項３】
前記クロスバーの前記出力が、テーブルエントリの所望のサブセットに属さない場合、0値に等しいものとして前記第1のベクトル出力を生成するステップをさらに含む、請求項1に記載の方法。
【請求項４】
インデックスの前記第1のサブセットが不連続である、請求項1に記載の方法。
【請求項５】
インデックスの第2のサブセットを指定する第2のSIMD命令を受け取るステップと、
前記クロスバーにおいて、インデックスの前記第2のサブセットを用いてテーブルエントリの前記第1のサブセットを検索するステップと
をさらに含む、請求項1に記載の方法。
【請求項６】
インデックスの前記第1のサブセットとインデックスの前記第2のサブセットが重複しない、請求項5に記載の方法。
【請求項７】
インデックスの前記第1のサブセットが偶数番号のインデックスを含み、インデックスの前記第2のサブセットが奇数番号のインデックスを含む、請求項5に記載の方法。
【請求項８】
インデックスの第3のサブセットを指定する第3のSIMD命令を受け取るステップと、
前記クロスバーにおいて、テーブルエントリの第2のサブセットを検索するステップと
をさらに含み、テーブルエントリの前記第1のサブセットとテーブルエントリの前記第2のサブセットが重複しない、請求項1に記載の方法。
【請求項９】
インデックスの第4のサブセットを指定する第4のSIMD命令を受け取るステップと、
前記クロスバーにおいて、テーブルエントリの前記第2のサブセットを検索するステップと
をさらに含む、請求項8に記載の方法。
【請求項１０】
インデックスの前記第3のサブセットとインデックスの前記第4のサブセットが重複しない、請求項9に記載の方法。
【請求項１１】
インデックスの前記第3のサブセットが偶数番号のインデックスを含み、インデックスの前記第4のサブセットが奇数番号のインデックスを含む、請求項9に記載の方法。
【請求項１２】
前記クロスバーのサイズが、インデックスの前記第1のサブセットにおけるインデックスの数に基づく、請求項1に記載の方法。
【請求項１３】
テーブルを含むメモリと、
第1の単一命令複数データ(SIMD)命令を実行するように構成されたプロセッサと
を備え、前記プロセッサが、
前記第1のSIMD命令によって指定されたインデックスの第1のサブセットを用いて、前記テーブルのテーブルエントリの第1のサブセットを検索するように構成されたクロスバーと、
前記クロスバーの出力に基づいて前記第1のSIMD命令の第1のベクトル出力を生成するための論理構成要素と
を備える、装置。
【請求項１４】
前記論理構成要素が、前記クロスバーの前記出力がテーブルエントリの所望のサブセットに属する場合、前記クロスバーの前記出力に等しいものとして前記第1のベクトル出力を生成するためにANDゲートを含む、請求項13に記載の装置。
【請求項１５】
前記ANDゲートが、前記クロスバーの前記出力がテーブルエントリの所望のサブセットに属さない場合、0値に等しいものとして前記第1のベクトル出力を生成するように構成される、請求項14に記載の装置。
【請求項１６】
インデックスの前記第1のサブセットが不連続である、請求項13に記載の装置。
【請求項１７】
前記プロセッサが、第2のSIMD命令を実行するようにさらに構成され、前記クロスバーが、前記第2のSIMD命令によって指定されたインデックスの第2のサブセットを用いてテーブルエントリの前記第1のサブセットを検索するようにさらに構成される、請求項13に記載の装置。
【請求項１８】
インデックスの前記第1のサブセットとインデックスの前記第2のサブセットが重複しない、請求項17に記載の装置。
【請求項１９】
インデックスの前記第1のサブセットが偶数番号のインデックスを含み、インデックスの前記第2のサブセットが奇数番号のインデックスを含む、請求項17に記載の装置。
【請求項２０】
前記プロセッサが、第3のSIMD命令を実行するようにさらに構成され、前記クロスバーが、前記第3のSIMD命令によって指定されたインデックスの第3のサブセットを用いてテーブルエントリの第2のサブセットを検索するようにさらに構成され、テーブルエントリの前記第1のサブセットとテーブルエントリの前記第2のサブセットが重複しない、請求項13に記載の装置。
【請求項２１】
前記プロセッサが、第4のSIMD命令を実行するようにさらに構成され、前記クロスバーが、前記第4のSIMD命令によって指定されたインデックスの第4のサブセットを用いてテーブルエントリの前記第2のサブセットを検索するようにさらに構成される、請求項20に記載の装置。
【請求項２２】
インデックスの前記第3のサブセットとインデックスの前記第4のサブセットが重複しない、請求項21に記載の装置。
【請求項２３】
インデックスの前記第3のサブセットが偶数番号のインデックスを含み、インデックスの前記第4のサブセットが奇数番号のインデックスを含む、請求項21に記載の装置。
【請求項２４】
前記クロスバーのサイズが、インデックスの前記第1のサブセットにおけるインデックスの数に基づく、請求項13に記載の装置。
【請求項２５】
セットトップボックス、音楽プレーヤ、ビデオプレーヤ、エンターテインメントユニット、ナビゲーションデバイス、通信デバイス、携帯情報端末(PDA)、固定位置データユニット、およびコンピュータからなる群から選択されるデバイスに組み込まれる、請求項13に記載の装置。
【請求項２６】
テーブルを記憶するための手段と、
インデックスの第1のサブセットを指定する第1の単一命令複数データ(SIMD)命令を受け取るための手段と、
検索されたテーブルエントリを生成するために、インデックスの前記第1のサブセットを用いてテーブルエントリの第1のサブセットを検索するための手段と、
前記検索されたテーブルエントリに基づいて前記第1のSIMD命令の第1のベクトル出力を生成するための手段と
を備える、システム。
【請求項２７】
プロセッサによって実行されると、テーブルのエントリを検索するための動作を前記プロセッサに実行させる、前記プロセッサによって実行可能な命令を記憶した非一時的コンピュータ可読記憶媒体であって、
インデックスの第1のサブセットを指定する第1の単一命令複数データ(SIMD)命令を受け取るためのコードと、
クロスバーにおいて、インデックスの前記第1のサブセットを用いてテーブルエントリの第1のサブセットを検索するためのコードと、
前記クロスバーの出力に基づいて前記第1のSIMD命令の第1のベクトル出力を生成するためのコードと
を記憶した、非一時的コンピュータ可読記憶媒体。
【請求項２８】
前記クロスバーの前記出力が、テーブルエントリの所望のサブセットに属する場合、前記クロスバーの前記出力に等しいものとして前記第1のベクトル出力を生成するためのコードをさらに記憶した、請求項27に記載の非一時的コンピュータ可読記憶媒体。
【請求項２９】
前記クロスバーの前記出力が、テーブルエントリの所望のサブセットに属さない場合、0値に等しいものとして前記第1のベクトル出力を生成するためのコードをさらに記憶した、請求項27に記載の非一時的コンピュータ可読記憶媒体。
【請求項３０】
インデックスの前記第1のサブセットが不連続である、請求項27に記載の非一時的コンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
開示する態様は、単一命令複数データ(SIMD: single instruction multiple data)命令を使用したテーブルルックアップ演算(table lookup operation)に関する。より詳細には、例示的な態様は、テーブルエントリのサブセットを検索するためのインデックスのサブセットを指定するSIMD命令に関する。
【背景技術】
【０００２】
単一命令複数データ(SIMD)命令が、データ並列処理を活用するために処理システムにおいて使用される場合がある。データ並列処理は、同じまたは共通のタスクが、たとえば、データベクトルの2つ以上のデータ要素に対して実行される必要があるとき存在する。複数の命令を使用するのではなく、共通のタスクは、共通のタスクが複数のデータ要素に対して実行されるように定義する単一のSIMD命令を使用することによって、データ要素のうちの2つ以上に対して並行して実行され得る。
【０００３】
いくつかの処理システムは、SIMDテーブルルックアップ演算をサポートする場合があり、SIMD命令が、検索される必要があるテーブルの2つ以上のエントリに対応する2つ以上のインデックスを含む場合がある。しかしながら、SIMD命令においてインデックスが指定される順序は、テーブルエントリがメモリまたは記憶ロケーションに配列される順序に対応する必要はない。たとえば、第1のインデックス値が第1のテーブルエントリに対応する場合、第1のインデックス値はSIMD命令において第2の位置または第2のSIMDレーンに掲載されてもよい。
【０００４】
SIMDテーブルルックアップ演算においてテーブルエントリにインデックスをマップするために、従来の処理システムは、クロスバーを含む場合がある。クロスバーは、スイッチまたはマルチプレクサを使用して実装される場合がある。たとえば、N個のインデックスを使用してN個のテーブルエントリを検索するために、N×Nクロスバーが、N個のN入力マルチプレクサを使用して実装される場合がある。各N入力マルチプレクサは、N個のテーブルエントリすべてを入力として受け取り、N個のインデックス値のうちの特定の1つに基づいて、N個のテーブルエントリのうちの1つを出力として選択してもよい。クロスバー実装形態は、所望の機能を実現するが、N個のN入力マルチプレクサを実装するために大きいハードウェアコストが生じる。さらに、クロスバー実装形態は、演算される(be operated on)データベクトルのサイズ(たとえば、その中のデータ要素の数)の増加に伴い、容易にはスケーリングすることができない。
【０００５】
別の従来の手法は、複数のテーブルエントリを含むテーブルをメモリシステムに記憶することを含む。SIMD命令は、各テーブルエントリに対してインデックスではなくメモリアドレスを指定してもよい。いくつかの実装形態では、すべてのテーブルエントリに対して共通のベースアドレスを仮定することによって、完全なメモリアドレスではなくオフセット値が指定されてもよい。いずれの場合も、SIMD命令は、メモリアドレスまたはオフセットを使用してメモリロケーションからテーブルエントリを収集するロード命令のセットとして実装され得る。しかしながら、SIMDテーブルルックアップ命令ごとに並列ロード演算のセットを実装することは、より大きいベクトル長またはテーブルエントリ数に合わせてスケールリングすることができない、複雑で費用がかかる動作である。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
したがって、SIMDテーブルルックアップ演算の効率的かつ非常にスケーラブルな実装のための技術が必要とされている。
【課題を解決するための手段】
【０００７】
例示的な態様は、テーブルのエントリを検索するためのシステムおよび方法を対象とする。プロセッサが、インデックスの第1のサブセットを指定する第1の単一命令複数データ(SIMD)命令を含む、1つまたは複数のSIMD命令を受け取る。テーブルエントリの第1のサブセットが、クロスバーを使用して、インデックスの第1のサブセットを用いて検索される。第1のSIMD命令の第1のベクトル出力は、クロスバーの出力がテーブルエントリの所望のサブセットに属するかどうかに基づくものである。同様に、第2、第3、および第4のSIMD命令が、クロスバーを使用して残りのテーブルエントリを検索するためにインデックスの対応する第2、第3、および第4のサブセットを指定する。クロスバーのサイズは、テーブルエントリを検索するために使用されるインデックスのサブセットにおけるインデックスの数に基づくものである。
【０００８】
たとえば、例示的な態様は、プロセッサによって、メモリに記憶されたテーブルのエントリを検索する方法に関する。方法は、インデックスの第1のサブセットを指定する第1の単一命令複数データ(SIMD)命令を受け取るステップと、プロセッサによって実装されるクロスバーにおいて、インデックスの第1のサブセットを用いてテーブルエントリの第1のサブセットを検索するステップと、クロスバーの出力に基づいて第1のSIMD命令の第1のベクトル出力を生成するステップとを含む。
【０００９】
別の例示的な態様は、テーブルを備えるメモリと、第1の単一命令複数データ(SIMD)命令を実行するように構成されたプロセッサとを備える装置を含む。プロセッサは、第1のSIMD命令によって指定されたインデックスの第1のサブセットを用いて、テーブルのテーブルエントリの第1のサブセットを検索するように構成されたクロスバーと、クロスバーの出力に基づいて第1のSIMD命令の第1のベクトル出力を生成するロジックとを含む。
【００１０】
別の例示的な態様は、テーブルを記憶するための手段と、インデックスの第1のサブセットを指定する第1の単一命令複数データ(SIMD)命令を受け取るための手段と、検索されたテーブルエントリを生成するためにインデックスの第1のサブセットを用いてテーブルエントリの第1のサブセットを検索するための手段と、検索されたテーブルエントリに基づいて第1のSIMD命令の第1のベクトル出力を生成するための手段とを備えるシステムに関する。
【００１１】
また別の例示的な態様は、プロセッサによって実行されるとき、プロセッサにテーブルのエントリを検索するための演算を実行させる、プロセッサによって実行可能な命令を含む非一時的コンピュータ可読記憶媒体を対象とし、この非一時的コンピュータ可読記憶媒体は、インデックスの第1のサブセットを指定する第1の単一命令複数データ(SIMD)命令を受け取るためのコードと、クロスバーにおいて、インデックスの第1のサブセットを用いてテーブルエントリの第1のサブセットを検索するためのコードと、クロスバーの出力に基づいて第1のSIMD命令の第1のベクトル出力を生成するためのコードとを含む。
【００１２】
添付の図面は、本発明の態様の記述において助けになるように提示され、単に態様の説明のために提供されており、態様を制限するものではない。
【図面の簡単な説明】
【００１３】
【図１】例示的な態様による、SIMD命令を使用してテーブルルックアップを実行するための処理システムを示す図である。
【図２】例示的なクロスバー構造を示す図である。
【図３】SIMD命令を使用してテーブルルックアップを実行する方法を示す図である。
【図４】本開示の態様が有利に採用される場合がある例示的な処理デバイス400を示す図である。
【発明を実施するための形態】
【００１４】
本発明の態様は、本発明の特定の態様を対象とする以下の説明および関連する図面において開示される。本発明の範囲から逸脱することなく、代替態様が考案され得る。加えて、本発明のよく知られている要素は、本発明の関連する詳細を不明瞭にしないように、詳細には説明されない、または省略される。
【００１５】
「例示的」という単語は、本明細書では、「例、実例、または例証として機能する」を意味するために使用される。「例示的」として本明細書において説明されるいずれの態様も、必ずしも他の態様よりも好ましいか、または有利であると解釈されるべきでない。同様に、「本発明の態様」という用語は、本発明のすべての態様が議論された特徴、利点、または動作モードを含むことを求めるものではない。
【００１６】
本明細書で使用する用語は、特定の態様のみを説明する目的のためのものであり、本発明の態様の限定であることを意図しない。本明細書で使用する単数形「a」、「an」、および「the」は、コンテキストがはっきりと別段に指示しない限り、複数形も含むことが意図される。さらに、「備える(comprises)」、「備えている(comprising)」、「含む(includes)」、および/または「含んでいる(including)」という用語は、本明細書で使用されるとき、述べられた特徴、整数、ステップ、動作、要素、および/または構成要素の存在を明示するが、1つまたは複数の他の特徴、整数、ステップ、動作、要素、構成要素、および/またはそれらのグループの存在または追加を排除しないことが理解されよう。
【００１７】
さらに、多数の態様について、たとえば、コンピューティングデバイスの要素によって実行すべきアクションのシーケンスに関して説明する。本明細書で説明する様々なアクションは、特定の回路(たとえば、特定用途向け集積回路(ASIC))によって実行されるか、1つもしくは複数のプロセッサによって実行されるプログラム命令によって実行されるか、またはその両方の組合せによって実行されることが可能であることが認識されよう。加えて、本明細書で説明するこれらの一連のアクションは、実行されると、関連するプロセッサに本明細書で説明する機能を実行させる、対応するコンピュータ命令のセットを記憶した任意の形態のコンピュータ可読記憶媒体内において完全に具現化されるものと見なすことができる。したがって、本発明の様々な態様はいくつかの異なる形態で具現化されてもよく、それらのすべてが、請求する主題の範囲内に入ると考えられる。加えて、本明細書で説明する態様の各々について、任意のそのような態様の対応する形態は、たとえば、説明するアクションを実行する「ように構成された論理構成要素(logic)」として本明細書で説明される場合がある。
【００１８】
本開示の例示的な態様は、従来のクロスバー実装形態を使用した完全なテーブルルックアップの複雑性を減少させる、テーブルルックアップのためのSIMD命令を対象とする。一態様では、例示的なSIMD命令が、ルックアップ時間およびクロスバー複雑性を減少させる部分的なテーブルルックアップを対象としてもよい。たとえば、単一のSIMD命令を使用してN個のテーブルエントリを含むテーブルの完全なテーブルルックアップを実行するのではなく、N個のテーブルエントリの第1のサブセットの部分的なテーブルルックアップが、1つまたは複数のSIMD命令(たとえば、N個のテーブルエントリの第1のサブセットの偶数番号のエントリのルックアップおよび奇数番号のエントリのルックアップに対する異なるSIMD命令)を使用して実行されてもよい。同様に、1つまたは複数のSIMD命令(たとえば、偶数番号のエントリのルックアップおよび奇数番号のエントリのルックアップに対する異なるSIMD命令)が、N個のテーブルエントリの第2のサブセットなどの他のサブセットの部分的なテーブルルックアップを実行するために使用され得る。第1および第2のサブセットなどの異なるサブセットは、重複しない(たとえば、第1のサブセットは下半分に関係する場合があり、第2のサブセットはN個のテーブルエントリの上半分に関係する場合がある)。
【００１９】
いくつかの態様では、様々なサブセットを検索するために使用されるSIMD命令は、たとえば、偶数番号のエントリまたは奇数番号のエントリを単に指定してもよく、テーブルルックアップ演算は、SIMD命令が関係するテーブルエントリのサブセットに応じて実施されてもよい。したがって、第1のSIMD命令が、テーブルエントリの下半分に対応する偶数番号のインデックスを指定してもよく、第2のSIMD命令が、テーブルエントリの下半分に対応する奇数番号のインデックスを指定してもよい。第3のSIMD命令が、テーブルエントリの上半分に対応する偶数番号のインデックスを指定してもよく、第4のSIMD命令が、テーブルエントリの上半分に対応する奇数番号のインデックスを指定してもよい。当技術分野で知られているBenesまたはClosネットワークを使用して実装されるクロスバーは、従来の方法で完全なテーブルルックアップを実施するよりも、そのような不連続のテーブルルックアップ演算(たとえば、偶数番号または奇数番号のインデックス)にテーブルルックアップを分解するためのより少ない段および複雑さで実装することができる。
【００２０】
一態様では、ルックアップ演算がテーブルエントリの正しいまたは所望のサブセットに関係することを確認するために各インデックスの一部分を使用することができるように、各インデックスはマルチビット値であってもよい。たとえば、第1のSIMD命令は、第1のサブセットのM個のテーブルエントリに対応するM個のインデックスの第1のサブセットを含んでもよい。M個のインデックスが、予想されるまたは所望の第1のサブセットのM個のテーブルエントリにマッピングすることを確認するために、比較論理が利用されてもよい。M個のインデックスの1つまたは複数の最上位ビット(MSB)が、第1のサブセットのM個のテーブルエントリに対応することを確実にするために、それらをチェックすることができる。M個のインデックスの残りのビットは、たとえば、従来の方法で完全なテーブルルックアップを実行するために実装され得るN×Nクロスバーよりも小さいM×Mクロスバーを使用することによって、第1のサブセット内のM個のテーブルエントリを検索するために使用することができる。
【００２１】
次に図1を参照すると、例示的な態様による装置または処理システム100が示されている。処理システム100は、メモリ103と、プロセッサ101とを備える。メモリ103は、プロセッサ101とは異なるように図示されているが、これは説明のためにすぎず、態様によっては、メモリ103は、プロセッサ101の一部である場合がある(たとえば、メモリ103は、テーブルを記憶するための、プロセッサ101に組み込まれたレジスタまたは他の手段のセットである場合がある)。プロセッサ101は、例示的な態様によるテーブルルックアップを行うために、SIMD命令を実行するための論理構成要素(logic)を含むことができる。
【００２２】
図示の例では、メモリ103は、テーブル102を含むように示されている。テーブル102は、16個のテーブルエントリ、T0〜T15(そのすべてが明示的に示されているわけではない)を含む。16個のテーブルエントリT0〜T15のうちの2つ以上を、対応する16個のインデックス、0〜15を使用して並行して検索するために、SIMD命令が使用されてもよい。(たとえば、16×16クロスバーを用いて)16個の命令すべてのルックアップに(たとえば、16個のインデックスを指定する)単一のSIMD命令を使用するのではなく、例示的な態様では、クロスバー104などのより小さいクロスバー(たとえば、4×4クロスバー)を用いてテーブル102の部分的なルックアップを行うために、複数のSIMD命令を使用することができる。
【００２３】
さらに詳細には、図1に示すSIMD命令106は、(たとえば、図示していない命令キャッシュから)プロセッサ101によって受け取られる場合がある4つの考えられるSIMD命令の1つである。4つのSIMD命令の組合せが、テーブル102の16個のテーブルエントリすべてを検索するために使用され得る。SIMD命令106は、インデックス0〜15の第1のサブセットを含む。より具体的には、SIMD命令106は、各々が1つのインデックス値を含む4つのレーン、(右から左に)106a〜dを指定する。SIMD命令106と同様のさらに3つのSIMD命令が、テーブル102の残りのエントリに対してインデックスの他のサブセットを指定してもよい。4つのSIMD命令を使用するテーブルルックアップは、1つまたは複数のサイクルで行われてもよく、ループとして行われてもよい。さらなるそのようなSIMD命令が、テーブル102よりも大きいテーブルサイズを検索するのに使用される場合がある。したがって、例示的な実装形態は、スケーラブルである。
【００２４】
前述のように、一態様では、SIMD命令106は、インデックスの第1のサブセットを指定してもよく、インデックスの第1のサブセットは、不連続のインデックスであってもよい。図示のように、命令106のレーン106aはインデックス4を指定し、レーン106bはインデックス2を指定し、レーン106cはインデックス6を指定し、レーン106dはインデックス0を指定する。SIMD命令106において指定された4つのインデックスすべてが不連続であり、さらに、それらはテーブルエントリの特定のサブセット、すなわち、テーブルエントリT0〜T15のうちの下半分(T0〜T7)に対応する。クロスバー104(これについては図2を参照してさらに説明する)は、(右から左に)レーン106a〜106d中のインデックス4、2、6、0にそれぞれ対応するテーブルエントリT4、T2、T6、およびT0を検索するために使用されてもよい。例示的な態様では、対応するSIMD命令によって提供されたインデックスのサブセットを用いて検索されるテーブル102のエントリを表す、クロスバー104の出力が、テーブルエントリの正しいまたは所望のサブセット(たとえば、すなわちテーブルエントリT0〜T15のうちの下半分(T0〜T7)または上半分(T8〜T15))に属するかどうかが確認される。クロスバー104の出力が所望のサブセットに属する場合、結果112として示す、対応する出力ベクトルが、クロスバー104の出力に等しいものとして生成され、そうでない場合、出力ベクトルまたは結果112は、0値に等しいものとして生成される。したがって、プロセッサ101は、次のように、クロスバー104の出力に基づいて結果112を生成するために、ANDゲート110などの論理構成要素を含む。結果112は、たとえば、プロセッサ101によって実行される命令の結果を記憶するために使用されるレジスタ(たとえば、プロセッサ101の、図示していない、レジスタファイルの一部)であり得る。
【００２５】
一態様では、SIMD命令106が、テーブル102の16個のインデックスすべてを検索するために使用することができる4つのSIMD命令のうちの第1であると見なされる場合、第1のSIMD命令は、テーブルエントリの第1のサブセット(すなわち、テーブルエントリT0〜T15のうちの下半分(T0〜T7))のテーブルエントリを検索するためのインデックスの第1のサブセット(すなわち、偶数番号のインデックス)を含む。第2のSIMD命令が、テーブルエントリの第1のサブセットのテーブルエントリを検索するためのインデックスの第2のサブセット(すなわち、奇数番号のインデックス)を含むことができる。第3および第4のSIMD命令は、同様に、テーブルエントリの第2のサブセット(すなわち、テーブルエントリT0〜T15のうちの上半分(T8〜T15))を検索するためのインデックスの第3および第4のサブセット(すなわち、それぞれ、偶数番号および奇数番号のインデックス)を含むことができる。
【００２６】
テーブルエントリの正しいまたは所望のサブセット(たとえば、第1のSIMD命令106の場合は下半分T0〜T7)が検索されることを確実にするために、コンパレータ108が使用されて、インデックスのサブセットが所望のサブセットに対応する範囲内に入るかどうかをチェックする。一例では、4ビットの場合、[3:0]が使用されて、2進記数法でインデックス0〜15を表す。4ビットのインデックスの最上位ビットまたはビット[3]は、テーブルエントリの第2のサブセットまたは上半分T8〜T15の場合は「1」、テーブルエントリの第1のサブセットまたは下半分T0〜T7の場合は「0」である。したがって、コンパレータ108は、SIMD命令106が特定の演算のためにインデックスの正しいサブセットを指定することを確実にするために、レーン106a〜106d中のインデックスのサブセットの各々のビット[3]を、「0」というサブテーブルの選択値と比較するように構成されてもよい。サブテーブルの選択値は、SIMD命令106のオペランドによって、またはプログラマーもしくはコンパイラによって供給されてもよい。コンパレータ108が、インデックスのサブセットが(図示の例のように)テーブルエントリの所望のサブセットに対応することを明らかにする場合、コンパレータ108は、ANDゲート110への入力である「1」という値を出力する。ANDゲート110はまた、別の入力としてクロスバー104の出力を受け取り、クロスバー104の出力がテーブルエントリの所望のサブセットに属することが確認される場合、それらを結果112に渡す。結果112は、インデックス4、2、6、および0のサブセットにそれぞれ対応する、テーブルエントリの第1のサブセットのテーブルエントリT4、T2、T6、およびT0を含むSIMD命令106の出力ベクトルである。言い換えれば、クロスバー104の出力がテーブルエントリの正しいまたは所望のサブセットに属する場合、ANDゲート110が、クロスバー104の出力に等しいものとして結果112を生成する。
【００２７】
一方、コンパレータ108が、インデックスのサブセットがテーブルエントリの所望のサブセットに対応しない(たとえば、サブテーブルの選択値が、テーブルエントリの上半分T8〜T15に対応する「1」である)ことを明らかにする場合、ANDゲート110の出力はすべて「0」であり、結果112に0値が書き込まれるようにする。言い換えれば、クロスバー104の出力がテーブルエントリの正しいまたは所望のサブセットに属さない場合、ANDゲート110は、0値に等しいものとして結果112を生成する。完全なテーブルルックアップが複数のサイクルで、または複数の命令(たとえば、上記で説明した第1から第4のSIMD命令)の使用によって行われる場合は、部分的なテーブルルックアップのための特定の命令の焦点ではないテーブルエントリのサブセットからの寄与を0にするために、結果「0」を書き込む機能が採用されてもよい。さらに、サブテーブルの選択に任意の数のビットが使用されてもよいことは当業者には理解されよう。たとえば、テーブル102がより大きい、たとえば32エントリのテーブルの一部であった場合、インデックスは、5以上のビット幅であってもよく、全テーブルT0〜T31の第1のサブセットテーブルエントリT0〜T7上のルックアップに焦点を当てるために、ビット[5:4]が使用されてもよい。
【００２８】
次に図2を参照すると、クロスバー104の展開図が示されている。前述のように、テーブルルックアップのためのクロスバーは、当技術分野で知られているBenesネットワークまたはClosネットワークに基づいて実装されてもよい。図2では、4×4クロスバー216が、クロスバー104に実際に実装される場合がある論理構成要素に対応する。図2はまた、破線の8×8クロスバー214、ならびに破線の行202および210を示す。以下でさらに説明するように、図2の破線は、クロスバー104に実際には実装されない機能に対応するが、クロスバー104の例示的な実装形態におけるハードウェア節減を説明するために示されている。
【００２９】
より詳細には、クロスバー104が、8個のインデックスを含むSIMD命令を使用したテーブルエントリT0〜T7の第1のサブセット全体または下半分のテーブルルックアップのために使用された場合、8個の対応するインデックスすべてを使用して、行202のテーブルエントリの第1のサブセットの8個すべてを検索するために、8×8クロスバー214が実装されて、行202の検索されたテーブルエントリを含む出力行210を生成することがある。したがって、行202は、8×8クロスバー214への入力であってもよい潜在的なテーブルエントリとして8個のテーブルエントリT0〜T7すべてを含むように示されている。しかしながら、行210に8個の出力(検索されたテーブルエントリ)を生成するために行202に8個のテーブルエントリT0〜T7がある8×8クロスバー214を避けることができる。それゆえ、避けることができる8×8クロスバー214の入力行202、出力210、ならびにスイッチ(たとえば、当技術分野で知られているように、クロスバーにおいてデータを転送または移動するためにマルチプレクサまたは同様の論理構成要素を使用して実装される場合がある、ボックスとして示される)および関係する接続は、破線で示されている。代わりに、以下で説明する4×4クロスバー216を、クロスバー104に実際に実装することができ、したがって、4×4クロスバー216の対応する入力、出力、転送要素、および関係する接続が、図2では実線で示されている。
【００３０】
すでに説明したように、例示的なSIMD命令106は、偶数番号のインデックスのみを指定するので、偶数番号のインデックスに対応する、テーブルエントリの第1のサブセットの偶数番号のテーブルエントリ(すなわち、T0、T2、T4、およびT6)のみが、検索される必要がある。したがって、テーブルエントリの第1のサブセットの偶数番号のテーブルエントリ(すなわち、T0、T2、T4、およびT6)のみが、行204において4×4クロスバー216に入力され、実線で対応するボックスに示されている。対応して、行204の偶数番号のテーブルエントリを、偶数番号のインデックスのみで検索することができ、したがって、残りのテーブルエントリを検索するための論理構成要素を回避することができる(上述のように、破線で示される)。4つの偶数番号のインデックスのみで行204のテーブルエントリを検索するために使用される4×4クロスバー216中のスイッチ(ボックス)および関係する接続は、SIMD命令106(図1参照)のレーン106a〜dでそれぞれインデックス4、2、6、および0を使用した、検索されたテーブルエントリを含む出力行212とともに、実線で示される。具体的には、出力行212の検索されたテーブルエントリ(右から左に)T4、T2、T6、およびT0を生成するためのスイッチの3段にわたって入力行204のテーブルエントリT0、T2、T4、およびT6からたどられる例示的なパスを強調するために、太線が使用される。入力行202から出力行212までのパスに含まれるスイッチまたは接続の詳細は当業者には理解されるので、本開示ではさらなる詳細な説明を行わない。したがって、図1〜図2を組み合わせて参照すると、出力行212の検索されたテーブルエントリが、コンパレータ108およびANDゲート110に基づく結果112に提供され得る。
【００３１】
したがって、クロスバー104は、SIMD命令106に対するルックアップ演算を実行するために、4×4クロスバー216に実線で示す論理構成要素を実装してもよい。諒解され得るように、4×4クロスバー216は、8×8クロスバー214と比較して、より少ない段およびスイッチを備えた簡略化されたクロスバーネットワークである。一般に、例示的なテーブルルックアップにおいて使用されるクロスバーのサイズは、対応するSIMD命令によって指定されるインデックスの数に基づくことができる(たとえば、第1のSIMD命令106で指定される4つのインデックスを使用してテーブル102を検索するためには4×4クロスバー)。対応して、(たとえば、不連続のテーブルエントリの)例示的な部分的なテーブルルックアップ演算の実装において、ハードウェアコストが削減される。
【００３２】
引き続き図2を参照すると、前述の第2のSIMD命令に対するルックアップ演算が、テーブルエントリの第1のサブセットの奇数番号のテーブルエントリ(すなわち、テーブルエントリT0〜T15の第1のサブセットT0〜T7のテーブルエントリT1、T3、T5、およびT7)を検索するために、インデックスの第2のサブセット(たとえば、奇数番号のインデックス)を含むことができる。したがって、奇数番号のテーブルエントリT1、T3、T5、およびT7は、それぞれ図2に示す偶数番号のテーブルエントリT0、T2、T4、T6の代わりに、行204において提供される場合がある。上記の第1のSIMD命令106に対する偶数番号のテーブルエントリT0、T2、T4、T6を検索することの説明と同様に、第2のSIMD命令において指定された奇数番号のインデックスを使用してテーブルエントリT1、T3、T5、およびT7を検索するために、4×4クロスバー216を実装することができる。またしても、4×4クロスバー216に実線で示されるスイッチおよびそれぞれの接続のみが、第2のSIMD命令において指定される特定の奇数番号のインデックスに基づいて4×4クロスバー216の段にわたって様々なパスを実装するために利用されてもよい。第2のSIMD命令に対するテーブルエントリを検索することのさらなる詳細は、第1のSIMD命令に対して上記で行った詳細な説明と同様であるので、これを省略する。
【００３３】
同様に、インデックスの第3のサブセットとインデックスの第4のサブセット(たとえば、偶数番号のインデックス8、10、12、14および奇数番号のインデックス9、11、13、15)が、第3および第4のSIMD命令の対応する実装のために、4×4クロスバー216を使用して行204に提供されるテーブルエントリの第2のサブセットのテーブルエントリ(たとえば、テーブルエントリT0〜T15の第2のサブセットT8〜T15の、それぞれT8、T10、T12、T14およびT9、T11、T13、T15)を検索するために使用されてもよい。
【００３４】
したがって、態様は、本明細書において開示したプロセス、機能、および/またはアルゴリズムを実施するための様々な方法を含むことが理解されよう。たとえば、図3に示すように、一態様が、メモリ(たとえば、メモリ103)に記憶されたテーブル(たとえば、エントリT0〜T15を含むテーブル102)のエントリを、プロセッサ(たとえば、プロセッサ101)によって検索するための方法300を含むことができる。
【００３５】
さらに詳細には、方法300のブロック302は、インデックスの第1のサブセットを指定する第1の単一命令複数データ(SIMD)命令を受け取ることを含む。たとえば、ブロック302は、命令キャッシュから、インデックスの第1のサブセット(たとえば、下半分T0〜T7)を含むSIMD命令106を受け取ることを含むことができ、インデックスの第1のサブセットは不連続であり、たとえば、偶数番号のインデックス(たとえば、インデックス0、2、4、6)である。
【００３６】
ブロック304は、プロセッサによって実装されるクロスバーにおいて、インデックスの第1のサブセットを用いてテーブルエントリの第1のサブセットを検索することを含む。たとえば、ブロック304は、クロスバー104の4×4クロスバー216を使用し、SIMD命令106によって指定されたインデックスの第1のサブセットを使用してテーブル102の下半分のテーブルエントリを検索することに関係し得る。クロスバーのサイズは、インデックスの第1のサブセットにおけるインデックスの数に基づくことができる(たとえば、インデックスの第1のサブセットにおける4つのインデックスに基づく4×4クロスバー)。
【００３７】
ブロック306は、クロスバーの出力に基づいて第1のSIMD命令の第1のベクトル出力(たとえば、結果112)を生成することを含む。たとえば、ブロック306は、(たとえば、上記のように、ANDゲート110およびサブテーブルの選択108を使用して)4×4クロスバー216の出力行212が、テーブルエントリの所望のサブセットに属する場合、4×4クロスバー216の出力行212に等しいものとして第1のベクトル出力を生成することを含んでもよい。そうではなく、4×4クロスバー216の出力行212が、テーブルエントリの所望のサブセットに属さない場合、ブロック306は、0値に等しいものとして第1のベクトル出力を生成することを含んでもよい。
【００３８】
さらなる態様では、方法300は、インデックスの第2のサブセット(たとえば、奇数番号のインデックス1、3、5、7)を指定する第2のSIMD命令を受け取ることと、クロスバーにおいて、インデックスの第2のサブセットを用いてテーブルエントリの第1のサブセットを検索することとを含むことができ、インデックスの第1のサブセットとインデックスの第2のサブセットは、重複しない。さらに、方法300はまた、インデックスの第3のサブセット(たとえば、偶数番号のインデックス8、10、12、14)を指定する第3のSIMD命令を受け取ることと、クロスバーにおいて、テーブルエントリの第2のサブセット(たとえば、上半分T8〜T15)を検索することとを含むことができ、テーブルエントリの第1のサブセット(たとえば、下半分T0〜T7)およびテーブルエントリの第2のサブセットは、重複しない。同様に、方法300はさらに、インデックスの第4のサブセット(たとえば、奇数番号のインデックス9、11、13、および15)を指定する第4のSIMD命令を受け取ることと、クロスバーにおいて、テーブルエントリの第2のサブセットを検索することとを含むことができ、インデックスの第3のサブセットとインデックスの第4のサブセットは、重複しない。
【００３９】
さらに、例示的な態様は、本明細書で説明する機能を実施するための様々な手段を含むこともまた理解されよう。たとえば、上記の説明から、処理システム100は、例示的な態様の機能を実施するための手段を備えることができることがわかる。一例では、処理システム100は、テーブル(たとえば、テーブル102)を記憶するための手段(たとえば、メモリ103)を含むことができる。処理システム100はまた、インデックスの第1のサブセット(たとえば、インデックス0、2、4、6)を指定する第1の単一命令複数データ(SIMD)命令(たとえば、SIMD命令106)を受け取るための手段(たとえば、プロセッサ101)を含むことができる。処理システム100は、インデックスの第1のサブセットを用いてテーブルエントリの第1のサブセットを検索するための手段(たとえば、クロスバー104)と、クロスバーの出力に基づいて第1のSIMD命令の第1のベクトル出力を生成するための手段(たとえば、ANDゲート110、結果112)とを含むことができる。
【００４０】
図4を参照すると、例示的な態様に従って構成された処理デバイス400の特定の例示的な態様のブロック図が示されている。たとえば、処理デバイス400は、図3の方法300を実行するように構成されてもよい。処理デバイス400は、プロセッサ101を含む(ここでは4×4クロスバー104のみを示すが、図1に示すプロセッサ101の残りの細部は、明快のために図4から削除した)。図4に示すように、プロセッサ101は、(明快のためにこの図には示していないテーブル102を含むことができる)メモリ103と通信していてもよい。
【００４１】
図4は、プロセッサ101およびディスプレイ428に結合された、ディスプレイコントローラ426も示している。コーダ/デコーダ(コーデック)434(たとえば、オーディオおよび/または音声コーデック)は、プロセッサ101に結合することができる。(モデムを含んでもよい)ワイヤレスコントローラ440などの他の構成要素も示されている。スピーカー436およびマイクロフォン438は、コーデック434に結合することができる。図4は、ワイヤレスコントローラ440をワイヤレスアンテナ442に結合することができることも示している。特定の態様では、プロセッサ101、ディスプレイコントローラ426、メモリ103、コーデック434、およびワイヤレスコントローラ440は、システムインパッケージデバイスまたはシステムオンチップデバイス422に含まれる。
【００４２】
ある特定の態様では、入力デバイス430および電源444が、システムオンチップデバイス422に結合される。さらに、ある特定の態様では、図4に示すように、ディスプレイ428、入力デバイス430、スピーカー436、マイクロフォン438、ワイヤレスアンテナ442、および電源444は、システムオンチップデバイス422の外部に位置する。ただし、ディスプレイ428、入力デバイス430、スピーカー436、マイクロフォン438、ワイヤレスアンテナ442、および電源444の各々は、インターフェースまたはコントローラのような、システムオンチップデバイス422の構成要素に結合することができる。
【００４３】
図4はワイヤレス通信デバイスを示しているが、プロセッサ101およびメモリ103は、セットトップボックス、音楽プレーヤ、ビデオプレーヤ、娯楽ユニット、ナビゲーションデバイス、携帯情報端末(PDA)、固定ロケーションデータユニット、またはコンピュータ内に組み込むこともできることに留意されたい。さらに、処理デバイス400の少なくとも1つまたは複数の例示的な態様は、少なくとも1つの半導体ダイに組み込まれてもよい。
【００４４】
当業者は、情報および信号が、様々な異なる技術および技法のいずれを使用しても表される場合があることを諒解されよう。たとえば、上記の説明全体にわたって参照される場合があるデータ、命令、コマンド、情報、信号、ビット、シンボル、およびチップは、電圧、電流、電磁波、磁場もしくは磁性粒子、光場もしくは光学粒子、またはそれらの任意の組合せによって表される場合がある。
【００４５】
さらに、当業者であれば、本明細書で開示する態様に関して説明する様々な例示的な論理ブロック、モジュール、回路、およびアルゴリズムステップが、電子ハードウェア、コンピュータソフトウェア、または両方の組合せとして実装される場合があることを諒解されよう。ハードウェアおよびソフトウェアのこの互換性を明確に示すために、種々の例示的な構成要素、ブロック、モジュール、回路、およびステップについて、上記では概してそれらの機能に関して説明してきた。そのような機能をハードウェアとして実装するか、ソフトウェアとして実装するかは、具体的な適用例および全体的なシステムに課された設計制約に依存する。当業者は説明した機能を特定の用途ごとに様々な方法で実装してもよいが、そのような実装決定は本発明の範囲からの逸脱を引き起こすものと解釈されるべきではない。
【００４６】
本明細書において開示される態様に関して説明する方法、シーケンスおよび/またはアルゴリズムは、直接ハードウェアにおいて具現化されても、プロセッサによって実行されるソフトウェアモジュールにおいて具現化されても、またはその2つの組合せにおいて具現化されてもよい。ソフトウェアモジュールは、RAMメモリ、フラッシュメモリ、ROMメモリ、EPROMメモリ、EEPROMメモリ、レジスタ、ハードディスク、リムーバブルディスク、CD-ROM、または当技術分野で知られている任意の他の形態の記憶媒体内に存在してもよい。例示的な記憶媒体は、プロセッサが記憶媒体から情報を読み取ること、および記憶媒体に情報を書き込むことができるようにプロセッサに結合される。代替として、記憶媒体はプロセッサに一体化される場合がある。
【００４７】
したがって、本開示の一態様は、SIMD命令を使用してテーブルのエントリを検索するための演算を実行するための方法を具現化するコンピュータ可読媒体を含むことができる。したがって、本発明は例示の例に制限されず、本明細書に記載される機能性を実施するための任意の手段は、本発明の態様に含まれる。
【００４８】
上記の開示が本発明の例示の態様を示す一方で、添付される特許請求の範囲により規定されるような、本発明の範囲から逸脱することなく、本明細書に様々な変形および変更を行うことができることに留意されたい。本明細書に記載される本発明の態様に従う方法クレームの機能、ステップ、および/または行為を、任意の特定の順序で実施する必要はない。さらに、本発明の要素は、単数形で記載され、特許請求される場合があるが、単数形への制限が明示的に言及されない限り、複数形が意図される。
【符号の説明】
【００４９】
100  処理システム
101  プロセッサ
102  テーブル
103  メモリ
104  クロスバー
106  SIMD命令
108  コンパレータ
110  ANDゲート
112  結果
202  入力行
204  入力行
210  出力行
212  出力行
214  8×8クロスバー
216  4×4クロスバー
400  処理デバイス
422  システムオンチップデバイス
426  ディスプレイコントローラ
428  ディスプレイ
430  入力デバイス
434  コーダ/デコーダ(コーデック)
436  スピーカー
438  マイクロフォン
440  ワイヤレスコントローラ
442  ワイヤレスアンテナ
444  電源
【図１】
2018523245.tif 000003
【図２】
2018523245.tif 000004
【図３】
2018523245.tif 000005
【図４】
2018523245.tif 000006
【手続補正書】
【提出日】平成30年2月15日(2018.2.15)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
メモリに記憶されたテーブルエントリをプロセッサによって検索する方法であって、
インデックスの第1のサブセットを指定する第1の単一命令複数データ(SIMD)命令を受け取るステップであって、インデックスの前記第1のサブセットの各々が、前記テーブルエントリの第1のサブセットに属するテーブルエントリに対応する、受け取るステップと、
前記プロセッサによって実装されるクロスバーにおいて、インデックスの前記第1のサブセットを用いてテーブルエントリの前記第1のサブセットを検索するステップであって、前記クロスバーへの入力の数が、インデックスの前記第1のサブセットにおけるインデックスの数よりも大きくない、ステップと、
前記クロスバーの出力に基づいて前記第1のSIMD命令の第1のベクトル出力を生成するステップと
を含む、方法。
【請求項２】
前記クロスバーの前記出力が、テーブルエントリの所望のサブセットに属する場合、前記クロスバーの前記出力に等しいものとして前記第1のベクトル出力を生成するステップをさらに含む、請求項1に記載の方法。
【請求項３】
前記クロスバーの前記出力が、テーブルエントリの所望のサブセットに属さない場合、0値に等しいものとして前記第1のベクトル出力を生成するステップをさらに含む、請求項1に記載の方法。
【請求項４】
インデックスの前記第1のサブセットが不連続である、請求項1に記載の方法。
【請求項５】
インデックスの第2のサブセットを指定する第2のSIMD命令を受け取るステップと、
前記クロスバーにおいて、インデックスの前記第2のサブセットを用いてテーブルエントリの前記第1のサブセットを検索するステップと
をさらに含む、請求項1に記載の方法。
【請求項６】
インデックスの前記第1のサブセットとインデックスの前記第2のサブセットが重複しない、請求項5に記載の方法。
【請求項７】
インデックスの前記第1のサブセットが偶数番号のインデックスを含み、インデックスの前記第2のサブセットが奇数番号のインデックスを含む、請求項5に記載の方法。
【請求項８】
インデックスの第3のサブセットを指定する第3のSIMD命令を受け取るステップと、
前記クロスバーにおいて、テーブルエントリの第2のサブセットを検索するステップと
をさらに含み、テーブルエントリの前記第1のサブセットとテーブルエントリの前記第2のサブセットが重複しない、請求項1に記載の方法。
【請求項９】
インデックスの第4のサブセットを指定する第4のSIMD命令を受け取るステップと、
前記クロスバーにおいて、テーブルエントリの前記第2のサブセットを検索するステップと
をさらに含む、請求項8に記載の方法。
【請求項１０】
インデックスの前記第3のサブセットとインデックスの前記第4のサブセットが重複しない、請求項9に記載の方法。
【請求項１１】
インデックスの前記第3のサブセットが偶数番号のインデックスを含み、インデックスの前記第4のサブセットが奇数番号のインデックスを含む、請求項9に記載の方法。
【請求項１２】
前記テーブルエントリの前記第1のサブセットが、連続したテーブルエントリを含む、請求項1に記載の方法。
【請求項１３】
テーブルを含むメモリと、
第1の単一命令複数データ(SIMD)命令を実行するように構成されたプロセッサと
を備え、前記プロセッサが、
前記第1のSIMD命令によって指定されたインデックスの第1のサブセットを用いて、前記テーブルのテーブルエントリの第1のサブセットを検索するように構成されたクロスバーであって、インデックスの前記第1のサブセットの各々が、前記テーブルエントリの前記第1のサブセットに属するテーブルエントリに対応し、前記クロスバーへの入力の数が、インデックスの前記第1のサブセットにおけるインデックスの数よりも大きくない、クロスバーと、
前記クロスバーの出力に基づいて前記第1のSIMD命令の第1のベクトル出力を生成するための論理構成要素と
を備える、装置。
【請求項１４】
請求項1から12のいずれか一項に記載の方法を実行するための手段を備える装置。
【請求項１５】
請求項1から12のいずれか一項に記載の方法をコンピュータまたはプロセッサに実行させるための少なくとも1つの命令を記憶したコンピュータ可読記憶媒体。
【国際調査報告】
2018523245.tif 000007
2018523245.tif 000008