最適化問題に対する超高速&安定計算

クラスタ計算機やスーパーコンピュータ上での大規模最適化問題やグラフ探索などの研究のお話が中心

Intel デュアルコア Atom

2008年08月31日 00時07分12秒 | Weblog
シングルコア Atom 230 搭載の PC を購入して Linux を動かし始めたら、9月にはデュアルコアの Atom 330 が発表されることになった。実物が出てこないと分からないことも多いが、基本的に現行の 230 を拡張してデュアルコアに変えていくので、クロック周波数 1.6GHz, FSB 533MHz, L2 キャッシュ 1MB, TDP 8W になるようだ。
Intel Atom N520 搭載のミニノートも購入したのだが、Atom と Windows Vista の組み合わせは最悪に近い。Atom の構想から考えれば OS は余分な機能を省いて、出来るだけ軽いものが望ましい。少しずつ現行の Atom 230 を使っている内に特性等が理解できるようになってきた。本当に必要な機能だけ絞って、計算させる場合にはそれほど性能の悪いチップではないと思う。カーナビなどはいまだにクロック周波数が数百MHz の組み込み系 CPU を使っているので、それと比較すると相当な性能向上になる。
コメント
この記事をはてなブックマークに追加

SDPA クラスタでの SDPARA の実験 その1

2008年08月30日 03時57分54秒 | Weblog
SDPA クラスタで図中にあるパラメータ k の適正値を見付ける実験を行った。
1: 使用する SDPA : LiF.1Sigma.STO6G.pqg.dat-s
2: SDPARA 7.0.1 + GotoBLAS 1.26
3: 32 プロセス × 4 スレッド(GotoBLAS)

○ k = 2.2
2m44.682s
○ k = 3
2m42.861s
○ k = 5
2m42.113s
○ k = 7
2m45.416s
○ k = 9
2m44.541s

1997 年 (SDPA 3.x) の段階では k = 2.2 が適正値だったが、現在ではそれよりも大きめの値が良い。SDPA だと図中にあるように、k = 7 から 10 ぐらい。今回の実験では k = 5 が良い。SDPA と SDPARA では微妙に k の適正値が異なるようだ。
コメント
この記事をはてなブックマークに追加

SDPA クラスタで Linpack 測定 その5

2008年08月29日 03時12分29秒 | Weblog
SDPA クラスタでの Linpack 測定の続報。SDPARA だと MPICH2 の方が MPICH よりも高速だが、Linpack だと以下のように微妙な感じになっている。

1: GotoBLAS マルチスレッド動作時(16 プロセス × 8 スレッド) : MPICH 1.2.7
============================================================================
T/V N NB P Q Time Gflops
----------------------------------------------------------------------------
WR11C2C4 310000 200 1 16 15408.65 1.289e+03
----------------------------------------------------------------------------

2: GotoBLAS マルチスレッド動作時(32 プロセス × 4 スレッド) : MPICH2 1.0.7
============================================================================
T/V N NB P Q Time Gflops
----------------------------------------------------------------------------
WR11C2C4 310000 200 4 8 14202.99 1.398e+03
----------------------------------------------------------------------------

3: GotoBLAS マルチスレッド動作時(32 プロセス × 4 スレッド) : MPICH 1.2.7
============================================================================
T/V N NB P Q Time Gflops
----------------------------------------------------------------------------
WR11C2C4 310000 200 4 8 14200.38 1.399e+03
----------------------------------------------------------------------------
コメント
この記事をはてなブックマークに追加

Xeon 対 Atom

2008年08月28日 00時49分13秒 | Weblog
以前も Core2 と Atom の比較をしたことがあったが、そのときの Atom の数値実験は仮想マシン上の Linux だったので、今度は以下のマシンと OS で両者を比較してみる。共に 64bit 動作だが、クロック周波数は Xeon の方が約2倍となっている。

○ Xeon
Dell PowerEdge 2900
CPU : Intel Xeon X5460 3.16GHz
メモリ : 48GB
OS : CentOS 5.2 for x86_64

○ Atom
MSI Wind PC
CPU : Intel Atom 230 1.6GHz
メモリ : 1GB
OS : Fedora 9 for x86_64

1: GLPK 4.29 整数計画問題
○ stein27.mps
Xeon : 1.486s
Atom : 10.033s
○ air06
Xeon : 6.810s
Atom : 45.026s
○ min_rep_under_thput_39600.0_test18.dat(ファイル配置最適化問題)
Xeon : 3.984s
Atom : 31.217s

2: 最短路問題
○ FLA 10 クエリ(データ名は最短路問題オンライン・ソルバーと同じ)
Xeon : 0.341s
Atom : 2.929s
○ LKS 10 クエリ
Xeon : 0.811s
Atom : 9.724s

3: SDP (半正定値計画問題) : SDPA 7.2.0 + GotoBLAS 1.26(Xeon) or GotoBLAS 1.27(Atom) : 1 スレッド
○ mcp500-1.dat-s
Xeon : 3.970s
Atom : 30.442s
○ theta5.dat-s
Xeon : 23.154s
Atom : 184.620s
○ mater-4.dat-s
Xeon : 6.890s
Atom : 30.635s
コメント
この記事をはてなブックマークに追加

Atom 搭載 PC

2008年08月27日 23時35分11秒 | Weblog
Intel Atom 230 搭載の MSI Wind PCを購入した。Intel Atom にも様々な型番があるが 230 だけが x86_64(64bit)対応になっている。SuSE Linux がプレインストールされているのだが 32bit 版だったので、Fedora 9 の 64bit 版をインストールし直した。

CPU : Intel Atom 230
チップセット : Intel 945GC + ICH7M
メモリ : DDR2-533 SO-DIMM 1GB
HDD : 3.5インチ160GB (SATA)
LAN : Realtek RTL-8111B 101/100/1000BASE-T

高度な処理には向かないが、通常の使用では十分な性能を持っている。価格は 34,800 円と非常に安い。この PC を対象とするのは。今後の組込み系機器がこの程度の性能を持つと想定されるからである。
コメント
この記事をはてなブックマークに追加

走りやすさマップ

2008年08月26日 01時00分04秒 | Weblog
現行カーナビの VICS では時間優先の経路を示してくれるのだが、道路の走りやすさも重視した経路探索の試みも行われている。例えば道路の走りやすさマップとは、道路の幅、カーブの大きさ・多さ、歩道と車道の分離状況などにより、車の走りやすさランクを6段階に分類した地図のことで、インターネットから全国各地の地図が公開されている。
ただし走りやすい道というのは眠くなりやすいという性質も持っている。多少勾配やカーブ等があった方が眠くなりにくい。高速道路も 80km/h ぐらいで走行車線を走ると速度違反で捕まることもなく燃費も良いのだが、これも眠くなりやすく高速催眠現象(ハイウェイ・ヒプノーシス)などを引き起こす原因になる。日本の高速道路は眠くならないように意図的に長い直線を避けていると言われるが、緊急時に高速道路が滑走路として使いにくくなるので、これは一長一短である。
実際にいろいろな場所に車で行ってカーナビを使うと実際に足りない機能、欲しい機能が見えてくる。多様なサービスを提供しようと思うと、どうしても新しくかつ大量のデータが必要となるので、無線ネットワークでサーバにアクセスして経路探索を行う方法も併用するのが良いのではないだろうか(どうせ地上でなければ GPS も機能しないので)。現在は定額で数 Mbps の無線接続サービスがあるので簡単にできる。個別のカーナビに任せているとほとんどの車が同じ経路を選び、新たな渋滞を引き起こす可能性があるが、サーバ方式では交通管制を行うこともできる。いずれにしても高速かつコンパクトな最短路探索エンジンがあった方が良い。
コメント
この記事をはてなブックマークに追加

SDPARA + マルチスレッド

2008年08月25日 04時48分00秒 | Weblog
SDPARA は Ver. 1.x では ATLAS をリンクして基本的にシングルスレッドで使用していたので、今度は GotoBLAS, Intel MKL, ATLAS 等何でも使用できるように変えてみた。ついでに Linpack 測定のように GotoBLAS をマルチスレッドで動作させることにした。しかし、SDPARA で計算する場合には F_1 式の計算ならば DGEMM などが呼び出されてマルチスレッドの効果が上がるが、ほとんどが F_3 式の計算なのでマルチスレッド化による効果はない。
というわけで基本的に疎な問題(F_3 式を多用する場合)では、SDPARA をマルチスレッドで実行する意味は無さそうだが、以下の実験結果を見るとそうでもないようだ。

1: 疎な問題 : CO.1Sigma.STO6G.pqg.dat-s
○128 プロセス x 1 スレッド : 11.035 sec. / 1 iteration
○32 プロセス x 4 スレッド : 9.528 sec. / 1 iteration

2: 密な問題 : D512.dat
○128 プロセス x 1 スレッド : 13.539 sec. / 1 iteration
○32 プロセス x 4 スレッド : 9.557 sec. / 1 iteration
コメント
この記事をはてなブックマークに追加

SDPA クラスタで Linpack 測定 その4

2008年08月24日 04時22分55秒 | Weblog
そろそろ実際のアプリケーションを実行するために、Linpack 測定は一旦終了する。ここまでの結果報告をする。

●新 SDPA クラスタ (2008年)
16 Nodes, 32 CPUs, 128 CPU cores;
CPU : Intel Xeon 5460 3.16GHz (quad cores) x 2 / node
Memory : 48GB / node
HDD : 6TB(RAID 5) / node
NIC : GbE x 2 and Myrinet-10G x 1 / node
OS : CentOS 5.2 for x86_64
Linpack : R_max = 1.399TFlops, R_peak = 1.618TFlops, R_max / R_peak = 86.46%


1: GotoBLAS シングルスレッド動作時(128 プロセス × 1 スレッド)の最高値
============================================================================
T/V N NB P Q Time Gflops
----------------------------------------------------------------------------
WR01C2C4 308000 200 16 8 14370.31 1.355e+03
----------------------------------------------------------------------------

2: GotoBLAS マルチスレッド動作時(64 プロセス × 2 スレッド)の最高値
============================================================================
T/V N NB P Q Time Gflops
----------------------------------------------------------------------------
WR11C2C4 300000 200 4 16 13070.24 1.377e+03
----------------------------------------------------------------------------
N = 300000 以上にすれば、もう少し上がるだろう。


3: GotoBLAS マルチスレッド動作時(32 プロセス × 4 スレッド)の最高値
============================================================================
T/V N NB P Q Time Gflops
----------------------------------------------------------------------------
WR11C2C4 310000 200 4 8 14200.38 1.399e+03
----------------------------------------------------------------------------
コメント
この記事をはてなブックマークに追加

これまでの Linpack 測定

2008年08月23日 04時17分23秒 | Weblog
Linpack 測定自体が研究というわけではなく、義務でもないが、性能の目安と個人的な興味で常にクラスタ計算機の Linpack 測定を行ってきた。これまでのクラスタ計算機での Linpack 測定の結果をまとめておく。

1: 写真左上の初代 SDPA クラスタ(2003年)
40 Nodes, 80 CPUs, 80 cores;
CPU : AMD Athlon MP 2400+ 2.0GHz x 2 / node
Memory : 1GB or 2GB / node
NIC : GbE x 2 / node
OS : RedHat 7.2 for x86
Linpack(HPL + ATLAS) : 160.0GFlops

2: 写真右上の初代 OPT クラスタ(2003年)
16 Nodes, 32 CPUs, 32 cores;
CPU : AMD Opteron 240 1.4GHz x 2 / node
Memory : 2GB / node
NIC : GbE x 1 / node
OS : Fedora Core 1 for x86_64
Linpack(HPL + ATLAS) : 58.2GFlops

3: 写真左下の XEON クラスタ(2004年)
8 Nodes, 16 CPUs, 32 cores(HyperThread);
CPU : Intel Xeon (nocona) 2.8GHz x 2 / node
Memory : 2GB / node
NIC : GbE x 1 / node
OS : Fedora Core 3 for x86_64
Linpack(HPL + ATLAS) : 37.8GFlops

4: 写真右下の中段の二代目 OPT クラスタ(2005年)
5 Nodes, 10 CPUs, 20 cores;
CPU : AMD Opteron 270 2.0GHz x 2 / node
Memory : 4GB / node
NIC : GbE x 2 / node
OS : CentOS 5.2 for x86_64
Linpack(HPL + ATLAS) : 58.0GFlops

5: 写真右下の下段の POWER クラスタ(2007年)
4 Nodes, 8 CPUs, 32 cores;
CPU : Intel Xeon E5345 2.33GHz x 2 / node
Memory : 16GB / node
NIC : GbE x 1 and Myrinet-10G x 1 / node
OS : CentOS 5.2 for x86_64
Linpack(HPL + GotoBLAS) : R_max = 240.80GFlops, R_peak = 298.24GFlops, R_max / R_peak = 80.74%

1 と 2 のクラスタ計算機を合計しても、5 に及ばないところに時代の差を感じる。また 5 以外はいろいろと工夫すればもっと性能が上げられただろう。
コメント
この記事をはてなブックマークに追加

SDPA クラスタで Linpack 測定 その3

2008年08月22日 03時56分04秒 | Weblog
Linpack 測定の続き。1.399TFlops なので、性能比率は 1.399 / 1.61792 = 86.47% となった。

============================================================================
T/V N NB P Q Time Gflops
----------------------------------------------------------------------------
WR11C2C4 300000 200 4 8 12896.95 1.396e+03
----------------------------------------------------------------------------

============================================================================
T/V N NB P Q Time Gflops
----------------------------------------------------------------------------
WR11C2C4 300000 224 4 8 12888.49 1.397e+03
----------------------------------------------------------------------------

============================================================================
T/V N NB P Q Time Gflops
----------------------------------------------------------------------------
WR11C2C4 300000 200 4 16 13070.24 1.377e+03
----------------------------------------------------------------------------

============================================================================
T/V N NB P Q Time Gflops
----------------------------------------------------------------------------
WR11C2C4 310000 224 4 8 14210.47 1.398e+03
----------------------------------------------------------------------------

============================================================================
T/V N NB P Q Time Gflops
----------------------------------------------------------------------------
WR11C2C4 310000 200 4 8 14200.38 1.399e+03
----------------------------------------------------------------------------
コメント
この記事をはてなブックマークに追加

カーネル 2.6.25

2008年08月21日 02時55分38秒 | Weblog
日経 Linux 9月号の特集で Linux のカーネル 2.6.25 での大きな変更点や新機能について詳細に解説されている。組込み系向けの新機能搭載やリアルタイム性の向上などが行われている。今後は Linux もリアルタイム OS としての性格が強くなっていくことが予想される。手持ちのカーネル 2.6.25 と言うと Fedora 9 なので、これで新機能の確認を行っている。Linux では仮想アドレス空間のサイズも物理的に使用できる実メモリのサイズも全プロセスで平等だが、2.6.25 ではプロセスごとに割り当てられる実メモリの量を変更できるようになっている。さらにリアルタイム・スケジュールの改善として、CPU 時間をグループ単位で割り当てることができるようになった。いずれもこれからの最適化ソフトウェア開発にはあった方が良いものである。
コメント
この記事をはてなブックマークに追加

Atom で最適化

2008年08月20日 02時16分44秒 | Weblog
Intel Atom 搭載の 5万円台のミニノートが結構売れているようであるが、Intel Atom + メモリ 1 or 2GB + HDD or SSD + 無線 & 有線ネットワーク + 液晶モニターで 5 万円台ということなので、同仕様のパーソナルナビゲーションでも 5 万円台で作れるということであろう(実際には OS が Linux などさらに価格的に有利だが)。HDD が無いと GPS アンテナが内蔵できるのでコスト的にも有利になる。クラリオンが今年中に北米で Intel Atom + 4.8 インチ液晶 + WiFi + GPS + USB + Bluetooth などを装備したインターネット接続機能付きの車載ナビゲーションを発売する(700ドル程度)。
現在取組み中の最適化問題の中には最短路や切り出し問題など、現場での実行が想定されるものもあるので、これくらいの性能のマシンで解を計算できることが望ましい(基本的に前者は最適解、後者は近似解)。クラスタ計算機で最適化するのも Atom で最適化するのも、無駄な計算をしない、また計算機のリソースを使い切るという意味では同じだが、システムとしてのまとめ方が異なる。
コメント
この記事をはてなブックマークに追加

SDPA クラスタで Linpack 測定 その2

2008年08月19日 09時30分05秒 | Weblog
以下のパラメータで実験したところ 1.396TFlops となったので、性能比率さらに大きくなって 1.396 / 1.61792 = 86.28% になった。1.4TFlops 近くまで達した。当初の目的は 80% = 1.294TFlops なので、これは予想以上の性能だ。

============================================================================
HPLinpack 1.0a -- High-Performance Linpack benchmark -- January 20, 2004
Written by A. Petitet and R. Clint Whaley, Innovative Computing Labs., UTK
============================================================================

An explanation of the input/output parameters follows:
T/V : Wall time / encoded variant.
N : The order of the coefficient matrix A.
NB : The partitioning blocking factor.
P : The number of process rows.
Q : The number of process columns.
Time : Time in seconds to solve the linear system.
Gflops : Rate of execution for solving the linear system.

The following parameter values will be used:

N : 300000
NB : 200
PMAP : Row-major process mapping
P : 4
Q : 8
PFACT : Crout
NBMIN : 4
NDIV : 2
RFACT : Crout
BCAST : 1ringM
DEPTH : 1
SWAP : Mix (threshold = 64)
L1 : transposed form
U : transposed form
EQUIL : yes
ALIGN : 8 double precision words

----------------------------------------------------------------------------

- The matrix A is randomly generated for each test.
- The following scaled residual checks will be computed:
1) ||Ax-b||_oo / ( eps * ||A||_1 * N )
2) ||Ax-b||_oo / ( eps * ||A||_1 * ||x||_1 )
3) ||Ax-b||_oo / ( eps * ||A||_oo * ||x||_oo )
- The relative machine precision (eps) is taken to be 2.220446e-16
- Computational tests pass if scaled residuals are less than 16.0

============================================================================
T/V N NB P Q Time Gflops
----------------------------------------------------------------------------
WR11C2C4 300000 200 4 8 12896.95 1.396e+03
----------------------------------------------------------------------------
コメント (2)
この記事をはてなブックマークに追加

SDPA クラスタで Linpack 測定

2008年08月18日 02時36分58秒 | Weblog
HPL 用の GotoBLAS を提供していただいたので、これを用いて Linpack 測定をやり直した。CPU が Intel Xeon 5460 (クアッドコア)なので、1 CPU 上で 4 スレッドの計算を行う。以下のパラメータで実験した場合には 1.387TFlops となるので、性能比率は 1.387 / 1.61792 = 85.73% になった。

============================================================================
HPLinpack 1.0a -- High-Performance Linpack benchmark -- January 20, 2004
Written by A. Petitet and R. Clint Whaley, Innovative Computing Labs., UTK
============================================================================

An explanation of the input/output parameters follows:
T/V : Wall time / encoded variant.
N : The order of the coefficient matrix A.
NB : The partitioning blocking factor.
P : The number of process rows.
Q : The number of process columns.
Time : Time in seconds to solve the linear system.
Gflops : Rate of execution for solving the linear system.

The following parameter values will be used:

N : 300000
NB : 160
PMAP : Row-major process mapping
P : 4
Q : 8
PFACT : Crout
NBMIN : 4
NDIV : 2
RFACT : Crout
BCAST : 1ringM
DEPTH : 1
SWAP : Mix (threshold = 64)
L1 : transposed form
U : transposed form
EQUIL : yes
ALIGN : 8 double precision words

----------------------------------------------------------------------------

- The matrix A is randomly generated for each test.
- The following scaled residual checks will be computed:
1) ||Ax-b||_oo / ( eps * ||A||_1 * N )
2) ||Ax-b||_oo / ( eps * ||A||_1 * ||x||_1 )
3) ||Ax-b||_oo / ( eps * ||A||_oo * ||x||_oo )
- The relative machine precision (eps) is taken to be 2.220446e-16
- Computational tests pass if scaled residuals are less than 16.0

============================================================================
T/V N NB P Q Time Gflops
----------------------------------------------------------------------------
WR11C2C4 300000 160 4 8 12976.65 1.387e+03
----------------------------------------------------------------------------
コメント (2)
この記事をはてなブックマークに追加

Atom で Linux

2008年08月17日 02時29分25秒 | Weblog
せっかく Intel Atom 搭載の機器を購入したのに OS が リソースを大量に消費する Vista では意味がないと思っている人は多いだろう。そこで Intel が中心となって Atom 用の Linux "Moblin" が開発されている。 実際に Atom 搭載機にインストールして試してみようと思ったが、インストールの手間やドライバの整備状況などを考慮して、しばらく待つことにした。もう少し待てば Moblin がインストールされた機器の販売もされるようになるだろう。Atom + Linux のマシンで最短路問題を解くソフトウェアの開発や実行が主目的になる。
コメント
この記事をはてなブックマークに追加