LINPACK

LINPACK benchmarks
作者	ジャック・ドンガラ、ジム・バンチ、クリーブ・モラー、ギルバート・スチュアート
初版	1979年
公式サイト	www.netlib.org/benchmark/performance.ps
	テンプレートを表示

LINPACK
作者	ジャック・ドンガラ、ジム・バンチ、クリーブ・モラー、ギルバート・スチュアート
プログラミング; 言語	FORTRAN
種別	ライブラリ
公式サイト	www.netlib.org/linpack/
	テンプレートを表示

LINPACK（リンパック）は、主として線型代数の数値計算を目的とした、行列およびベクトルの演算が実装されているライブラリである。

概要

MINPACK、EISPACK と同様、米国アルゴンヌ国立研究所でFORTRANライブラリとして開発された。実際に開発を行ったのはジャック・ドンガラ、ジム・バンチ、クリーブ・モラー、ギルバート・スチュアートである。1970年代から1980年代初期のスーパーコンピュータを対象として設計され^[1]^[2]、その後より洗練されたライブラリLAPACKに取って代わられた。

LINPACK は BLAS（Basic Linear Algebra Subprograms、基本線形代数サブプログラム群）ライブラリを使ってベクトル演算や行列演算を行う。

後述するLINPACKベンチマークは、LINPACKのユーザーズマニュアルの一部として公開されたのが最初である。

ベンチマーク

LINPACK ベンチマークは LINPACK に基づいたベンチマークプログラムで、システムの浮動小数点演算性能を評価する。ジャック・ドンガラが考案したもので、理学・工学で一般的な n×n の線型方程式系^[3] Ax = b を解く速度を測定する。このベンチマークの最新版はTOP500で世界の高速なコンピュータの性能値としてランキングに使用されている^[4]。

コンピュータが実世界の問題を解く性能の近似値を得ることを目的としている。しかし、1つの測定値でコンピュータシステムのあらゆる性能を代表させることは不可能であり、あくまでも1つの単純化である。それでも、メーカーが提供するピーク性能値に対してLINPACKベンチマークがよい補正を提供している。ピーク性能とは、そのコンピュータが理論上達成しうる最高性能であり、クロック周波数、1秒間の命令サイクル数、1サイクルで実行可能な演算回数などから計算される。実際の性能は常にピーク性能よりも低い^[5]。コンピュータの性能は様々な要素が相互に絡み合った複雑な問題である。LINPACKベンチマークで測定するのは、64ビット浮動小数点演算（通常、加算と乗算）の1秒あたりの実行回数（FLOPS）である。しかし、実アプリケーションを実行したときの性能は、LINPACKベンチマークを適切に設定して測定したときの最高性能よりずっと低くなる可能性が高い^[6]。

歴史

LINPACKベンチマークは1979年、LINPACKのユーザーズマニュアルの付録として公開されたのが最初である^[7]。LINPACKパッケージを使って問題を解く際にかかる時間をユーザーが推定する手がかりを与えることを目的として設計された。そのため、当初は大きさ100の行列問題を23種類用意していた。大きさは当時のメモリ容量を考慮して選択された。-1 から 1 の範囲内の浮動小数点数を10000個、無作為に生成し密係数行列を作る。そして、部分ピボット選択によるLU分解を使用する。その後、行列の大きさを300や1000にしたり、制限を緩めるなどして、行列やベクトルの演算を実装するようになったハードウェアアーキテクチャによる最適化を役立てられるようにしていった^[8]。オーダー1000の大きさの問題の場合、そのベンチマークを LINPACK 1000 と呼び、問題を解くアルゴリズムを修正可能である^[5]。1991年には任意の大きさの問題を解くベンチマークが登場した^[9]。これでスーパーコンピュータの極限性能に近い値を得られるようになり、その2年後にTOP500リストが公開されるようになった。

具体的なベンチマーク

LINPACK 100

1979年、LINPACKのユーザーズマニュアル^[10]で公表されたオリジナルのベンチマークにほぼ近い。部分ピボット選択によるガウスの消去法で問題を解き、2/3n³ + 2n² 回の浮動小数点演算を行う。n は 100 で、問題を定義する行列 A の次数である。サイズが小さく、ソフトウェアの柔軟性が欠けていたため、多くの最新のコンピュータでは限界性能を引き出すことができない。しかし、計算中心のユーザープログラムの性能を見積もるのにはある程度役立つ^[5]。

LINPACK 1000

問題のサイズを大きくして行列の次数を1000とし、アルゴリズムを変更可能にしたため、コンピュータの限界に近い性能を引き出せるようになった。残っている制限は、相対精度を低くしないという点と、演算回数は 2/3n³ + 2n² 回 (n = 1000) だという点である^[5]。

HPLinpack

従来のベンチマークは並列コンピュータの性能測定には適していない^[11]。そこで、並列コンピュータ向きの新たなベンチマーク Linpack’s Highly Parallel Computing benchmark、または HPLinpack ベンチマークが考案された。HPLinpackではサイズ n をそのマシンでの最高性能を引き出せる値にまで大きくできる。演算回数は 2/3n³ + 2n² 回だがアルゴリズムは選択可能である。シュトラッセンのアルゴリズムは演算回数を減らしてしまうので使えない^[12]。精度は次の式が成り立つようになる必要がある。

{\lVert Ax-b\rVert  \over \lVert A\rVert \lVert x\rVert n\epsilon }\leq O(1)

ここで $\epsilon$ はそのマシンの精度、n は問題のサイズ^[13]、 $\lVert \cdot \rVert$ は行列ノルム、 $O(1)$ はO-記法である。

各システムについて、次の数値を報告する^[5]。

R_max: そのマシンで最大の問題についての性能（GFLOPS）
N_max: そのマシンでの最大の問題のサイズ
N_1/2: Rmaxの半分の性能となるときの問題のサイズ
R_peak: そのマシンの理論上のピーク性能（GFLOPS）

これらの結果を使って、TOP500リストが年に2回更新される^[4]。

実装

前節ではベンチマークの基本的規則を解説している。それら規則に基づいたプログラムの実装は様々であり、FORTRANによる実装^[14]、C言語による実装^[15]、Javaによる実装^[16]などがある。

HPL

HPLはHPLinpackをC言語で実装したもので、本来はガイドラインとして書かれたものだが、TOP500でも広く使われている。なお、HPL以外のテクノロジーやパッケージを使うことに問題はない。HPLはn次の線型方程式系を生成し、部分ピボット選択によるLU分解でそれを解く。使用するにはMPIとBLASまたはVSIPLをインストールしておく必要がある^[17]。

大まかに言えば、このアルゴリズムには次のような特徴がある^[18]^[19]。

2次元ブロックで周期的データ配布を行う。
様々な深さの先読みを伴う right-looking 法の一種を使ったLU分解
再帰的パネル分解
パネルブロードキャストには6種類の方式がある。
帯域幅を低減するスワップ・ブロードキャスト・アルゴリズム
深さ1の先読みを伴う後退代入

批判

LINPACKベンチマークが成功した要因は、HPLinpackのスケーラビリティ^[20]、1つの数値を生成するため比較が容易であるという事実、それまでの測定値を蓄積したデータベースが存在すること^[21]が挙げられる。しかしリリース直後からLINPACKベンチマークには地道に最適化を施すプログラマだけが達成できる性能レベルを提供するもので、しかもその最適化はそのマシンでしか意味が無いという批判が浴びせられた^[22]。また、解いている問題は密係数行列の線型方程式系であり、それが科学技術計算全般を代表するものではないという批判もある^[23]。LINPACKベンチマークを推進してきたジャック・ドンガラは、CPUのピーク性能とCPU数だけが強調されており、帯域幅やネットワークへのストレスが十分でないと述べている^[24]。米国立スーパーコンピュータ応用研究所のトム・ダニングはLINPACKベンチマークについて「興味深い現象の1つだ。それを知っているほとんど全員がそれをあざ笑う。彼らはその限界を理解しているが、何年にも渡って我々はその値を使ってきたため、一種のマインドシェアが生じている」と述べた^[25]。ドンガラによれば、「システムの性能を様々な面から明らかにすることは重要」なので「TOP500の主催者はベンチマークの範囲を拡大する方法を積極的に模索している」という^[20]。TOP500のベンチマークの拡張について可能性の高いものとして、HPCチャレンジベンチマークがある^[26]。他に、倍精度浮動小数を要素とする行列の演算（特に乗算）を多用して、大規模な連立一次方程式を解くというベンチマークである点は共通だが、密ではなく疎な行列を対象とするHPCG（Conjugate Gradient、共役勾配法）や、そもそも数値計算ではない応用で近年重要性の増しているネットワーク構造（グラフ）の情報処理を対象としたGraph500などがある。

測定にかかる時間の問題

ジャック・ドンガラによれば、HPLinpackでよい性能値を得ようとすると測定に時間がかかるようになってきているという。2010年に開催された会議で、彼は「数年以内に」測定に2日半かかるようになるとの予想を行った^[27]。

脚注

^ Matlis, Jan (2005年5月30日). “Sidebar: The Linpack Benchmark”. ComputerWorld
^ Markoff, John (1991年9月22日). “Technology; Measuring How Fast Computers Really Are”. New York Times
^ ただし密係数行列。一般に、差分法や有限要素法などで解かれる大規模問題は、連結リストによって記述される参照の局所性の低い疎行列系であり、キャッシュメモリの恩恵をほとんど受けない。（つまりメモリバンド幅によって性能が決まる。）したがって、必ずしも実アプリケーションの性能を示すものではなく、指標の一つとして考えるのが妥当であろう。
^ ^a ^b “The Linpack Benchmark, TOP500 Supercomputing Sites”. 2012年1月11日閲覧。
^ ^a ^b ^c ^d ^e Dongarra, Jack J.; Luszczek, Piotr; Petitet, Antoine (2003), “The LINPACK Benchmark: past, present and future”, Concurrency and Computation: Practice and Experience (John Wiley & Sons, Ltd.): 803–820
^ Jack Dongarra interview by Sander Olson
^ Dongarra, J.J.; Moler, C.B.; Bunch, J.R.; Stewart, G.W. (1979), LINPACK: users' guide, SIAM
^ Dongarra, Jack (1988), “The LINPACK benchmark: An explanation”, Supercomputing (Springer Berlin/Heidelberg): 456–474
^ High Performance Linpack Benchmark 2012年1月10日閲覧。
^ LINPACK users' manual
^ Bailey, D.H.; Barszcz, E.; Barton, J.T.; Browning, D.S.; Carter, R.L.; Dagum, L.; Fatoohi, R.A.; Frederickson, P.O. et al. (1991), The NAS parallel benchmarks summary and preliminary results, “Supercomputing '91. Proceedings of the 1991 ACM/IEEE Conference”, Supercomputing: 158–165
^ “LINPACK FAQ - Can I use Strassen’s Method when doing the matrix multiples in the HPL benchmark or for the Top500 run?”. 2012年1月12日閲覧。
^ “LINPACK FAQ - To what accuracy must be the solution conform?”. 2012年1月12日閲覧。
^ “Linpack benchmark program in Fortran”. 2012年1月12日閲覧。
^ “Linpack benchmark program in C”. 2012年1月12日閲覧。
^ “Linpack benchmark program in Java”. 2012年1月12日閲覧。
^ “HPL - A Portable Implementation of the High-Performance Linpack Benchmark for Distributed-Memory Computers”. 2012年1月12日閲覧。
^ “HPL algorithm”. 2012年1月12日閲覧。
^ “HPL overview”. 2012年1月12日閲覧。
^ ^a ^b Meuer, Martin (2002年5月24日). “An interview with supercomputer legend Jack Dongarra”. 2012年1月13日閲覧。
^ Haigh, Thomas (2004), An interview with Jack J. Dongarra, "LINPACK is a benchmark that people often cite because there’s such a historical data base of information there, because it’s fairly easy to run, it’s fairly easy to understand, and it captures in some sense the best and worst of programming."
^ Hammond, Steven (1995), Beyond Machoflops: Getting MPPs Into the Production Environment
^ Gahvari, Hormozd; Hoemmen, Mark; Demmel, James; Yelick, Katherine (2006), “Benchmarking Sparse Matrix-Vector Multiply in Five Minutes”, SPEC Benchmark Workshop
^ Dongarra, Jack J. (2007), “The HPC Challenge Benchmark: A Candidate for Replacing Linpack in the Top500?”, SPEC Benchmark Workshop
^ Christopher Mims (2010年11月8日). “Why China's New Supercomputer Is Only Technically the World's Fastest”. 2011年9月22日閲覧。
^ Luszczek, Piotr; Dongarra, Jack J.; Koester, David; Rabenseifner, Rolf; Lucas, Bob; Kepner, Jeremy; Mccalpin, John; Bailey, David et al. (2005), Introduction to the HPC Challenge Benchmark Suite
^ Dongarra, Jack J. (2010), “LINPACK Benchmark with Time Limits on Multicore & GPU Based Accelerators”

外部リンク

LINPACK
BLAS
TOP500 Supercomputing Sites
Linpack Benchmark -- Java Version a web-based LINPACK benchmark
The HPL benchmark used in the TOP500

[1] Matlis, Jan (2005年5月30日). “Sidebar: The Linpack Benchmark”. ComputerWorld

[2] Markoff, John (1991年9月22日). “Technology; Measuring How Fast Computers Really Are”. New York Times

[3] ただし密係数行列。一般に、差分法や有限要素法などで解かれる大規模問題は、連結リストによって記述される参照の局所性の低い疎行列系であり、キャッシュメモリの恩恵をほとんど受けない。（つまりメモリバンド幅によって性能が決まる。）したがって、必ずしも実アプリケーションの性能を示すものではなく、指標の一つとして考えるのが妥当であろう。

[top500-4] “The Linpack Benchmark, TOP500 Supercomputing Sites”. 2012年1月11日閲覧。

[hplpaper-5] Dongarra, Jack J.; Luszczek, Piotr; Petitet, Antoine (2003), “The LINPACK Benchmark: past, present and future”, Concurrency and Computation: Practice and Experience (John Wiley & Sons, Ltd.): 803–820

[6] Jack Dongarra interview by Sander Olson

[7] Dongarra, J.J.; Moler, C.B.; Bunch, J.R.; Stewart, G.W. (1979), LINPACK: users' guide, SIAM

[8] Dongarra, Jack (1988), “The LINPACK benchmark: An explanation”, Supercomputing (Springer Berlin/Heidelberg): 456–474

[9] High Performance Linpack Benchmark 2012年1月10日閲覧。

[10] LINPACK users' manual

[11] Bailey, D.H.; Barszcz, E.; Barton, J.T.; Browning, D.S.; Carter, R.L.; Dagum, L.; Fatoohi, R.A.; Frederickson, P.O. et al. (1991), The NAS parallel benchmarks summary and preliminary results, “Supercomputing '91. Proceedings of the 1991 ACM/IEEE Conference”, Supercomputing: 158–165

[12] “LINPACK FAQ - Can I use Strassen’s Method when doing the matrix multiples in the HPL benchmark or for the Top500 run?”. 2012年1月12日閲覧。

[13] “LINPACK FAQ - To what accuracy must be the solution conform?”. 2012年1月12日閲覧。

[14] “Linpack benchmark program in Fortran”. 2012年1月12日閲覧。

[15] “Linpack benchmark program in C”. 2012年1月12日閲覧。

[16] “Linpack benchmark program in Java”. 2012年1月12日閲覧。

[17] “HPL - A Portable Implementation of the High-Performance Linpack Benchmark for Distributed-Memory Computers”. 2012年1月12日閲覧。

[18] “HPL algorithm”. 2012年1月12日閲覧。

[19] “HPL overview”. 2012年1月12日閲覧。

[DongIntel-20] Meuer, Martin (2002年5月24日). “An interview with supercomputer legend Jack Dongarra”. 2012年1月13日閲覧。

[21] Haigh, Thomas (2004), An interview with Jack J. Dongarra, "LINPACK is a benchmark that people often cite because there’s such a historical data base of information there, because it’s fairly easy to run, it’s fairly easy to understand, and it captures in some sense the best and worst of programming."

[22] Hammond, Steven (1995), Beyond Machoflops: Getting MPPs Into the Production Environment

[23] Gahvari, Hormozd; Hoemmen, Mark; Demmel, James; Yelick, Katherine (2006), “Benchmarking Sparse Matrix-Vector Multiply in Five Minutes”, SPEC Benchmark Workshop

[24] Dongarra, Jack J. (2007), “The HPC Challenge Benchmark: A Candidate for Replacing Linpack in the Top500?”, SPEC Benchmark Workshop

[25] Christopher Mims (2010年11月8日). “Why China's New Supercomputer Is Only Technically the World's Fastest”. 2011年9月22日閲覧。

[26] Luszczek, Piotr; Dongarra, Jack J.; Koester, David; Rabenseifner, Rolf; Lucas, Bob; Kepner, Jeremy; Mccalpin, John; Bailey, David et al. (2005), Introduction to the HPC Challenge Benchmark Suite

[27] Dongarra, Jack J. (2010), “LINPACK Benchmark with Time Limits on Multicore & GPU Based Accelerators”

[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]