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

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/3n3 + 2n2 回の浮動小数点演算を行う。n は 100 で、問題を定義する行列 A の次数である。サイズが小さく、ソフトウェアの柔軟性が欠けていたため、多くの最新のコンピュータでは限界性能を引き出すことができない。しかし、計算中心のユーザープログラムの性能を見積もるのにはある程度役立つ[5]。
LINPACK 1000

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

従来のベンチマークは並列コンピュータの性能測定には適していない[11]。そこで、並列コンピュータ向きの新たなベンチマーク Linpack’s Highly Parallel Computing benchmark、または HPLinpack ベンチマークが考案された。HPLinpackではサイズ n をそのマシンでの最高性能を引き出せる値にまで大きくできる。演算回数は 2/3n3 + 2n2 回だがアルゴリズムは選択可能である。シュトラッセンのアルゴリズムは演算回数を減らしてしまうので使えない[12]。精度は次の式が成り立つようになる必要がある。 ‖ A x − b ‖ ‖ A ‖ ‖ x ‖ n ϵ ≤ O ( 1 ) {\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 } は行列ノルム、 O ( 1 ) {\displaystyle O(1)} はO-記法である。

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

Rmax: そのマシンで最大の問題についての性能（GFLOPS）

Nmax: そのマシンでの最大の問題のサイズ

N1/2: Rmaxの半分の性能となるときの問題のサイズ

Rpeak: そのマシンの理論上のピーク性能（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つだ。