# Producing Wrong Data Without Doing Anything Obviously Wrong! > [!abstract] 概要 > 本論文は驚くべき結果を示す。一見無害な実験設定の側面を変えるだけで、システム研究者は実験から誤った結論を導きうる。実験設定の無害に見える側面が、評価に大きなバイアスをもたらしていることがある。この現象は、自然科学・社会科学では測定バイアス(measurement bias)と呼ばれる。 > 我々の結果は、測定バイアスがコンピュータシステムの評価において大きく、かつ普遍的であることを示す。大きいとは、測定バイアスが性能分析における効果を過大評価させたり、誤った結論さえ導いたりしうることを指す。普遍的とは、試したすべてのアーキテクチャ(Pentium 4、Core 2、m5 O3CPU)、試した両方のコンパイラ(gcc と Intel の C コンパイラ)、SPEC CPU2006 の C プログラムの大半で測定バイアスが生じることを指す。したがって、測定バイアスを無視することはできない。それにもかかわらず、ASPLOS、PACT、PLDI、CGO の最近の論文 133 本の文献調査で、実験結果を持つ論文のいずれも測定バイアスを十分に考慮していないことがわかった。 > 他の科学における同様の問題とその解決に着想を得て、2 つの方法を述べ実証する。測定バイアスを検知する方法(因果分析)と、回避する方法(実験設定のランダム化)である。 ## 論文情報 - 著者: [[Todd Mytkowicz]]、[[Amer Diwan]](コロラド大学ボルダー校)、[[Matthias Hauswirth]](ルガーノ大学)、[[Peter F. Sweeney]]([[IBM Research]])。 - 掲載: ASPLOS 2009(2009 年 3 月 7〜11 日、ワシントン DC)。SIGPLAN Notices に収録され、pp. 265-276。 - 分野: 計算機システムの性能評価の方法論。 ## 概要 コンパイラ最適化の効果を測る通常の実験は、プログラムの実行時間を測って最適化の有無を比べる。本論文は、実験設定の一部である UNIX 環境変数のサイズとリンク順序を変えるだけで、gcc の O3 が O2 に対して速く見えたり遅く見えたりすることを実測で示す。これらは測定バイアスであり、大きく(結論を反転させる)、普遍的で(3 種のマイクロアーキテクチャ・2 種のコンパイラ・SPEC CPU2006 の大半で生じる)、予測できない。文献調査は、133 本のうち測定バイアスを十分に扱う論文がないことを示す。対策として、実験設定のランダム化(回避)と因果分析(検知)を提案し、SPEC CPU2006 の perlbench で O3 の高速化率が 1.007 ± 0.003 と推定できることを示す。 ## 問題設定 - システム研究者は、ボトルネックの特定と最適化の効果確認に実験を使う。実験が偏っていれば、無意味な箇所に時間を費やし、効果のない最適化を有益と結論しうる。 - 比較対象の 2 つのシステム S1・S2 に対し、実験設定が一方を有利にする場合に測定バイアスが生じる。本論文は、測定バイアスを生む要因として次の 2 つを取り上げる。いずれもメモリ配置に影響するため、性能に効くことが既知である。 - UNIX 環境サイズ: 環境変数を格納する総バイト数。環境はコールスタックより前にメモリへ載るため、スタックの開始位置、ひいてはスタック上の局所変数のアラインメントを変える。 - リンク順序: リンカに渡す `.o` ファイルの順序。コードとデータの配置を変える。 - 他にも要因は多数ある(室温が CPU クロックに影響して、メモリ集約型か演算集約型かで効率が変わる例など)。ベンチマークの選択自体もバイアスになる。目的は要因の網羅ではなく、バイアスが存在することの実証と、その扱い方の提示である。 - 問いは「gcc の O3 最適化は有益か」に固定する。O3 の優劣を判定することが目的ではなく、バイアスがどれだけ容易に結論を左右するかを示すための題材である。 ## 提案手法 本論文の中心は測定バイアスの実証と 2 つの対処法である。 ### 動機となるマイクロカーネル(§2) 3 つの静的変数へ 65,536 回加算するだけの C コード(最適化なし)の実行時間を、未使用の環境変数の長さを変えながら Core 2 で測る。平均 5 回、95% 信頼区間つきで、多くの点で約 33%、1 点では約 300% も実行時間が変わる。環境が呼び出しスタックより先にメモリへ載るため、環境サイズがスタック位置を動かし、局所変数のアラインメントが各種ハードウェア構造に対して変わるからである。 ![[wiki/sources/_attachments/2009__SIGPLAN__Producing-Wrong-Data-Without-Doing-Anything-Obviously-Wrong/fig01-microkernel-env-size.png]] *Figure 1: (a) マイクロカーネルの C コード。(b) 環境変数サイズが性能に与える影響。* ### 測定基盤(§3.2、3.3) - 測定は Pentium 4、Core 2 のワークステーション、シミュレータ m5(O3CPU モデル)で行う。Linux 上で PAPI によりハードウェア性能モニタを読む。計装は `LD_PRELOAD` で `__libc_start_main` を上書きする共有ライブラリ(inter-loper)に置き、再コンパイルなしで静的メモリ配置を変えず、測定オーバーヘッドを抑える。 - ベストプラクティスに従う。環境変数を実験対象以外は unset した最小環境で測り、低負荷のマシンとローカルディスクを使い、同じ実験を複数回繰り返し、スタック開始位置のランダム化(Core 2 の一部カーネル)を無効にし、2 組のハードウェアと(可能なら)シミュレータで測る。バイアスはこれらに従った上でも現れる。 - 測るのは O2 のサイクル数を O3 のサイクル数で割った値(以下、O3 の高速化率)である。1 を超えれば O3 が有益になる。 | 項目 | Core 2 | Pentium 4 | m5 O3CPU | |---|---|---|---| | OS | Linux 2.6.25 | Linux 2.4.21 | なし | | ツールチェーン | gcc 4.1.3、icc 10.1 | gcc 4.2.1 | gcc 4.1.0 | | 測定 | papi-3.5.1 / perfmon-2.8 | papi-3.0.8 / perfctr-5.2.16 | なし | | マイクロアーキテクチャ | Core | NetBurst | Alpha | | クロック | 2.4 GHz | 2.4 GHz | 1 GHz | | L1 | 32K 命令 + 32K データ | 12K 命令 + 8K データ | 32K 命令 + 64K データ | | L2 | 128K 統合 | 512K 統合 | 2M 統合 | *Table 2: 使用したマシンの構成(抜粋)。* ### ベンチマーク(§3.1) SPEC CPU2006 v1.0 の C プログラムのうち CINT 9 本(gcc、libquantum、perlbench、bzip2、h264ref、mcf、gobmk、hmmer、sjeng)と CFP 3 本(sphinx3、milc、lbm)の計 12 本を使う。言語間で最適化レベルが比べられないため非 C は除く。図の作成に各ベンチマークを 5,940 回実行し、入力は `train` を使う。空の環境・既定のリンク順序での平均実行時間は最短の gcc が 1.3 秒(約 31 億サイクル)、最長の sjeng が 175 秒(約 4,199 億サイクル)で、最長のものはデータ生成に 12 日かかった。 ### 対処法 1: 実験設定のランダム化(§7.1) バイアスを生むと分かっている設定パラメータを変えて多数の実験設定を作り、比較する 2 システムをすべての設定で測る。2 つの分布を得て、t 検定などの統計的手法で S1 が S2 より良いかを判定する。ベンチマークを増やして多様な設定をそろえる方法と組み合わせる。 ### 対処法 2: 因果分析(§7.2) 結論「X が Y を引き起こした」を検証する手順である。(1) 介入: X に影響し他への影響が最小の操作を設計する。(2) 測定: 介入したシステムを測る。(3) 確認: Y が X の因果から期待される通りに変わったか確かめる。実験のデータが偏っていたり推論が誤っていたりして結論が偽になっていないかを検知する。バイアスのないデータを得る手法ではなく、バイアスがあっても結論が妥当かを確かめる手法である。 ## 新規性 - 性能評価で実験設定(環境変数サイズ、リンク順序)が結論を反転させうることを、複数のマイクロアーキテクチャ・複数のコンパイラ・シミュレータの実測で示した点。 - 測定バイアスが大きく、普遍的で、予測できないという 3 点を実験で切り分けた点。 - 学会 4 種の 133 本の文献調査で、実験手法の欠落を定量化した点。 - 自然科学・社会科学の対処法(ランダム化と因果分析)を、システムの性能評価へ直接持ち込んだ点。 - 関連研究との違い: Korn+、Maxwell+、Moore はパフォーマンスカウンタの精度をマイクロベンチマークで調べるのに対し、本論文は実プログラムで誤った性能分析を生む要因を調べる。Georges+ や Kalibera+ は統計的な厳密さを主張するが、実験設定自体の偏りは扱わない。Tsafrir+ の input shaking、Blackburn+ の複数ヒープサイズ、Alameldeen と Wood のキャッシュミス遅延の変動導入は、設定を変える追加手段として位置づけられる。 ## 実験設定 - 対象: gcc の O3(O2 に追加される最適化)の効果。指標は O2 と O3 のサイクル数の比。 - 変える軸: (i) UNIX 環境サイズ(0 バイトの空環境から 63 バイトずつ、最大 4,096 バイトまで)、(ii) リンク順序(既定、アルファベット順、乱数)。perlbench のリンク順序は 33 通り。 - 各点は O2・O3 を各 5 回実行した平均で、95% 信頼区間を付ける。 - 環境: Core 2(既定)、Pentium 4(Pentium 4 では CFP の 3 本は測っていない)、m5 O3CPU(小さな入力)。Intel の C コンパイラでも同じ実験を繰り返す。 - ベンチマーク: SPEC CPU2006 の C プログラム 12 本。 | 種別 | ベンチマーク | 平均サイクル数 | 秒 | |---|---|---|---| | CINT | gcc | 3,142,640,332 | 1.3 | | CINT | libquantum | 7,690,324,238 | 3.2 | | CINT | perlbench | 12,752,930,486 | 5.3 | | CINT | bzip2 | 13,840,302,589 | 5.8 | | CINT | h264ref | 46,785,473,888 | 19.5 | | CINT | mcf | 59,250,579,566 | 25.0 | | CINT | gobmk | 180,491,870,344 | 75.2 | | CINT | hmmer | 246,974,548,791 | 102.9 | | CINT | sjeng | 419,892,937,630 | 175.0 | | CFP | sphinx3 | 35,238,100,682 | 14.7 | | CFP | milc | 57,414,647,507 | 23.9 | | CFP | lbm | 232,213,767,693 | 96.8 | *Table 1: 使用したベンチマーク(空環境・既定リンク順序、15 回平均)。* ## 実験結果 ### 測定バイアスは大きく普遍的である(§4) - リンク順序(§4.1): perlbench の 33 通りで O3 の高速化率は 0.92〜1.10 に振れ、順序次第で O3 が高速化にも低速化にもなる。ランダムな順序が既定順序とアルファベット順の両方より速い場合もあり、各点は繰り返しても再現する。12 本中 libquantum・perlbench・bzip2・sphinx・lbm の 5 本で violin プロットが 1.0 をまたぎ、結論が食い違いうる。perlbench の最大と最小の差は 0.15 で、7% の低速化にも 8% の高速化にも見える。全ベンチマークの中央値の差は Core 2 で 0.02、Pentium 4 で 0.08 である。m5 でも bzip2 で 0.8〜1.1 に振れた。 ![[wiki/sources/_attachments/2009__SIGPLAN__Producing-Wrong-Data-Without-Doing-Anything-Obviously-Wrong/fig02-link-order.png]] *Figure 2: リンク順序が Core 2 上の O3 の高速化率に与える影響。(a) perlbench、(b) 全ベンチマーク。* - リンク順序の原因(§4.1.2): m5 で bzip2 を調べると、ホットループが 1 本のキャッシュラインに収まるかどうかが性能を決めていた(収まれば命令キューにラッチされ i-cache アクセスが不要になる)。Core 2 にはループストリーム検出器(LSD)という同様の機能があるが、Intel が詳細を公開せず、LSD を直接測るカウンタもなく、無効化もできないため、確認できない。 - UNIX 環境サイズ(§4.2): perlbench で高速化率は 0.91〜1.07 に振れ、環境サイズの増加に対して単調に増減しないので予測できない。全体では libquantum・perlbench・sphinx・lbm の 4 本が 1.0 をまたぐ。最大は lbm の 0.88〜1.09(12% の低速化にも 9% の高速化にも見える)。最大と最小の差の中央値は Core 2 で 0.01、Pentium 4 で 0.04 である。Pentium 4 では CINT 9 本のうち 6 本が 1.0 をまたぐ。 ![[wiki/sources/_attachments/2009__SIGPLAN__Producing-Wrong-Data-Without-Doing-Anything-Obviously-Wrong/fig03-env-size.png]] *Figure 3: UNIX 環境サイズが Core 2 上の O3 の高速化率に与える影響。(a) perlbench、(b) 全ベンチマーク。* - 環境サイズの原因(§4.2.2): 第 1 に、環境サイズがスタックの開始アドレスを変え、スタック変数のアラインメントが変わる。スタックの開始位置を固定すると、perlbench 以外のすべてのベンチマークで環境サイズによる差が消えた。第 2 に、perlbench は起動時に環境をヒープへコピーするため、ヒープ割り当て構造のアラインメントも変わる。ヒープ開始位置を固定すると影響が大きく減り、残りはスタック位置による。さらに perlbench のイベントを全 340 種収集すると、42 種が 25% 超変わり、`LOAD_BLOCK:OVERLAP_STORE`(先行ストアなどで待たされたロードの数)が 10 倍に増えた。ハードウェアが保守的にロードとストアの重なりを判定しているため、アラインメントの変化が重なりの数を変えた可能性が高い。ただし PEBS がこのイベントを対象とせず、確定はできない。 - Intel の C コンパイラ(§4.3): gcc がハードウェアのアラインメント選好を考慮しないためかと予想して icc で繰り返したが、バイアスは残った。リンク順序では 10 本(gcc は 6 本)が 1.0 をまたぎ、violin の高さの中央値は 0.03(gcc は 0.02)である。環境サイズでは 6 本(gcc は 4 本)が 1.0 をまたぎ、高さの中央値は 0.006(gcc は 0.01)である。 ![[wiki/sources/_attachments/2009__SIGPLAN__Producing-Wrong-Data-Without-Doing-Anything-Obviously-Wrong/fig04-icc-bias.png]] *Figure 4: Core 2 上の Intel C コンパイラでのバイアス。(a) リンク順序、(b) UNIX 環境サイズ。* ### 測定バイアスは予測できない(§5) - perlbench で、環境サイズを増やしても O3 の高速化率は単調に変わらない。 - perlbench のリンク順序でも環境サイズでも、Pentium 4 での最良の設定と Core 2 での最良の設定は別である(図 5 の丸印)。ソフトウェアをリンク済みで配布するベンダは、特定のマシンで調整した順序が別のマシンで最良になる保証を持てない。 ![[wiki/sources/_attachments/2009__SIGPLAN__Producing-Wrong-Data-Without-Doing-Anything-Obviously-Wrong/fig05-perlbench-machines.png]] *Figure 5: perlbench の測定バイアス。(a) リンク順序、(b) UNIX 環境サイズ。横軸は Pentium 4、縦軸は Core 2 の O2 のサイクル数。* ### 文献調査(§6) - 対象は ASPLOS 2008、PACT 2007、PLDI 2007、CGO 2007 の計 133 本。うち 88 本が実験手法と評価の節を持ち、以降はこの 88 本を扱う。判断に迷う場合は論文に有利に解釈した。 - 36 本がシミュレーションを使う。§4.1 のとおりシミュレータでもバイアスは生じる。 - 報告された高速化率の中央値は 10% で、§4 のバイアスで隠れうる大きさである。 - 環境サイズやリンク順序への言及はどの論文にもない。83 本は複数のベンチマークまたは入力(平均 10.6 ± 1.8 本)を使うが、多様性が十分でなければバイアスは相殺されない。 ### 対処法の評価(§7) - ベンチマークを増やす方法(§7.1.1): 12 本のスイートで 66 通りのメモリ配置の設定を作り、設定ごとに全体の平均高速化率を求めると、設定間で 7% の変動が残る(図 6)。スイートの規模ではなく多様性が肝心であり、SPEC CPU2006 の C プログラムでは多様性が足りない。 - ランダム化(§7.1.2): perlbench で 22 通りのリンク順序 × 22 通りの環境サイズ = 484 設定を作り、各 3 回実行して O2 と O3 の分布を t 検定で比べると、95% 信頼区間で高速化率は 1.007 ± 0.003 と推定され、O3 は僅かに速い(図 7)。設定の変え方が不十分なら別のバイアスが残りうる。 - 因果分析(§7.2): 「環境サイズがスタック開始位置を変え、それが O3 の高速化率を変える」という結論に対し、(1) スタックの開始アドレスを固定する介入、(2) 環境サイズを 4,096 バイトまで変えて O3 の高速化率を計算、(3) 環境サイズが高速化率に影響しないことの確認、の手順で検証した。perlbench 以外のすべてのベンチマークで結論が確認され、perlbench では結論が棄却されて別の結論(ヒープ位置の影響)を立てて確認した。 ![[wiki/sources/_attachments/2009__SIGPLAN__Producing-Wrong-Data-Without-Doing-Anything-Obviously-Wrong/fig06-07-randomization.png]] *Figure 6: 実験設定を変えたときの O3 の高速化率の分布。Figure 7: perlbench の O3 の高速化率をランダム化で求める。95% 信頼区間で 1.007 ± 0.003。* ## 考察 - 測定バイアスは、環境設定・リンク順序に限らず、問題領域ごとに固有の要因を持つ。除去できる種類(ループのアラインメントを揃えるなど)はあっても、すべては除去できない。ランダム化と因果分析は過渡的な手段ではなく、恒久的な手段である。 - ソフトウェア側の要請: (1) 多様なベンチマークを整備する(DaCapo のような取り組みを他の領域・言語へ広げる)。(2) 実験設定をランダム化する要因の目録を作り、ランダムな設定を自動生成するツールを作る。 - ハードウェア側の要請: (1) 内部の詳細の公開(OpenSPARC のような例)。(2) 主要部品のイベントを取るカウンタ、機能を無効化する手段、イベントを命令へ結びつける仕組み(PEBS は Intel のマニュアルの Table 18.16 で 9 種のイベントに限られる)。 - 結論のたとえ: 小さな町だけの世論調査で全国選挙を予測しないのと同様に、少数の設定と少数のベンチマークで最適化の効果を予測してはならない。 - 医学の類推: 引用の多い臨床研究 49 本のうち、後続研究が 16% を反証し、16% が過大な主張だった(Ioannidis)。後続研究はより多くの被験者とランダム化試行を使い、バイアスが小さかったと思われる。 ## 強み / 弱点・課題 - 強み - 要因の挙動を測る対象が実プログラム(SPEC CPU2006)と複数のアーキテクチャ・コンパイラにわたり、バイアスの普遍性が説得的である。 - 原因を 2 段階(高水準: スタック位置とアラインメント、低水準: ロードとストアの重なり)で調べ、介入で仮説を検証している。 - 対処法が他分野の標準手法(ランダム化、因果分析)に基づき、適用手順と結果例(1.007 ± 0.003)を示す。 - 弱点・課題 - 要因は 2 つに限られ、他の要因(室温、ベンチマークの選択など)は例示にとどまり、実験で確かめたのはこの 2 つだけである。 - ハードウェアの詳細が非公開のため、低水準の原因(LSD、LOAD_BLOCK の重なり)を確定できず、仮説の範囲にとどまる。 - ランダム化はどの要因をどの範囲で変えれば十分かの基準を与えず、変え方が不十分なら別のバイアスが残りうると著者自身が述べる。 - 実験は所要時間の都合で train 入力と単一スレッドのプログラムに限られ、m5 では入力をさらに小さくしている。