(57)【要約】【課題】計算領域を複数の小領域に分割して、ＧＰＵの複数のマルチプロセッサで各小領域に関わる数値計算を並列処理する方法において、計算速度の高速化及び安定化、並びに、計算アルゴリズムとプログラム開発の簡単化を図るための技術を提供する。【解決手段】ホストコンピュータが計算領域のすべての要素のデータをグローバルメモリに格納し、ＧＰＵが計算領域を複数の小領域に分割し、小領域毎に、当該小領域内のすべての要素のデータのメモリアドレスが連続となるように、グローバルメモリに格納されているデータを並び替える。その後、ＧＰＵの各マルチプロセッサが、自身に割り当てられた小領域内の要素のデータのうち複数回参照が生じるデータを共有メモリに転送し、数値計算を実行する。【選択図】図１
2013168000.tif 000002
【特許請求の範囲】
【請求項１】
ホストコンピュータと、複数のマルチプロセッサからなるＧＰＵと、を有するシステムが実行する数値計算方法であって、
前記システムは、前記ホストコンピュータと前記マルチプロセッサの両方からアクセス可能な第一のメモリと、マルチプロセッサごとに設けられ且つ前記第一のメモリよりも高速な第二のメモリと、を有しており、
前記数値計算方法は、
前記ホストコンピュータが数値計算の対象となる計算領域のすべての要素のデータを前記第一のメモリに格納するデータ格納工程と、
前記ＧＰＵが前記計算領域を複数の小領域に分割する領域分割工程と、
前記ＧＰＵが前記複数の小領域を前記複数のマルチプロセッサにそれぞれ割り当てる割当工程と、
各マルチプロセッサが、自身に割り当てられた小領域内の要素のデータのうち少なくとも一部のデータを、前記第一のメモリから自身に設けられた第二のメモリに転送する転送工程と、
各マルチプロセッサが前記第一のメモリに格納されたデータと前記第二のメモリに格納されたデータを用いて数値計算を実行する計算工程と、
を含んでおり、
前記領域分割工程は、小領域毎に、当該小領域内のすべての要素のデータのメモリアドレスが連続となるように、前記第一のメモリに格納されているデータを並び替えるオーダリング工程を含む
ことを特徴とする数値計算方法。
【請求項２】
前記領域分割工程では、所定の体積を満たす範囲で且つ表面積が最も小さくなる形状となるように、各小領域の形状が決定される
ことを特徴とする請求項１に記載の数値計算方法。
【請求項３】
前記一部のデータは、数値計算において複数回参照されるデータである
ことを特徴とする請求項１または２に記載の数値計算方法。
【請求項４】
前記第二のメモリは、マルチプロセッサに設けられたオンチップメモリである
ことを特徴とする請求項１〜３のうちいずれか１項に記載の数値計算方法。
【請求項５】
ホストコンピュータと、複数のマルチプロセッサからなるＧＰＵと、前記ホストコンピュータと前記マルチプロセッサの両方からアクセス可能な第一のメモリと、マルチプロセッサごとに設けられ且つ前記第一のメモリよりも高速な第二のメモリと、を有するシステムに対し、
請求項１〜４のうちいずれか１項に記載の数値計算方法の各工程を実行させる
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）を利用した数値計算に関する。
【背景技術】
【０００２】
非特許文献１には、数値解析の対象となる計算領域（計算空間ともよぶ）の全体を小領域に分割し、隣接参照が生じるデータをＧＰＵの共有メモリに分散するという技術が開示されている。
一般的に偏微分方程式の数値計算では、計算領域内で連続する定数や変数を格子点上に離散化し、隣接する格子点のデータ同士の差分をとることで偏微分を近似する。ここで差分を計算する変数データ、すなわち隣接参照が生じるデータはメモリアクセス頻度が非常に高い。
そのため非特許文献１の方法では、このような隣接参照が生じるデータをＧＰＵのマルチプロセッサ毎に用意されている高速な共有メモリに配置させ、メモリアクセス時間を削減し計算を高速化している。ただしＧＰＵの共有メモリは一つ一つの容量が小さく、また別のマルチプロセッサからは参照できないため、計算領域を小領域に分割しそれぞれを各マルチプロセッサに担当させている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】小川慧，青木尊之：ＣＵＤＡによる定常反復Ｐｏｉｓｓｏｎベンチマークの高速化，情報処理学会研究報告書，２００８−ＨＰＣ−１１５，ｐｐ．１９−２３（２００８）
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上記非特許文献１の方法には三つの課題がある。一つ目は、計算領域全体の大きさや形状に対し計算速度が不安定であること、二つ目は、小領域の最適な形状が不明であること、三つ目は、小領域の形状が異方的な場合にプログラムが煩雑となることである。以下、それぞれについて詳しく説明する。
【０００５】
非特許文献１の方法では、計算領域を幾つかの小領域に分割し、各領域をＧＰＵのマルチプロセッサに独立に処理させる。そのため、グローバルメモリへのアクセスは小領域単位のアクセスとなる。しかしグローバルメモリにおいて小領域内のデータがどのようなアドレス分布を持つかについては不明である。例えば計算領域全体の大きさや形状が変化した場合、小領域内データのメモリアドレス分布が不変である保証はない。
【０００６】
一方、一般的にメモリアクセス先のアドレス分布が不連続になると、アクセス遅延が発生し時間がかかることが知られている。そのため非特許文献１の方法では、計算領域全体の大きさや形状が変化した際に、小領域内データのメモリアドレス分布の連続性が悪化して、計算速度が低下する可能性がある。
【０００７】
またこれは小領域の形状についても全く同様である。すなわち、非特許文献１の方法では、小領域の形状と小領域内データのメモリアドレス分布との関係が明確でない。本来小領域の形状は、領域外参照ができるだけ少なくなるよう表面積が最も小さい等方的な形状が望ましいが、メモリアドレス分布の連続性の影響により、最適な形状は不明である。そのため最適な形状が異方的な形状になる可能性があり、その場合はプログラムの領域分割
工程において異方性を意識しなければならず非常に煩雑である。
【０００８】
本発明は上記課題に鑑みてなされたものであり、計算領域を複数の小領域に分割して、ＧＰＵの複数のマルチプロセッサで各小領域に関わる数値計算を並列処理する方法において、計算速度の高速化及び安定化、並びに、計算アルゴリズムとプログラム開発の簡単化を図るための技術を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の第一態様は、ホストコンピュータと、複数のマルチプロセッサからなるＧＰＵと、を有するシステムが実行する数値計算方法であって、前記システムは、前記ホストコンピュータと前記マルチプロセッサの両方からアクセス可能な第一のメモリと、マルチプロセッサごとに設けられ且つ前記第一のメモリよりも高速な第二のメモリと、を有しており、前記数値計算方法は、前記ホストコンピュータが数値計算の対象となる計算領域のすべての要素のデータを前記第一のメモリに格納するデータ格納工程と、前記ＧＰＵが前記計算領域を複数の小領域に分割する領域分割工程と、前記ＧＰＵが前記複数の小領域を前記複数のマルチプロセッサにそれぞれ割り当てる割当工程と、各マルチプロセッサが、自身に割り当てられた小領域内の要素のデータのうち少なくとも一部のデータを、前記第一のメモリから自身に設けられた第二のメモリに転送する転送工程と、各マルチプロセッサが前記第一のメモリに格納されたデータと前記第二のメモリに格納されたデータを用いて数値計算を実行する計算工程と、を含んでおり、前記領域分割工程は、小領域毎に、当該小領域内のすべての要素のデータのメモリアドレスが連続となるように、前記第一のメモリに格納されているデータを並び替えるオーダリング工程を含むことを特徴とする数値計算方法である。
【００１０】
本発明の第二態様は、ホストコンピュータと、複数のマルチプロセッサからなるＧＰＵと、前記ホストコンピュータと前記マルチプロセッサの両方からアクセス可能な第一のメモリと、マルチプロセッサごとに設けられ且つ前記第一のメモリよりも高速な第二のメモリと、を有するシステムに対し、本発明の第一態様に係る数値計算方法の各工程を実行させることを特徴とするプログラムである。
【発明の効果】
【００１１】
本発明によれば、計算領域を複数の小領域に分割して、ＧＰＵの複数のマルチプロセッサで各小領域に関わる数値計算を並列処理する方法において、計算速度の高速化及び安定化、並びに、計算アルゴリズムとプログラム開発の簡単化を図ることができる。
【図面の簡単な説明】
【００１２】
【図１】本発明の一実施形態に係る数値計算方法のフローチャート。
【図２】本発明の一実施形態に係る数値計算システムの構成図。
【図３】本発明の一実施形態に係るデータの並び替え方法を示す図。
【図４】従来例と本発明の実施例の計算結果の比較を示す図。
【発明を実施するための形態】
【００１３】
本発明の一実施形態に係る数値計算方法を、図１のフローチャート及び図２のシステム構成図に基づいて説明する。本実施形態の数値計算システムは、例えば微分方程式を近似的に解くなどの数値解析（数値計算）をＧＰＵを用いて並列処理するシステムに関する。本システムは、３次元シミュレーション、流体シミュレーション、構造解析など、様々な分野への応用が可能である。
【００１４】
図２に示すように、本システムは、ホストコンピュータ１０９とＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１１２とから構成される。ホストコンピュータ
１０９とＧＰＵ１１２の間は高速なインタフェースにより接続されている。ホストコンピュータ１０９は、ＧＰＵ１１２を制御するためのコンピュータであり、ＣＰＵ１１０、メモリ１１１などを有する汎用のコンピュータで構成される。図示しないが、ホストコンピュータ１０９は、ユーザが数値計算の境界条件や計算条件などを入力するための入力装置、数値計算の経過や結果を出力するための表示装置、不揮発性の補助記憶装置なども備えている。ＧＰＵ１１２は、高速な並列計算を実行するためのコプロセッサである。ＧＰＵ１１２は複数のマルチプロセッサ１１４とグローバルメモリ（第一のメモリ）１１３を有している。各々のマルチプロセッサ１１４の内部にはオンチップメモリとしての共有メモリ（第二のメモリ）１１５が設けられている。グローバルメモリ１１３は、ホストコンピュータ１０９とマルチプロセッサ１１４の両方がアクセス可能な大容量のメモリであり、例えばホストコンピュータ１０９から与えられるデータやマルチプロセッサ１１４での計算結果などを格納するために利用される。一方、共有メモリ１１５は、小容量であるとか、マルチプロセッサ１１４しかアクセスできないなどの制約があるものの、グローバルメモリ１１３に比べてアクセス速度が格段に速く、数値計算において複数回参照されるデータを格納するのに適している。
【００１５】
図１のフローチャートに沿って、本システムの数値計算方法の流れを説明する。なお図１に示す数値計算方法の各処理は、ホストコンピュータ１０９のメモリ１１１または補助記憶装置に格納されたプログラムをＣＰＵ１１０が実行することにより実現される。また、数値計算に関しては、ホストコンピュータ１０９のＣＰＵ１１０の制御の下、ＧＰＵ１１２の複数のマルチプロセッサ１１４が上記プログラムに基づき並列に処理を行う。
【００１６】
図１に示すように、まずホストコンピュータ１０９が、数値計算の対象となる計算領域（計算空間ともよぶ）のすべての要素のデータをグローバルメモリ１１３に格納する（ステップ１０１：データ格納工程）。具体的には、例えばホストコンピュータ１０９が計算領域の各格子点について離散化されたデータを生成し、ＧＰＵ１１２のグローバルメモリ１１３にデータを転送すればよい。
【００１７】
次にホストコンピュータ１０９が、ＧＰＵ１１２の各々のマルチプロセッサ１１４に割り当てる小領域の形状を決定する（ステップ１０２）。その形状は、所定の体積を満たす範囲で且つ表面積が最も小さくなるような形状とする。ここで小領域の体積とはすなわち小領域を構成する要素数を表し、所定の体積とは例えば一つのマルチプロセッサに割り当てられるスレッド数（例えば５１２）でよい。また表面積を最も小さくするとは、例えば小領域を構成する各辺の長さを等しくすることであり、３次元の格子空間で小領域を構成する要素数が５１２の場合は、各辺の要素数を８にすればよい。
【００１８】
次にＧＰＵ１１２が計算領域全体を複数の小領域に分割する（ステップ１０３）。このとき、各小領域の形状は、ステップ１０２で決定したものが用いられる。
【００１９】
次にＧＰＵ１１２は、小領域毎に、当該小領域内のすべての要素のデータのメモリアドレスが連続となるように、グローバルメモリ１１３に格納されているデータを並び替える（ステップ１０４）。この処理をデータのオーダリングとよぶ。図３に、オーダリング前のデータのメモリアドレスの一例と、オーダリング後のデータのメモリアドレスの一例を示す。６×６要素の２次元の計算領域を３×３要素の小領域４つに分割する場合を示している。なお表示されている数字は、グローバルメモリ１１３におけるメモリアドレスを模擬的に整数で表したものである。図３の下段に示すように、オーダリング後のグローバルメモリ１１３では、一つの小領域内の９個の要素のデータが連続したメモリアドレスに格納されることとなる。
【００２０】
次にＧＰＵ１１２は、各小領域を、それぞれ処理を担当するマルチプロセッサ１１４に
割り当てる（ステップ１０５：割当工程）。
【００２１】
次に各マルチプロセッサ１１４が、自身に割り当てられた小領域のデータのうち少なくとも一部のデータをグローバルメモリ１１３から自プロセッサ内部の共有メモリ１１５に転送する（ステップ１０６：転送工程）。共有メモリ１１５は小容量であるため、小領域の数値計算に用いるすべてのデータを共有メモリ１１５に格納することはできない。そこで、数値計算において複数回参照されるデータ（典型的には、隣接参照が生じるデータ）を優先的に共有メモリ１１５に格納するとよい。
【００２２】
次に各マルチプロセッサ１１４が、グローバルメモリ１１３と共有メモリ１１５の両メモリ内のデータを用い、反復法によって近似解を更新する（ステップ１０７）。計算された近似解は各マルチプロセッサ１１４がグローバルメモリ１１３に書き込む。ここでの反復法は、ヤコビ法や共役勾配法その他、いかなる反復法でもよい。近似解更新の詳細については公知の技術であるためここでは説明を割愛する。
次にホストコンピュータ１０９が近似解の収束判定を行い、収束していれば処理を終了し、そうでなければステップ１０７に戻る（ステップ１０８）。
【００２３】
以上、本発明の一実施形態について説明したが、ステップ１０２〜ステップ１０４の領域分割工程を、ステップ１０１より先にホストコンピュータ１０９が、メモリ１１１上で行ってもよい。
また、反復法を例にとって説明したが、格子点に離散化されたデータ同士が互いを参照し合う、いわゆる行列ベクトル積演算が複数回発生する数値計算方法であればいずれの方法であってもよく、例えば陽解法においても有効である。
また、ステップ１０６の転送工程は、各マルチプロセッサ１１４が、グローバルメモリ１１３上のデータにアクセスする際に、自動的にデータを自プロセッサ内部の共有メモリ１１５に転送する、いわゆるキャッシュ機能を利用しても構わない。
【００２４】
（実施例）
以上説明した本発明の一実施形態に係る数値計算方法の効果について、以下に詳しく説明する。
【００２５】
効果の確認には、３次元格子空間においてＰｏｉｓｓｏｎ方程式を一次精度で離散化して得られた連立一次方程式の、左辺の計算をターゲットとした。使用したＧＰＵはＮｖｉｄｉａ社のＴｅｓｌａＣ１０６０であり、浮動小数点の精度は倍精度である。また各マルチプロセッサが担当する小領域の要素数は５１２要素とした。
【００２６】
図４（ａ）、図４（ｂ）に比較例の実験結果を示す。図４（ａ）、図４（ｂ）では、グローバルメモリにデータを格納する際のアドレス順序は、最も一般的な辞書式順序付けを採用した。なお図４（ａ）は、小領域の形状を８×８×８要素の立方体形状にした場合の結果であり、図４（ｂ）は、メモリアドレスが連続になる方向に沿って小領域をできるだけ扁平にした場合の結果である。
【００２７】
グラフの縦軸は計算速度の指標となるＧＦＬＯＰＳ値を表し、横軸は要素数、すなわち計算領域全体の大きさを表している。同じ要素数に対して複数のデータがプロットされているのは、様々な形状の計算領域をテストしているためである。
【００２８】
図４（ａ）と図４（ｂ）のどちらも計算領域の形状に対してＧＦＬＯＰＳ値にばらつきが生じている。また図４（ａ）と図４（ｂ）のどちらが良い性能を示すかは計算領域の形状に対して一定ではなく、最適な小領域形状は不明である。ただし結果のばらつきは図４（ａ）より図４（ｂ）が小さく、大まかな傾向としては扁平すなわち異方的な形状が適し
ていると言える。
【００２９】
一方、図４（ｃ）に本発明の実施例の実験結果を示す。小領域の形状は図４（ａ）と同様の、８×８×８要素の立方体形状である。図４（ａ）及び図４（ｂ）の結果と比較すると、計算領域の形状に対するＧＦＬＯＰＳ値のばらつきが非常に小さい。またいかなる計算領域の大きさや形状に対しても、比較例と同等もしくはそれ以上のＧＦＬＯＰＳ値を示している。
【００３０】
以上の実験結果から分かるように、本発明の数値計算方法によれば、計算領域全体の大きさや形状が変化しても、小領域内データのメモリアドレスが連続であるため、アクセス遅延が生じず、計算速度が高速で安定である。このことは、小領域の形状に関しても同じことがいえる。そのため、小領域の最適な形状が明確となる。すなわち、領域外参照が最も少なくなる形状である、所定の体積を満たす範囲で且つ表面積が最も小さい等方的な形状が、小領域の形状として最適であることが明確となる。そして、小領域の最適な形状が等方的な形状であるため、計算領域全体を分割する際に、異方性を意識する必要がなく、計算アルゴリズムとプログラム開発を簡単化できる。
【符号の説明】
【００３１】
１０９：ホストコンピュータ、１１２：ＧＰＵ、１１３：グローバルメモリ、１１４：マルチプロセッサ、１１５：共有メモリ
【図１】
2013168000.tif 000003
【図２】
2013168000.tif 000004
【図３】
2013168000.tif 000005
【図４】
2013168000.tif 000006