(57)【要約】【課題】配列データをＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上で転置するためのシステム、方法及びコンピュータ可読ストレージ媒体を提供する。【解決手段】ＳＩＭＤ形式の行列が受け取られる。この行列は、通常のデータ形式を有する行列ＭをＳＩＭＤ変換したものから成る。この行列の各要素から行列Ｍの転置のＳＩＭＤ変換の各要素へのマッピングが定義される。行列Ｍ及びこの定義されたマッピングに基づき、ＳＩＭＤ転置行列Ｔが生成される。行列Ｍの複数の列上で動作するように、行方向アルゴリズムが修正なしでＳＩＭＤ転置行列Ｔに適用される。【選択図】  図６
2011100452.tif 000002
【特許請求の範囲】
【請求項１】
行列をＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上で転置するためのコンピュータ実装方法であって、
（ａ）第１形式の行列ＭをＳＩＭＤ形式の行列Ｓに変換するステップを有し、
前記ＳＩＭＤ形式は、前記ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上の複数のコアの各々が前記行列Ｍ内の一の行上で１ＤＦＦＴ動作を並列に実行することを可能にするように構成され、
（ｂ）前記行列Ｓの各要素からＳＩＭＤ形式の前記行列Ｍの転置内の一の要素へのマッピングを検索するステップを有し、
前記マッピングは、前記行列Ｍの転置用の前記行列ＳのＳＩＭＤ形式を保存するように定義され、
（ｃ）前記検索されたマッピングに基づき、ＳＩＭＤ転置行列Ｔを生成するステップを有し、
前記ＳＩＭＤ転置行列Ｔは、前記ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上の複数のコアの各々が前記行列Ｍ内の転置された一の行上で１ＤＦＦＴ動作を並列に実行することを可能にするように構成される、コンピュータ実装方法。
【請求項２】
前記ＳＩＭＤ形式の前記行列Ｓは、前記行列Ｍのｒ行の同時処理のために構成され、前記変換されたデータは、複数ブロックのシーケンスを含み、各ブロックは、前記行列Ｍの連続するｒ行（但し、ｒは２以上の正の整数）を含み、当該連続するｒ行は、当該連続するｒ行の第１要素が、順次メモリ・アドレスに関して当該連続するｒ行の任意の第２要素に先行するようにインターリーブされる、請求項１に記載のコンピュータ実装方法。
【請求項３】
前記第１形式は、行優先形式及び列優先形式のうちの１つである、請求項１に記載のコンピュータ実装方法。
【請求項４】
（ｄ）前記行列Ｓに基づき、ｓ個（但し、ｓは２以上の正の整数）のセグメントを生成するステップと、
（ｅ）前記ｓ個のセグメントを前記ＳＩＭＤマルチコア・プロセッサ・アーキテクチャのｓ個の処理要素に割り当てるステップとをさらに有し、
前記ステップ（ｃ）が、各処理要素上で各セグメントを転置するステップを含む、請求項１に記載のコンピュータ実装方法。
【請求項５】
各処理要素上で各セグメントを転置する前記ステップが、当該各処理要素に対しローカルのメモリ上で生じ、
前記ステップ（ｃ）が、前記処理要素の各々によって、各転置セグメントを当該処理要素のうち任意の処理要素に対してもローカルでないメモリに分散させるステップをさらに含む、請求項４に記載のコンピュータ実装方法。
【請求項６】
各処理要素上で各セグメントを転置する前記ステップが、当該各セグメントをｄ個（但し、ｄは２以上の正の整数）のサブディビジョンに分割するステップを含み、
各サブディビジョンは、当該処理要素に対してローカルのメモリのサイズを超えないものであり、
各処理要素上で各セグメントを転置する前記ステップが、当該各セグメントの各サブディビジョンを当該各処理要素上で転置するステップをさらに含む、請求項４に記載のコンピュータ実装方法。
【請求項７】
前記行列Ｍが、２５６×２５６、５１２×５１２又は１０２４×１０２４のサイズを有する行列の形態でＭＲＩ装置から取り込まれたイメージ・データの一部を格納する、請求項１に記載のコンピュータ実装方法。
【請求項８】
行列をＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上で転置するように構成されたアプリケーション・プログラムを格納するコンピュータ可読ストレージ媒体であって、
前記アプリケーション・プログラムが、
（ａ）第１形式の行列ＭをＳＩＭＤ形式の行列Ｓに変換するステップを実行し、
前記ＳＩＭＤ形式は、前記ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上の複数のコアの各々が前記行列Ｍ内の一の行上で１ＤＦＦＴ動作を並列に実行することを可能にするように構成され、
（ｂ）前記行列Ｓの各要素からＳＩＭＤ形式の前記行列Ｍの転置内の一の要素へのマッピングを検索するステップを実行し、
前記マッピングは、前記行列Ｍの転置用の前記行列ＳのＳＩＭＤ形式を保存するように定義され、
（ｃ）前記検索されたマッピングに基づき、ＳＩＭＤ転置行列Ｔを生成するステップを実行し、
前記ＳＩＭＤ転置行列Ｔは、前記ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上の複数のコアの各々が前記行列Ｍ内の転置された一の行上で１ＤＦＦＴ動作を並列に実行することを可能にするように構成される、コンピュータ可読ストレージ媒体。
【請求項９】
前記ＳＩＭＤ形式の前記行列Ｓは、前記行列Ｍのｒ行の同時処理のために構成され、前記変換されたデータは、複数ブロックのシーケンスを含み、各ブロックは、前記行列Ｍの連続するｒ行（但し、ｒは２以上の正の整数）を含み、当該連続するｒ行は、当該連続するｒ行の第１要素が、順次メモリ・アドレスに関して当該連続するｒ行の任意の第２要素に先行するようにインターリーブされる、請求項８に記載のコンピュータ可読ストレージ媒体。
【請求項１０】
前記第１形式は、行優先形式及び列優先形式のうちの１つである、請求項８に記載のコンピュータ可読ストレージ媒体。
【請求項１１】
前記アプリケーション・プログラムが、
（ｄ）前記行列Ｓに基づき、ｓ個（但し、ｓは２以上の正の整数）のセグメントを生成するステップを実行し、
（ｅ）前記ｓ個のセグメントを前記ＳＩＭＤマルチコア・プロセッサ・アーキテクチャのｓ個の処理要素に割り当てるステップを実行し、
前記ステップ（ｃ）が、各処理要素上で各セグメントを転置するステップを含む、請求項８に記載のコンピュータ可読ストレージ媒体。
【請求項１２】
各処理要素上で各セグメントを転置する前記ステップが、当該各処理要素に対しローカルのメモリ上で生じ、前記ステップ（ｃ）が、前記処理要素の各々によって、各転置セグメントを当該処理要素のうち任意の処理要素に対してもローカルでないメモリに分散させるステップをさらに含む、請求項１１に記載のコンピュータ可読ストレージ媒体。
【請求項１３】
各処理要素上で各セグメントを転置する前記ステップが、当該各セグメントをｄ個（但し、ｄは２以上の正の整数）のサブディビジョンに分割するステップを含み、
各サブディビジョンは、当該処理要素に対してローカルのメモリのサイズを超えないものであり、
各処理要素上で各セグメントを転置する前記ステップが、当該各セグメントの各サブディビジョンを当該各処理要素上で転置するステップをさらに含む、請求項１１に記載のコンピュータ可読ストレージ媒体。
【請求項１４】
前記行列Ｍが、２５６×２５６、５１２×５１２又は１０２４×１０２４のサイズを有する行列の形態でＭＲＩ装置から取り込まれたイメージ・データの一部を格納する、請求項８に記載のコンピュータ可読ストレージ媒体。
【請求項１５】
ＳＩＭＤマルチコア・プロセッサと、
行列をＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上で転置するように構成されたアプリケーション・プログラムを保持するメモリとを備え、
前記アプリケーション・プログラムが、
（ａ）第１形式の行列ＭをＳＩＭＤ形式の行列Ｓに変換するステップを実行し、
前記ＳＩＭＤ形式は、前記ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上の複数のコアの各々が前記行列Ｍ内の一の行上で１ＤＦＦＴ動作を並列に実行することを可能にするように構成され、
（ｂ）前記行列Ｓの各要素からＳＩＭＤ形式の前記行列Ｍの転置内の一の要素へのマッピングを検索するステップを実行し、
前記マッピングは、前記行列Ｍの転置用の前記行列ＳのＳＩＭＤ形式を保存するように定義され、
（ｃ）前記検索されたマッピングに基づき、ＳＩＭＤ転置行列Ｔを生成するステップを実行し、
前記ＳＩＭＤ転置行列Ｔは、前記ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上の複数のコアの各々が前記行列Ｍ内の転置された一の行上で１ＤＦＦＴ動作を並列に実行することを可能にするように構成される、システム。
【請求項１６】
前記ＳＩＭＤ形式の前記行列Ｓは、前記行列Ｍのｒ行の同時処理のために構成され、前記変換されたデータは、複数ブロックのシーケンスを含み、各ブロックは、前記行列Ｍの連続するｒ行（但し、ｒは２以上の正の整数）を含み、当該連続するｒ行は、当該連続するｒ行の第１要素が、順次メモリ・アドレスに関して当該連続するｒ行の任意の第２要素に先行するようにインターリーブされる、請求項１５に記載のシステム。
【請求項１７】
前記第１形式は、行優先形式及び列優先形式のうちの１つである、請求項１５に記載のシステム。
【請求項１８】
前記アプリケーション・プログラムが、
（ｄ）前記行列Ｓに基づき、ｓ個（但し、ｓは２以上の正の整数）のセグメントを生成するステップを実行し、
（ｅ）前記ｓ個のセグメントを前記ＳＩＭＤマルチコア・プロセッサ・アーキテクチャのｓ個の処理要素に割り当てるステップを実行し、
前記ステップ（ｃ）が、各処理要素上で各セグメントを転置するステップを含む、請求項１５に記載のシステム。
【請求項１９】
各処理要素上で各セグメントを転置する前記ステップが、当該各処理要素に対しローカルのメモリ上で生じ、前記ステップ（ｃ）が、前記処理要素の各々によって、各転置セグメントを当該処理要素のうち任意の処理要素に対してもローカルでないメモリに分散させるステップをさらに含む、請求項１８に記載のシステム。
【請求項２０】
各処理要素上で各セグメントを転置する前記ステップが、当該各セグメントをｄ個（但し、ｄは２以上の正の整数）のサブディビジョンに分割するステップを含み、
各サブディビジョンは、当該処理要素に対してローカルのメモリのサイズを超えないものであり、
各処理要素上で各セグメントを転置する前記ステップが、当該各セグメントの各サブディビジョンを当該各処理要素上で転置するステップをさらに含む、請求項１８に記載のシステム。
【請求項２１】
前記行列Ｍが、２５６×２５６、５１２×５１２又は１０２４×１０２４のサイズを有する行列の形態でＭＲＩ装置から取り込まれたイメージ・データの一部を格納する、請求項１５に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチコア・プロセッサ・アーキテクチャ上で効率的な高速フーリエ変換（ＦＦＴ）を実行することに係り、さらに詳細に説明すれば、ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上の効率的なＦＦＴに適合した形式（format）で配列データを転置することに係る。
【背景技術】
【０００２】
現に利用可能な幾つかのプロセッサは、「単一命令複数データ」（ＳＩＭＤ）拡張命令セットをサポートする。ＳＩＭＤは、単一命令が複数のデータ項目について並列に動作することを示す。例えば、１つの「加算」ＳＩＭＤ命令は、８つの１６ビット値を並列に加算することができる。すなわち、この加算動作（単一動作）は、単一のクロック・サイクル中に、互いに異なる８セットのデータ値（複数データ）について実行される。一般に、これらのデータ値は、一のベクトルの複数の要素として供給される。従って、ＳＩＭＤ処理は、ベクトル処理と呼ばれることもある。ＳＩＭＤ命令は、単一命令の一部として複数の動作を実行することにより、実行速度を著しく増加させる。ＳＩＭＤ拡張命令セットの周知の例は、マルチメディア処理用の拡張命令セットであるＭＭＸ、ストリーミングＳＩＭＤ拡張命令セットであるＳＳＥ及びベクトル演算用の拡張命令セットであるＶＭＸを含む。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
ＳＩＭＤマルチコア・プロセッサ上で高速フーリエ変換（ＦＦＴ）を効率的に計算することは、困難であることが分かった。サイズが大きな１次元ＦＦＴ（１ＤＦＦＴ）については、処理対象の独立データ・ブロックがより大きなグループになることに起因して、より高度の並列性（parallelism）を得ることができる。しかし、１ＤＦＦＴは、複雑さＯ（Ｎ ｌｏｇ Ｎ）を有する、基本的に再帰的なアルゴリズムである。従って、サイズがより小さい１ＤＦＦＴについては、単一行の並列性は非常に小さい。さらに、ＦＦＴを実行するための現在のライブラリは、比較的小さな配列データ上で実行されるＦＦＴ(例えば、２５６×２５６ピクセル、５１２×５１２ピクセル又は１０２４×１０２４ピクセルのイメージ・サイズ上で実行されるＦＦＴ）に適合していない。より大きなサイズの１ＤＦＦＴから或る程度のＳＩＭＤ並列性が抽出されるが、より小さなサイズについては、行内アルゴリズムのごく小さな並列性が抽出されるに過ぎない。さらに、マルチコアＦＦＴ用の現在のライブラリは、独立型であるために、計算−動作−入力／出力（ＩＯ）の最適化に必要とされる作業の機能的なパイプライン処理を可能にしない。
【課題を解決するための手段】
【０００４】
本発明の１つの実施形態は、  行列をＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上で転置するためのコンピュータ実装方法に向けられている。このコンピュータ実装方法は、
（ａ）第１形式の行列ＭをＳＩＭＤ形式の行列Ｓに変換するステップを有し、
前記ＳＩＭＤ形式は、前記ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上の複数のコアの各々が前記行列Ｍ内の一の行上で１ＤＦＦＴ動作を並列に実行することを可能にするように構成され、
（ｂ）前記行列Ｓの各要素からＳＩＭＤ形式の前記行列Ｍの転置内の一の要素へのマッピングを検索するステップを有し、
前記マッピングは、前記行列Ｍの転置用の前記行列ＳのＳＩＭＤ形式を保存するように定義され、
（ｃ）前記検索されたマッピングに基づき、ＳＩＭＤ転置行列Ｔを生成するステップを有し、
前記ＳＩＭＤ転置行列Ｔは、前記ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上の複数のコアの各々が前記行列Ｍ内の転置された一の行上で１ＤＦＦＴ動作を並列に実行することを可能にするように構成される。
【０００５】
本発明の他の実施形態は、行列をＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上で転置するように構成されたアプリケーション・プログラムを格納するコンピュータ可読ストレージ媒体に向けられている。前記アプリケーション・プログラムは、
（ａ）第１形式の行列ＭをＳＩＭＤ形式の行列Ｓに変換するステップを実行し、
前記ＳＩＭＤ形式は、前記ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上の複数のコアの各々が前記行列Ｍ内の一の行上で１ＤＦＦＴ動作を並列に実行することを可能にするように構成され、
（ｂ）前記行列Ｓの各要素からＳＩＭＤ形式の前記行列Ｍの転置内の一の要素へのマッピングを検索するステップを実行し、
前記マッピングは、前記行列Ｍの転置用の前記行列ＳのＳＩＭＤ形式を保存するように定義され、
（ｃ）前記検索されたマッピングに基づき、ＳＩＭＤ転置行列Ｔを生成するステップを実行し、
前記ＳＩＭＤ転置行列Ｔは、前記ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上の複数のコアの各々が前記行列Ｍ内の転置された一の行上で１ＤＦＦＴ動作を並列に実行することを可能にするように構成される。
【０００６】
本発明のさらに他の実施形態は、ＳＩＭＤマルチコア・プロセッサと、行列をＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上で転置するように構成されたアプリケーション・プログラムを保持するメモリとを備えるシステムに向けられている。前記アプリケーション・プログラムは、
（ａ）第１形式の行列ＭをＳＩＭＤ形式の行列Ｓに変換するステップを実行し、
前記ＳＩＭＤ形式は、前記ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上の複数のコアの各々が前記行列Ｍ内の一の行上で１ＤＦＦＴ動作を並列に実行することを可能にするように構成され、
（ｂ）前記行列Ｓの各要素からＳＩＭＤ形式の前記行列Ｍの転置内の一の要素へのマッピングを検索するステップを実行し、
前記マッピングは、前記行列Ｍの転置用の前記行列ＳのＳＩＭＤ形式を保存するように定義され、
（ｃ）前記検索されたマッピングに基づき、ＳＩＭＤ転置行列Ｔを生成するステップを実行し、
前記ＳＩＭＤ転置行列Ｔは、前記ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上の複数のコアの各々が前記行列Ｍ内の転置された一の行上で１ＤＦＦＴ動作を並列に実行することを可能にするように構成される。
【発明の効果】
【０００７】
本発明は、ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上で配列データを転置することができるという効果を奏する。また、本発明は、通常のデータ形式を有する行列の複数の列上で動作するように、行方向（row-wise）アルゴリズムを修正なしでＳＩＭＤ転置行列に適用することができるという効果を奏する。
【図面の簡単な説明】
【０００８】
【図１】本発明の１つの実施形態に従った、配列データをＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上で転置するためのシステムを示すブロック図である。
【図２】本発明の１つの実施形態に従った、４×４の行列上で２Ｄ ＦＦＴを実行するためのデータ・フローを示す図である。
【図３】本発明の１つの実施形態に従った、４ウェイのＳＩＭＤ形式を有する８×８の行列上でＳＩＭＤ転置を実行するためのデータ・フローを示す図である。
【図４】本発明の１つの実施形態に従った、行列の複数のセグメントを同時に転置するためのデータ・フローを示す図である。
【図５】本発明の１つの実施形態に従った、行列の複数のサブディビジョンを同時に転置するためのデータ・フローを示す図である。
【図６】本発明の１つの実施形態に従った、ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上で効率的なＦＦＴを実行するための方法を示すフローチャートである。
【図７】本発明の１つの実施形態に従った、ＳＩＭＤ形式のデータを転置するための方法を示すフローチャートである。
【図８】本発明の１つの実施形態に従った、ＳＩＭＤ転置機構の諸コンポーネントを示すブロック図である。
【発明を実施するための形態】
【０００９】
本発明の諸実施形態は、ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上の効率的な多次元ＦＦＴに適合した形式で配列データを転置するための技術を提供する。配列データは、行優先順序（row-major order）で格納された多次元配列からＳＩＭＤ形式に変換される。ＳＩＭＤ形式に変換されたデータは、複数ブロックのシーケンスを含み、その各ブロックは、ＳＩＭＤベクトル・プロセッサが複数の行（ｒ行）上で同時に動作するように、ｒ行からのデータをインターリーブする。すなわち、単一のベクトル命令は、一度にｒ個の行要素（各行から１つずつ）を処理する。その結果、より小さなサイズの１ＤＦＦＴの実行は、マルチコア・プロセッサ内で最適化される。より小さなサイズの１Ｄ（１次元）ＦＦＴの例は、２５６×２５６、５１２×５１２、１０２４×１０２４及び２０４８×２０４８の行列上で実行されるＦＦＴを含む。
【００１０】
より小さなサイズの１ＤＦＦＴについての単一行の並列性を増加させるために、本発明の諸実施形態が提供するＳＩＭＤデータ構造は、複数の浮動小数点値を同時に処理すべき一のＳＩＭＤベクトル命令を使用するように構成されている。例えば、一のＣｅｌｌＢＥ（CellBroadband Engine）プロセッサは、単一のＳＩＭＤベクトル命令を用いて、４つの単精度浮動小数点値を同時に処理する。このＳＩＭＤデータ構造は、ＣｅｌｌＢＥプロセッサのようなＳＩＭＤマルチコア・プロセッサ上でＦＦＴを処理するように適合化される。さらに、１つの実施形態では、ＦＦＴアルゴリズムは、このＳＩＭＤデータ構造とともに使用するように最適化される。
【００１１】
さらに、より高次元のＦＦＴに必要な諸動作は、このデータ構造を使用して構築される。例えば、イメージ処理の分野では、イメージ・データは、２次元配列として格納される。さらに、２次元配列のデータは、（例えば、Ｃプログラミング言語によって使用される）通常の行優先順序又は（例えば、ＦＯＲＴＲＡＮプログラミング言語によって使用される）列優先順序（column-major order）で格納される。イメージ・ビューアのようなイメージ・データ上で動作するアプリケーションは、イメージ・データが行優先（又は列優先）順序で格納されることを期待する。２次元配列は、イメージ・データをピクセル位置に対応する（ｘ，ｙ）ピクセル形式で格納するのが普通である。
【００１２】
本発明の諸実施形態がその上で動作するデータ構造は、より小さなサイズのＦＦＴ（例えば、ＭＲＩ装置から取り込まれた２５６×２５６、５１２×５１２又は１０２４×１０２４のサイズを有するイメージ内のイメージ・データ）が、ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上で効率的に処理されることを可能にする。通常の行優先順序で格納されたデータは、複数行ＳＩＭＤ１Ｄ ＦＦＴアルゴリズムに適合したＳＩＭＤデータ形式に変換される。このＳＩＭＤデータ形式を使用するために、ＦＦＴアルゴリズムは、一度にｒ行及び／又はｒ列（例えばｒ＝４）上で標準の基数−２又は基数−４のアルゴリズム（又は他の基数（ｎ）のＦＦＴアルゴリズムの組み合わせ）を実行するように、これを修正することができる。単一の命令を使用して処理される行又は列の数は、プロセッサのＳＩＭＤレジスタ内に配置される浮動小数点データ要素の数に対応する。１２８ビットのＳＩＭＤレジスタについては、ｒ＝４、すなわち、４つの単精度浮動小数点値を当該レジスタ内に配置することができる。
【００１３】
前述のように、本明細書に開示した技術は、ＳＩＭＤ転置動作を定義する。このＳＩＭＤ転置動作は、既にＳＩＭＤ形式を有するデータ（例えば、イメージ）を転置するために使用される。１つの実施形態では、ベクトル複数行ＦＦＴコードがｒ行のグループにおけるデータを一度に処理した後（例えば、４バイトの浮動小数点データ及び１２８ビットのＳＩＭＤレジスタの場合、ｒ＝４）、このデータは、表示のために及び／又はこのデータを行優先順序（又は列優先順序）で受け取ることを期待するアプリケーションによるさらなる処理のために、通常の行優先順序に逆変換される。
【００１４】
以下、本発明の諸実施形態を説明する。しかし、本発明は、本明細書に開示した特定の実施形態に制限されないことを理解されたい。以下で説明する諸特徴及び諸要素の任意の組み合わせは、異なる実施形態に関係するか否かに拘わらず、本発明を実装又は実施するように意図される。さらに、本発明の諸実施形態は、他の可能な解決手段及び／又は従来技術に比べて優れた効果を奏することができるが、所与の実施形態が特定の効果を奏するか否かは、本発明を制限するものではない。従って、以下で説明する諸側面、諸特徴、諸実施形態及び諸効果は、例示であるに過ぎず、請求項において明示的に記載されている場合を除き、請求項に係る発明の制限事項であると見なされない。同様に、「本発明」という用語の使用は、本明細書に開示した任意の発明的主題の一般化として解すべきではなく、請求項において明示的に記載されている場合を除き、請求項に係る発明の制限事項であると見なされるべきではない。
【００１５】
本発明の１つの実施形態は、コンピュータ・システムと関連して使用するためのプログラムとして実装される。かかるプログラムは、（本明細書に開示した方法を含む）諸実施形態の諸機能を定義し、種々のコンピュータ可読ストレージ媒体上に保持される。例えば、コンピュータ可読ストレージ媒体は、（ｉ）情報を永久的に格納するための書き込み不能なストレージ媒体（例えば、ＣＤ−ＲＯＭドライブによって読み取り可能なＣＤ−ＲＯＭディスクのようなコンピュータ内の読み取り専用メモリ装置）と、（ｉｉ）変更可能な情報を格納するための書き込み可能なストレージ媒体（例えば、ディスケット・ドライブ内のフレキシブル・ディスク又はハード・ディスク・ドライブ）とを含む。かかるコンピュータ可読ストレージ媒体は、本発明の諸機能を指令するコンピュータ可読命令を担持する場合、本発明の諸実施形態である。他の媒体は、コンピュータに情報を伝送するための通信媒体を含み、かかる通信媒体は、コンピュータ、電話網、無線通信ネットワーク等を含む。特に、後者の実施形態は、インターネット及び他のネットワークと情報を送受することを含む。かかる通信媒体は、本発明の諸機能を指令するコンピュータ可読命令を搬送する場合、本発明の諸実施形態である。広義には、コンピュータ可読ストレージ媒体及び通信媒体は、本明細書においてコンピュータ可読媒体と称する。
【００１６】
本発明の諸実施形態を実装するために実行される諸ルーチンは、オペレーティング・システム又は特定のアプリケーションの一部、コンポーネント、プログラム、モジュール、オブジェクト又は諸命令のシーケンスとすることができる。本発明のコンピュータ・プログラムは、複数の命令から構成され、そしてこれらの命令は、ネイティブ・コンピュータによって機械可読フォーマット（従って、実行可能な命令）に変換される。また、諸プログラムは、諸変数及び諸データ構造から構成され、その一方又は両方は、当該プログラムに対しローカルに存在するか、メモリ内に存在するか、又はストレージ装置上に存在する。さらに、以下で説明する種々のプログラムは、本発明の特定の実施形態で実装される当該プログラムを使用するアプリケーションに基づいて、これを識別することができる。しかし、以下で使用する任意の特定のプログラム命名法は、便宜上のものであるに過ぎないから、本発明は、かかる命名法によって識別されるか及び／又は暗示される特定のアプリケーション内でのみ使用するように制限されない。
【００１７】
以下、プロセッサ（ＰＰＵ：Power Processor Unit）並びにそのＬ１及びＬ２キャッシュを有するＰＰＥ（Power Processor Element ）を含むＣｅｌｌＢＥを参照して、実施形態を説明する。各Ｃｅｌｌ ＢＥコンピュータは、複数のＳＰＥ（SynergisticProcessor Element）と、ローカル・ストアと、高帯域の内部要素相互接続バスであるＥＩＢ（Element Interconnect Bus）とを含む。各ＳＰＥは、ＳＰＵ（Synergistic Processor Unit）を提供する。本明細書及び図面の記述は、ＣｅｌｌＢＥコンピュータを想定しているが、本発明の諸実施形態は、他のプロセッサ・アーキテクチャに関連して使用するように容易に適合させることができる。
【００１８】
図１は、本発明の１つの実施形態に従った、ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上で配列データを転置するためのシステム１００を示すブロック図である。システム１００は、コンピュータ１１０を含む。図示のように、コンピュータ１１０は、ＣｅｌｌＢＥコンピュータである。さらに、コンピュータ１１０は、ネットワークを介して他のコンピュータに接続することができる。ネットワークは、通信ネットワーク及び／又は広域ネットワーク（ＷＡＮ）とすることができる。特定の実施形態では、ネットワークはインターネットである。
【００１９】
図示のように、ＣｅｌｌＢＥコンピュータ１１０は、Ｃｅｌｌ ＰＰＵ １２０と、８つのＣｅｌｌＳＰＵ １３０、１３２と、ＥＩＢ １４０と、メモリ１５０と、ストレージ装置とを含む。コンピュータ１１０に含まれる１つ以上のプロセッサ１２０、１３０、１３２は、メモリ１５０及び任意のストレージ装置（例えば、ハード・ドライブ、フラッシュ・メモリ又はＣＤ若しくはＤＶＤ−ＲＯＭのようなコンピュータ可読ストレージ媒体）から命令及びデータを獲得する。各プロセッサ１２０、１３０、１３２は、命令、論理及び数学的処理を実行するプログラム可能論理装置である。さらに、コンピュータ１１０は、ストレージ（例えば、ハード・ディスク・ドライブ、フラッシュ・メモリ装置、光媒体等）を含む。メモリ１５０は、コンピュータ１１０の動作を管理するように構成されたオペレーティング・システムを含む。オペレーティング・システムの例は、ＵＮＩＸ（登録商標）、マイクロソフト社のＷｉｎｄｏｗｓ（登録商標）オペレーティング・システム及びＬｉｎｕｘ（登録商標）オペレーティング・システムを含む。
【００２０】
また、コンピュータ１１０は、他の周辺装置（例えば、ディスプレイ、キーボード・マウス、ネットワーク・インタフェース装置等）を含む。図示のように、コンピュータ１１０のメモリ１５０は、ＳＩＭＤ転置機構１７０及び行列１５２を含む。行列１５２は、複数の行列セグメント１５４、１５６、１５８、１６０を含み、当該各セグメントは行列１５２の細分された一部を表す。特に、各セグメントは、ＳＩＭＤ転置機構１７０によって転置すべき諸要素の集合を表す。図２〜図８及び関連する記述は、コンピュータ１１０上で稼働するＳＩＭＤ転置機構１７０の構造及び動作を詳述する。１つの実施形態に従って、１つ以上のＣｅｌｌＳＰＵ １３０、１３２のローカル・ストアは、ＳＩＭＤ転置機構１７０及び行列セグメント１５４、１５６、１５８、１６０を含む。
【００２１】
図２は、本発明の１つの実施形態に従った、４×４の行列上で２Ｄ ＦＦＴを実行するためのデータ・フロー２００を示す。図示のように、データ・フロー２００は、行優先形式の行列２１０を含む。行列２１０は、値ｖ１ないしｖ１６を含む。さらに、行列２１０（及び図２の他の全ての行列）は、物理メモリ内に順次に格納することができる。例えば、（値ｖ１ないしｖ１６を保持する）行列２１０の各個別セルは、メモリ１５０の順次メモリ・アドレスに対応する。２ＤＦＦＴは、通常のデータ形式（例えば、行優先形式）における行列上の動作を表す、ステップ２１１、２１３、２１５、２１７を介して、行列２１０上で実行することができる。行列２１８は、行列２１０の２ＤＦＦＴの結果を表す。
【００２２】
行列２１０とは対照的に、行列２２０は、ＳＩＭＤ形式で図示されている。但し、複数の行列値は、複数の行が並列に処理されるように、メモリ内で順序付けられる。例えば、２ＤＦＦＴは、ＳＩＭＤ形式の行列上の動作を表す、ステップ２２１、２２３、２２５、２２７を介して、ＳＩＭＤ形式の行列２２０上で実行することができる。さらに、行列２１０の２ＤＦＦＴの結果を表す行列２１８を生成するために、（ステップ２２９を介して）ＳＩＭＤ形式から行優先形式への逆変換を実行することができる。
【００２３】
行優先形式の行列２１０上の２ＤＦＦＴは、（ステップ２１１を介する）行方向の１Ｄ ＦＦＴに続いて、（ステップ２１３、２１５、２１７を介する）列方向のＦＦＴを含む。ステップ２１１では、１ＤＦＦＴを行列２１０の複数の行上で実行することにより、行列２１２を生成する。例えば、行列２１０の第１行（ｖ１，ｖ２，ｖ３，ｖ４）上の１ＤＦＦＴは、ｖ１'，ｖ２'，ｖ３'，ｖ４' を生成する。ステップ２１３では、行列２１２を転置することにより、行列２１４を生成する。すなわち、行列２１２は、その主対角線（ｖ１'，ｖ６'，ｖ１１'，ｖ１６' ）によって折り返される。例えば、ｖ２' 及びｖ５' は、それぞれの位置を交換する。
【００２４】
ステップ２１５では、行列２１４の複数の行上で行方向の１ＤＦＦＴが実行される。実際には、ステップ２１５の行方向の１Ｄ ＦＦＴは、ステップ２１３で実行された転置動作に起因して、行列２１２の複数の列上で動作する。例えば、行列２１４の第１行（ｖ１'，ｖ５'，ｖ９'，ｖ１３' ）上の１Ｄ ＦＦＴは、ｖ１''，ｖ５''，ｖ９''，ｖ１３'' を生成する。ステップ２１７では、行列２１６上で第２の転置動作を実行することにより、行列２１８を生成する（その結果、行列２１８の複数の行は、行列２１０の複数の行に対応する）。すなわち、行列２１６は、その主対角線（ｖ１''，ｖ６''，ｖ１１''，ｖ１６'' ）によって折り返される。例えば、ｖ５'' 及びｖ２'' は、それぞれの位置を交換する。行列２１８（ｖ１'' ないしｖ１６'' ）は、行優先形式の行列２１０の２ＤＦＦＴ（周波数領域表現）を表す。
【００２５】
代替的に、（ステップ２１９を介して）行優先形式の行列２１０をＳＩＭＤ形式の行列２２０に変換することにより、行列２１０の２ＤＦＦＴの計算中に行並列性を活用することができる。行並列性を活用することができるのは、ＳＩＭＤ形式のデータがメモリ内に配置される正確な方法（way）のためである。すなわち、ＳＩＭＤ形式の行列は、メモリ内に順次に格納された複数の浮動小数点値を同時に処理するために、ＳＩＭＤベクトル命令を使用するように構成される。例えば、ＣｅｌｌＢＥプロセッサは、単一のＳＩＭＤベクトル命令を用いて、４つの単精度浮動小数点値を同時に処理する。ＳＩＭＤ形式の行列は、かかるＳＩＭＤマルチコア・プロセッサ上でＦＦＴを処理するように適合化される。図２に示す例では、行列２２０は、２行が同時に処理されることを可能にする。すなわち、１つのＳＩＭＤベクトル命令（単一命令）は、２つの単精度浮動小数点値（複数データ）上で動作することができる。
【００２６】
ステップ２１９では、行優先形式の行列２１０は、ＳＩＭＤ形式の行列２２０に変換される。ＳＩＭＤ形式は、次のように記述することができる。２次元配列の諸要素は、任意の通常の順序（例えば、複数の行が順次に格納される行優先順序、又は複数の列が順次に格納される列優先順序）で格納される。説明の便宜上、２次元データが次の値を有する４×４の行列であると仮定する。
（表１）
＜２次元データの例＞
１    ２    ３    ４
５    ６    ７    ８
９  １０  １１  １２
１３  １４  １５  １６
【００２７】
かかる４×４の行列は、２次元配列として表される。この２次元配列を宣言するために、例えば、次のようなソース・コードの構文が使用される。
（表２）
＜配列宣言の例−Ｃソース・コード＞
int data[4][4] = { {1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16}};
【００２８】
Ｃプログラミング言語は、前記宣言に基づき、行優先順序を使用するから、諸要素は、メモリ１５０内の順次メモリ・アドレス（１〜１６としてラベル付けされる）に次のように格納される。
（表３）
＜行優先順序の例＞
1 2 3 4 5 6 7 89 10 11 12 13 14 15 16
【００２９】
代替的に、この４×４の行列は、列優先順序を使用する２次元配列として表される。列優先順序を使用するプログラミング言語の１例は、ＦＯＲＴＲＡＮである。この場合、諸要素は、メモリ１５０内の順次メモリ・アドレスに次のように格納される。
（表４）
＜列優先順序の例＞
1 5 9 13 2 6 10 143 7 11 15 4 8 12 16
【００３０】
１つの実施形態では、ＳＩＭＤフォーマッタは、データを複数ブロックのシーケンスに変換する。但し、各ブロックは、ｒ行を表す。その後、ｒ行は、ＳＩＭＤ動作を使用して同時に処理される。ブロック数は、ｂによって表される。もし、ｍがこの２次元データの行数を表すものとすれば、ブロック数ｂは、式ｂ＝ｍ／ｒによって計算される。例えば、各ブロックが２行（ｒ＝２）を表すものとすれば、４×４の行列（ｍ＝４）は、２ブロック（４／２＝２）を含む。ブロック１は、最初の２行（すなわち、値１２ ３ ４及び５６ ７ ８を保持する２行）を含み、ブロック２は、最後の２行（すなわち、値９１０ １１ １２及び１３１４ １５ １６を保持する２行）を含む。ＳＩＭＤフォーマッタは、これらのブロックをメモリ内に順次に配置する。しかし、各ブロック内では、ＳＩＭＤフォーマッタは、各行の第１要素が（順次メモリ・アドレスに関して）各行の第２要素に先行するように、各行の諸要素をインターリーブする。
【００３１】
例えば、行列２２０のブロック１は、行列２１０の第１及び第２行からの値を保持する。しかし、ＳＩＭＤフォーマッタは、これらの行の全ての第１要素（値１及び５）が、これらの行の任意の第２要素（値２及び６）の前に来るように、これらの諸要素をインターリーブする。同様に、これらの行の全ての第２要素（値２及び６）は、（順次メモリ・アドレスに関して）これらの行の任意の第３要素（値３及び７）に先行し、以下同様である。図２において、行列２１０からの２次元データは、ＳＩＭＤ形式に変換された行列２２０として図示されている。ＳＩＭＤ形式のデータの諸要素は、メモリ１５０内の順次メモリ・アドレスに次のように格納される。
（表５）
＜ＳＩＭＤ形式の例＞
1 5 2 6 3 7 4 89 13 10 14 11 15 12 16
【００３２】
ＳＩＭＤ形式の２次元データは、２ブロックのシーケンスとして表される。但し、各ブロックは、２行（ｒ＝２）を表す。各ブロックでは、２行からのデータは、当該２行の全ての第１要素が当該２行の任意の第２要素の前に来るように、インターリーブされる。このことは、全ての要素についても、以下同様である。より一般的に説明すれば、ＳＩＭＤ形式では、当該ブロックにおける当該２行の全てのｉ番目の要素は、当該ブロックにおける当該２行の任意の（ｉ＋１）番目の要素の前に来る。各要素は、整数、倍精度浮動小数点数又は単精度浮動小数点数のような任意のデータ・タイプとすることができる。さらに、各要素は、複素数（例えば、メモリ内に順次に格納される２つの１６ビット単精度浮動小数点数によって表される複素数）とすることもできる。また、複素数は、２つの配列として、すなわち当該複素数の実数部のための第１配列及び当該複素数の虚数部のための第２配列として、表すことができる。
【００３３】
ＳＩＭＤ形式では、２次元データは、一度にｒ行を同時に処理するように適合される。具体的には、各ＳＩＭＤ命令は、ｒ行の各々からの１要素を処理することができ、そのため、ｒ要素の全体については、単一のＳＩＭＤ命令で処理される。従って、ＳＩＭＤ形式は、複数行ＳＩＭＤ１Ｄ ＦＦＴアルゴリズムに適合する。というのは、ＳＩＭＤ形式は、（ＳＩＭＤ形式で動くように修正された）当該アルゴリズムが計算中に行並列性を活用することを可能にするからである。
【００３４】
ステップ２１９では、ＳＩＭＤフォーマッタは、行優先形式の行列２１０をＳＩＭＤ形式の行列２２０に変換する。この特定の例では、行列２２０は、２ウェイのＳＩＭＤ形式（ｒ＝２、すなわち各ブロックは２行を表す）にある。例えば、行列２２０の第１行は、（行列２１０のようにｖ１，ｖ２，ｖ３，ｖ４ではなく）ｖ１，ｖ５，ｖ２，ｖ６になる。
【００３５】
ＳＩＭＤ形式の行列２２０上の２ＤＦＦＴは、（ステップ２２１を介する）行方向の１Ｄ ＦＦＴに続いて、（ステップ２２３、２２５、２２７を介する）列方向のＦＦＴを含む。ステップ２２１では、行列２２０の諸要素（行列２２０の複数の行に対応）上で１ＤＦＦＴを実行することにより、行列２２２を生成する。例えば、行列２１０の第１行に対応する行列２２０の諸要素（ｖ１，ｖ２，ｖ３，ｖ４）上で１Ｄ ＦＦＴを実行することにより、ｖ１'，ｖ２'，ｖ３'，ｖ４' が生成される。ステップ２２１で実行される１Ｄ ＦＦＴは、ＳＩＭＤ形式の行列２２０の列並列性を活用することができる。例えば、単一のＳＩＭＤベクトル命令を使用することにより、複数の行（ｖ１，ｖ２，ｖ３，ｖ４）及び（ｖ５，ｖ６，ｖ７，ｖ８ ）を同時に処理することができる。実行される１Ｄ ＦＦＴは、ＳＩＭＤ形式の行列２２０に関連してＳＩＭＤベクトル命令を使用するように修正された、任意のスカラー１ＤＦＦＴアルゴリズムを含むことができる。
【００３６】
ステップ２２３では、ＳＩＭＤ転置機構１７０は、行列２２４を生成する。具体的には、ＳＩＭＤ転置機構１７０は、行列２１０の１行（例えば、ｖ１，ｖ２，ｖ３，ｖ４）に対応する行列２２２の諸位置（例えば、ｖ１'，ｖ２'，ｖ３'，ｖ４' ）上の諸動作が行列２１０の１列（例えば、ｖ１，ｖ５，ｖ９，ｖ１３）上で動作するように、行列２２２を再配置する。例えば、ＳＩＭＤ転置機構１７０は、ｖ１'，ｖ２'，ｖ３'，ｖ４' の位置をｖ１'，ｖ５'，ｖ９'，ｖ１３' とそれぞれ交換する。１つの実施形態では、転置は、ＳＩＭＤ転置行列２２４における諸要素の新しい位置を表す正確なインデックスを記述する。すなわち、このマッピングは、ＳＩＭＤ形式の行列の各要素をＳＩＭＤ転置行列の一の要素に関連付ける。表６は、２ウェイのＳＩＭＤ形式を有する４×４の行列用のマッピングを例示する。
（表６）
＜要素マッピングの例（２ウェイのＳＩＭＤ、４×４の行列＞
入力インデックス（行列２２２）    出力インデックス（行列２２４）
−−−−−−−−−−−−−− −−−−−−−−−−−−−−
行１、列１（ｖ１' ）                行１、列１
行１、列２（ｖ５' ）                行１、列３
行１、列３（ｖ２' ）                行１、列２
行１、列４（ｖ６' ）                行１、列４
行２、列１（ｖ３' ）                行３、列１
行２、列２（ｖ７' ）                行３、列３
行２、列３（ｖ４' ）                行３、列２
行２、列４（ｖ８' ）                行３、列４
行３、列１（ｖ９' ）                行２、列１
行３、列２（ｖ１３' ）              行２、列３
行３、列３（ｖ１０' ）              行２、列２
行３、列４（ｖ１４' ）              行２、列４
行４、列１（ｖ１１' ）              行４、列１
行４、列２（ｖ１５' ）              行４、列３
行４、列３（ｖ１２' ）              行４、列２
行４、列４（ｖ１６' ）              行４、列４
【００３７】
この特定の例では、ＳＩＭＤ転置機構１７０は、表６の定義されたマッピングを使用して、行列２２２を行列２２４に変換する。すなわち、このマッピングは、行列２１０の１行（例えば、ｖ１，ｖ２，ｖ３，ｖ４）に対応する行列２２２の諸位置（例えば、ｖ１'，ｖ２'，ｖ３'，ｖ４' ）上の諸動作が行列２１０の１列（例えば、ｖ１，ｖ５，ｖ９，ｖ１３）上で動作するように、ＳＩＭＤ形式の行列２２２をＳＩＭＤ転置行列２２４に変換する。一般に、ＳＩＭＤ転置行列は、行優先形式の行列２１０の転置のＳＩＭＤ変換を実行することに同等である。
【００３８】
表６の例では、ＳＩＭＤ転置機構１７０は、行列２２２の中間の２行をそれぞれ交換し、行列２２２の各行の中間の２要素をそれぞれ交換する。
【００３９】
本明細書において、本発明の諸実施形態は、２ウェイのＳＩＭＤ形式を有する４×４の行列のＳＩＭＤ転置動作に関して説明されるが、本発明の諸実施形態は、他の行列サイズ（例えば、２５６×２５６の行列及び２の累乗とは異なるサイズを有する行列を含む）、他の行列タイプ（例えば、３Ｄ及び４Ｄ行列のようなより次元の大きい行列）及び他のＳＩＭＤ形式タイプ（例えば、４ウェイのＳＩＭＤ）をサポートするように適合させることができる。
【００４０】
ステップ２２５では、行方向の１ＤＦＦＴ（ステップ２２１の動作と同じ）が、行列２２４の諸要素上で実行される。実際には、ステップ２２５の行方向の１ＤＦＦＴは、ステップ２２３で実行された転置動作に起因して、行列２１０の複数の列に対応する行列２２４の諸要素上で動作する。例えば、行列２１０の第１列に対応する行列２２４の諸要素（ｖ１'，ｖ５'，ｖ９'，ｖ１３' ）上の１Ｄ ＦＦＴは、（ｖ１''，ｖ５''，ｖ９''，ｖ１３'' ）を生成する。ステップ２２７では、行列２２６上で第２のＳＩＭＤ転置動作を実行することにより、行列２２８を生成する（その結果、行列２２８の複数の行は、行列２２０の複数の行に対応する）。例えば、ＳＩＭＤ転置機構１７０は、表６のマッピングを逆方向に実行することにより、行列２２８を生成することができる。ステップ２２９では、行列２２８をＳＩＭＤ形式から通常のデータ形式（例えば、行優先形式）に逆変換することにより、行列２１８を生成する。
【００４１】
図３は、本発明の１つの実施形態に従った、４ウェイのＳＩＭＤ形式を有する８×８の行列上でＳＩＭＤ転置を実行するためのデータ・フロー３００を示す。このデータ・フロー３００では、記号「ｖ１」ないし「ｖ６４」（及び記号「ｖ１' 」ないし「ｖ６４' 」）は、単に「１」ないし「６４」を表すものとする。すなわち、「１」ないし「６４」は、実際の数値を表さないが、行列３１０の諸要素を表すものとする。図示のように、データ・フロー３１０は、行優先形式の行列３１０を含む。行列３１０（及び図３の他の全ての行列）は、物理メモリ内に順次に格納することができる。例えば、（記号１ないし６４を保持する）行列３１０の各個別セルは、メモリ１５０の順次メモリ・アドレスに対応することができる。ステップ３１５（図２のステップ２１９及び２２１に対応）では、行列３１０が４ウェイのＳＩＭＤ形式に変換され（そして、行列３１０の複数の行上で１ＤＦＦＴが実行され）、その結果、行列３２０が生成される。ステップ３２５（図２のステップ２２３に対応）では、ＳＩＭＤ転置機構１７０は、行列３２０上でＳＩＭＤ転置を実行することにより、行列３３０を生成する。４×４の行列用のマッピングを生成するための一般的な技術（例えば、表６）を使用して、８×８の行列用の（又は任意のサイズの行列用の）マッピングを生成することができる。
【００４２】
すなわち、前述のように、これらのマッピングは、転置行列用のＳＩＭＤ形式を保存するために使用することができ、そのため、当該行列の複数の行を並列に処理することが可能になる。１つの実施形態では、所与の行列サイズ（例えば、４×４、８×８、２５６×２５６等）用のマッピングをハード・コード化し且つこれを使用すると、ＳＩＭＤ形式の転置行列を作成するために、ＳＩＭＤ転置機構１７０がＳＩＭＤ形式の行列の諸要素をどのように交換しなければならないかを識別することができる。
【００４３】
従って、ＳＩＭＤ転置機構１７０は、行列３１０の１行に対応する行列３２０の諸の位置（例えば、１ないし８）上の諸動作が行列３１０の１列（例えば、１、９、１７、２５、３３、４１、４９、５７）上で動作するように、行列３２０を再配置する。例えば、ＳＩＭＤ転置機構１７０は、ｖ２'，ｖ１０'，ｖ１８'，ｖ２６' の位置をｖ９'，ｖ１０'，ｖ１１'，ｖ１２' とそれぞれ交換する。ＳＩＭＤ転置行列は、行優先形式の行列３１０の転置を実行することに同等である。
【００４４】
ステップ３３５（図２のステップ２２５に対応）では、行列３３０の諸要素（行列３１０の複数の列に対応）上で１ＤＦＦＴが実行される。ステップ３３５で実行される１Ｄ ＦＦＴは、ＳＩＭＤ形式の行列３２０の諸要素（行列３１０の複数の列に対応）の列並列性を活用することができる。例えば、単一のＳＩＭＤベクトル命令を使用して、４列（１、９、１７、２５、３３、４１、４９、５７）（２、１０、１８、２６、３４、４２、５０、５８）（３、１１、１９、２７、３５、４３、５１、５９）、及び（４、１２、２０、２８、３６、４４、５２、６０）を同時に処理することができる。
【００４５】
図４は、本発明の１つの実施形態に従った、行列を転置するためのデータ・フロー４００を示す。図示のように、データ・フロー４００は、０ないし１５の行列インデックスを使用する、行優先形式の行列４１０を含む。ステップ４５０では、ＳＩＭＤ転置機構１７０は、行列４１０を複数のセグメント４１２、４１４、４１６、４１８に分割する。ＳＩＭＤ転置機構１７０は、行列のサイズ及びコンピュータ１１０の処理要素の数に基づき、当該行列を複数のセグメントに分割することができる。説明の便宜上、ＳＩＭＤ転置機構１７０は、行列４１０を４つのセグメント（０、１、４、５）、（２、３、６、７）、（８、９、１２、１３）及び（１０、１１、１４、１５）に分割するものとする。コンピュータ１１０の諸処理要素は、これらの４つのセグメントを同時に転置することができる。
【００４６】
ステップ４５２では、ＣｅｌｌＳＰＵ １３２１−４ 上のＳＩＭＤ転置機構１７０は、諸セグメント４１２、４１４、４１６、４１８を転置する。例えば、ＣｅｌｌＳＰＵ １３２１ は、セグメント４１２を転置することにより、転置セグメント４２２を生成する。ステップ４５４では、複数の処理要素の各々で稼働するＳＩＭＤ転置機構１７０は、転置セグメント４２２、４２４、４２６、４２８をそれぞれのＣｅｌｌＳＰＵ １３２のローカル・ストアからメモリ１５０に移動させる。例えば、セグメント４１４上で動作するＣｅｌｌ ＳＰＵ １３２２は、転置セグメント４２４を行列４３０に格納する。ステップ４５４の後、ＣｅｌｌＰＰＵ １２０上で稼働するＳＩＭＤ転置機構１７０は、必要であれば、転置動作を完成するために行列４３０を再編成する。例えば、ＳＩＭＤ転置機構１７０は、転置動作を完成するために、異なるセグメント４２２、４２４、４２６、４２８からの諸要素をそれぞれ交換する。結果的に得られる行列は、行列４１０の転置のＳＩＭＤ変換と同等である。
【００４７】
図５は、本発明の１つの実施形態に従った、行列の複数のサブディビジョンを同時に転置するためのデータ・フロー５００を示す。図４では、各セグメントの全体は各処理要素のローカル・ストアにそれぞれ収容されていたが、図５は、各セグメントが任意の処理要素のローカル・ストアのサイズを超えるシナリオを示す。図示のように、データ・フロー５００は、２５６×２５６の行列５１０を含む。ステップ５５１では、ＳＩＭＤ転置機構１７０は、１つの実施形態に従って、行列５１０を複数のセグメントに分割する。例えば、ＳＩＭＤ転置機構１７０は、行列５１０を４つのセグメント５２０、５３０、５４０、５５０に分割する。また、ＳＩＭＤ転置機構１７０は、各セグメント５２０、５３０、５４０、５５０を、その転置を行うべき一の処理要素１３２に割り当てる。例えば、ＳＩＭＤ転置機構１７０は、セグメント５２０を第１のＣｅｌｌＳＰＵ １３２に割り当て、セグメント５３０を第２のＣｅｌｌ ＳＰＵ １３２に割り当て、セグメント５４０を第３のＣｅｌｌＳＰＵ １３２に割り当て、セグメント５５０を第４のＣｅｌｌ ＳＰＵ １３２に割り当てる。
【００４８】
しかし、一の処理要素１３２のローカル・ストアは、一のセグメントの全体を収容できないことがある。例えば、セグメント５２０は、ＣｅｌｌＳＰＵ １３２用のローカル・ストアのサイズを超えることがある。１つの実施形態では、ＳＩＭＤ転置機構１７０は、一の処理要素（例えば、一のＣｅｌｌＳＰＵ）のローカル・ストアのサイズに基づき、一のセグメントを複数のサブディビジョンに分割する。例えば、ＳＩＭＤ転置機構１７０は、セグメント５２０を４つのサブディビジョン５２２、５２４、５２６、５２８に分割する。各サブディビジョン５２２、５２４、５２６、５２８は、一の処理要素１３２のローカル・ストアのサイズを超えないサイズを有する。
【００４９】
ステップ５５２では、各処理要素は、割り当てられた各セグメント５２０、５３０、５４０、５５０の第１サブディビジョン５２２、５３２、５４２、５５２を同時に転置することにより、第１の転置サブディビジョン５６２、５７２、５８２、５９２を生成する。ステップ５５４では、各処理要素は、割り当てられた各セグメント（例えば、セグメント５２０）の第２サブディビジョン（例えば、サブディビジョン５２４）を同時に転置することにより、第２の転置サブディビジョン（例えば、転置サブディビジョン５６４）を生成し、その後、全てのサブディビジョンが転置されるまで、同様の動作を繰り返す。
【００５０】
図６は、本発明の１つの実施形態に従った、ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上で効率的なＦＦＴを実行するための方法６００を示すフローチャートである。図示のように、方法６００は、ステップ６１０で開始し、そこで、ＳＩＭＤ転置機構１７０は、通常のデータ形式を有する行列を受け取る。例えば、ＳＩＭＤ転置機構１７０は、図２の行列２１０を受け取る。ステップ６２０では、ＳＩＭＤ転置機構１７０は、この行列をＳＩＭＤ形式に変換する。図２は、（ステップ２１９を介して）行列２２０が生成される例を示す。重要なことは、複数のＳＩＭＤベクトル・プロセッサが、ＳＩＭＤ形式の行列の複数の行（この特定の例では、２行）上で同時に動作することである。ステップ６３０では、ＳＩＭＤ転置機構１７０は、受け取った行列の行ごとに１ＤＦＦＴを実行する。図２は、（ステップ２２１を介して）行列２２２が生成される例を示す。
【００５１】
ステップ６４０では、ＳＩＭＤ転置機構１７０は、この行列をＳＩＭＤ転置する。図２は、（ステップ２２３を介して）行列２２４が生成される例を示す。ステップ６５０では、ＳＩＭＤ転置機構１７０は、受け取った行列の列ごとに１ＤＦＦＴを実行する。図２は、（ステップ２２５を介して）行列２２６が生成される例を示す。ステップ６６０では、ＳＩＭＤ転置機構１７０は、この行列上で他のＳＩＭＤ転置を実行する。例えば、図２に示すように、（ステップ２２７を介して）行列２２６をＳＩＭＤ転置することにより、行列２２８が生成される。ステップ６７０では、ＳＩＭＤ転置機構１７０は、この行列を通常のデータ形式に逆変換することができる。例えば、ＳＩＭＤ転置機構１７０は、図２のステップ２２９を実行することにより、行列２１８を生成する。ステップ６７０の後、方法６００は終了する。
【００５２】
本明細書では、ＳＩＭＤ変換（１ＤＦＦＴ）及びＳＩＭＤ転置を実行するＳＩＭＤ転置機構１７０を参照して本発明の諸実施形態を説明したが、本明細書に開示した諸実施形態は、例示を目的とするものであって、本発明を制限するものではないことが意図される。他の実施形態も、広く予測されるからである。例えば、変換、転置及びＦＦＴ機能は、種々の方法で編成された異なるソフトウェア・モジュールによって実行することができる。
【００５３】
図７は、本発明の１つの実施形態に従った、ＳＩＭＤ形式のデータを転置するための方法７００を示すフローチャートである。方法７００は、図１のＳＩＭＤ転置機構１７０によって実行することができる。方法７００の諸ステップは、図６のステップ６４０及び６６０に対応し、表６の要素マッピング例を参照して説明する。
【００５４】
図示のように、方法７００は、ステップ７１０で開始し、そこで、ＳＩＭＤ転置機構１７０は、ＳＩＭＤ形式の行列を受け取る。例えば、ＳＩＭＤ転置機構１７０は、図２の行列２２２を受け取る。ステップ７２０では、ＳＩＭＤ転置機構１７０は、この行列のサイズ及びコンピュータ１１０上の処理要素の数に基づき、当該行列を複数のセグメントに分割する。図４は、行列４１０が４つのセグメント４１２、４１４、４１６、４１８に分割される例を示す。
【００５５】
ステップ７３０では、ＳＩＭＤ転置機構１７０は、各セグメントを一の処理要素に割り当てる。例えば、ＳＩＭＤ転置機構１７０は、図４のセグメント４１２を第１のＣｅｌｌＳＰＵ １３２に割り当てる。また、ＳＩＭＤ転置機構１７０は、一のセグメントが割り当てられた処理要素のローカル・ストアのサイズを超えるか否かを決定する。そうであれば、ＳＩＭＤ転置機構１７０は、各セグメントを複数のサブディビジョンに分割する。各サブディビジョンは、割り当てられた処理要素のローカル・ストアのサイズを超えないものとする。例えば、ＳＩＭＤ転置機構１７０は、図５のセグメント５２０をサブディビジョン５２２、５２４、５２６、５２８に分割する。
【００５６】
ステップ７４０では、割り当てられた各処理要素上で稼働中のＳＩＭＤ転置機構１７０は、行列の各セグメントを転置する。例えば、図４の第１のＣｅｌｌＳＰＵ １３２は、セグメント４１２を転置することにより、転置セグメント４２２を生成する。ステップ７５０では、割り当てられた各処理要素は、転置セグメントをそれぞれのローカル・ストアからメモリ１５０に分散させる。例えば、図４の第３のＣｅｌｌＳＰＵ １３２は、転置セグメント４２６をメモリ１５０内の転置行列４３０のセグメント位置４２４に分散させる。ステップ７６０では、ＳＩＭＤ転置機構１７０は、転置動作を完成するために、必要に応じて、転置行列４３０を再編成する。例えば、ＳＩＭＤ転置機構１７０は、転置動作を完成するために、セグメント間の諸要素をそれぞれ交換する。ステップ７６０の後、方法７００は終了する。
【００５７】
図８は、本発明の１つの実施形態に従った、図１のＳＩＭＤ転置機構１７０の諸コンポーネントを示すブロック図８００である。図示のように、ＳＩＭＤ転置機構１７０は、行列マネージャ８１０、セグメント・ジェネレータ８２０、セグメント・マネージャ８３０、転置マネージャ８４０及び再編成機構（reorganizer）８５０を含む。図示のように、行列マネージャ８１０は、ＳＩＭＤ形式の行列１５２を受け取るように構成される。例えば、行列マネージャ８１０は、図２の行列２２２を受け取る。さらに、セグメント・ジェネレータ８２０は、受け取った行列１５２に基づき、複数のセグメント１８０を生成する。例えば、セグメント・ジェネレータ８２０は、図４のセグメント４１２、４１４、４１６、４１８（図１のセグメント１５４、１５６、１５８、１６０に対応）を生成する。また、セグメント・ジェネレータ８２０は、セグメントごとに複数のサブディビジョンを生成することができる。例えば、セグメント・ジェネレータ８２０は、図５のセグメント５２０についてサブディビジョン５２２、５２４、５２６、５２８を生成する。
【００５８】
セグメント・マネージャ８３０は、各セグメントを一の処理要素に割り当てる。例えば、セグメント・マネージャ８３０は、図４のセグメント４１２、４１４、４１６、４１８を４つの処理要素１３２に割り当てる。さらに、転置マネージャ８４０は、ＳＩＭＤ行列からＳＩＭＤ転置行列へのマッピングを定義する。例えば、転置マネージャ８４０は、表６（４×４行列用）のマッピングを定義する。
【００５９】
転置マネージャ８４０は、行列１５２の各セグメントを転置する。例えば、各処理要素１３２上で稼働する転置マネージャ８４０は、図４の割り当てられた各セグメント４１２、４１４、４１６、４１８を転置する。また、転置マネージャ８４０は、各転置セグメントを各処理要素のローカル・ストアからメモリ１５０に分散させる。例えば、図４の第３の処理要素１３２上で稼働する転置マネージャ８４０は、転置セグメント４２６をメモリ１５０内の転置行列４３０のセグメント位置４２４に分散させる。さらに、再編成機構８５０は、１つの実施形態に従って、行列１５２の転置を完成するために、必要であれば、メモリ１５０内の諸要素を再配置する。例えば、再編成機構８５０は、複数のセグメント１８０間の諸要素を再配置することができる。
【００６０】
もちろん、本明細書に開示した諸実施形態は、例示を目的とするものであって、本発明を制限するものではないことが意図される。他の実施形態も、広く予測されるからである。例えば、本発明の諸実施形態は、他のサイズの行列（例えば、５１２×５１２の行列）、処理要素の他の数（例えば、３２個の処理要素）、及び１ブロック当たりの他の行数（例えば、８ウェイのＳＩＭＤ、１６ウェイのＳＩＭＤ等）をサポートするように適応させることができる。
【００６１】
有利なことに、本発明の諸実施形態は、ＳＩＭＤマルチコア・プロセッサ・アーキテクチャ上で配列データを転置する。１つの実施形態では、ＳＩＭＤ転置機構１７０は、ＳＩＭＤ形式の行列を受け取る。この行列は、通常のデータ形式を有する行列ＭのＳＩＭＤ変換から成る。ＳＩＭＤ転置機構１７０は、この行列の各要素から行列Ｍの転置のＳＩＭＤ変換の一の要素へのマッピングを定義することができる。さらに、ＳＩＭＤ転置機構１７０は、行列Ｍ及び定義されたマッピングに基づき、ＳＩＭＤ転置行列Ｔを生成することができる。行列Ｍの複数の列上で動作するように、行方向アルゴリズムを修正なしでＳＩＭＤ転置行列Ｔに適用することができる。
【００６２】
前述の説明は、本発明の諸実施形態に向けられているが、本発明の基本的な範囲から逸脱することなく、他の実施形態を考案することができる。本発明の範囲は、以下の請求項の記載によって決定される。
【符号の説明】
【００６３】
１１０・・・ＣｅｌｌＢＥコンピュータ
１２０・・・ＣｅｌｌＰＰＵ
１３０、１３２・・・ＣｅｌｌＳＰＵ
１４０・・・ＥＩＢ
１５０・・・メモリ
１５２・・・行列
１５４、１５６、１５８、１６０・・・行列セグメント
１７０・・・ＳＩＭＤ転置機構
１８０・・・行列セグメント
８１０・・・行列マネージャ
８２０・・・セグメント・ジェネレータ
８３０・・・セグメント・マネージャ
８４０・・・転置マネージャ
８５０・・・再編成機構
【図１】
2011100452.tif 000003
【図２】
2011100452.tif 000004
【図３】
2011100452.tif 000005
【図４】
2011100452.tif 000006
【図５】
2011100452.tif 000007
【図６】
2011100452.tif 000008
【図７】
2011100452.tif 000009
【図８】
2011100452.tif 000010