２０１１年

今年(2011年)も今日で終わりとなりました。10月から JST CREST の研究プロジェクトが開始されまして、様々な研究プロジェクトの立ち上げや研究計画の策定を行っております。最適化関連の研究であるのと同時に Big Data 処理のプロジェクトとしての性格も持っています。

今後の大まかな予定について

◯第１回 Graph CREST シンポジウム
開催日：2012年3月23日（金）
場所：中央大学（予定）：東京開催は決定

◯Graph500 関連
超大規模スパコン（複数）での実行とカーネルの拡張（最短路問題）

◯実データやセンサーデータ関連の研究(ストリーミング処理等、グラフ解析)

◯数理計画問題(SDPやMIP等)の大規模実行

◯GraphDB、可視化処理

第１回 Graph CREST シンポジウム

第１回 Graph CREST シンポジウムが以下の内容で開催予定となっております。また詳細が決定次第、こちらのブログからも発表する予定です。

開催日：2012年3月23日（金）
場所：中央大学（予定）

9:45 - 10:00 Katsuki Fujisawa
Introduction :
CREST project and Workshops on Computational Aspects for Solving Large Scale Optimization Problems
10:00 - 10:30 Toyotaro Suzumura
Tentative titel:
Performance Evaluation of Graph500 on Large-Scale Distributed Environment
10:30 - 11:00 Hans Mittelmann
Tentative title: Benchmarks for Optimization Software
11:00 - 11:15 Break
11:15 - 11:45 TOH Kim Chuan
Computational experience in solving large scale semidefinite programmin
11:45 - 12:15 Yasuaki Matsukawa
A Primal Barrier Function Phase I Algorithm for Nonsymmetric Conic Optimization Problems
12:15 - 13:30 Lunch
13:30 - 15:00 Tutorial Session 1
- Timo Berthold
What is Linear and Mixed Integer Programming(LP/MIP)
- Ambros Gleixner, Stefan Heinz
How to model and solve LPs and MIPs (SCIP, ZIMPL)
- Stefan Heinz
Tentative title: Column Generation using SCIP
15:30 - 15:45 Break
15:45 - 16:45 Tutorial Session 2
- Ambros Gleixner
Improving the Accuracy of LP Solvers
- Timo Berthold
Primal Heuristics for MIP
16:45 - 17:00 Break
17:00 - 17:30 Domenico Salvagnin
Three ideas for the Quadratic Assignment Problem
17:30 - 18:00 Shunji Umetani
A heuristic algorithm for the set multicover problem with
　　　　　　　generalized upper bound constraints

調達予定 その４

Westmere-EX 搭載 40 コアマシンの購入許可がようやく下りてきた(年末ぎりぎり）。しばらく発注作業も出来ないので実際に入手できるのは１ヶ月以上先の話になる。ちなみに現在まで AMD Opteron Magny-cours 48 コアマシンは高負荷時での安定性が弱く、大規模実験には使用が難しいところもあったが、今度の Westmere-EX は是非安定して動作して欲しいところ。このマシンは立てればミニタワーで倒せばラックにマウントできるそうだ。Infiniband などの拡張は来年度以降に行う予定。

CPU : Intel Xeon E7-4870 4 way 2.40GHz 30M L3 cache (合計 40 コア)
メモリ： ACTICA DDR3 1333 ECC REG 512GB( 16GB x 32)
電源：1400W
HDD : 1TB x 4 (RAID5)

TSUBAME 2.0 と SDPA, SDPARA その２

前回の続きで SDPARA の TSUBAME 2.0 での make について。
make には Intel Compilier + mvapich2 を使うので、以下のように設定を行う。

export PATH=/usr/apps/mvapich2/1.5.1/intel/bin:$PATH
export LD_LIBRARY_PATH=/usr/apps/mvapich2/1.5.1/intel/lib:$LD_LIBRARY_PATH

Make ファイル内は一部を以下のように書き換える。ScaLAPCK は個人的に ILP64 化したものを利用している。

CC = mpicc
CXX = mpicxx
F77 = mpif90
CFLAGS = -O2 -m64 -funroll-all-loops -openmp -shared-intel -mcmodel=medium -DMKL_ILP64
CXXFLAGS = -O2 -m64 -funroll-all-loops -openmp -shared-intel -mcmodel=medium -DMKL_ILP64
FFLAGS = -O2 -m64 -i8 -funroll-all-loops -shared-intel -mcmodel=medium -DMKL_ILP64
F77FLAGS = -O2 -m64 -i8 -funroll-all-loops -shared-intel -mcmodel=medium -DMKL_ILP64

INTEL_INCL = /usr/apps/isv/intel/11.1.072/mkl/include
INTEL_LIBS = /usr/apps/isv/intel/11.1.072/mkl/lib/em64t
INTEL_LIBS2 = /usr/apps/isv/intel/11.1.072/lib/intel64

LAPACK_LIBS = -lmkl_lapack95_ilp64
BLAS_LIBS = $(HOME)/sdpa-src/lib.mvapich2.intel.64bit/libgoto2.a -lmkl_intel_ilp64 -lmkl_intel_thread -lmkl_lapack95_ilp64 -lmkl_core

SCALAPACK_LIBS = $(HOME)/sdpa-src/lib.mvapich2.intel.64bit/libscalapack.a -lmkl_blacs_intelmpi_ilp64
FORTRAN_LIBS = -lgfortran -lifcore -limf
PTHERAD_LIBS = -liomp5 -lpthread

GPSやRFIDなどのセンサーを用いた人や車などの位置情報

少し前のプレスリリースですが、GPSやRFIDなどのセンサーを用いて人や車などの位置情報を大量に取得ということですので、非常に貴重データで様々な分野への応用も期待できます。今後はストリーミング処理、前処理(確率やグラフ探索等)によるデータ縮約それに最適化手法との組み合わせなどが有望ではないかと思います。

富士通研、従来比60倍高速の時空間データ処理技術を開発

富士通研究所は10月17日、緯度や経度などの位置情報を含むデータの中から、注目の出来事が発生しているエリアを正確かつ高速に探索する時空間データ処理技術を開発したと発表した。

TSUBAME 2.0 と SDPA, SDPARA

東工大のスパコン TSUBAME 2.0 上で SDPA と SDPARA のバイナリ作成を行った。

例えば SDPA 7.4.0 は Intel Compiler を用いて以下のように configure & make することができる。

◯ SDPA 7.4.0

export SDPA_HOME=$(HOME)/sdpa7.intel
export INTEL_LIB=/usr/apps/isv/intel/11.1.072/mkl/lib/em64t
export INTEL_LIB2=/usr/apps/isv/intel/11.1.072/lib/intel64
export CC=icc
export CXX=icpc
export F77=ifort
export CFLAGS="-O2 -openmp -DDIMACS_PRINT"
export CXXFLAGS="-O2 -openmp -DDIMACS_PRINT"
export FFLAGS="-O2 -openmp -i8"
./configure --with-blas="-L${SDPA_HOME}/lib -lgoto2 -L${INTEL_LIB} -liomp5" --with-lapack="-L${SDPA_HOME}/lib -lgoto2 -L${INTEL_LIB} -lpthread -lgoto2 -lstdc++ -lifcore -limf -lifport"
make

SDPARA は OpenMPI でも MVAPICH でもどちらでも良いが、今回は MVAPICH2 を使用した。

X10 のサンプルとコンパイルと実行

X10 のバイナリが /usr/local/X10/x10-trunk/x10.dist/bin/ がインストールされていると仮定する。このディレクトリを環境変数 PATH に含める。

/usr/local/X10/x10-trunk/x10.dist/bin/は以下の通り。

-rwxr-xr-x 1 root root 47406 12月 25 03:42 X10Launcher
-rwxr-xr-x 1 root root 5001 12月 25 03:40 apgas
-rw-r--r-- 1 root root 3476 12月 25 03:39 apgas.in
-rwxr-xr-x 1 root root 5210 12月 25 03:40 precommit
-rw-r--r-- 1 root root 3685 12月 25 03:39 precommit.in
-rwxr-xr-x 1 root root 777 12月 25 03:39 runx10
-rwxr-xr-x 1 root root 8996 12月 25 03:40 x10
-rw-r--r-- 1 root root 7471 12月 25 03:39 x10.in
-rwxr-xr-x 1 root root 5173 12月 25 03:40 x10c
-rwxr-xr-x 1 root root 459 12月 25 03:39 x10c++
-rw-r--r-- 1 root root 3648 12月 25 03:39 x10c.in
-rwxr-xr-x 1 root root 686 12月 25 03:39 x10doc
-rwxr-xr-x 1 root root 2150 12月 25 03:40 x10j
-rw-r--r-- 1 root root 625 12月 25 03:39 x10j.in

次に HelloWholeWorld.x10 という名前で以下のソースファイルを作成する。

import x10.io.Console;
class HelloWholeWorld {HelloWholeWorld.x10
　public static def main(Array[String]) {
　　finish for (p in Place.places()) {
　　async at (p)
　　Console.OUT.println("Hello World from place" +p.id);
　　}
　}
}

次に x10c++ というコンパイラでコンパイルを行ってバイナリを作成する。
x10c++ -o HelloWholeWorld HelloWholeWorld.x10

実行結果
runx10 HelloWholeWorld
Hello World from place0

X10 のビルド

X10 のビルドについて。

SC11 で X10 の Tutorial が行われた。資料は現在公開中。
SC'11 Tutorial Materials Available

X10 のソースからのビルドに必要な環境は以下の通り。
◯Java 6.0 compatible SDK.
◯ant 1.7 or better
◯g++ 4.2 or better

これらの条件を満たす CentOS 6 や Fedora 16 では簡単にビルドは終わる。

svn co https://x10.svn.sourceforge.net/svnroot/x10/trunk x10-trunk
cd x10-trunk/x10.dist
ant dist

CentOS 5 はこれらの条件を満たさないので、yum で gcc44 やjava-1.6.0-openjdk をインストールする。ant は最新版を別途インストールする方が良い。jni.h が見つからないと言われることがあるので注意を（適当な場所にコピーしたり、シンボリックリンクを貼ってもよい）。
ただし、CentOS 5 (RHEL 5) にはバイナリ配布もあるので、そちらを使うこともできる。

SDPA 1998年 v.s. SDPA 2011年

久しぶりに自分の博士論文を見る機会があったので、1998年当時の SDPA 4.1.0 と現在の SDPA 7.4.0 の性能を比較してみた。アルゴリズム、実装それに計算機などの差があるので、以下のように 1998 年と現在を比較すると爆速になっている。それでも制御系の問題は高速化するのは比較的難しい。

◯問題 m1250.dat-s ：最大カット問題
SDPA 4.1.0 (1998年) 111615.9秒
SDPA 7.4.0 (2011年) 9.4秒

◯問題 control11.dat-s：制御系
SDPA 4.1.0 (1998年) 6903.0秒
SDPA 7.4.0 (2011年) 26.8秒

◯問題 theta6.dat-s：最大クリーク問題
SDPA 4.1.0 (1998年) 19028.7秒
SDPA 7.4.0 (2011年) 9.3秒


◯計算サーバ 1998年
DEC AlphaServer 8400
CPU : Alpha21164A-437MHz
メモリ：8GB

◯計算サーバ 2011年
CPU : インテル(R) Xeon(R) プロセッサー X5670(2.93GHz: TurboBoost 3.2GHz、12MB キャッシュ、6.4 GT/s QPI) x 2個
メモリ： 128GB (16X8GB/2R/1333MHz/DDR3 RDIMM/CPUx2)
OS : CentOS 5.7 for x86_64

停電とネットワーク停止

１２月２６日の全館停電のため以下のようにネットワークも停止します。そのため以下の期間では全てのサーバ(メールや Web 関係、Online Solver等)が停止します。再会は２７日夕方の予定です。

【ネットワーク停止について】
停止期間 ： １２月２５日（日）１５：００ ～ １２月２７日（火）１６：００（予定）

【停電について】
停電日時 ： １２月２６日（月）８：００ ～ １７：００
停電範囲 ： 後楽園キャンパス全館

JORSJ SCOPE 特集号

以下のように JORSJ の SCOPE 特集号が刊行されました。５月くらいから本格的に論文を募集しまして、７月に投稿〆切となりました。スケジュール的には厳しいものがありましたが、関係者の皆様のご協力によって予定通り Vol.54, No.4 として刊行することができました。その他の経緯等については以下の EDITORIAL INTRODUCTION をご覧下さい。

JORSJ, Vol.54 No.4

EDITORIAL INTRODUCTION
Katsuki Fujisawa and Jun-ya Gotoh (Chuo University)

LAGRANGIAN RELAXATION AND PEGGING TEST FOR LINEAR ORDERING PROBLEMS
Noriyoshi Sukegawa, Yoshitsugu Yamamoto, and Liyuan Zhang (University of Tsukuba)

AN EXTENSION OF THE ELIMINATION METHOD FOR A SPARSE SOS POLYNOMIAL
Hayato Waki and Masakazu Muramatsu (The University of Electro-Communications)

LOWER BOUNDS FOR THE MAXIMUM NUMBER OF SOLUTIONS GENERATED BY THE SIMPLEX METHOD
Tomonari Kitahara and Shinji Mizuno (Tokyo Institute of Technology)

A NONLINEAR CONTROL POLICY USING KERNEL METHOD FOR DYNAMIC ASSET ALLOCATION
Yuichi Takano (Tokyo Institute of Technology) and Jun-ya Gotoh (Chuo University)

LAGRANGIAN-BASED COLUMN GENERATION FOR THE NODE CAPACITATED IN-TREE PACKING PROBLEM
Yuma Tanaka, Shinji Imahori, and Mutsunori Yagiura (Nagoya University)

MAXIMUM FLOW-COVERING LOCATION AND SERVICE START TIME PROBLEM AND ITS APPLICATION TO TOKYO METROPOLITAN RAILWAY NETWORK
Ken-ichi Tanaka (The University of Electro-Communications)

NETAL: HIGH-PERFORMANCE IMPLEMENTATION OF NETWORK ANALYSIS LIBRARY CONSIDERING COMPUTER MEMORY HIERARCHY
Yuichiro Yasui, Katsuki Fujisawa (Chuo University), Kazushige Goto (Microsoft Corporation), Naoyuki Kamiyama (Kyushu University), and Mizuyo Takamatsu (Chuo University)

gcc 4.6.2 v.s. Intel Compiler 12.1.0 その２

前回と同じ実験を今度は nehalem 系の Xeon のマシンで行ってみた。やはり gcc 4.6.2 と Intel Compiler 12.1.0 の性能は拮抗している。最新判の SDPA 7.4.0 が gcc 4.6.2 でコンパイル出来ないのが残念なところ。

◯問題 theta6.dat-s
gcc 4.6.2 (SDPA 7.3.2)：12.770秒
icc 12.1.0 (SDPA 7.3.2)：12.360秒
icc 12.1.0 (SDPA 7.4.0 ILP64)：11.235秒

◯問題 nug12_r2.dat-s
gcc 4.6.2 (SDPA 7.3.2)：151.134秒
icc 12.1.0 (SDPA 7.3.2)：150.020秒
icc 12.1.0 (SDPA 7.4.0 ILP64)：144.879秒

◯問題 FH2+.1A1.STO6G.pqgt1t2p.dat-s
gcc 4.6.2 (SDPA 7.3.2)：99.944秒
icc 12.1.0 (SDPA 7.3.2)：97.561秒
icc 12.1.0 (SDPA 7.4.0 ILP64)：98.494秒

○計算サーバ (2 CPU x 4 コア = 8 コア)
CPU : Intel Xeon 5550 (2.66GHz / 8MB L3) x 2
Memory : 72GB (18 x 4GB / 800MHz)
OS : Fedora 16 for x86_64

CREST研究員＆研究補助員募集中

当 CREST で現在研究員と研究補助員を募集中です。詳しくは以下をご覧下さい。適任者が現れて採用が決定次第、早めに採用を打ち切ります。

http://jrecin.jst.go.jp/seek/SeekJorDetail?fn=0&id=D111120772&ln_jor=0

http://jrecin.jst.go.jp/seek/SeekJorDetail?fn=0&id=D111120770&ln_jor=0

gcc 4.6.2 v.s. Intel Compiler 12.1.0

gcc 4.6.2 (Fortran も含む) と Intel Compiler 12.1.0 (Fortran も含む)の対決。ちなみに MUMPS の影響で SDPA 7.4.0 は gcc でのコンパイルが正常に出来ない。

◯意外と gcc (4.6.2) は速い
◯F3 式律速型の問題（FH2+.1A1.STO6G.pqgt1t2p.dat-s)では SDPA 7.4.0 と Intel Compiler の組み合わせが速い


◯問題 theta6.dat-s
gcc 4.6.2 (SDPA 7.3.2)：12.715秒
icc 12.1.0 (SDPA 7.3.2)：16.361秒
icc 12.1.0 (SDPA 7.4.0 ILP64)：15.845秒

◯問題 nug12_r2.dat-s
gcc 4.6.2 (SDPA 7.3.2)：87.151秒
icc 12.1.0 (SDPA 7.3.2)：93.600秒
icc 12.1.0 (SDPA 7.4.0 ILP64)：88.441秒

◯問題 FH2+.1A1.STO6G.pqgt1t2p.dat-s
gcc 4.6.2 (SDPA 7.3.2)：59.100秒
icc 12.1.0 (SDPA 7.3.2)：62.121秒
icc 12.1.0 (SDPA 7.4.0 ILP64)：48.910秒


○計算サーバ (4 CPU x 12 コア = 48 コア)
CPU : AMD Opteron 6174 (2.20GHz / 12MB L3) x 4
Memory : 256GB (16 x 16GB / 1066MHz)
OS : Fedora 16 for x86_64

現在進行中の SDPA(SDPARA)関連の研究

現在進行中の SDPA(SDPARA)関連の研究は以下の通りです。アルゴリズム的にも HPC 的にもまだまだ改良＆高速化の余地は大きいようです。

1: TSUBAME 2.0 のような CPU + GPU システム上での SDPARA の Cholesky 分解の高速化

2: SDPARA(SDPA)の X10 化

3: SDPA での解の精度向上（主双対内点法終了後に解の精度を高めるため、様々な補正作業を行う）