2005/12/05

前回のおさらい（１）
前回のおさらい（１）z 最適なストライピングユニットサイズの選択– 大きくするか，小さくするか，トレードオフの問題– 解析的に求めるのが難しく，今後の課題となっている
z RAIDの例– Thinking Machines 社 Scale Array– NCR社 6298
– Hewlett-Packard研究所 TickerTAIP/DataMesh– UCB RAID-II– Auspex NetServer– NetApp Multiprotocol Filer– SiliconGraphics Challenge RAID
– Sun Microsystems StorEDGE

データ工学特論（４）
情報基盤センター
天野 浩文
この講義に関するwebサイト：
http://isabelle.cc.kyushu-u.ac.jp/~amano/data-engineering/

データ工学特論（４）

データ工学特論（４）12

前回のおさらい（２）
前回のおさらい（２）

前回のおさらい（３）前回のおさらい（３）z 並列計算機のアーキテクチャ …その多様な分類法– Flynnの分類（1966）z 分散メモリ型並列計算機では，それぞれのメモリにデータを読み込む必要がある– 共有メモリ型よりも難しくなる• SISD （これは並列ではない）• SIMD• MISD• MIMD

相互結合網– 共有メモリ型並列計算機と分散メモリ型並列計算機– 超並列計算機– SMPクラスタ

データ工学特論（４）

データ工学特論（４）それぞれのプロセッサのメモリにデータが読み込まれなければならない
3

データはメモリのどこにあっても，すべてのプロセッサから使える

データ工学特論（４）412005/12/05

前回のおさらい（４）前回のおさらい（４）前回のおさらい（５）前回のおさらい（５）z 分散メモリ型並列計算機– 多数のPE（processing element）と大容量の主記憶によって大量のデータを用いた大規模な計算を行うことができる– 複数のディスクを搭載し，それを並列に駆動できる
z 高度な科学技術計算では，計算の精度をあげようとす
ると必要なデータの量が急激に増大することが多い– そのようなプログラムは，計算時間を短縮するため，並列化されることが多い– 並列プログラムにディスク入出力を行わせる必要が出てくる

z 並列プログラムのデータ入出力

データ工学特論（４）5– 単一のPEが代表で入出力を行う⇒大容量のデータの入出力には時間がかかる– 複数のPEが同時に入出力を行う⇒プログラマが制御するのは面倒

並列入出力のためのしくみ
並列入出力のためのしくみ

z 複数のPE上で動作している各プロセスが，自分の必要とするデータを並列に入出力
z あたかも，それぞれがローカルディスクにアクセスしているかのように（物理的にはそうでなくてもよい）z 並列ファイルシステム

プロセス

計算部分
（並列モード）後処理部分（単一PEモード）

データ工学特論（４）並列入出力のイメージ
並列入出力のイメージ

PE

前処理部分
（単一PEモード）

6（どちらかというと）複数のディスクをまとめて１つのファイルシステ
ムのイメージを提供– Vestaファイルシステム– Acaciaファイルシステム

z 並列入出力ライブラリ（どちらかというと，ディスクはバラバラで，それを並列に使うイメージを提供）– Bordawekar らの並列入出力プリミティブ– Galbreath らの応用指向並列入出力パッケージ

データの流れz 並列入出力インタフェース– MPIの集団型入出力インタフェース
ディスク
データ工学特論（４）

データ工学特論（４）7

データ工学特論（４）822005/12/05

Vestaファイルシステム
Vestaファイルシステム

Vesta
Vesta の想定する環境の想定する環境

z 超並列計算機SPシリーズのための並列ファイルシステム（IBM ワトソン研究所）– 科学技術計算用
科学技術計算におけるファイル入出力…大規模ファイルの読み書きが中心
z Vesta 並列ファイルシステムの設計方針– 並列性
入出力を行う応用プログラムからディスクの駆動プログラムまで，すべて並列に動作させる– スケーラビリティ
超並列計算機のPE数が増大しても拡張可能に– MIMDスタイル
同一ファイルに対して異なる関数を実行可能

z 計算ノードとストレージノードからなる超並列計算機– 計算ノード
計算を実行．データの入出力はストレージノードに要求– ストレージノード
計算ノードからの入出力要求を処理．それぞれがディスクアレイを保有．

データ工学特論（４）ストレージノード
低遅延・高速ネットワーク

計算ノード

9

データ工学特論（４）10

物理分割（Physical
物理分割（Physical Partitioning）－（１）Partitioning）－（１）

物理分割（Physical
物理分割（Physical Partitioning）－（２）Partitioning）－（２）z Vestaファイルの基本構造…２次元ファイル⇒物理パーティションの集まり
物理パーティション⇒レコードの線形並び
z 物理パーティション数とレコードサイズはファイル作成時に決定…その後は変化しないz レコードの基本順序 (canonical ordering)１レコード単位で各物理パーティション上をストライピン
グ
z 物理パーティションの意味
１つのストレージノードにまとめて蓄えられるデータのまとまり
z ファイルの格納に使われるストレージノードとの対応– 実際のストレージノード数より小さいとき⇒各物理パーティションを１ストレージノードに格納– 実際のストレージノード数より大きいとき⇒全パーティションを全ストレージノードに均等分配

レコード

物理パーティション

データ工学特論（４）

データ工学特論（４）11データ工学特論（４）1232005/12/05
論理分割（Logical
論理分割（Logical Partitioning）－（１）Partitioning）－（１）

論理分割（Logical
論理分割（Logical Partitioning）－（２）Partitioning）－（２）z Vesta のファイルの「見え方 (view)」を制御– テンプレート…レコードのレイアウトの最小単位

z 物理パーティション（下の例では１２本）がカバーされるまでタイルパターンを繰り返す．レコード数が増大すると，これを下方向に繰り返す．

0
12345

垂直グループサイズ(Vgs)

物理パーティション

１カラムは同一物理パーティション内に割り付ける
隣接するカラムは「隣接」する物理パーティションに割り付ける

水平グループサイズ(Hgs)– タイルパターン…これの繰り返しで物理パーティションをカバー
垂直インターリーブ(Vi)水平インターリーブ(Hi)左のように設定すると，６系統の論理パーティションが作成される⇒6つのプロセスで利用

データ工学特論（４）13012345678910110120121213141213143453451516171516170
1201212131412131434534
515161715161701201212131412131434
5345151617151617678678181920
18192091011910112122232122
23678678181920
181920910119101121
2223
21
22
23

6786
7818
1920
18
1920

910
11
910
11
2122
23
212223

データ工学特論（４）Vesta
Vesta ファイルへのアクセス（１）
ファイルへのアクセス（１）Vesta
Vesta ファイルへのアクセス（２）ファイルへのアクセス（２）z 通常の UNIX ではopen システムコールでz Vesta_create … Vestaファイルの生成
単一のプロセスが代表して呼び出す⇒この呼び出し部分だけはどうしても並列にならない（Vesta サーバ側は並列に動作可能）– ファイルの有無のチェック– パーミッションのチェック– ファイルシステムのテーブルにエントリを追加– プロセスのファイルディスクリプタテーブルにエントリを追加

z パラメータ– その Vesta ファイルが使用する物理パーティション数z Vestaでは…UNIXの open に相当する操作を細分化– Vesta_create … Vesta ファイルの生成– Vesta_attach … 既存のVestaファイル情報の取得– Vesta_open … 取得した情報をもとにローカルにファイルをオープン
データ工学特論（４）

データ工学特論（４）14– レコードサイズ（ストライピングユニットサイズ）

15

データ工学特論（４）1642005/12/05
Vesta
Vesta ファイルへのアクセス（３）ファイルへのアクセス（３）Vesta
Vesta ファイルへのアクセス（４）ファイルへのアクセス（４）z Vesta_attach …Vesta ファイル情報の取得

z Vesta_open …Vestaファイルを各プロセスがオープン– 物理パーティション数と位置– レコードサイズ– パラメータ• ファイル名• 水平・垂直グループサイズ• 水平・垂直インターリーブ• 論理パーティション番号z Vesta_attach_share,
Vesta_attach_accept
巨大ジョブの場合には間接通信も可能– 代表のプロセスが Vesta_attachを実行– 続いて Vesta_attach_share を実行– 他のプロセスは Vesta_attach_accept を実行
他のプロセス他のプロセス他のプロセス他のプロセス他のプロセス他のプロセス– コールのたびに特定の論理パーティションに対するファイルディスクリプタが返る（各プロセスがそれぞれ独立のオフセットを持つ）
z Vesta_open_share, Vesta_open_accept
論理パーティション内でのオフセットを共有できる

Vesta サーバ
代表のプロセス
データ工学特論（４）

データ工学特論（４）

17

Vesta
Vesta ファイルへのアクセス（５）ファイルへのアクセス（５）

利用例
利用例

z Vesta_read, Vesta_write
オープンした論理パーティションへのアクセス– フラグ
複数の物理パーティションにまたがるアクセスの制御の「慎重さ」を制御

z 行列積 C=A×B• CAUTIOUS：複数のプロセスが同一パーティションを操作する際の原子性 atomicity と線形順序を保証（原子性…各プロセスのデータがまとめて入出力されるか，あるいはまったく入出力されないかのどちらかであるように保証されること）• RECKLESS：保証しない

z Vesta_read_q, Vesta_write_q
非同期読み出し・書き込みのスタート
データ工学特論（４）

データ工学特論（４）

19

AC

B

18

pdim=sqrt(PROC_NUM);
blk_size=MAT_SIZE/pdim;
float A[MAT_SIZE][blk_size],B[blk_size][MAT_SIZE],
C[blk_size][blk_size];
Vgs=blk_size; Vi=pdim;
Hgs=MAT_SIZE; Hi=1;
fda=Vesta_open("A",Vgs,Vi,Hgs,Hi,me/pdim);Vgs=MAT_SIZE; Vi=1;
Hgs=blk_size; Hi=pdim;
fdb=Vesta_open("B",Vgs,Vi,Hgs,Hi,me%pdim);
Vgs=blk_size; Vi=pdim;
Hgs=blk_size; Hi=pdim;
fdc=Vesta_open("C",Vgs,Vi,Hgs,Hi,me);Vesta_read(fda,A,MAT_SIZE*blk_size);
Vesta_read(fdb,B,MAT_SIZE*blk_size);for (i=0; i<blk_size; i++)for (j=0; j<blk_size; j++) {C[i][j]=0;
for (k=0; k<MAT_SIZE; k++)C[i][j] += A[k][j] * B[j][k]}Vesta_write(fdc,C,blk_size*blk_size);
データ工学特論（４）2052005/12/05
並列ファイルシステム
並列ファイルシステム Acacia
Acacia

実装の概要
実装の概要

z 並列計算機 Fujitsu AP1000 用ファイルシステム– ファイルアクセスモードの指定– ディレクトリアクセスモードの指定– ファイルレイアウトの制御– 分散ファイルキャッシングの利用
ホストz AP1000…並列処理研究用計算機– 最大1024プロセッサ
PE
PE
PEPE
PE
PE
（ディスク装着時は512）– PEのサブセットにディスクを搭載することができる

z キャッシュタスク– 各PEでデータをキャッシュ– ユーザタスク，ファイルサーバタスクとの通信
z ファイルサーバタスク– ディスクのあるPEにのみ配置– ディスクへのアクセスを担当

データ工学特論（４）PEPE

user task user task

user task user task

user task user task

cache task

cache task

cache task

file server task

データ工学特論（４）2122ファイルアクセスモード（１）ファイルアクセスモード（１）ファイルアクセスモード（２）ファイルアクセスモード（２）z 複数のPEが同一のファイルへのアクセスするときのアクセスのしかたを制御
z 複数のモードをサポート– 独立モード– 複製モード– 共有モードz 独立モード– 各PEが独立のファイルポインタを持つ⇔同一ファイル中の任意の位置に独立にアクセス– 各キャッシュタスクが独立にファイルサーバタスクと通信– ファイルの一貫性はファイルサーバタスクが管理– 分散ファイルキャッシング（後述）を用いても効率はあまり望めない• 無指定• 固定順，固定長• 任意順，固定長• 任意順，可変長user task 1

user task 2

user task 3

file
データ工学特論（４）

データ工学特論（４）23

データ工学特論（４）2462005/12/05

ファイルアクセスモード（３）ファイルアクセスモード（３）ファイルアクセスモード（４）ファイルアクセスモード（４）z 複製モード– 各PEがファイルポインタを持つが，値はすべて同じ– 全PEが同じ位置で同じデータをアクセス– ディスクを持つファイルサーバが読み出し・書き込
みを代行– 読み出しの場合，ファイルサーバが読んだデータを全PEのキャッシュタスクにブロードキャスト

z 共有モード– ファイルポインタが各PEで共有される（同時に使われるというよりも，使い回しされるというイメージ）– 各PEがアクセスするデータに重なりがなく，連続z 共有モード(1)－無指定– ファイルアクセスが直列化されるため非効率

user task 1

user task 2

user task 3

user task 1

user task 2

user task 3

filefile
データ工学特論（４）

データ工学特論（４）2526

ファイルアクセスモード（５）ファイルアクセスモード（５）ファイルアクセスモード（６）ファイルアクセスモード（６）z 共有モード(2)－固定順・固定長z 共有モード(3)－固定順・可変長– アクセスは読み・書きのいずれかに統一される– 順序はPEの番号順，サイズが可変– ファイル内の各レコードのサイズをファイルレイアウト（後述）として別途登録しておけば，前のタスクのアクセス完了前に他のタスクのアクセス位置を計算できる（ただし，書き込み時にレコードサイズの変更はできない）– 各タスクからのアクセスが読み出し・書き込みのいずれかに統一される– 順序はPEの番号順，サイズが固定– 各タスクのアクセス位置を独立に計算できる(読み出しの場合）

user task 1

user task 2

user task 3(読み出しの場合）

user task 1

user task 2

user task 3

filefile
データ工学特論（４）

データ工学特論（４）27

データ工学特論（４）2872005/12/05

ファイルアクセスモード（７）ファイルアクセスモード（７）ファイルアクセスモード（８）ファイルアクセスモード（８）z 共有モード(4)－任意順・固定長z 共有モード(5)－任意順・可変長– アクセスは読み出し・書き込みのいずれかに統一される– 順序は任意（ファイルサーバが決定），サイズも可変– ファイルレイアウトの利用による効率化– 順序付けによるネットワークの有効利用– アクセスは読み出し・書き込みのいずれかに統一– 順序は任意（ファイルサーバが決定），サイズは固定– 前のタスクのアクセス完了前に他のタスクのアクセス位置を計算できる– ネットワークが有効利用できる順序をサーバが勝手に決めてよい(読み出しの場合）

user task 1

user task 2

user task 3(読み出しの場合）

fileuser task 1

user task 2

user task 3

file
データ工学特論（４）

データ工学特論（４）2930

ディレクトリアクセスモード（１）ディレクトリアクセスモード（１）ディレクトリアクセスモード（２）ディレクトリアクセスモード（２）z 各PEが多数のファイルにアクセスする場合，ファイルアクセスよりもディレクトリアクセスが性能低下の原因となる可能性
z 複数プログラムモード（デフォルト）– 各ファイルのオープン処理は独立– 同一ファイルのオープンは直列化される– ディレクトリを持つファイルサーバがボトルネックになる可能性が大きい

z 単一プログラムモード– 各PEが同じファイルのオープンを並行に行う場合に利用可能– 同じファイルポインタを共有する必要はない．
– クローズは独立に実行可能

user task 1

file 1user task 2

user task 2

user task 3

user task 3

file 2
データ工学特論（４）

データ工学特論（４）user task 1

directry

file31

データ工学特論（４）directry
32

8

2005/12/05

ファイルレイアウト制御（１）ファイルレイアウト制御（１）ファイルレイアウト制御（２）ファイルレイアウト制御（２）zファイルサーバタスク–逐次型–これらを論理的にまとめたものが並列ファイルサーバの役割をする
z並列ファイル–複数の順次ファイル(sequential file) に格納された固定長のブロックを Round-Robin 順序で並べたもの

z ファイルレイアウトパラメータ…ファイルごとに指定可能server #1
block #1

server #1
block #1

server #2
block #1

server #3
block #1

server #1
block #2

server #1
block #2

server #2
block #1

– 逐次型ファイルサーバの数と順序• 並列ファイルをインターリーブして格納するサーバの数• サーバの間の順序– ブロック長• 逐次サーバ内で処理されるブロックのサイズ– 冗長度

server #2
block #2

• 多数のディスクが使用されることによるMTTFの低下を防ぐための冗長情報の与え方

server #2
block #2

データ工学特論（４）33

データ工学特論（４）34

ファイルレイアウト制御（３）ファイルレイアウト制御（３）分散ファイルキャッシング（１）分散ファイルキャッシング（１）zファイルレイアウトパラメータ（つづき）

z各タスクがアクセスするブロックに重なりがある場合–一度読み込んだデータをキャッシュしておくとディスクアクセスを削減できる–しかも，一度読み込んだデータが次に役に立つのは，別のプロセッサにおいてである–各タスクのアクセスの順序をうまく制御しなくては不正な結果やデッドロックが生じることがある
zこれは，並行処理における一貫性制御と同じ問題– 逐次型ファイルサーバの数と順序– ブロック長– 冗長度– 論理レコード長• 可変長レコードが使用される場合は，各レコードのサイズを事前に指定可能• 各逐次サーバはこれをできるだけ同一ブロック内に配置

データ工学特論（４）

データ工学特論（４）35データ工学特論（４）3692005/12/05

一貫性制御方式の例（１）一貫性制御方式の例（１）一貫性制御方式の例（２）一貫性制御方式の例（２）z 二相ロック（Two Phase Locking）方式…古典的方法

z 木プロトコル（Tree Protocol)– アクセスする共有資源の間に半順序をつけ，全タスクがその順にしたがってロックを確保する– ２つのフェーズに分かれていなくても，等価な結果を生む直列スケジュールが存在することが保証される．
– デッドロックを回避できることが保証される．
z Acaciaでは…
２ブロック逐次ロック（Two Block Sequential Locking）
木プロトコルの変種– ユーザタスクのアクセスするブロックの順序が，全ユーザタスクで一定になっていると仮定– そうすると，すべてのロックを保持しつづける必要はなく，最大２ブロックまででよい．

– ロックをかけるフェーズとはずすフェーズが分離されるようにする．
（ロックをはずすフェーズが始まるまでは全ロックを保持）– 各タスクが任意の順序でアクセスしても，等価な結果を生む直列スケジュールが存在することが保証される．
– ただし，デッドロックの可能性ありロック確保数

ロックを確保するフェーズと解放するフェーズに分離
時間
データ工学特論（４）

データ工学特論（４）3738

分散ファイルキャッシング（２）分散ファイルキャッシング（２）分散ファイルキャッシング（３）分散ファイルキャッシング（３）z キャッシュタスク間のロック委託による２ブロック逐次ロック(1)

ユーザタスクは全要求（1, 2, 3）をキャッシュタスク１に送る．

(2)キャッシュタスク１はブロック１をロックする（取れるまで待つ）．

(3)

キャッシュタスク１はブロック１を送受信（方向は読み・書きによる）．

(4)

キャッシュタスク１は残りの要求（2, 3）を次のキャッシュタスク２に転送する．

(5)キャッシュタスク２はブロック２をロックする（取れるまで待つ）．

(6)

キャッシュタスク２はブロック２が取れたことをキャッシュタスク１に報告する．

(7)

キャッシュタスク１はブロック１をアンロックする．

(8)キャッシュタスク２はブロック２を送受信（方向は読み・書きによる）．

(9)キャッシュタスク１は残りの要求（2, 3）を次のキャッシュタスク２に転送する．

user task(8)(13) ブロック３の送受信(3)
ブロック２のブロック１
送受信の送受信(4)cache task 1
cache task 2
残りの要求
block 1
block 22, 3 を送信(1) 要求1,2, 3を送信

(2) ブロック１をロック(7) ブロック１をアンロック(6) 返答(5) ブロック2をロック(12) ブロック2をアンロック

サーバ数：３(9)cache task 3
残りの要求
block 3
3 を送信(11) 返答(10) ブロック3をロック(14) ブロック3をアンロック(10) キャッシュタスク３はブロック３をロックする（取れるまで待つ）．
(11) キャッシュタスク３はブロック３が取れたことをキャッシュタスク１に報告する．
(12) キャッシュタスク２はブロック２をアンロックする．
(13) キャッシュタスク３はブロック３を送受信（方向は読み・書きによる）．

データ工学特論（４）

データ工学特論（４）39(14) キャッシュタスク３はブロック３をアンロックする．
データ工学特論（４）40102005/12/05

分散ファイルキャッシング（４）分散ファイルキャッシング（４）分散ファイルキャッシングの性能（１）分散ファイルキャッシングの性能（１）z ２ブロック逐次ロック– ステップ(3)と(4)は交換しても可z 一般に，ロックによる並行処理では– リソースの空きを待つ順序のグラフに閉路がなければ，デッドロックはおきない
z ２ブロック逐次ロックは，ブロックのアクセス順序が線形であるので，複数のタスクがいてもサイクルはできない
z しかし，個々のキャッシュタスクに入ってくる要求の順序は線形でない

z 実験環境– ディスクなしPEのみのAP1000でシミュレーション(ストレージサーバはホスト）– キャッシュ入れ替えアルゴリズム：LRU

キャッシュタスクは，複数のタスクからの要求に並列・並行に応答できなければならない
データ工学特論（４）z パラメータ
キャッシュブロックサイズ(byte)
要求サイズ(byte)
PE 数

256512 1024 2048 4096 8192 16384

12825624512 1024 2048 4096
81632648192
128

データ工学特論（４）4142

分散ファイルキャッシングの性能（３）分散ファイルキャッシングの性能（３）z 全PEがファイル全体に対し連続読み出しをかけるときのPE１台あたりの転送性能

z 各PEが重なりのない連続セグメントに書き込むとき
32KB 16KB
1000
8KB
2KB 4KB
1KB
1000.5KB

1000

4KB
2KB

8KB

16KB

1KB

(KB/PE/sec)

1000.5KB
Block Size = 0.25KB
10.1

Block Size
= 0.25KB
10110要求サイズ(KB)
データ工学特論（４）

データ工学特論（４）(KB/PE/sec)

転送速度

32KB

転送速度

分散ファイルキャッシングの性能（２）分散ファイルキャッシングの性能（２）

0.1

40
43

10要求サイズ(KB)
データ工学特論（４）404411

2005/12/05

Acaciaファイルシステムの総合的な転送性能（１）Acaciaファイルシステムの総合的な転送性能（１）Acaciaファイルシステムの総合的な転送性能（２）Acaciaファイルシステムの総合的な転送性能（２）z 総合的な転送性能の指標– 持続総合転送速度(Sustained Aggregate Rate)z 256MBのファイルを16KB単位で32ディスクに分散させた場合（128PEのAP1000） ディスクのあるPEに計算負荷がか

z 実験で評価
– 前提

15
1050

• ファイルのオープン・クローズのオーバーヘッドは無視• キャッシュによる性能向上を無視（毎回ディスクアクセス）• ファイルアクセスモードの選択による性能向上も無視

データ工学特論（４）かると，性能が急激に低下する

SAR(MB/sec)• max ：各PEの転送速度の単純和• min：最も遅いPEでの処理が終わるまでの時間で転送デー
タ量の総和を割る

4060
80100120
読み出しタスク数•タスクが増えると，最初はSARが上昇，その後はだんだん飽和•ディスクのあるPEでもユーザタスクが走り始めると SARminが極端に悪化
45020

データ工学特論（４）46

まとめまとめz 並列プログラムのデータ入出力– 単一プロセッサに代表してやらせる– 各プロセッサで並列にやる
z 並列入出力のためのしくみ– 並列ファイルシステム• Vesta• Acacia

データ工学特論（４）

データ工学特論（４）4712