マルチカラーオーダリングによるスレッド 並列型  ソルバによる  のベンチマーク評価
岩 下 武 史Ý
杉 崎 由 典 ÝÝ

金 澤 正 憲Ý
青 木 正 樹ÝÝ                 
             ÝÝÝÝÝÝ

本稿で用いるベンチマークは線形反復解法の一つであ はじめにる

京都大学学術情報メディアセンターでは，  年  月法 の並列化ソルバである．同手法は有限要素法や差分法から生ずる対称な係数行列をもつ連立一次方にスーパーコンピュータを置き換え，それまでの並列ベク程式の解法として最も一般的なものの一つである．

トル型計算機 富士通  から  クラスタ型並列法は共役勾配法に不完全コレスキー分解前処理を施した計算機 富士通

 に移行した  ． クラスタ型手法であるが，一般に共役勾配法に関する処理は並列化

並列計算機は，近年スーパーコンピュータのシステムとしが容易であり，前処理に伴う計算は並列処理が難しいとて主流の形態となっており，パーソナルコンピュータにおされている．そこで，不完全コレスキー分解やその広いけるプロセッサのマルチコア化を鑑みると，一層その傾向カテゴ リである  分解前処理の並列化に関して様々なは強まると考えられる．そこで本稿では，代表的な  を

バでは，マルチカラーオーダ リング法 を用いる．同ソルバベンチマークによる性手法は，未知変数を並列処理に適した形に並び替えるリクラスタ型並列計算機の一つである富士通対象として，並列化

能評価を行う．

オーダリング手法の一種で，古くから知られた古典的手 は，富士通社製の  互換プロ法である．しかし ，その有用性は様々なアプ リケーショセッサを使用した，所謂スカラ型の並列計算機システム

ンで知られ，最新の数値シミュレーションにおいてもそである．本計算機システムはノード と呼ばれるメモリをの概念が利用されている ．マルチカラーオーダ リング

共有したマルチプロセッサシステムを高速のクロスバネッ

法の実装方法は複数考えられるが，本稿では構造型の差富士通

提案がなされている ．その中で，本稿で用いるソルトワークにより相互に接続した形態を持ち，一般に 分解析と非構造型の有限要素解析のクラスタ型と呼ばれるカテゴ リに属する．同計算機は，れぞれ異なる方法を用いる．差分解析では，ストライドノード 内に   個のアクセスによる方法を用い，有限要素解析では，間接ア種を対象とし，そ を持つノード 内高密度プロセッ
サ実装を特徴とし，   の共有メモリ空間を有している．一般にノード 内の並列処理には  などの ドレッシングによる方法を使用する．本ベンチマークにによるスレッド 並列処理が用いられる．一方，複数のノー効利用性，並列台数効果等について検討を行う．

ド を使用した並列処理の場合には，ノード 間のデータ転送に   等の通信ライブラリが使用され，マルチプロセスによる処理が行われる．本稿では， より，スカラ型並列計算機において重要なキャッシュの有 並列化  法ベンチマーク
 マルチカラーオーダリング法による並列化 の  ノードを用い， により記述されたスレッド法

並列処理ベンチマークプログラムにより評価を行う．

法ソルバは大きく分けて，反復解法により連立一次方程式の求解を行う反復部と前処理行列を求める等

Ý 京都大学学術情報メディアセンター    ÝÝ 富士通株式会社

           の反復解法に必要なセッティングを行うセットアップ部に分けられる．このうち，計算時間の点では一般的に反復部が支配的であり，大規模問題ではより顕著である．本

稿では並列処理のための付加的に必要な処理を含めて反構造型の差分解析に適しており，文献復の前段階のセットアップ部は並列化せず，逐次処理と体的手法が提案されている．本解析においても，差分解法の反復部分は以下のような計算により構

析ベンチマークでは本手法によりマルチカラーオーダ リする．

成される． 前進・後退代入計算， ベクトルの内積においてその具ングの実装を行う．

計算， 行列ベクトル積， ベクトルの更新およびノルムの計算 である．このうち，計算量として支配的であるのは，前進・後退代入計算と行列ベクトル積計算である．また，これらの計算部分のうち内積計算や行列ベ

Color 1

クトル積計算は並列化が容易であり，前進・後退代入計算の並列化が一般に困難であるとされている．そこで，従Color 2

来から前進・後退代入計算の並列処理に関する様々な提案がなされている
本稿では，

．

分解前処理に伴う前進・後退代入計算のColor 3並列化のために，マルチカラーオーダリング法を用いる．
同手法は，未知変数の順序を入れ替えることにより係数行列の非ゼロパターンを並列処理可能な形に変換するリオーダ リング手法の一種である．リオーダ リング手法に

図

マルチカラーオーダ リング法における係数行列   Æ         関する研究は様々になされており，多くのオーダ リングが提案されているが，マルチカラーオーダリングはスレッ

差分解析ベンチマークド 並列処理に向いたオーダリングである．マルチカラー

本ベンチマークでは，次式で与えられるオーダ リングでは，互いに依存関係にない未知変数を一ン方程式の境界値問題の差分解析を用いる!

つのグループとし，これを  色とみなす．ここで， 番目る可能性があるので，各色に関する処理が終了するごと#    Æ#    $        " 
 " に同期，または通信が発生する．そのため，同期・通信コ

ここで  は % 格子点を辞書式順序付けで並べた場合の格ストを削減するためになるべく少ない色数での利用が好子番号を  として% ! &  '  である! 未知数の個ましいと考えれてきたが， 数は   とする! 式  を点差分公式により離散化し % 得られる連立一次方程式を法により解く!の未知変数と  番目の未知変数が依存関係にないとは係数行列の     要素   が  であることを意味する．この
結果，各色内で前進・後退代入計算の並列処理が可能となる．一方，異なる色に属する未知変数間は依存関係があ    " 次元ポアソ   " 

 分解前処理では一般に多くの色数を用いるほうが前処理効果が高く， 色から  色の利用が有効であるという報告がある ．この

ここで % 解析プログラム上において% 係数行列と前処理行ような従来の研究結果によると，マルチカラーオーダリ列は辞書式順序付け法に基づきそれぞれ  つの一次元配ングは他のオーダ リングと比べて前処理効果が高く，反列と  つの一次元配列に格納される  ．また，本ベンチ復法の収束性に優れる．一方，同手法は元来ベクトル計

マークではマルチカラーオーダリングの実装は，(&)*%算機のために開発された方法であり，共有メモリ型の並+ が文献 に示している間接参照を必要とせず，計列処理での実装に向いている．即ち，同手法は色毎にス算順序のみを入れ替える方法を用いる．その結果，本ベンテージ化されている方法であるが，あるプロセッサが利チマークにおいて前進・後退代入計算は色数をストライド用するデータは，その直前の色に関する処理では複数の幅とするストライド アクセスをもつ計算手順により行わプロセッサが処理を行った結果となる．従って，同手法れる．図

を分散メモリ型並列計算機上のプロセス並列で利用するログラムを示す．図 において，+, は各スレッド のス

ことを考えると，非常に多数の  対  通信を実装する必レッド - を表す．また，.*/* は色数であり，&+,，要があり，オーバーヘッド の点から現実的ではない．
マルチカラーオーダ リングの実装法には大きく種類に本ベンチマークにおける前進代入計算のプ+, は各スレッドが計算する領域の開始行番号と終了行番号を表す．内側のループが各スレッド で並行的にある．即ち，陽的に未知変数を並べ替える方法と計算順行われ，その後バリア同期をとる．この操作が色数の数序のみを入れ替える方法である．ここで，前者の場合にだけ行われる．なお，後退代入計算も同様の手順で並列は係数行列は図  のような形になる ．本解析例では，非化される．

構造型の解析において同手法を用いる．一方，メモリ上 有限要素解析ベンチマークの係数行列データの格納に別の順序付けを用い，計算順

本ベンチマークでは，電磁場解析の一種である  次元

序のみを入れ替える方法は，未知変数間の関係が簡単な渦電流場の解析を対象とする．解析対象内の電磁界を記01 2  32+,%%.*/*
!!
!
!!
!
,* .*/*"%.*/*4,* "&+,'.*/*%+,%.*/*
5"5446547,84 $4.4965497,849,,*01  2
,,*
図

01 2
!!
!
!!
!
,* .*/*"%.*/*401 -  32??
,* ".&*.%.&*.'4
,* ?"/*@A%/*@A'4??"//A?
5"545??6/.?7,.??
,,*
,,*
,,*

マルチカラーオーダ リング法による並列化前進代入計算（差分解析ベンチマーク） ! " # $  %     %        &'  (   %  )*

図

述する方程式は % マクスウェル方程式において変位電流の + " # $  %     %       &'    %  )*

項を無視することにより与えられる! 本解析では % 辺要素を使用し % 磁気ベクトルポテンシャルのみによる定式化を

マルチカラーオーダ リング法による並列化前進代入計算（ 有限要素解析ベンチマーク）

表行う 4法を用いるので % 支配方程式は次式で与えられる!

    
ここで %

"





'

 は磁気ベクトルポテンシャル % は強制電流の電流密度%  は磁気抵抗率%  は導電率を表す! 磁気ベクトルポテンシャルをベクトル補間関数により近似展開し % 式   にガラーキン法を適用することにより% 次式が得られる!

: ;  ' : ;ここで %    "    は未知変数  からなる列ベクトルを表  は列ベクトルを表し % 以下の

す! : ;% : ; は行列%                ように与えられる!



 







"

ここで %数を表す! 未知変数の総数をは次正方行列%: ;:; " : ; '>の連立一次方程式が得られる．ここで，本稿では解析対象として電気学会  次元渦電流解析モデル  を用いる．
表  に解析の諸元を示す．本解析では，解析領域中に非導電性の部分（空気領域）が含まれるため% 係数行列 :;は半正定値となる!
本解析では，時間発展問題のある  ステップをベンチ法をそのまま用いることができない．そこ

どあり，法 本解析は非構造型の解析であるため，並列化法

計算では間接アドレッシングが用いられる．また，マル<として % 行列 : ;% : ;次元ベクトルである! 式  中の時間微分項を後退差分法により解くと，:;  "  
但し %

 

ソルバにおける行列・ベクトル積演算や前進・後退代入

 はベクトル補間関  および   は

 '  を用いることとする．

 



は各要素%  は全要素数%

で，加速パラメータを ! としたシフト付き



 



場解析では，係数行列は正値性を失っている場合がほとん  "

  " > : ;

マーク問題とする．本解析のような辺要素を用いた電磁  "有限要素解析ベンチマーク（ + 次元渦電流解析）の諸元,%  +      -% ) $
./!.
-%    +!012.
-%  +3!!!4

=チカラーオーダ リング法の実装については未知変数を陽的に並び替える手法を使用した．このとき，前進代入計算の並列化プログラムは図  のように与えられる．図中において，.&*. は . 番目の色の未知変数の開始番号であり，各色毎に代入計算が並列化される．

 数 値 実 験 実 行 環 境本ベンチマークは京都大学学術情報メディアセンターの富士通（  < !

5 ）上で行った．プ

ログラムは B3C  により書かれ，並列処理の として  を用いている．コンパイル時の最適化
オプションには 4DE&A " を指定した．また，法の収束基準として右辺ベクトルノルムと残差ノルムの比を用い，その値が 以下となった時点で収束とみなす．

差分解析ベンチマーク結果

表 に差分解析ベンチマークの結果を示す．なお，表中において計算時間は反復の開始から終了までの間の経過時間を示しており，不完全コレスキー分解などの反復解法部のセットアップ部分の時間は含まれていない．まず，マルチカラーオーダリング法による並列化法の収束性については，色数を増やすほど向上しており，従来の研究結果と合致している   ．差分解析におけるオーダリングの影響については，文献  において， .*+A/*, の数が多いほど収束性が悪化することが示されており，マルチカラーオーダ リングにおいて色数が増加するに従い収束性が増すことを説明することができる．また，著者らの一部も文献  において，オーダリングと収束性の関係を示す指標を提案しており，その値からも本現象を説明することができる．一方，表  に   時における  反復あたりの計算時間と色数の関係を示すが，色数が増すにつれて大幅に  反復あたりの計算時間を要していることがわかる．これはストライド 幅が増加することにより，キャッシュのヒット率が大きく低下したことによる．ベクトル計算機上での実行では，バンクコンフリクトを起こす場合を除けば  反復あたりの計算時間は色数に対してあまり変化しないため，高い収束性が得られる
色数の多い場合が有効となるがスカラ型の計算機では注意が必要である．次に，速度向上については概ね高い並列化効率を得ている．特に色数が多い場合にはスーパーリニアな性能を示しており，色数  の場合には顕著である．これは，並列化によりデータアクセスの局所性が高まりキャッシュのヒット率が向上したためである．プ
ロファイラによる分析では，色数  の場合の代入計算ループについて   時と <  時で， キャッシュミス率， キャッシュミス率，3 ミス率がそれぞれ

F → ! F，F → !F，!<F → !F のように大幅に向上している．これらの結果から上記のような速度向上が得られたものと考えられる．最後に総合的な表

差分解析ベンチマーク結果,% ! 5  )  '  (  &* 色数 ! の場合
" 数 計算時間（ 秒） 反復回数 速度向上
!32
1..
.
!
+2
1..
2.
30!+
4//
+3!
2
34+
4//
432
!
!04
4//
/.+
1
2/
1..
+
&%* 色数 3 の場合
" 数 計算時間（ 秒） 反復回数 速度向上

+.3
+++
.
!
01
++!
0+
3/!+
++
+!/
2
1+
++
3/4
!
+++
++!
/!
1!.
++4
&* 色数 2 の場合
" 数 計算時間（ 秒） 反復回数 速度向上

333
01
.
!
!42
01
0!
3
+1
01
+!4
2/420
31
!
3+0
0
.!
1!003!.3&* 色数 !. の場合
" 数 計算時間（ 秒） 反復回数 速度向上
4/4
.03
.
!
+!0
.0+
2!
3
24
.0.
+!!
2
++
.1/
330
!
402
.12
.+
1
!+0
.0+!4&* 色数 .. の場合
" 数 計算時間（ 秒） 反復回数 速度向上

00+
.!
.
!
+3
.+!30
3/2
.!
022
2+/.
.!
/2
!
!+!
.!
+++
1
31
.!
4!/
表   反復あたりの計算時間と色数の関係,% + 6    % $               %   
色数!
32!. ..
計算時間（ミリ秒）
44 !!2 +02 443 013

計算性能を考えると，本解析では色数 ，  数 <の場合が最もよい結果となった．これは，色数を多くし表中において計算時間は反復の開始から終了までの間のた場合でも十分に各プロセッサが扱うデータサイズが小経過時間を示している．まず，色数と反復回数との関係さい場合にはキャッシュのヒット率が向上し，収束性に優では， から   程度の色数の変化ではそれほど大きなれた色数の多い場合が有効であることを示している．し差はなかった．但し，色数を  以上とした場合には改かし，問題サイズに対してプロセッサ数が十分ではない善が見られることが分かっている．次に， 反復あたり場合には，最小の色数である色の場合が有効となると考えられる．の計算時間については，色数が増大するに従って増加しているが差分解析ほど 顕著ではない．これは色数の増加

 有限要素解析ベンチマーク結果

に従ってキャッシュのヒット率が下がることが原因と考え

表  に有限要素解析ベンチマークの結果を示す．なお，られるが，差分解析と比べて未知変数間のデータ関係が表

表

有限要素解析ベンチマーク結果,% 3 5  )  '   &* 色数 3. の場合
" 数 計算時間（秒） 反復回数 速度向上
2!+
3/1
.
!
31
3/1
/0
3!!
3/1
+222
4
3/1
03
!
001
3/1
.1
11
3/1
+4&%* 色数 2. の場合
" 数 計算時間（秒） 反復回数 速度向上
2//
4./
.
!
343
4./
/23!!24./+/4
2
!!
4./
0+/!
2+3
4./
.2
1104./
+3
&* 色数 !. の場合
" 数 計算時間（秒） 反復回数 速度向上
/.
3/0
.
!
4/!
3/0!.
3!22
3/0
3+2
3/
3/0
0/1
!
.
3/0
0
1
21
3/0
31

有限要素解析ベンチマークにおけるラージページの効果,% 4 7(       '   %  )&* 色数 3. の場合
" 数 計算時間（ 秒） 反復回数 速度向上
03/3/1
.
!
+2!
3/1
/1
3
/4
3/1
+23
2

3/1100
!
0+!
3/1
.!
1
40/3/1
+.
&%* 色数 2. の場合
" 数 計算時間（ 秒） 反復回数 速度向上
244./
.
!
3+4./
/0
3!.2
4./
+/
2
14./0.+!
00+4./
.4
11!
4./
++&* 色数 !. の場合
" 数 計算時間（ 秒） 反復回数 速度向上
.01
3/0
.
!
4+1
3/0!..
3!1
3/0
3+
2
3!
3/0
041
!
/!2
3/0
1
10+
3/0
30

複雑な有限要素解析では元来ランダムアクセスとなって16いるためにその低下率は小さい．次に並列化効率についN 40 colors
N 80 colors
N 120 colors
L 40 colors
L 80 colors
L 120 colors

14ては全体的に高い値を得ており，マルチカラーオーダ リ
12

能では，色数  の場合が最も計算時間が短かった．
次に，  が備えるラージページ機能について本Speed-up

ング法の有効性を示している．総合的なベンチマーク性

108

ベンチマークにより評価を行った．当該の機能はページ6サイズを大きくすることにより，大きな配列を扱う科学

4

技術計算において 3 ミスの軽減を狙った機能である．

2

表にその結果を示す．また，図  に本ベンチマークにおいて色数 ，  数を  とした場合を基準とする速度向上を示す．表 ，図  より，いずれの色数の場合にも性能が改善され，ラージページ機能が有効であることが分かる．

 お わ り に00246810121416

Number of processors-8 ノーマルページ
8 3    '    %  ) &-8    8    *図

有限要素解析ベンチマークにおける速度向上（使用， ラージページ使用）

同様の傾向が見られたが，色数に対する  反復あたりの本稿では，マルチカラーオーダ リング法による並列化価を行った．色数をストライド 幅とするストライド アク

 が備える 88
機能について評価を行ったが， 万自由度の当該ベンセスをもつ差分解析ベンチマークでは，色数の増加に従チマーク問題において性能改善が見られた．

法ソルバベンチマークにより

 の性能評

計算時間の変化は差分解析の場合と比べて小さかった．また，本ベンチマークではい，キャッシュのヒット率が著しく低下し， 反復あたりの計算時間が増加する現象が見られた．しかし ，使用プロセッサ数を増加することによりアクセスするデータの局所性が高まり，スーパーリニアな並列台数効果を得ることにより，色数が大きい場合でも問題サイズが適度に小さければ高い性能を得ることができることがわかった．
有限要素解析ベンチマークにおいても差分解析の場合と参

考 文献

 杉崎 由典，青木 正樹，義久 智樹，金澤 正憲 「 におけるスレッド 並列の台数効果と高速化手法について」
情報処理学会 研究報告              ! " # $ %& # '"(" " )
Æ( *   %&&(  &*+ ,   -.. // 0 1  

,       23 )"   (4 # / $ 5!+ .1  --1 // 1.6 .
 7   " # / $ %
&+ (    "  /"   ,  8  2 '" 94 4  : 2("5!  9(& " 2 ; <=  &  )4(  (&/  3(>
+   --- // --  
1 ? @& (  $  # A!(! B  " " &! + )  (4   //  1-.   8!;  B  ! 2" ;( # 94  ( )!4 B+ - -0- //1, 1.0 2 ="   "&  4C( !  ( 94 #   > ))B    3 &  %+   ,0 // - ,- 2 '"  ? %& 9 // ! ( $A (4+
 1  -- // 1,1 1
「同期点の少ない並列化 ))B
 岩下 武史，島崎 眞昭；

     

        

法のためのブロック化赤−黒順序付け 」，情報処理学会論文誌，   , @ ，，// 0-, - ．

  8   $("=%  B/" 2"% //(" #  %>4 " ;( # 94  $A
(4+ @: /   --  =" 2 @" 7  "& D )&/ ) #   94  $A (4  1 @ // , 6 1 , 2 @ @ 2"" 2 &  ? !&!)&/ # ! " #  %  3 &  , 8 4( 3   %+   .  --  // ., .1
 ? 3!= 2 @   3!%!  (( # )4( )"(( # " ))B"+   .  --,
// -0 -1         