Dependency Analysis入門
このエントリは言語実装 Advent Calendar 2019 - Qiita 16日目の記事です。1日ばかりフライングですが先に記事が完成してしまったので投稿します。
κeenです。最近最適化コンパイラの本の読書会をやっているのですが、そこで学んだことの一部をアウトプットします。
Dependencyとは
ここで扱うDependencyとは何なのか、Dependencyが分かると何が嬉しいのかを見ていきます。
例えば以下のプログラムを考えましょう。
let mut v = 1;
v += 1;
println!("{}", v);
変数 v を1に束縛したあと v に1を足し込み、それを表示しています。結果は2が表示されますね。
2
もしこのプログラムの2行目と3行目を入れ替えて以下のようにしたとしましょう。
let mut v = 1;
println!("{}", v);
v += 1;
これだと v に1足し込む前に v の値を表示しているので1が表示されますね。
1
結果が変わってしまいました。一般に、プログラムを書き換えると結果が変わってしまうことがあります。
もう1つ、例を見てみましょう。以下のプログラムを考えます。変数が1つ増えました。
let mut v = 1;
let mut w = 1;
v += 1;
w += 1;
println!("{}", v + w);
実行すると4が表示されますね。
4
このプログラムも先程と同様に3行目と4行目を入れ替えて1を足し込む順番を変えたらどうなるでしょう。
let mut v = 1;
let mut w = 1;
w += 1;
v += 1;
println!("{}", v + w);
この場合は結果は変わらず4が表示されます。
4
プログラムの順番を変更したにもかかわらず、結果が変わっていません。 最初の例とこの例違い、もちろん感覚では分かるかと思いますが、ちゃんと理路整然と説明できますか？ もうちょっと言うとプログラムの順番の変更で結果が変わるかと変わらないかを判定するプログラムを書けますか？
この違いを説明するために使う語彙が「Dependency」、それをプログラムで調べて書き換えられるかを検査するのが「Dependency Analysis」です。
さて、Dependencyが分かると何が嬉しいのかを見ていきましょう。 先程までの例だと少し単純すぎるのでもうちょっと実用的な例を出します。 以下のシンプルなプログラムを考えます。
fn f(v: &mut [f32]) {
for i in 0..(v.len() - 1) {
v[i + 1] = v[i] + 1.0;
}
}
次の要素に今の要素 + 1.0をしているだけのかわいいループです。
この関数を実行するときは全て1.0で埋まった128要素の配列（要するに[1.0; 128]）を渡してあげることにします。
実行せずにいきなり書き換えてしまいますが、このプログラムはloop unrollして以下のように書き換えられますね。
const SIZE: usize = 8;
fn f(v: &mut [f32]) {
let limit = v.len() - 1;
for i in (0..(limit - (SIZE - 1))).step_by(SIZE) {
v[i + 1] = v[i] + 1.0;
v[i + 2] = v[i + 1] + 1.0;
v[i + 3] = v[i + 2] + 1.0;
v[i + 4] = v[i + 3] + 1.0;
v[i + 5] = v[i + 4] + 1.0;
v[i + 6] = v[i + 5] + 1.0;
v[i + 7] = v[i + 6] + 1.0;
v[i + 8] = v[i + 7] + 1.0;
}
for i in (limit / SIZE * SIZE)..limit {
v[i + 1] = v[i] + 1.0;
}
}
ここまではプログラムの結果は変わらず1.0づつ増える数列になります。
1, 2, 3, 4, 5, 6, 7, 8
9, 10, 11, 12, 13, 14, 15, 16
17, 18, 19, 20, 21, 22, 23, 24
25, 26, 27, 28, 29, 30, 31, 32
33, 34, 35, 36, 37, 38, 39, 40
41, 42, 43, 44, 45, 46, 47, 48
49, 50, 51, 52, 53, 54, 55, 56
57, 58, 59, 60, 61, 62, 63, 64
65, 66, 67, 68, 69, 70, 71, 72
73, 74, 75, 76, 77, 78, 79, 80
81, 82, 83, 84, 85, 86, 87, 88
89, 90, 91, 92, 93, 94, 95, 96
97, 98, 99, 100, 101, 102, 103, 104
105, 106, 107, 108, 109, 110, 111, 112
113, 114, 115, 116, 117, 118, 119, 120
121, 122, 123, 124, 125, 126, 127, 128
これをSIMD化してみましょう。ループ内の8回の足し算を一度に同時に行なってしまう訳です。
fn f(v: &mut [f32]) {
// アラインメントの扱いが面倒 & + 1してるのでどのみちアライメントが崩れるのでloadu/storeuを使う
use std::arch::x86_64::{_mm256_add_ps, _mm256_loadu_ps, _mm256_set1_ps, _mm256_storeu_ps};
unsafe {
let limit = v.len() - 1;
let ones = _mm256_set1_ps(1.0);
let ptr = v.as_mut_ptr();
for i in (0..(limit - (SIZE - 1))).step_by(SIZE) {
let data = _mm256_loadu_ps(ptr.offset(i as isize));
let ret = _mm256_add_ps(data, ones);
_mm256_storeu_ps(ptr.offset((i + 1) as isize), ret);
}
for i in ((limit - (SIZE - 1)) / SIZE * SIZE)..limit {
v[i + 1] = v[i] + 1.0;
}
}
}
ちょっと厳ついプログラムになってしまいました。
これを実行してみると、結果が変わってしまっていることが分かます。
1, 2, 2, 2, 2, 2, 2, 2
2, 3, 2, 2, 2, 2, 2, 2
2, 3, 2, 2, 2, 2, 2, 2
2, 3, 2, 2, 2, 2, 2, 2
2, 3, 2, 2, 2, 2, 2, 2
2, 3, 2, 2, 2, 2, 2, 2
2, 3, 2, 2, 2, 2, 2, 2
2, 3, 2, 2, 2, 2, 2, 2
2, 3, 2, 2, 2, 2, 2, 2
2, 3, 2, 2, 2, 2, 2, 2
2, 3, 2, 2, 2, 2, 2, 2
2, 3, 2, 2, 2, 2, 2, 2
2, 3, 2, 2, 2, 2, 2, 2
2, 3, 2, 2, 2, 2, 2, 2
2, 3, 2, 2, 2, 2, 2, 2
2, 3, 4, 5, 6, 7, 8, 9
このプログラムはSIMD化できないんですね。
じゃあSIMD化が常に悪かというと、そうでもありません。
今度は書き込む場所を v[i + 1] から v[i - 1] にしてみましょう。
fn f(v: &mut [f32]) {
for i in 1..v.len() {
v[i - 1] = v[i] + 1.0;
}
}
これは結果はこうなります。
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 1
この関数をSIMD化してみましょう。
fn f2(v: &mut [f32]) {
use std::arch::x86_64::{_mm256_add_ps, _mm256_loadu_ps, _mm256_set1_ps, _mm256_storeu_ps};
unsafe {
let limit = v.len();
let ones = _mm256_set1_ps(1.0);
let ptr = v.as_mut_ptr();
for i in (1..(limit - (SIZE - 1))).step_by(SIZE) {
let data = _mm256_loadu_ps(ptr.offset(i as isize));
let ret = _mm256_add_ps(data, ones);
_mm256_storeu_ps(ptr.offset((i - 1) as isize), ret);
}
for i in ((limit - (SIZE - 1)) / SIZE * SIZE)..limit {
v[i - 1] = v[i] + 1.0;
}
}
}
この結果は変わらずこうなります。
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 2
2, 2, 2, 2, 2, 2, 2, 1
こっちの場合だとSIMD化は合法な変換となりました。 SIMD化ができればプログラムは速くなるので、書き換えられる場合書き換えられない場合を見極められると嬉しいですよね。
依存関係基本のキ
最初のプログラムを再掲します。
let mut v = 1;
v += 1;
println!("{}", v);
これの2行目と3行目を入れ替えるとプログラムの結果が変わるのでした。 それぞれ何をしているか少し抽象的に書くとこうなります。
- 2行目: 変数
vに値を書き込んでいる - 3行目: 変数
vから値を呼び出している
同じ変数 に対する 書き込み のあとに 読み出し です。一般にこれらの順番を入れ替えるとプログラムが壊れるのです。また、入れ替えたあとに元に戻すことを考えると、読み出しのあとに書き込みをしてもプログラムが壊れるのが分かるかと思います。さらに、書き込み同士でも順番を入れ替えるとプログラムの結果が変わります。
let mut v = 1;
v = 0;
v = 2;
println!("{}", v);
この2行目と3行目を入れ替えると結果が変わりますね。
このように同じ変数に対する読み書きは順番を入れ替えるとプログラムの結果が変わってしまいます。このことをデータの 依存関係 （Dependency）があると言います。先程紹介した読み出し-書き込み、書き込み-読み出し、書き込み-書き込みの依存関係にはそれぞれ名前がついています。
- 読み出し-書き込み: フロー依存 (flow dependence)
- 書き込み-読み出し: 逆依存 (anti-dependence)
- 書き込み-書き込み: 出力依存 (output dependence)
なお、読み出し-読み出しは入れ替えても結果が変らないので気にしないことにします。 一応これにも 入力依存 (input dependence) という名前がついていて、入力依存のあるプログラム同士を近くに配置するとレジスタやキャッシュの再利用が捗るなどの使い途はあるのですが今回の主眼ではないので扱いません。
さて、プログラムの1行目を $\mathit{L1}$ 、 2行目を $\mathit{L2}$ などと表記することにすると、 $\mathit{LN}$ から $\mathit{LM}$ へフロー依存関係があることを、もったいぶって以下のように書きます。
\[ \mathit{LN}\ \delta{}^f\ \mathit{LM} \]
他にも逆、出力依存はそれぞれ $\mathit{LN}\ \delta{}^a\ \mathit{LM}$ 、 $\mathit{LN}\ \delta{}^o\ \mathit{LM}$ と書きます。あとどの種類でもいいので依存があることを $\delta^*$ と書いたりもします。
最初のプログラムの例でいうと $\mathit{L1}\ \delta^f\ \mathit{L2}$ 、 $\mathit{L2}\ \delta^a\ \mathit{L2}$ （v += 1 は v = v + 1 なので）、 $\mathit{L2}\ \delta^f\ \mathit{L3}$ ですね。フロー依存と逆依存から構成されています。
記法を紹介しましたが以後も「どこどこからここそこにフロー依存がある」と説明するので特に使う予定はありません。ホワイトボードなんかに書くときに使って下さい。あと論文読んでるとたまに出てきます。
偽りの依存とSSA
さて、3つの依存のうち、フロー依存が真の依存、それ以外は偽りの依存と言われています。 出力依存があるプログラムを思い出してみましょう。
let mut v = 1;
v = 0;
v = 2;
println!("{}", v);
このプログラムは簡単な書き換えで出力依存が消えます。
let v1 = 1;
let v2 = 0;
let v3 = 2;
println!("{}", v3);
同様に逆依存も変数名のつけかえで依存関係を消せます。 もう少し言うと、変数の上書きを禁止して、上書く場合は新しい変数を導入することにすると、変数の書き換えがそもそもなくなるので逆や出力の依存関係が発生しなくなります。
さてこの変換、便利なのであらゆるプログラムに適用したいのですが1つ障害があります。
if やループなど制御フローの絡むプログラムだと詰んでしまいます。
fn f(cond: bool) -> i32 {
let mut v = 0;
if cond {
v = 1;
} else {
v -= 1;
}
return v;
}
fn sum(n: i32) -> i32 {
let mut i = 0;
let mut sum = 0;
loop {
if i < n {
break;
}
i += 1;
sum += i;
}
return sum;
}
これらはプログラムのある地点に至るまでに通った経路がその時々で変わるのでバシっと「この値を使う」と言えません。
そこで「こちらから来たときはこの値、そちらから来たときはその値」を取る演算子 φ を導入してあげます。
φ 演算子を使うと先程のプログラムも変数の書き換えがないように変換できます。
fn f(cond: bool) -> i32 {
let v1 = 0;
if cond {
let v2 = 1;
} else {
let v3 = v1 - 1;
}
// 「変数名」と「変数が定義された場所」と「どの経路を通ってきたか」が簡単に対応づくので
// 「then節から来たときはv2、else節から来たときはv3」の略記として以下を採用する
let v4 = φ(v2, v3);
return v4;
}
fn sum(n: i32) -> i32 {
let i1 = 0;
let sum1 = 0;
loop {
let i2 = φ(i1, i3);
let sum2 = φ(sum1, sum3);
if i2 < n {
break;
}
let i3 = i2 + 1;
let sum3 = sum2 + i3;
}
return sum3;
}
こうしてできあがった「変数の上書き禁止」、つまり1変数あたり1代入のプログラムは 静的単一代入 （Static Single Assignment、SSA）形式と呼ばれます。
SSAは3種類あった依存関係を1種類にまで落としているのでプログラムの諸々解析がやりやすく、LLVMやGCCなど多くのコンパイラで内部表現として使われています。 LLVMを使っている人には馴染みのある形式でしょう。
SSAの限界
前節のストーリーのまま進めばよかったのですが、残念ながらSSAには限界があります。 ポインタが来ると無力です。LLVMでもスタックやヒープの値は書き換え可能ですよね。 さらに配列とループが来ると死にます。例えばQuick Sortのプログラムを思い浮かべてみて下さい。これの依存関係を実行前に事前に除去するのは無理そうですね。 一応SSAを拡張して配列も扱えるようにする話もなくはないみたいですが、大人しく諦めた方がよさそうです。
SSAで配列を扱うのは諦めましたが、これは一般の場合で扱うのが難しいだけです。 条件が揃えば配列とループを使うコードでも依存関係の分析ができます。 それをやっていきましょうというのが今回の主題です。
ループの正規化
今回扱うのがループと配列ということが決まったので、ループを扱いやすくしておきましょう。 ループの繰り返しに使う変数（誘導変数 （induction variable））ってループ展開の例で出てきたように8つ飛ばしだったりします。
const SIZE: usize = 8;
for i in (1..(limit - (SIZE - 1))).step_by(SIZE) {
v[i - 1] = v[i] + 1.0;
v[i] = v[i + 1] + 1.0;
v[i + 1] = v[i + 2] + 1.0;
v[i + 2] = v[i + 3] + 1.0;
v[i + 3] = v[i + 4] + 1.0;
v[i + 4] = v[i + 5] + 1.0;
v[i + 5] = v[i + 6] + 1.0;
v[i + 6] = v[i + 7] + 1.0;
}
これをループの回転に使う変数とループ内で使う変数に分離します。 ループの回転に使う変数の方は0から始まって1刻みで進むようにします。 要するに「今ループのn回目」というのを表現する変数です。 これをループの 正規誘導変数 （normalized induction variable）といいます。 元の誘導変数は正規誘導変数から計算します。
const SIZE: usize = 8;
// 正規誘導変数 ni を使って0から1刻みでループを回す
for ni in 0..(limit - (SIZE - 1) - 1) / SIZE {
// 元の誘導変数 i は正規誘導変数 ni から計算する
let i = SIZE * ni + 1;
v[i - 1] = v[i] + 1.0;
v[i] = v[i + 1] + 1.0;
v[i + 1] = v[i + 2] + 1.0;
v[i + 2] = v[i + 3] + 1.0;
v[i + 3] = v[i + 4] + 1.0;
v[i + 4] = v[i + 5] + 1.0;
v[i + 5] = v[i + 6] + 1.0;
v[i + 6] = v[i + 7] + 1.0;
}
ループの正規形が得られました。 そして今回扱う対象ですが、ループの 反復空間 （iteration space）が正規誘導変数のアフィン式で書けるようなループのみ扱うことにします。以下に正規誘導変数のアフィン式で書ける反復空間、書けない反復空間の例を挙げます。
例: (i を正規誘導変数、N を適当な定数とする)
- OK:
0 < i,i < N(=i > 0,-1 * i + N > 0) - OK:
1 < i,4 * i + 1 < N(=i - 1 > 0,-4 * i + (-1 + N) > 0) - NG:
0 < i,i * i < N
配列を舐める素直なループは大抵該当しますが、 loop でグルグル回って特定の条件を満たしたら break するような変則的なループだと該当しません。
依存関係の分析
準備の万端が整ったので依存性の解析をしていきましょう。
まずはシンプルなループについてです。
fn f(v: &mut [f32]) {
for i in 0..(v.len() - 1) {
v[i + 1] = v[i] + 1.0;
}
}
このループを正規化します。といってもほぼ正規化されてるのであんまり変化はないです。
fn f(v: &mut [f32]) {
for ni in 0..(v.len() - 1) {
let i = ni;
v[i + 1] = v[i] + 1.0;
}
}
このループの繰り返しの間での依存関係を求めたいです。 ループ内では1つ配列から1回読み出して1回書き込んでるので話は簡単ですね。 「読み出しと書き込みで同じ場所を触るのはいつか」という問いを立てればよさそうです。
もうちょっと言うと「$i_1$ 番目のループでの読み出しと $i_2$ 番目のループでの書き込みが一致する条件」を問えばよいです。読み出しはインデックスに i 、書き込みはインデックスに i + 1 を使っていて、 let i = ni なので以下の式が立ちます。
\[ i_1 = i_2 + 1 \]
この式から書き込みと読み出しの関係を計算します。配列の要素に書き込んだあと、ループが何回転回ったら読み込むかを計算すればよさそうです。この値を 依存距離（dependence distance）といいます。
\[ i_1 - i_2 = 1 \]
1と出ました。書き出した値を次のループで読み出しているということです。 つまり、 ループの繰り返しの間にフロー依存があります。 一般に依存距離が正ならループの繰り返し間にフロー依存があります。 フロー依存のあるプログラムをSIMD化した（書き込む前に読み出した値で計算した）のでプログラムが壊れた訳です。
さて、では書き込む要素を v[i - 1] にしたバージョンでやってみましょう。
fn f(v: &mut [f32]) {
for i in 1..v.len() {
v[i - 1] = v[i] + 1.0;
}
}
これもループを正規化します。
fn f(v: &mut [f32]) {
for ni in 0..v.len() - 1 {
let i = ni + 1;
v[i - 1] = v[i] + 1.0;
}
}
ここから色々あって次の式が立ちます。
\[ i_1 + 1 = i_2 + 1 - 1 \]
依存距離を計算します。
\[ i_1 - i_2 = -1 \]
今度は-1が出ました。一般に依存距離が負ならループの繰り返し間に逆依存があります。 逆依存（読み出したあとに書き込まれる依存）のあるプログラムで書き込む前に読み出した値を使って計算しても特に問題はないのでプログラムが壊れなかった訳です。
これでループのあるプログラムでも特定の条件を満たせば依存関係を分析できましたし、SIMD化もできるようになりました。
依存関係の分析の一般化
先程の依存関係の分析はかなりシンプルなもののみ扱っていました。 例えば行列の乗算なんかを扱おうとすると一般化が必要です。 具体的には
- ループはネストする
- 正規誘導変数が複数になるのでそれらのベクトルを考えることになる
- 反復空間が多次元化するので正規誘導変数ベクトルのアフィン式 $\mathbf{A}\mathbf{i} + \mathbf{b} > \mathbf{0}$ を考えることになる
- 依存距離がベクトル化する（距離ベクトル、distance vector）
- 配列が多次元化する
- 配列の添字も多次元化するのでベクトルにすることになる
- 依存関係の式もベクトル化するので行列とのかけ算やらベクトルの大小関係やらを考えることになる
依存距離がベクトル化することで依存関係がちょっと複雑化します。 「一番外側のループでは依存関係はないけど2番目ではフロー依存があってあって一番内側ではなくなって…」のようになります。 そうすると外側はスレッド並列化できますし、内側はSIMD並列化できますが、真ん中のループはいじれないなんかの「部分的に変換可能な箇所がある」という結果が出たりします。 都合のいい依存関係でなかった場合はループの順番を入れ替えることで都合のいい依存関係にするような変換もあります。
これらは落ち着いて考えればどうにかなるものが多いのですが、ちょっと長くなってしまうので割愛します。参考文献を参照して下さい。
まとめ
データの依存関係について整理しました。 そしてフロー依存以外はSSA形式に変換することで取り除けることも確認しました。 しかし配列とループを扱うときはSSAだけでは対処できないのでループの正規化や正規誘導変数などを用いて依存関係を分析できることを紹介しました。 さらに今回紹介した簡単な例だけでなく一般化した手法が存在することも紹介しました。
今回の記事は日本語で依存関係の分析を扱った資料ってないよなーと思って書き始めたのですが、よく調べたら中田先生のコンパイラの構成と最適化に載ってました。 ちゃんと読んでないことがバレますね。
参考文献
- M. Wolfe, High performance compilers for parallel computing
- 中田育男、コンパイラの構成と最適化
- R. Allen, K. Kennedy, Optimizing compilers for modern architectures