【手続補正書】
【提出日】平成30年12月10日(2018.12.10)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
構造化疎行列表現の取得及び利用のためのコンピュータ実装方法において、
各部分が行及び列のうちの１つを含む疎行列の部分における１つ以上の順序で配置された１つ以上の非ゼロエントリを含む前記疎行列の構造化圧縮表現を、１つ以上のキャッシュ及び１つ以上のプロセッサを備えた少なくとも一つのサーバによって取得するステップを含み、
前記取得するステップは、
前記表現に含まれる複合配列であって、前記非ゼロエントリと前記非ゼロエントリを含む部分の一つにおけるインデックスとの一つをそれぞれが有する１つ以上の要素を含む複合配列を取得するステップと、
前記順序の１つ以上における最初である前記非ゼロエントリを含む前記要素それぞれについての前記複合配列におけるインデックスを有するインデックス配列であって、前記行列における前記非ゼロエントリの数をさらに有するインデックス配列を取得するステップとを有し、
方法は、さらに、前記プロセッサのそれぞれが前記１つ以上のキャッシュのうちの一つにおいて前記複合配列の前記１つ以上の要素にアクセスすることを含む疎線形代数演算を前記圧縮表現上で前記少なくとも一つのサーバによって実行するステップであって、前記要素における前記非ゼロエントリと前記要素における前記インデックスとを取得する、ステップを含み、
前記部分の前記非ゼロエントリ及び前記インデックスが異なる配列である前記疎行列の表現上の前記疎線形代数演算が実行される間に前記部分のうちの一つにおける前記非ゼロエントリ及び前記インデックスをキャッシュから取得する障害の数が比較されるときに、前記アクセスの間に前記キャッシュから前記部分のうちの一つにおける前記非ゼロエントリと前記インデックスとを取得する障害の数が削減される、方法。
【請求項２】
各複合配列の要素インデックスが、列優先順序でその非ゼロエントリの行のインデックスを含み、前記順序が各列における前記非ゼロエントリの順序を含む、請求項１に記載の方法。
【請求項３】
さらに、
前記行列の各列を処理することによって複数の要素を含む密ベクトルによって前記行列の疎行列転置ベクトル乗算を実行するステップと、
前記インデックス配列を使用してその列における前記非ゼロエントリを含む全ての前記複合配列要素の前記複合配列におけるインデックスを識別するステップと、
そのエントリの前記インデックスを使用して前記密ベクトルの要素のいずれかによってその列における前記非ゼロエントリのそれぞれを乗算するステップと、
その列における前記非ゼロエントリのそれぞれについての乗算結果を加算し、異なる密ベクトルの加算結果を格納するステップとを含む、請求項２に記載の方法。
【請求項４】
各複合配列の要素インデックスが、行優先順序でその非ゼロエントリの列のインデックスを含み、前記順序が各行における前記非ゼロエントリの順序を含む、請求項１に記載の方法。
【請求項５】
さらに、
前記行列の各行を処理することによって複数の要素を含む密ベクトルによって前記行列の疎行列ベクトルの乗算を実行するステップと、
前記インデックス配列を使用してその行における前記非ゼロエントリを含む全ての前記複合配列要素の前記複合配列におけるインデックスを識別するステップと、
そのエントリの前記インデックスを使用して前記密ベクトルの要素のいずれかによってその行における前記非ゼロエントリのそれぞれを乗算するステップと、
その行における前記非ゼロエントリのそれぞれについての乗算結果を加算し、異なる密ベクトルの加算結果を格納するステップとを備える、請求項４に記載の方法。
【請求項６】
さらに、
前記構造化圧縮表現を処理することと、
前記処理の結果を使用してランク付け分析を実行することとを備える、請求項１に記載の方法。
【請求項７】
効率的な疎行列表現及び使用のためのコンピュータ実装方法において、
疎行列の圧縮表現をそれぞれが１つ以上のグラフィックス処理ユニット（ＧＰＵ）のプロセッサコアを備えた１つ以上のストリーミングプロセッサを備える少なくとも一つのサーバによって取得するステップであって、前記疎行列が前記行列の複数の部分の１つ以上において１つ以上の非ゼロエントリを含み、前記行列の部分が前記行列におけるそれらの位置に基づいてインデックス付けされ、前記部分が前記行列の行及び列の一つを含む、ステップと、
前記行列の部分について複数のパーティションを前記少なくとも一つのサーバによって定義するステップと、
前記圧縮表現を使用して前記部分のそれぞれにおける前記非ゼロエントリの数を前記少なくとも一つのサーバによって取得するステップと、
その部分における前記非ゼロエントリの数に基づいて前記パーティションのいずれかを有する部分のそれぞれを前記少なくとも一つのサーバによって関連付けるステップであって、前記パーティションのそれぞれに関連する部分が、残りのパーティションに関連する範囲と異なる範囲内にある前記非ゼロエントリの数を有する、ステップと、
前記パーティションのそれぞれに関連する全ての部分であり、それらのインデックスの順序でリスト化された前記部分のリストを前記少なくとも一つのサーバによって作成するステップと、
前記リストを含むマッピング配列を含む前記行列のパーティション化された圧縮表現を前記少なくとも一つのサーバによって作成するステップと、
前記パーティションのそれぞれに関連する前記部分の前記パーティションに関連する前記範囲に基づく処理のための前記ストリーミングプロセッサの１つ以上における所定の数の前記ＧＰＵのプロセッサコアを前記少なくとも一つのサーバによって割り当てるステップと、
前記パーティションのそれぞれに関連する前記部分のそれぞれを、割り当てられた
前記所定の数の前記ＧＰＵのプロセッサコアによって処理するステップとを含む、方法。
【請求項８】
前記範囲の一つが１から３１の前記非ゼロエントリを含み、前記範囲の第２の一つが３１から１０２４の前記非ゼロエントリを含み、前記範囲の第３の一つが１０２４以上の前記非ゼロエントリの数を含む、請求項７に記載の方法。
【請求項９】
さらに、
前記パーティションのそれぞれに関連する前記行列の部分における非ゼロエントリの数に基づいて前記パーティションをインデックス付けるステップと、
前記パーティションのそれぞれについて、前記パーティションのインデックスに基づいて前記配列におけるそのパーティションに先行する全てのパーティションのサイズであり、前記パーティションに関連する複数の部分の数を含む前記サイズを識別するステップであって、そのパーティションについての前記リストを前記サイズに基づく位置において前記配列に挿入するステップとを含む、請求項７に記載の方法。
【請求項１０】
前記行列の列の一つを含む前記各部分が、さらに、
前記マッピング配列にリスト化されたパーティションのそれぞれの列のそれぞれを処理することによって複数の要素を含む密ベクトルによって前記行列の疎行列ベクトル転置乗算を実行するステップと、
その列における前記非ゼロエントリのそれぞれに関連付けられた前記圧縮表現におけるインデックスを識別するステップと、
その非ゼロエントリの前記インデックスを使用して前記密ベクトルの要素のいずれかによってその列における前記非ゼロエントリのそれぞれを乗算するステップと、
その列における前記非ゼロエントリのそれぞれについての乗算結果を加算し、異なる密ベクトルにおける加算結果を格納するステップとを備える、請求項９に記載の方法。
【請求項１１】
前記行列の行の一つを含む前記各部分が、さらに、
前記マッピング配列にリスト化されたパーティションのそれぞれの行のそれぞれをシーケンシャルに処理することによって複数の要素を含む密ベクトルによって前記行列の疎行列ベクトル転置乗算を実行するステップと、
その行における前記非ゼロエントリのそれぞれに関連付けられた前記圧縮表現におけるインデックスを識別するステップと、
その非ゼロエントリの前記インデックスを使用して前記密ベクトルの要素のいずれかによってその行における前記非ゼロエントリのそれぞれを乗算するステップと、
その行における前記非ゼロエントリのそれぞれについての乗算結果を加算し、異なる密ベクトルにおける加算結果を格納するステップとを備える、請求項７に記載の方法。
【請求項１２】
前記パーティション化された圧縮表現は、さらに、前記行列の前記部分のそれぞれにおける前記非ゼロエントリの最初の一つに関連するインデックスを含み、前記部分のそれぞれの前記処理は、割り当てられた前記ＧＰＵのプロセッサコアのそれぞれによって、前記サーバに含まれる１つ以上のキャッシュの一つにシーケンシャルにアクセスするステップを含み、前記インデックス配列における複数のインデックスは、前記マッピング配列の前記リストにおいて、前記インデックス配列における複数のインデックスに関連する前記部分の順序でリスト化されており、シーケンシャルに行われる前記アクセスは、前記複数のインデックスへの非シーケンシャルなアクセスと比較されるときに、各キャッシュにおける前記インデックス配列へのランダムなアクセスを削減することによる前記処理の間に、キャッシュミスの数を削減する、請求項７に記載の方法。
【請求項１３】
さらに、
前記パーティションのそれぞれに関連する前記部分を処理するための複数のカーネル関数から一つを選択するステップを含み、  前記カーネル関数が、前記部分の一つを処理する前記ＧＰＵの１つのプロセッサコアによって実行される一つの処理スレッドを割り当てるカーネル関数（ｆ1T1Rカーネル関数）と、前記部分の一つを処理する前記ＧＰＵの１つより多くのプロセッサコアによって実行される処理スレッドのワープを割り当てるカーネル関数（ｆ1W1Rカーネル関数）と、前記処理スレッドの前記ワープを実行する前記ＧＰＵのプロセッサコアの数より多い前記所定の数の前記ＧＰＵのプロセッサコアであって、前記部分の一つを処理するプロセッサコアによって実行される処理スレッドのブロックを割り当てるカーネル関数（ｆ1B1Rカーネル関数）とのうちの１つ以上を含み、前記ｆ1W1Rカーネル関数が選択される前記部分のそれぞれは、前記ｆ1T1Rカーネル関数が選択される前記部分のそれぞれのものより多い前記非ゼロエントリを含み、前記ｆ1B1Rカーネル関数が選択される前記部分のそれぞれは、前記ｆ1W1Rカーネル関数が選択される前記部分のそれぞれのものより多い前記非ゼロエントリを含む、請求項７に記載の方法。
【請求項１４】
前記部分のそれぞれは、前記行の一つを含み、方法は、さらに、
複数の要素を含む密ベクトルによる前記行列における前記行の一つの疎行列ベクトル乗算を前記ｆ1T1Rカーネル関数によって割り当てられる処理スレッドによって実行するステップを含み、前記実行するステップは、
前記マッピング配列を用いて、前記スレッドに割り当てられた前記行を識別するステップと、
前記行における前記非ゼロエントリのそれぞれに関連する前記圧縮表現においてインデックスを識別するステップと、
前記行における前記非ゼロエントリのそれぞれを、前記非ゼロエントリの前記インデックスを用いて前記密ベクトルの前記要素の一つと乗算するステップと、
前記行における前記非ゼロエントリのそれぞれについての乗算結果を加算し、異なる密ベクトルの加算結果を格納するステップとを有する、請求項１３に記載の方法。
【請求項１５】
前記部分のそれぞれは、前記列のうちの一つを含み、前記方法は、さらに、
前記行列の前記列のうちの一つの疎行列ベクトル転置乗算を複数の要素を含む密ベクトルにより、前記ｆ1T1Rカーネル関数により割り当てられた処理スレッドによって実行するステップと、
前記スレッドに割り当てられた前記列を前記マッピングアレイを用いて識別するステップと、
前記列において、前記非ゼロエントリのそれぞれに関連する前記圧縮表現でインデックスを識別するステップと、
前記非ゼロエントリの前記インデックスを用いて、前記列における前記非ゼロエントリのそれぞれを前記密ベクトルの前記要素のうちの一つと乗算するステップと、
前記列における前記非ゼロエントリのそれぞれについて、前記乗算結果を加算し、異なる密ベクトルの加算結果を格納するステップと、
を含む、請求項１３に記載の方法。
【請求項１６】
前記部分のそれぞれは、前記行のうちの一つを含み、前記方法は、さらに、
前記行列の前記行のうちの一つの疎行列ベクトル乗算を複数の要素を含む密ベクトルにより、前記ｆ1W1Rカーネル関数により割り当てられた処理スレッドのワープによって実行するステップと、
前記ワープに割り当てられた前記行を前記マッピングアレイを用いて識別するステップと、
前記ワープにおける前記スレッドのそれぞれに割り当てられた前記行における前記非ゼロエントリの前記圧縮表現でインデックスを識別し、前記非ゼロエントリの前記インデックスを用いて、前記スレッドに割り当てられた前記非ゼロエントリのそれぞれを前記密ベクトルの前記要素のうちの一つと乗算するステップと、
前記スレッドに割り当てられた前記非ゼロエントリのそれぞれについて、前記乗算結果を合計するステップと、
前記ワープにおける前記スレッドの全てについて前記合計を組み合わせて、組み合わせた合計を異なる密ベクトルで格納するステップと、
を含む、請求項１３に記載の方法。
【請求項１７】
前記部分のそれぞれは、前記列のうちの一つを含み、前記方法は、さらに、
前記行列の前記列のうちの一つの疎行列ベクトル乗算を複数の要素を含む密ベクトルにより、前記ｆ1W1Rカーネル関数により割り当てられた処理スレッドのワープによって実行するステップと、
前記ワープに割り当てられた前記列を前記マッピングアレイを用いて識別するステップと、
前記ワープにおける前記スレッドのそれぞれに割り当てられた前記列における前記非ゼロエントリの前記圧縮表現でインデックスを識別し、前記非ゼロエントリの前記インデックスを用いて、前記スレッドに割り当てられた前記非ゼロエントリのそれぞれを前記密ベクトルの前記要素のうちの一つと乗算するステップと、
前記スレッドに割り当てられた前記非ゼロエントリのそれぞれについて、前記乗算結果を合計するステップと、
前記ワープにおける前記スレッドの全てについて前記合計を組み合わせて、組み合わせた合計を異なる密ベクトルで格納するステップと、
を含む、請求項１３に記載の方法。
【請求項１８】
前記部分のそれぞれは、前記行のうちの一つを含み、前記方法は、さらに、
前記行列の前記行のうちの一つの疎行列ベクトル乗算を複数の要素を含む密ベクトルにより、前記ｆ1B1Rカーネル関数により割り当てられた処理スレッドのブロックによって実行するステップと、
前記ブロックに割り当てられた前記行を前記マッピングアレイを用いて識別するステップと、
前記ブロックにおける前記スレッドのそれぞれに割り当てられた前記行における前記非ゼロエントリの前記圧縮表現でインデックスを識別し、前記非ゼロエントリの前記インデックスを用いて、前記スレッドに割り当てられた前記非ゼロエントリのそれぞれを前記密ベクトルの前記要素のうちの一つと乗算するステップと、
前記スレッドに割り当てられた前記非ゼロエントリのそれぞれについて、前記乗算結果を合計するステップと、
前記合計の完了に応じて、前記ブロックにおける前記スレッドを同期するステップと、
前記ブロックのうちの同期されたスレッド全てについて前記合計を組み合わせて、組み合わせた合計を異なる密ベクトルで格納するステップと、
を含む、請求項１３に記載の方法。
【請求項１９】
前記部分のそれぞれは、前記列のうちの一つを含み、前記方法は、さらに、
前記列のうちの一つの疎行列ベクトル乗算を複数の要素を含む密ベクトルにより、前記ｆ1B1Rカーネル関数により割り当てられた処理スレッドのブロックによって実行するステップと、
前記ブロックに割り当てられた前記列を前記マッピングアレイを用いて識別するステップと、
前記ブロックにおける前記スレッドのそれぞれに割り当てられた前記列における前記非ゼロエントリの前記圧縮表現でインデックスを識別し、前記非ゼロエントリの前記インデックスを用いて、前記スレッドに割り当てられた前記非ゼロエントリのそれぞれを前記密ベクトルの前記要素のうちの一つと乗算するステップと、
前記スレッドに割り当てられた前記非ゼロエントリのそれぞれについて、前記乗算結果を合計するステップと、
前記合計の完了に応じて、前記ブロックにおける前記スレッドを同期するステップと、
前記ブロックのうちの同期されたスレッド全てについて前記合計を組み合わせて、組み合わせた合計を異なる密ベクトルで格納するステップと、
を含む、請求項１３に記載の方法。
【請求項２０】
前記圧縮表現は、圧縮疎行符号化、圧縮疎列符号化、構造化圧縮疎行符号化及び構造化圧縮疎列符号化の一つを含み、方法は、さらに、
式δ＝γ／（λｂ＋１）を用いて、パーティション化された前記圧縮表現により要求される過剰な空間的オーバーヘッドを予測するステップを含み、
δが前記過剰な空間的オーバーヘッドであり、γがパーティション化された前記圧縮表現における前記部分の合計数に対する前記非ゼロエントリを含む前記部分の数の割合であり、ｂがパーティション化された前記圧縮表現における行（又は列）の数に対する前記非ゼロエントリの数の割合である、請求項７に記載の方法。