LINPACK

LINPACK（リンパック）は、主しゅとして線型せんけい代数だいすうの数値すうち計算けいさんを目的もくてきとした、行列ぎょうれつおよびベクトルの演算えんざんが実装じっそうされているライブラリである。

LINPACK

作者さくしゃ	ジャック・ドンガラ、ジム・バンチ、クリーブ・モラー、ギルバート・スチュアート
プログラミング 言語げんご	FORTRAN
種別しゅべつ	ライブラリ
公式こうしきサイト	www.netlib.org/linpack/

概要がいよう

MINPACK、EISPACK と同様どうよう、米国べいこくアルゴンヌ国立こくりつ研究所けんきゅうじょでFORTRANライブラリとして開発かいはつされた。実際じっさいに開発かいはつを行おこなったのは ジャック・ドンガラ、ジム・バンチ、クリーブ・モラー、ギルバート・スチュアートである。1970年代ねんだいから1980年代ねんだい初期しょきのスーパーコンピュータを対象たいしょうとして設計せっけいされ、その後ごより洗練せんれんされたライブラリLAPACKに取とって代かわられた。

LINPACK は BLAS（Basic Linear Algebra Subprograms、基本きほん線形せんけい代数だいすうサブプログラム群ぐん）ライブラリを使つかってベクトル演算えんざんや行列ぎょうれつ演算えんざんを行おこなう。

後述こうじゅつするLINPACKベンチマークは、LINPACKのユーザーズマニュアルの一部いちぶとして公開こうかいされたのが最初さいしょである。

ベンチマーク

LINPACK benchmarks

作者さくしゃ	ジャック・ドンガラ、ジム・バンチ、クリーブ・モラー、ギルバート・スチュアート
初版しょはん	1979年ねん (1979)
公式こうしきサイト	www.netlib.org/benchmark/performance.ps

LINPACK ベンチマークは LINPACK に基もとづいたベンチマークプログラムで、システムの浮動ふどう小数点しょうすうてん演算えんざん性能せいのうを評価ひょうかする。ジャック・ドンガラが考案こうあんしたもので、理学りがく・工学こうがくで一般いっぱん的てきな n×n の線型せんけい方程式ほうていしき系けい Ax = b を解とく速度そくどを測定そくていする。このベンチマークの最新さいしん版ばんはTOP500で世界せかいの高速こうそくなコンピュータの性能せいのう値ちとしてランキングに使用しようされている。

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

歴史れきし

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

具体ぐたい的てきなベンチマーク

LINPACK 100

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

LINPACK 1000

問題もんだいのサイズを大おおきくして行列ぎょうれつの次数じすうを1000とし、アルゴリズムを変更へんこう可能かのうにしたため、コンピュータの限界げんかいに近ちかい性能せいのうを引ひき出だせるようになった。残のこっている制限せいげんは、相対そうたい精度せいどを低ひくくしないという点てんと、演算えんざん回数かいすうは 2/3n³ + 2n² 回かい (n = 1000) だという点てんである。

HPLinpack

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

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

ここで $\epsilon$ はそのマシンの精度せいど、n は問題もんだいのサイズ、$\lVert \cdot \rVert$ は行列ぎょうれつノルム、$O(1)$ はO-記法きほうである。

各かくシステムについて、次つぎの数値すうちを報告ほうこくする。

• R_max: そのマシンで最大さいだいの問題もんだいについての性能せいのう（GFLOPS）
• N_max: そのマシンでの最大さいだいの問題もんだいのサイズ
• N_1/2: Rmaxの半分はんぶんの性能せいのうとなるときの問題もんだいのサイズ
• R_peak: そのマシンの理論りろん上じょうのピーク性能せいのう（GFLOPS）

これらの結果けっかを使つかって、TOP500リストが年としに2回かい更新こうしんされる。

実装じっそう

前節ぜんせつではベンチマークの基本きほん的てき規則きそくを解説かいせつしている。それら規則きそくに基もとづいたプログラムの実装じっそうは様々さまざまであり、FORTRANによる実装じっそう、C言語げんごによる実装じっそう、Javaによる実装じっそうなどがある。

HPL

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

大おおまかに言いえば、このアルゴリズムには次つぎのような特徴とくちょうがある。

• 2次元じげんブロックで周期しゅうき的てきデータ配布はいふを行おこなう。
• 様々さまざまな深ふかさの先読さきよみを伴ともなう right-looking 法ほうの一種いっしゅを使つかったLU分解ぶんかい
• 再帰さいき的てきパネル分解ぶんかい
• パネルブロードキャストには6種類しゅるいの方式ほうしきがある。
• 帯域たいいき幅はばを低減ていげんするスワップ・ブロードキャスト・アルゴリズム
• 深ふかさ1の先読さきよみを伴ともなう後退こうたい代入だいにゅう

批判ひはん

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

測定そくていにかかる時間じかんの問題もんだい

ジャック・ドンガラによれば、HPLinpackでよい性能せいのう値ちを得えようとすると測定そくていに時間じかんがかかるようになってきているという。2010年ねんに開催かいさいされた会議かいぎで、彼かれは「数すう年ねん以内いないに」測定そくていに2日にち半はんかかるようになるとの予想よそうを行おこなった。

外部がいぶリンク

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