Survey: Portable High-Performance Programs

Survey:
Portable High-Performance
Programs の一部
2000.4.12 遠藤敏夫
今回の内容

Portable High-Performance Programs
[Frigo 99(PhD)]
テーマはportability

Cache-oblivious algorithms
([Frigo et al. 99], PhD Chap 3)



メモリ階層に対してportable
逐次の話
Portable parallel memory (PhD Chap 4)


Cilk: 並列性に対してportable
Cilkの性能モデルにメモリ階層の影響を追加
Frigo


Cilkグループ(MIT)の一員
FFTWで1999年Wilkinson賞を受賞

FFTW: FFTに特化したコンパイラによって高
速化

Cilkの性能モデルにメモリ階層の影響を追
加

遠藤の行く手に立ちふさがる人物
Cache-oblivious algorithms
Oblivious … a. 忘れっぽい、気づかない
対義語: aware, conscious



プログラムのメモリアクセスパターンの工夫により、キャッ
シュミスの少ない(=速い)プログラムを作ることができる
でも、プログラマに各計算機固有(アーキテクチャに
aware)の最適化をやらせたくない
いくつかの問題に対して、cache-obliviousかつ性能のよ
いアルゴリズムを提案


行列積、転置行列、ソート、FFT
キーワードはdivide and conquer
準備: 理想キャッシュモデル(1)
Cache
CPU
Main memory
Q
Z
H
L




キャッシュは1階層のみ
ラインサイズL(word), ライン数H
キャッシュサイズ Z = LH (word)
プログラムを走らせたときのキャッシュミス数Q
準備: 理想キャッシュモデル(2)

Full associative

ライン置換え規則: 将来のアクセスが最後である
ようなラインを追い出す


局所性を完全に利用できる
Z = Ω(L2) (L2オーダー以上)を仮定
この理想的キャッシュでのミス数Qが小さいアルゴ
リズムを提案
行列積(1):単純方式
C

=
A
B
A, B, C: n×n行列
単純なアルゴリズム(iterativeアルゴリズム):
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
for (k = 0; k < n; k++)
C[i,j] += A[i,k] * B[k,j]
計算量はO(n3)
行列積(2) :単純方式の評価
C
A
B
×n

単純アルゴリズムでのキャッシュミス数Qは？
ここでは、だいたいn < Z/3 < n2として考える
(一行ならキャッシュに収まるが、行列全体はムリ)
 C: 全体writeを1回…QC = O(n2/L)
 A: 各行n回readしてから次へ… QA = O(n2/L)
 B: 全体readをn回…QB = O(n3/L)
結局、Q = O(n3/L)
アルゴリズム変更で減らせる!
行列積(3) :Blocked方式

Blockedアルゴリズム

各行列をs×s小行列に分割

s=O(√Z)

n
s
小行列がキャッシュに収まるような s
for (i = 0; i < n/s; i++)
for (j = 0; j < n/s; j++)
for (k = 0; k < n/s; k++)
mul(s, A, B, C, i, j, k)
この中は普通にiterative
行列積(4): Blocked方式の評価

一回のmul では



計算量はO(s3)で普通
キャッシュミスQ=O(s2/L)ですむ
Blockedアルゴリズム全体では


計算量はO(n3)で普通
キャッシュミスQ=O(n3/Ls)=O(n3/L√Z)



(nがいくつでも成立する式はQ=O(n+n2/L+n3/L√Z) )
Qは単純アルゴリズムより√Z倍減った！
しかし、sをzに依存させる必要(cache-aware)
行列積(5): Recursive方式

Recursiveアルゴリズム

行列A, B, Cを4等分しながら
再帰呼び出し
if (n == 1)
C += A B
再帰の終点
else
A→A11, A12, A21, A22 (B, Cも同様)
C11 += A11 B11; C11 += A12 B21
C12 += A11 B12; C12 += A12 B22
C21 += A21 B11; C21 += A22 B21
C22 += A21 B12; C22 += A22 B22
サイズをn/2にして
再帰呼び出し
(divide&conquer!)
行列積(6):
Recursive方式の評価

枝別れしていったいつかは、全行列がキャッシュ
に収まるサイズになる

その時のサイズはs=O(√Z)のはず
計算量、ミス数の議論はBlockedと同じ

Q=O(n+n2/L+n3/L√Z)


プログラム中にZ, Lに依存する変数は現れない (cache-

oblivious)
Blockedアルゴリズムと同等(違ったとしても定数倍)のQ
行列積(7): recursiveは速いか？
0.35
0.3
0.25
iter
rec-1
rec-4
rec-32
0.2
0.15
0.1
0.05
0
0




200
400
600
(調査: 遠藤)
横軸… n, 縦軸… (実行時間 / n3)
venus(Ultra SPARC 360MHz)
Iterative(iter)とrecursive(rec-X)を比較
考察:
 iterはn>256くらいで遅くなる
 rec-Xはnにほぼ依存しないが、rec-1は遅すぎる
 再帰を4や32で止めるとiterに勝つ
Funnel sort (1)
入力
n個


マージソートの一種
多数のk-merger(図中三角)の組み合わせ


結果列(長さn)
一番右はn1/3-merger
計算量=O(n log n), Q=O((n/L)(1+log Z n))
Funnel sort (2): k-merger

k-mergerの外部仕様


長さk2×k本の入力列 →長さk3の出力列
k-mergerの内部構造



√k個の√k-merger L1…L√k
√k本のFIFOキュー(長さ2k3/2)
1個の√k-merger R
√k本
k本
L1
L2
R
Funnel sort (3): k-mergerの詳細

以下を、入力データがなくなるまで繰り返す



Liのうち、バッファが半分以下しか埋まっていない
mergerたちを動作させる
→ 全バッファが少なくとも半分埋まる
Rを動作させる
最終的に、各Liはk回づつ、Rはk3/2回動作する


内部mergerに小出しにさせることにより、バッファサイ
ズを小さく押さえるというのがツボらしい
k-mergerのデータサイズはO(k2) (自分の出力バッファ
除く)
Funnel sort (4): Qの概略

外/内方向の再帰について
k-merger を1回動かしたときのミス数 QM(k)
 kがO(√Z)より大きい…QM(k) ≦ 2k3/2 QM(√k) + k2
 kがO(√Z)以下…QM(k) = O(k3/L)
 帰納法により、 QM(k)=O(k3/L+k3 log Z k/L)

左右方向の再帰について
funnel sort全体のミス数Q(n)
 nがO(Z)より大きい…Q(n) = n1/3 Q(n2/3) + QM(n1/3)
 nがO(Z)以下…Q(n)=O(n/L)
 帰納法により、Q(n) = O((n/L)(1+log Z n))
Funnel sort(5): 他ソートとの比較
NがZよりも大きいとき、

Funnel sort では Q(n) = O((n/L) log Z n)
2way merge sortでは Q(n) = O((n/L) log2(n/Z))多分

たとえば Z=216, n=224のとき、

log Z n : log2(n/Z) = 24/16 : 24-16 = 1.5 : 8
nが十分大きければ、log Z倍funnel sortが有利

Cache-oblivious algorithmまとめ

いくつかの問題に対し、Cache-obliviousかつミス
数の少ないアルゴリズムを提案・議論


少なくともsortでは、ミス数は漸近的最適


基本方針はdivide&conquer
行列積・FFTではlower boundが知られてないらしい
future work: cache-obliviousアルゴリズムが
cache-awareアルゴリズムに勝てない場合はある
のか？
Portable parallel memory

ここから後半です。

ここでの結論は、
TP(Z,L) = O((T1+μQ)/P + μHT∞)
背景: Cilk(1)

文脈: 並列言語Cilkは、

細粒度マルチスレッド機能を提供


プログラマはCPU数などを気にせず並列プログラミ
ング
並列プログラムの性能モデルを提供


1CPUでの実行時間 T1と、クリティカルパス長さ T∞
から、並列実行時間を求めることができる
しかし、モデルにメモリ階層の影響が入っていなか
った → 本研究により追加
背景: Cilk(2)

行列積のプログラム例(文法はいい加減)
if (n == 1) C = A B
else
A→A11, A12, A21, A22 (B, Cも同様)
spawn(C11 = A11 B11); spawn(T11 = A12 B21)
spawn(C12 = A11 B12); spawn(T12 = A12 B22)
spawn(C21 = A21 B11); spawn(T21 = A22 B21)
spawn(C22 = A21 B12); spawn(T22 = A22 B22)
sync;
matrix_add(n, T, C) /* C += T を並列実行 */


任意の場所でのfork /親によってjoin
lock/unlockなし
背景: Cilk(3)
タスク
クリティカルパス中
のタスク
依存関係
T1: 全タスク量(1プロセッサでの実行時間)
T∞: クリティカルパス長のとき、
Pプロセッサでの平均実行時間 O(T1/P + T∞)
メモリ階層を考慮した
性能モデル



分散共有メモリを仮定
Location-consistency (後述)
プログラムのメモリアクセスは各メモリに対して均
等に起こると仮定

遠藤の研究では、ばらつきがある場合に対応
メモリモデル(1)

各プロセッサは以下を持つ:




サイズZ=H×LのLRUキャッシュ
十分なサイズのメモリ
キャッシュミス時は、自分または他プロセッサの
メモリからキャッシュへコピー
平均ミス(fetch)コスト μ
CPU
CPU
CPU
CPU
cache
cache
cache
cache
memory
memory
memory
memory
メモリモデル(2):
location-consistency



Relaxed consistency modelの一種
Cilkのスレッドスケジューラと連携
location-consistencyの定義:

Cをスレッド依存グラフとしたとき、任意の
location(cache line) lについてCのtopological sort Tlが
存在し、lへのreadの結果はTlにおける直前のwriteの
結果である

直観: タスクu→vという依存関係があるならuでの
write結果は必ずvに見える
メモリモデル(3)

Location consistencyを実現するために
 プロセッサp上のタスクuと、q上のvに、u→v と
いう依存関係があるとき、


pはu後に全cache lineをreconcile(write back)
qはv前に全cache lineをreconcile, flush
メモリモデルへの意見



ハードウェアDSMで実装するなら、CPUが全reconcile命
令などを備えている必要
ソフトウェアDSMだとすると、よそのmemoryから直接
cacheへ通信できるという前提が不自然
relaxed モデルを採用した理由は、不定期に起こる
invalidationを避けるためと考えられる
 別プロセッサ間タスク依存のあるときのみ、余分に
reconcile&flush

遠藤の研究では(ほぼ)sequential consistencyである
マシンを対象。その変わりプログラムがほとんど
invalidationを起こさないことを仮定
記号・用語説明(1)




T1: 全仕事量(ミスコストなし)
T1(Z,L): 全仕事量(ミスコスト込み)
μ: 一回のtransfer (fetch/reconcile)平均時間
Q: 逐次でのミス数


T∞: クリティカルパス長(ミスコストなし)


T1(Z,L) = T1 +μ Q
T∞(Z,L)というのは使わない
TP(Z,L): Pプロセッサでの実行時間
記号・用語説明(2)

Subcomputation :仕事グラフを以下の時点で区
切ったもの



プロセッサが仕事を得た時点 /ひまになった時点
同期待ちを起こした時点/ 起こされた時点
並列実行時のtransferの分類


intrinsic transfer: 逐次に実行したときでも起こるもの
(総数Q)
extrinsic transfer: 並列実行のときのみ起こるもの

用法: あるsubcomputationがN個のextrinsic transferを引き起
こした
transfer数の議論

各subcomputationに、最大3Hのextrinsic transfer
が対応(Hはcache line数、H=Z/L)




subcomputation開始時に最大Hのreconcile
subcomputation実行中に、逐次の時より最大H余計に
ミス(fetch)
subcomputation終了時に最大Hのreconcile
並列時の平均キャッシュミス数は

Q(Z,L) + O(HPT∞)
並列化オーバヘッドの議論

event=task steal試行+extrinsic transfer

各プロセッサが以下の仮定を満たすとき、



event回数の、全プロセッサでの合計は平均で
O(HPT∞)



task steal成功の間にはH回以上のtransfer
task steal試行の間には1回以上のtransfer
27HP回のeventのうち、少なくとも4P回がsteal 試行
4P回steal試行があれば、1/2以上の確率でcritical
pathにそって仕事が進む
event回数×μが並列化オーバヘッド
並列実行時間の議論

PプロセッサでのCilkプログラム平均実行時間は
TP(Z,L) = O((T1(Z,L)/P + μHT∞)
= O((T1+μQ)/P + μHT∞)

各プロセッサの消費する時間の合計は、
 計算+intrinsic transferに T1(Z,L)
 eventに O(μHPT∞)
補足: アクセス衝突

これまでの議論はtransfer時に衝突がないことを
仮定。衝突があると、transferコストはμ以上にな
るかも

→ transfer対象がランダムで平均しているという仮定
なので、衝突コストを入れてもせいぜい定数倍、という
ことを証明

意見: 確かにこの仮定が成り立つなら、定数倍という
結果は感覚的に納得できる。しかしOrigin2000のよう
なマシンではその仮定が崩れうる。遠藤の研究はそこ
に注目。
Portable parallel memoryまとめ

Cilkの実行時間モデルにキャッシュの影響を追
加


Cilkのスレッドスケジューラ、location-consistency、アク
セスがbalanced、という仮定のもとで
TP(Z,L) = O((T1+μQ)/P + μHT∞)
divide&conquerプログラムにおいて、使用メモリ
量の上限を解析(未survey)
自分の研究について


並列時キャッシュミス = 逐次時キャッシュミス +
O(H × steal回数) というのを先にやられてしまっ
た
Frigoはオーダー解析をメインに行っているので、
定数部にも注目し、実験を通して予測と実測の
比較をメインにやっていきたい

プログラムを並列GCに限定(invalidationがおそらくあ
まり起こらない、タスクグラフが簡単)

Download Report