LINPACKのソースを表示

{{Infobox Software
| name                   = Linpack
| title                  = LINPACK
| author                 = [[ジャック・ドンガラ]]、ジム・バンチ、[[クリーブ・モラー]]、ギルバート・スチュアート
| programming language   = [[FORTRAN]]
| genre                  = [[ライブラリ]]
| website                = {{URL|http://www.netlib.org/linpack/}}
}}
'''LINPACK'''（リンパック）は、主として[[線型代数]]の[[数値解析|数値計算]]を目的とした、行列およびベクトルの演算が実装されている[[ライブラリ]]である。

== 概要 ==
[[MINPACK]]、[[EISPACK]] と同様、米国[[アルゴンヌ国立研究所]]で[[FORTRAN]]ライブラリとして開発された。実際に開発を行ったのは [[ジャック・ドンガラ]]、ジム・バンチ、[[クリーブ・モラー]]、ギルバート・スチュアートである。1970年代から1980年代初期の[[スーパーコンピュータ]]を対象として設計され<ref>{{Cite news |title=Sidebar: The Linpack Benchmark |first=Jan |last=Matlis |date=2005-05-30 |newspaper=ComputerWorld |url= http://www.computerworld.com/s/article/102050/Sidebar_The_Linpack_Benchmark}}</ref><ref>{{Cite news |newspaper=New York Times |title=Technology; Measuring How Fast Computers Really Are |first=John |last=Markoff |date=1991-09-22 |url= http://select.nytimes.com/gst/abstract.html?res=F20616FF39550C718EDDA00894D9494D81}}</ref>、その後より洗練されたライブラリ[[LAPACK]]に取って代わられた。

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

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

== ベンチマーク ==
{{Infobox Software
| name = Linpack benchmarks
| title = LINPACK benchmarks
| author = [[ジャック・ドンガラ]]、ジム・バンチ、[[クリーブ・モラー]]、ギルバート・スチュアート
| released = {{Start date|1979}}
| website = {{URL|http://www.netlib.org/benchmark/performance.ps}}
}}

'''LINPACK ベンチマーク'''は LINPACK に基づいた[[ベンチマーク]]プログラムで、システムの[[浮動小数点数|浮動小数点]]演算性能を評価する。[[ジャック・ドンガラ]]が考案したもので、[[理学]]・[[工学]]で一般的な ''n''×''n'' の[[線型方程式系]]<ref>ただし密係数行列。一般に、[[差分法]]や[[有限要素法]]などで解かれる大規模問題は、[[連結リスト]]によって記述される[[参照の局所性]]の低い[[疎行列]]系であり、[[キャッシュメモリ]]の恩恵をほとんど受けない。（つまりメモリバンド幅によって性能が決まる。）したがって、必ずしも実アプリケーションの性能を示すものではなく、指標の一つとして考えるのが妥当であろう。</ref> ''Ax''&nbsp;=&nbsp;''b'' を解く速度を測定する。このベンチマークの最新版は[[TOP500]]で世界の高速なコンピュータの性能値としてランキングに使用されている<ref name="top500"/>。

コンピュータが実世界の問題を解く性能の近似値を得ることを目的としている。しかし、1つの測定値でコンピュータシステムのあらゆる性能を代表させることは不可能であり、あくまでも1つの単純化である。それでも、メーカーが提供するピーク性能値に対してLINPACKベンチマークがよい補正を提供している。ピーク性能とは、そのコンピュータが理論上達成しうる最高性能であり、クロック周波数、1秒間の命令サイクル数、1サイクルで実行可能な演算回数などから計算される。実際の性能は常にピーク性能よりも低い<ref name="hplpaper"/>。コンピュータの性能は様々な要素が相互に絡み合った複雑な問題である。LINPACKベンチマークで測定するのは、64ビット浮動小数点演算（通常、加算と乗算）の1秒あたりの実行回数（[[FLOPS]]）である。しかし、実アプリケーションを実行したときの性能は、LINPACKベンチマークを適切に設定して測定したときの最高性能よりずっと低くなる可能性が高い<ref>{{Citation |title = Jack Dongarra interview by Sander Olson |url = http://nextbigfuture.com/2010/06/jack-dongarra-interview-by-sander-olson.html}}</ref>。

=== 歴史 ===
LINPACKベンチマークは1979年、LINPACKのユーザーズマニュアルの付録として公開されたのが最初である<ref>{{Citation |last1 = Dongarra |first1 = J.J. |last2 = Moler |first2 = C.B. |last3 = Bunch |first3 = J.R. |last4 = Stewart |first4 = G.W. |title = LINPACK: users' guide |year = 1979 |publisher =  SIAM |url = https://books.google.ch/books?id=AmSm1n3Vw0cC&lpg=PR5&ots=EDFdqJhr8x&dq=info%3Ahttp%3A%2F%2Fs3da3171290b34600.scholar.google.com%2F0&lr&pg=SL2-PA1#v=onepage&q&f=false}}</ref>。LINPACKパッケージを使って問題を解く際にかかる時間をユーザーが推定する手がかりを与えることを目的として設計された。そのため、当初は大きさ100の行列問題を23種類用意していた。大きさは当時のメモリ容量を考慮して選択された。-1 から 1 の範囲内の浮動小数点数を10000個、無作為に生成し密係数行列を作る。そして、部分ピボット選択による[[LU分解]]を使用する。その後、行列の大きさを300や1000にしたり、制限を緩めるなどして、行列やベクトルの演算を実装するようになったハードウェアアーキテクチャによる最適化を役立てられるようにしていった<ref>{{Citation |last = Dongarra |first = Jack |title = The LINPACK benchmark: An explanation |year = 1988 |journal = Supercomputing |pages = 456–474 |publisher = Springer Berlin/Heidelberg |url = http://www.netlib.org/utk/people/JackDongarra/PAPERS/The-LINPACK-Benchmark-An-Explanation.pdf}}</ref>。オーダー1000の大きさの問題の場合、そのベンチマークを LINPACK 1000 と呼び、問題を解くアルゴリズムを修正可能である<ref name = "hplpaper">{{Citation |last1 = Dongarra |first1 = Jack J. |last2 = Luszczek |first2 = Piotr |last3 = Petitet |first3 = Antoine |title = The LINPACK Benchmark: past, present and future |year = 2003 |journal = Concurrency and Computation: Practice and Experience |pages = 803–820 |publisher = John Wiley & Sons, Ltd. |url = http://www.netlib.org/utk/people/JackDongarra/PAPERS/hplpaper.pdf}}</ref>。1991年には任意の大きさの問題を解くベンチマークが登場した<ref>{{Citation |title = High Performance Linpack Benchmark |accessdate = 2012-01-10 |url = http://icl.cs.utk.edu/graphics/posters/files/SC2010-HPL.pdf}}</ref>。これで[[スーパーコンピュータ]]の極限性能に近い値を得られるようになり、その2年後に[[TOP500]]リストが公開されるようになった。

=== 具体的なベンチマーク ===
==== LINPACK 100 ====
1979年、LINPACKのユーザーズマニュアル<ref>[https://books.google.ch/books?id=AmSm1n3Vw0cC&lpg=PR5&ots=EDFdqJhr8x&dq=info%3Ahttp%3A%2F%2Fs3da3171290b34600.scholar.google.com%2F0&lr&pg=SL2-PA1#v=onepage&q&f=false LINPACK users' manual]</ref>で公表されたオリジナルのベンチマークにほぼ近い。部分ピボット選択による[[ガウスの消去法]]で問題を解き、2/3n<sup>3</sup> + 2n<sup>2</sup> 回の浮動小数点演算を行う。''n'' は 100 で、問題を定義する行列 ''A'' の次数である。サイズが小さく、ソフトウェアの柔軟性が欠けていたため、多くの最新のコンピュータでは限界性能を引き出すことができない。しかし、計算中心のユーザープログラムの性能を見積もるのにはある程度役立つ<ref name="hplpaper"/>。

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

==== HPLinpack ====
従来のベンチマークは並列コンピュータの性能測定には適していない<ref>{{Citation |url = http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5348941&isnumber=5348846 |last1 = Bailey |first1 = D.H. |last2 = Barszcz |first2 = E. |last3 = Barton |first3 = J.T. |last4 = Browning |first4 = D.S. |last5 = Carter |first5 = R.L. |last6 = Dagum |first6 = L. |last7 = Fatoohi |first7 = R.A. |last8 = Frederickson |first8 = P.O. |last9 = Lasinski |first9 = T.A. |last10 = Schreiber |first10 = R.S. |last11 = Simon |first11 = H.D. |last12 = Venkatakrishnan |first12 = V. |last13 = Weeratunga |first13 = S.K. |contribution = The NAS parallel benchmarks summary and preliminary results |journal = Supercomputing |year = 1991 |title = Supercomputing '91. Proceedings of the 1991 ACM/IEEE Conference |pages = 158–165}}</ref>。そこで、並列コンピュータ向きの新たなベンチマーク Linpack’s Highly Parallel Computing benchmark、または HPLinpack ベンチマークが考案された。HPLinpackではサイズ n をそのマシンでの最高性能を引き出せる値にまで大きくできる。演算回数は 2/3n<sup>3</sup> + 2n<sup>2</sup> 回だがアルゴリズムは選択可能である。[[シュトラッセンのアルゴリズム]]は演算回数を減らしてしまうので使えない<ref>{{Cite web |url = http://www.netlib.org/utk/people/JackDongarra/faq-linpack.html#_Can_I_use |title = LINPACK FAQ - Can I use Strassen’s Method when doing the matrix multiples in the HPL benchmark or for the Top500 run? |accessdate = 2012-01-12}}</ref>。精度は次の式が成り立つようになる必要がある。

:<math>{\lVert Ax-b\rVert\over \lVert A\rVert \lVert x\rVert n \epsilon} \leq O(1)</math>

ここで <math>\epsilon</math> はそのマシンの精度、''n'' は問題のサイズ<ref>{{Cite web |url = http://www.netlib.org/utk/people/JackDongarra/faq-linpack.html#_Toc27885722 |title = LINPACK FAQ - To what accuracy must be the solution conform? |accessdate = 2012-01-12}}</ref>、<math>\lVert \cdot \rVert</math> は[[行列ノルム]]、<math>O(1)</math> は[[ランダウの記号|O-記法]]である。

各システムについて、次の数値を報告する<ref name="hplpaper"/>。
* R<sub>max</sub>: そのマシンで最大の問題についての性能（[[FLOPS|GFLOPS]]）
* N<sub>max</sub>: そのマシンでの最大の問題のサイズ
* N<sub>1/2</sub>: Rmaxの半分の性能となるときの問題のサイズ
* R<sub>peak</sub>: そのマシンの理論上のピーク性能（GFLOPS）
これらの結果を使って、[[TOP500]]リストが年に2回更新される<ref name="top500">{{Cite web |title = The Linpack Benchmark, TOP500 Supercomputing Sites |url = http://www.top500.org/project/linpack |accessdate = 2012-01-11}}</ref>。

=== 実装 ===
前節ではベンチマークの基本的規則を解説している。それら規則に基づいたプログラムの[[実装]]は様々であり、[[FORTRAN]]による実装<ref>{{Cite web |title = Linpack benchmark program in Fortran |accessdate = 2012-01-12 |url = http://www.netlib.org/benchmark/linpackd}}</ref>、[[C言語]]による実装<ref>{{Cite web |title = Linpack benchmark program in C |accessdate = 2012-01-12 |url = http://www.netlib.org/benchmark/linpackc }}</ref>、[[Java]]による実装<ref>{{Cite web |title = Linpack benchmark program in Java |accessdate = 2012-01-12 |url = http://www.netlib.org/benchmark/linpackjava}}</ref>などがある。

==== HPL ====
HPLはHPLinpackをC言語で実装したもので、本来はガイドラインとして書かれたものだが、TOP500でも広く使われている。なお、HPL以外のテクノロジーやパッケージを使うことに問題はない。HPLはn次の線型方程式系を生成し、部分ピボット選択によるLU分解でそれを解く。使用するには[[Message Passing Interface|MPI]]と[[Basic Linear Algebra Subprograms|BLAS]]またはVSIPLをインストールしておく必要がある<ref>{{Cite web |title = HPL - A Portable Implementation of the High-Performance Linpack Benchmark for Distributed-Memory Computers |accessdate = 2012-01-12 |url = http://www.netlib.org/benchmark/hpl}}</ref>。

大まかに言えば、このアルゴリズムには次のような特徴がある<ref>{{Cite web |url = http://www.netlib.org/benchmark/hpl/algorithm.html |title = HPL algorithm |accessdate = 2012-01-12}}</ref><ref>{{Cite web |url = http://icl.cs.utk.edu/hpl/overview/index.html |title = HPL overview |accessdate = 2012-01-12}}</ref>。
* 2次元ブロックで周期的データ配布を行う。
* 様々な深さの[[先読み]]を伴う right-looking 法の一種を使った[[LU分解]]
* 再帰的パネル分解
* パネル[[ブロードキャスト]]には6種類の方式がある。
* 帯域幅を低減するスワップ・ブロードキャスト・アルゴリズム
* 深さ1の先読みを伴う後退代入

=== 批判 ===
LINPACKベンチマークが成功した要因は、HPLinpackのスケーラビリティ<ref name="DongIntel">{{Cite web |url = http://www.taborcommunications.com/archives/102765.html |title = An interview with supercomputer legend Jack Dongarra |last = Meuer |first = Martin |date = 2002-05-24 |accessdate = 2012-01-13}}</ref>、1つの数値を生成するため比較が容易であるという事実、それまでの測定値を蓄積したデータベースが存在すること<ref>{{Citation |quote = 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. |title = An interview with Jack J. Dongarra |first = Thomas |last = Haigh |year = 2004 |url = http://history.siam.org/pdfs2/Dongarra_%20returned_SIAM_copy.pdf}}</ref>が挙げられる。しかしリリース直後からLINPACKベンチマークには地道に最適化を施すプログラマだけが達成できる性能レベルを提供するもので、しかもその最適化はそのマシンでしか意味が無いという批判が浴びせられた<ref>{{Citation |last = Hammond |first = Steven |title = Beyond Machoflops: Getting MPPs Into the Production Environment |year = 1995 |url = http://nldr.library.ucar.edu/repository/collections/TECH-NOTE-000-000-000-227}}</ref>。また、解いている問題は密係数行列の線型方程式系であり、それが科学技術計算全般を代表するものではないという批判もある<ref>{{Citation |last1 = Gahvari |first1 = Hormozd |last2 = Hoemmen |first2 = Mark |last3 = Demmel |first3 = James |last4 = Yelick |first4 = Katherine |title = SPEC Benchmark Workshop |contribution = Benchmarking Sparse Matrix-Vector Multiply in Five Minutes |year = 2006 |url = http://bebop.cs.berkeley.edu/pubs/gahvari2007-spmvbench-spec.pdf}}</ref>。LINPACKベンチマークを推進してきた[[ジャック・ドンガラ]]は、CPUのピーク性能とCPU数だけが強調されており、帯域幅やネットワークへのストレスが十分でないと述べている<ref>{{Citation |last = Dongarra |first = Jack J. |title = SPEC Benchmark Workshop |year = 2007 |contribution = The HPC Challenge Benchmark: A Candidate for Replacing Linpack in the Top500? |url = http://www.spec.org/workshops/2007/austin/slides/Keynote_Jack_Dongarra.pdf}}</ref>。[[米国立スーパーコンピュータ応用研究所]]のトム・ダニングはLINPACKベンチマークについて「興味深い現象の1つだ。それを知っているほとんど全員がそれをあざ笑う。彼らはその限界を理解しているが、何年にも渡って我々はその値を使ってきたため、一種のマインドシェアが生じている」と述べた<ref>{{Cite web | url = http://www.technologyreview.com/blog/mimssbits/25981/ | title = Why China's New Supercomputer Is Only Technically the World's Fastest | author = Christopher Mims | date = 2010-11-08 | accessdate = 2011-09-22}}</ref>。ドンガラによれば、「システムの性能を様々な面から明らかにすることは重要」なので「TOP500の主催者はベンチマークの範囲を拡大する方法を積極的に模索している」という<ref name="DongIntel" />。TOP500のベンチマークの拡張について可能性の高いものとして、[[HPCチャレンジベンチマーク]] がある<ref>{{Citation |title = Introduction to the HPC Challenge Benchmark Suite |year = 2005 |last1 = Luszczek |first1 = Piotr |last2 = Dongarra |first2 = Jack J. |last3 = Koester |first3 = David |last4 = Rabenseifner |first4 = Rolf |last5 = Lucas |first5 = Bob |last6 = Kepner |first6 = Jeremy |last7 = Mccalpin |first7 = John |last8 = Bailey |first8 = David |last9 = Takahashi |first9 = Daisuke |url = http://icl.cs.utk.edu/projectsfiles/hpcc/pubs/hpcc-challenge-benchmark05.pdf}}</ref>。他に、倍精度浮動小数を要素とする行列の演算（特に乗算）を多用して、大規模な連立一次方程式を解くというベンチマークである点は共通だが、密ではなく疎な行列を対象とするHPCG（Conjugate Gradient、[[共役勾配法]]）や、そもそも数値計算ではない応用で近年重要性の増しているネットワーク構造（グラフ）の情報処理を対象とした[[Graph500]]などがある。

==== 測定にかかる時間の問題 ====
[[ジャック・ドンガラ]]によれば、HPLinpackでよい性能値を得ようとすると測定に時間がかかるようになってきているという。2010年に開催された会議で、彼は「数年以内に」測定に2日半かかるようになるとの予想を行った<ref>{{Citation |last = Dongarra |first = Jack J. |conference = International Supercomputing Conference |contribution = LINPACK Benchmark with Time Limits on Multicore & GPU Based Accelerators |year = 2010 |url = http://www.netlib.org/utk/people/JackDongarra/SLIDES/isc-talk-06102.pdf}}</ref>。

== 脚注 ==
{{Reflist}}

== 外部リンク ==
* [http://www.netlib.org/linpack/ LINPACK]
* [http://www.netlib.org/blas/ BLAS]
* [http://www.top500.org/ TOP500 Supercomputing Sites]
* [http://www.netlib.org/benchmark/linpackjava/ Linpack Benchmark -- Java Version] a web-based LINPACK benchmark
* [http://www.netlib.org/benchmark/hpl/ The HPL benchmark] used in the [[TOP500]]

{{DEFAULTSORT:りんはつく}}
[[Category:数値解析ソフトウェア]]
[[Category:数値線形代数]]
[[Category:ベンチマーク]]
[[Category:数学に関する記事]]
[[Category:FORTRAN]]