2006/1/16

おさらい（１）
おさらい（１）z並列プログラムの入出力
単一のPEが代表で入出力を行う⇒大容量のデータの入出力には時間がかかる
複数のPEが同時に入出力を行う⇒プログラマが制御するのは面倒

データ工学特論（７）
情報基盤センター
天野 浩文

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

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

2

おさらい（２）
おさらい（２）

おさらい（３）
おさらい（３）z 並列入出力のイメージ
 複数のPE上で動作している各プロセスが，自分の必要とするデータを並列に入出力
 あたかも，それぞれがローカルディスクにアクセスしているかのように（物理的にはそうでなくてもよい）プロセスPEz 並列ファイルシステム（どちらかというと）複数のディスクをまとめて１つのファイルシステムのイメージを提供
 Vestaファイルシステム
 Acaciaファイルシステム

z 並列入出力ライブラリ（どちらかというと）すでにあるファイルシステムを並列に使うイメージを提供
 Bordawekar らの並列入出力プリミティブ
 Galbreath らの応用指向並列入出力パッケージ

データの流れz （既存のライブラリの）並列入出力インタフェース
 MPIの集団型入出力（collective I/O）インタフェース
ディスク3

データ工学特論(7)412006/1/16

おさらい（４）
おさらい（４） Vesta
Vesta

おさらい（５）
おさらい（５） Vesta
Vesta

z Vestaファイルの基本構造…２次元ファイル⇒物理パーティションの集まり
物理パーティション⇒レコードの線形並び
z 物理パーティション数とレコードサイズはファイル作成時に決定…その後は変化しない

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

レコード

物理パーティション

0

1

2

3

4

56

7

8

9

10

110
120
12121314121314

3453
4515
16
1715
16
170
120
12
12131412131434534515161715
16170
12012121314
12131434534515161715
16
17

6
786
7818
1920
18
1920

91011
9101121
22
23
21
22
23

6
786
7818
1920
18
1920

910
11910
1121
22
23
21
22
23

6
786
7818
1920
18
1920

91011
910
1121
22
23
21
22
23

56

おさらい（６）
おさらい（６） Acacia
Acaciaおさらい（７）
おさらい（７） Acacia
Acaciaz キャッシュタスク
 各PEでデータをキャッシュ ユーザタスク，ファイルサーバタスクとの通信z ファイルサーバタスク
 ディスクのあるPEにのみ配置
 ディスクへのアクセスを担当

zファイルアクセスモード
複数のPEが同一のファイルへのアクセスするときのアクセスのしかたを制御
z複数のモードをサポート
独立モード複製モード共有モード• 無指定• 固定順，固定長• 任意順，固定長• 任意順，可変長user task user task

user task user task

user task user task

cache task

cache task

cache task

file server task

7

データ工学特論(7)822006/1/16

おさらい（８）
おさらい（８） Acacia
Acacia

さて，今回は…
さて，今回は…

z 分散ファイルキャッシング

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

 キャッシュタスク間のロック委託による２ブロック逐次ロック
user task

サーバ数：３(13) ブロック３の(8)(3)(1) 要求1,送受信
ブロック２のブロック１
2, 3を送受信の送受信
送信
(4)
(9)
cache task 1
cache task 2
cache task 3
残りの要求
残りの要求
block 1
block 2
block 32, 3 を送信
3 を送信(2) ブロック１をロック(7) ブロック１をアンロック(6) 返答(5) ブロック2をロック(12) ブロック2をアンロック(11) 返答z 並列入出力ライブラリ(10) ブロック3をロック(14) ブロック3をアンロック（どちらかというと，すでにあるファイルシステムを並列に使うイメージを提供）
 Bordawekar らの並列入出力プリミティブ
 Galbreath らの応用指向並列入出力パッケージz （既存のライブラリの）並列入出力インタフェース
 MPI-2の並列入出力インタフェース

910

Bordawekar
Bordawekar らの並列入出力プリミティブ
らの並列入出力プリミティブ

巨大配列のプロセッサへのマッピング
巨大配列のプロセッサへのマッピング

zBordawekar, del Rosario, Choudhary (Univ. Syracuse, 1993)
Intel Touchstone Delta 用にさまざまなデータの分散法をサポートする並列入出力プリミティブを実装
二段階アクセス戦略（Two-Phase Access Strategy）
配列データのプロセッサへのマッピングとディスクへのマッピ
ングは別のものとして扱う
SPMD（Single Program, Multiple Data） 方式の並列プログラ
ムに，逐次ファイルと同様のインタフェースを提供•popen, pclose•pread, pwrite•proc_map, array_map

zVienna Fortran, Fortran D, High Performance Fortran などが許すプロセッサへのマッピングの例（SPMD: 同じプログラムのコピーをMIMD計算機の各プロセッサ上で同時に実行する形態のこと）

11

データ工学特論(7)Row Block012345678

Cyclic-Cyclic 0 3 6 0 3 6 0 3 61 4 7 1 4 7 1 4 7
2 5 8 2 5 8 2 5 80 3 6 0 3 6 0 3 6
1 4 7 1 4 7 1 4 72 5 8 2 5 8 2 5 80 3 6 0 3 6 0 3 6
1 4 7 1 4 7 1 4 7
2 5 8 2 5 8 2 5 8Column Block配列の各要
0 1 2 3 4 5 6 7 8
素を何番目のプロセッサに割り当てるか
Block-Block
036

1

472

58123

2006/1/16

配列データのディスクへのマッピング（１）配列データのディスクへのマッピング（１）配列データのディスクへのマッピング（２）配列データのディスクへのマッピング（２）zマッピングの例： 列優先順序（Column-Major Order）

zマッピングの例： 行優先順序（Row-Major Order）

配列01036912 1514710 13 16

ディスクブロック

配列

2345672580361472589121518101316191114172001

ディスクブロック

23456711 14 171314

直接アクセス方式
直接アクセス方式

２つのマッピングの干渉
２つのマッピングの干渉

z並列計算機付属の入出力ライブラリでサポートされる低水準入出力関数
PE番号とメモリ上のアドレスディスク上のブロックアドレス
z個々の入出力関数は，上記の２つを指定して呼び出す

z配列データのプロセッサへのマッピングとディスクへのマッピングが合わないとどうなるか
Column-Block の場合
入出力要求数＝ブロック数zこの方式では，配列データのプロセッサへのマッピングとディスクへのマッピングが合わない場合に困ったことになる

PE0block0 block4 block8

PE1

block1 block5 block9

PE2block2 block6 block10

PE3block3 block7 block11

block0
block1
block2
block3block4block5block6block7block8block9block10
block11
block12block13
block14block15

Row-Block の場合
入出力要求数＝PE数PE0block0 block1

block3

PE1

block4 block5

block7PE2

block8 block9

block11

block12 block13

block15

PE3（行優先順序）
15

データ工学特論(7)1642006/1/16

マッピングの種類と入出力要求の総数
マッピングの種類と入出力要求の総数

直接アクセス方式の性能（１）
直接アクセス方式の性能（１）zN×N配列を Column-Major で格納するときの入出力要求数

z実験に使用したシステム… Intel Touchstone Delta
Intel 80860 (i860)プロセッサ採用
後の Intel Paragon のプロトタイプ

Sdist
Rtrans = Rdist ×min( Sdist , S stripe )分散法

Rdist：ストライプサイズを無視したときの入出力要求数
Sdist：連続してアクセスできる最大ブロック数
Sstripe：ストライプサイズ

Rdist

Sdist

N∗ PN

Block-Cyclic

N∗ PN

Cyclic-Block

N2N2

1Block-Block

Cyclic-Cyclic

16P

16×32=512 PEs32
P

132×2=64 disks
1718

直接アクセス方式の性能
直接アクセス方式の性能

並列入出力プリミティブの設計
並列入出力プリミティブの設計

zColumn-BlockColumn-Major （列優先）との相性がよい

z直接アクセス方式の問題点
マッピングの違いにより，性能に極端な差が出る

zColumn-Major に対する性能の比較
Column-Block＞Column-Cyclic＞Row-Block＞Row-Cyclic
最良のものと最悪のものでは，２桁以上の差がある

z２段階アクセス方式（読み出しの場合の例）
ディスク上のデータ分散に最も適したマッピングでひとまずメモリに読み込むユーザの指定するプロセッサへのマッピングが食い違う場合には，プロセッサ間でデータを再分配する
zさまざまなマッピングを許すことができるが，性能はそれほど下がらない
zpopen, pclose, pread, pwrite
proc_map, array_map

19

データ工学特論(7)2052006/1/16

並列ファイルのオープン・クローズ
並列ファイルのオープン・クローズ配列のプロセッサへのマッピング
配列のプロセッサへのマッピング

zオープン
popen(ユニットナンバ，ファイル名，アクセスモード，フォーマット，モード，ディスク数，I/Oを行う PE 数 )array_map(データを格納する配列，サイズ情報配列，分散情報配列，ブロックサイズ配列，プロセッサ数配列 )…オープンする並列ファイルのID…sequential か direct か…書式付きか，書式なしか…新規，既存，etc.
…-1なら全部…各次元ごとに記述
…
〃…
〃…
〃

戻り値…アレイディスクリプタ (integer)．アレイディスクリプタテーブルのID．
z例：64×64配列を Block-Block で４プロセッサに分配するときのアレイディス
64
クリプタテーブル(Array Descriptor Table, ADT)
G lo b a l S iz e
D istr.
C ode
B lo c k S iz en p ro c s

zクローズ
pclose(ユニットナンバ)

164
1264
1

3-1-1

4-1-1

5-1-1

6-1-1

7-1-1-1
2-1
2-1-1-1-1-1-1-1-1-1-164
Block SizeはCyclicのときのみ使用する(-1は don't care)21

22

実プロセッサと論理プロセッサのマッピング
実プロセッサと論理プロセッサのマッピング

Read/Write
Read/Writezプロセッサ集合を物理レベル論理レベルに分けて定義できる

z並列読み出しpread(データ配列名，
読み込むデータのサイズ，...
アレイディスクリプタ，ユニットナンバ，
バッファ配列名，バッファサイズ )proc_map(次元ごとのプロセッサ数の配列， … ADT と同じもの
パラメータ，… 0 なら変更なし
ユーザ定義マップ情報配列 )z並列書き込み… pwriteもpreadと同様
z配列の実プロセッサへのマップとディスクとのマップの相性が悪いときには，自動的に中間的なマッピングを用いて入出力を行う．

23

データ工学特論(7)2462006/1/16

２段階アクセス方式の性能
２段階アクセス方式の性能

Galbreath
Galbreath らの応用指向並列入出力パッケージ
らの応用指向並列入出力パッケージ

zColumn-Majorで格納された10K*10K配列を64PEに分配する場合zGalbreath, Gropp, Levine (Argonne Nat. Lab., 1993)

最適 read 再配分
Column-Block
11395
Column-Cyclic
11395
2478
Row-Block
11395
1028
Row-Cyclic
11395
3092

計
直接アクセス 速度向上
11395
11395113873
63400
4.57
11623
78767
6.87
14487
*>248

（単位は msec． *は時間のオーダになってしまったもの）

Column-Blockに読み込むときが最も効率がよい（11395ms）．
Column-Cyclic, Row-Block, Row-Cyclic は，Column-Blockでアクセスしてから再配分する時間を合わせても，直接アクセス方式よりも数倍～数百倍効率がよい．

PETSc/Chameleon パッケージ
応用レベルの要求に適合した高水準の並列入出力(PIO)パッケージ

z実際の科学技術計算で必要となる入出力を分析…使用されているプログラムコードではなく，要求記述を分析入力（初期値）
デバッグ用作業ファイル (scratch file)チェックポイント／リスタート出力（計算結果）

25

26

科学技術計算プログラムにおける入出力
科学技術計算プログラムにおける入出力

PETSc/Chameleonパッケージの設計方針
PETSc/Chameleonパッケージの設計方針

z入力
大域的パラメータ…各PEに複製が置かれる
各格子点の初期状態…各PEに分割して置かれる
zデバッグ用途中の状態を記録して，逐次版の結果と比較…通常の逐次ファイルと同じ形式で書き込まれる必要がある．
z作業ファイル
再計算を省略したり，メモリに入りきれないデータを格納する．
zチェックポイント／リスタート
各PEの状態を書き込み，あとで元通りに読み込むことが必要．
z出力
いくつかのパラメータだけ出力するものから，各PEの値をすべて出力するものまで，さまざま．

zSPMDプログラムで使用するための高水準入出力関数
ライブラリ
共通のスカラー値（あるいは小配列）を読み書き分散配列を各プロセスが一斉に読み書き特定のプロセスがまとまったデータを読み書き
z従来型のストリーム入出力とのアナロジを残す
fopen, fclose, fread, fwrite, ...
z抽象化のレベルを高く分散配列の物理的な格納方法は意識しない異なるアーキテクチャへの移植や性能の向上は関数の実装レベルで吸収，応用プログラムには影響を与えないように

27

28

データ工学特論(7)72006/1/16

主な入出力関数
主な入出力関数システムのイメージシステムのイメージzPIFopen, PIFclose並列ファイルのオープン・クローズ
並列ファイルポインタ（PIFile構造体へのポインタ）を返す
zPIFReadCommon, PIFWriteCommon
各PEに複製されるデータの読み書き
zPIFReadDistributedArray,
PIFWriteDistributedArray
各PEに分割して置かれる配列データを単一ファイルから読み書き
zPIFRead, PIFWrite
各PEが大量データを読み書きするとき

ユーザ
データ

PE

PE

PE

PE

PE

パック
する
相互結合網

PIOパッ
ケージが応用プログラ
ムから隠蔽してしまう部
分

I/Oネットワーク

29

30

並列ファイルモードと逐次ファイルモード
並列ファイルモードと逐次ファイルモード

実機での性能実機での性能zPIFopen のパラメータを１個書き換えるだけで，並列ファイルを通常の UNIX ファイルと互換の逐次ファイルに書き出せる…デバッグに便利

zIBM SP-1 （ファイルサイズ：16MB）
各PEにディスクがついている
PE数とブロックサイズを変化させる
PE 数 分割の 性 能が 最 も 最小の最小のサイズ 低下するブ Read 性能 Write 性能
ロックサイズ MB/sec
MB/sec
44MB
8KB
626
82MB
64KB
1240
161MB
16KB
2630

zワークステーションクラスタにおける性能比較（ファイルサイズ：64KB）
ファイル形式 PE 数 ReadWrite
MB/sec MB/sec
並列2
6.8
3.7
逐次2
0.8
0.1

31

データ工学特論(7)応用プログラムが意識する部分

328

2006/1/16

MPI
MPI

MPIの概要（１）MPIの概要（１）z並列計算機の問題点
それぞれのメーカ・開発者が独自の構想で設計・実装• 固有のアーキテクチャ• 固有のプログラミング言語• 固有のプログラミング環境
次の並列機が登場するたびに，プログラムの書き換えが必要
zMPI (Message Passing Interface)プラットフォームが変わっても，同じプログラムを動作させることはできないか？ ⇒標準化への動き• 仮想的な分散メモリ型並列計算機の上のプロセッサ間通信ライブラリを提供• プログラミング言語は既存のものを活用• 並列計算機ごとにライブラリのほうを実装あるいは変更

z（PVMと並ぶ）並列プログラミングライブラリの国際標準
zCまたはFortranから呼び出すことのできる関数群
並列プロセスの初期化：MPI_Init()自分のプロセスIDの取得：MPI_Comm_rank()
プロセスの総数の取得：MPI_Comm_size()宛先のIDを指定してメッセージを送信：MPI_Send()
送信もとを指定して受信：MPI_Recv()
並列処理の終了：MPI_Finalize()などなど．
zSPMD (single-program, multiple-data)同一のプログラムのコピーを複数のプロセッサで走らせる実行形態

33

34

MPIの概要（２）MPIの概要（２）MPIの概要（３）MPIの概要（３）zプログラマはMPIの関数を呼び出すようなプログラムを１つ書く．
実行時にプログラムのコピーを配布して実行．

zプロセスによって処理の内容を変えたいときは…
プロセスIDによる条件分岐で対処#include ”mpi.h”...
void main(int argc, char* argv[]) {... /* 通常の逐次処理を行う部分 */MPI_Init(&argc, &argv);...
MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);...
if (my_rank==0) {/* プロセス0の処理内容 */...
/* 各プロセスで並列に行う処理 */...

} else {/* 他のプロセスの処理内容 */MPI_Finalize();... /* 通常の逐次処理を行う部分 */} /* main の終わり */}...
35

データ工学特論(7)3692006/1/16

MPIの概要（４）MPIの概要（４）MPIプログラムにおけるファイルI/Oの問題点
MPIプログラムにおけるファイルI/Oの問題点

zメッセージの送受の際に，宛先（送信元），メッセージのサイズ・種別，同時に集団型（collective）通信に参加するプロセス集合などを指定する．

zUNIXのファイル入出力インタフェース read(),write()を呼び出すことはできる．しかし．．．
もともとは非並列プログラムでのI/Oを想定
並列プロセスが同一ファイルに同時アクセスするための機能を持っていない• 同一ファイルの異なる部分にアクセスする機能がない• 不連続なデータを単一の操作でアクセスする機
能がない
多数のファイルアクセス要求をまとめて効率的に処理する機能を持っていない非同期アクセスの機能を持っていない

int MPI_Recv(void*
int
MPI_Datatype
int
int
MPI_Comm
MPI_Status)

messagecountdatatypesourcetagcommstatus/* out */,/* in */,/* in */,/* in */,/* in */,/* in */,/* out */

メッセージ
サイズ
送信元種別
プロセス集合（ステータス）

z派生データ型（derived data type）のデータを含むメッセージも扱える3738

MPI-2の並列入出力インタフェース（１）MPI-2の並列入出力インタフェース（１）MPI-2の並列入出力インタフェース（２）MPI-2の並列入出力インタフェース（２）z当初MPI-IOとして設計→MPI規格2.0で取り入れ
zファイル入出力を，メッセージ通信と見なす
read ⇒ receivewrite ⇒ sendz各プロセスが入出力要求を出す
z新たに３つの引数を追加…いずれもMPIの派生データ型
filetype ファイル上のデータ配置パターン
buftype ユーザバッファ上のデータ配置パターン
etype
要素型 (elementary datatype)zfiletype と etype はファイルをオープンするときに指定する
zbuftype は比較的自由に設定可能
zファイル上のデータ配置は，filetypeのパターンの繰り返し

zプロセス間のデータ分配の例

39

データ工学特論(7)etype

穴(hole)…このプロセスには「見えない」部分

process 1 filetype
process 2 filetype
process 3 filetype

プロセス１にとってのファイルデータ上の３つのパターンを重ね合わせてファイルを埋めると．．．

40

10

2006/1/16

MPI-2の並列入出力インタフェース（３）MPI-2の並列入出力インタフェース（３）集団型入出力（Collective
集団型入出力（Collective I/O）
I/O）

z行列データを読み出してメモリ上で転置する例

zMPIプログラムは，SPMD動作をする
各プロセスからの入出力関数の呼び出しは，一致とは言わな
いまでも，比較的まとまっているしたがって，これらの関数呼び出しを，それぞれバラバラのものと扱うこともできるが，各プロセスがいっせいに呼び出すものとして扱うこともできる．
zこのため，MPIの並列入出力関数は，同じ操作に対して，独立型と集団型の2種類のインタフェースが用意されている
独立型は，バラバラに動作する（実行の終了したプロセスは先に進んでよい）集団型は，同期して動作する（他のプロセスでの実行が終了するまで，全プロセスが待ち合わせに入る）

実ファイル中のデータレイアウト（行列が行優先順序で入っているものとする）(1) 各プロセスが自分の持ち分だけを読む

filetype
process1
process2
process3(2) 転置行列の列ベクトルを作り，要素１個分ずつずらしながらコピーする

buftype （各プロセスで共通）

process1にとってのデータ連続する５個のデータを３個ずつとばした位置に並べなおすと，転置行列の列ベクトルを作ることができる
41

集団型入出力の重要性
集団型入出力の重要性

位置決め

同期

Explict
offset

Sync

プロセス間協調独立型

z独立型では，各プロセスからの入出力要求が独立の入出力として扱われる
各プロセスからの要求を少数の入出力システムコールにまとめることが困難
効率の低下z集団型では，各プロセスからの入出力要求が同期して実行される
各プロセスがバラバラに発した入出力要求をひとまとめにすることができる
効率化の可能性
43

データ工学特論(7)

42

集団型

MPI_File_read_at
MPI_File_write_at
Async MPI_File_iread_at
MPI_File_iwrite_at

MPI_File_read_at_all
MPI_File_write_at_allMPI_File_read_at_all_begin
MPI_File_read_at_all_end
MPI_File_write_at_all_begin
MPI_File_write_at_all_end
Individual Sync MPI_File_read
MPI_File_read_all
offsetMPI_File_write
MPI_File_write_all
Async MPI_File_iread
MPI_File_read_all_begin
MPI_File_iwrite
MPI_File_read_all_end
MPI_File_write_all_begin
MPI_File_write_all_end
SharedSync MPI_File_read_shared MPI_File_read_ordered
offsetMPI_File_write_shared MPI_File_write_ordered
Async MPI_File_iread_shared MPI_File_read_ordered_begin
MPI_File_iwrite_shared MPI_File_read_ordered_end
MPI_File_write_ordered_begin
MPI_File_write_ordered_end
ブロッキング，ノンブロッキングととらえたほうがわかりやすいかも44

11

2006/1/16

まとめ
まとめz並列入出力ライブラリ（どちらかというと，すでにあるファイルシステムを並列に使うイメージを提供）
Bordawekar らの並列入出力プリミティブ• 二段階アクセス戦略• 行優先順序と列優先順序
Galbreath らの応用指向並列入出力パッケージ• 物理的なデータ構成をユーザから隠蔽• 逐次型のストリーム入出力インタフェースを並列版に拡張z（既存のライブラリの）並列入出力インタフェース
MPI-2の並列入出力インタフェース• 単一ファイル上のどの部分にアクセスするかを，プロセスごとに filetype によって指定
45

データ工学特論(7)12