LINPACK

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

LINPACK

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

概要

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

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

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

ベンチマーク

LINPACK benchmarks

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

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]。精度は次の式が成り立つようになる必要がある。

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

ここで ${\displaystyle \epsilon }$ はそのマシンの精度、n は問題のサイズ^[13]、${\displaystyle \lVert \cdot \rVert }$ は行列ノルム、${\displaystyle 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]。