研究日誌。

大規模なグラフ処理に対してメモリ階層構造を考慮した高性能なソフトウェアを開発。

広告

※このエリアは、60日間投稿が無い場合に表示されます。記事を投稿すると、表示されなくなります。

自己紹介(last update: 2014.04.15)

2014-06-20 14:50:55 | Weblog
研究日誌。
大規模なグラフ処理に対してメモリ階層構造を考慮した高性能なソフトウェアを開発。


○ Graph500 & Green Graph500
・November 2013:
Single-node (SGI Altix UV1000 @ JAIST) で最速の 50 位 (SCALE30 で 37.66 GTEPS)
Single-server (Intel(R) Xeon(R) E5-4650 x 4 sockets @ 中大) で最速の 51 位 (SCALE27 で 31.65 GTEPS)
Green Graph500 Small Data category で, Xperia-A-SO-04E で 1位 (153.17 MTEPS/W and 0.478 GTEPS) を達成.


・June 2013:
公式リストとして世界最高 64.12 MTEPS/W を記録し、1, 2, 3, 4, 5 位を独占
(上位12エントリー中, 6位以外の11エントリーを独占).


・November 2012:
CPU のみを使用した Single-node で最高位 (52 位) SCLAE26 / 10.4953 GTEPS を達成。
非公式 Green Graph500 で、世界最高 51.619 GTEPS/kW を達成, 1, 2, 3, 4, 5 位を独占。
2013年3月公式ウェブページ上に Unofficial list として公開。

・June 2012:
Single-node (CPU のみ) では 32位の SCLAE29 / 5.68 GTEPS が最高速。
その後リストの更新があり、SCALE 26 8.15 GTEPS として 25 位にランクイン。
Single node では CPU/GPU/FPGA 含めても世界最高速。


○ NUMA (Non-uniform Memory Access) アーキテクチャを考慮した並列アルゴリズムの高速化
・NUMA を考慮するためのライブラリ ULIBC (Ubiquity library for intel- ligently binding cores)
・並列 Simpath アルゴリズムに対する高速化
・半正定値計画問題に対する汎用高性能ソルバ SDPA に対する高速化と性能解析


○ NETAL (最短路問題 & 中心性計算)
・NETAL (NETwork Analysis Library) の開発
・9th DIMACS の参照実装に比べて、同一メモリ要求量で4倍の高速化を達成したダイクストラ法 (SSSP)
・9th DIMACS の参照実装の 229 倍の性能を達成した最短路"長"計算 (Multi-Source Label-Correcting + NUMA)
・全米道路ネットワーク USA-road-d.USA.gr に対する全対全最短路長計算を 7.75 日で終了
・複数の指標 (Closeness, Graph, Stress, and Betweenness) を同時に計算しつつ GraphCT の数十倍の性能
コメント
この記事をはてなブックマークに追加

Fast & Energy-Efficient Breadth-First Search on a Single NUMA System

2014-04-15 10:37:19 | Weblog
こちらでも紹介いただいていますが、ISC14 (International Supercomputing Conference) に投稿していた論文が採択されました。ISC14 プログラムも公開されています。

内容は Graph500 (Nov. 2013) と Green Graph500 (Nov. 2013) での成果をまとました。
・我々の既存研究 Hybrid BFS + NUMA を更に改善 (2.68 倍)
・実行時間の大部分を占めている Bottom-up での探索枝削減と、CSR グラフに対する in-direct アクセスの削減
・実ネットワークに対する計算機実験
・SGI Altix UV1000 上での性能解析
・Intel Xeon サーバや、Android device 上での電力性能解析

Title:
Fast & Energy-Efficient Breadth-First Search on a Single NUMA System

Authors:
Yuichiro Yasui, Chuo University & JST CREST
Katsuki Fujisawa, Chuo University & JST CREST
Yukinori Sato, JAIST & JST CREST

Abstract:
Breadth-first search (BFS) is an important graph analysis kernel. The Graph500 benchmark measures a computer's BFS performance using the traversed edges per second (TEPS) ratio. Our previous nonuniform memory access (NUMA)-optimized BFS reduced memory accesses to remote RAM on a NUMA architecture system; its performance was 11 GTEPS (giga TEPS) on a 4-way Intel Xeon E5-4640 system. Herein, we investigated the computational complexity of the bottom-up, a major bottleneck in NUMA-optimized BFS. We clarify the relationship between vertex out-degree and bottom-up performance. In November 2013, our new implementation achieved a Graph500 benchmark performance of 37.66 GTEPS (fastest for a single node) on an SGI Altix UV1000 (one-rack) and 31.65 GTEPS (fastest for a single server) on a 4-way Intel Xeon E5-4650 system. Furthermore, we achieved the highest Green Graph500 performance of 153.17 MTEPS/W (mega TEPS per watt) on an Xperia-A SO-04E with a Qualcomm Snapdragon S4 Pro APQ8064.

コメント
この記事をはてなブックマークに追加

NUMA-optimized Parallel Breadth-first Search on Multicore Single-node System

2013-08-12 09:12:26 | Weblog
こちらでも紹介いただいているが、IEEE BigData 2013 に提出していた論文 (regular paper) が採択されました。採択率が 17.37% と低いので採択されてほっとしました。

内容は CPU-based の single-node 上での並列幅優先探索に対する NUMA を考慮した高速化です。
・基本的なアルゴリズムは Beamer による Hybrid algorithm
・隣接枝リストに対する列方向分割によって、各スレッドのリモート RAM へのメモリアクセスを大幅に削減
・CPU Affinity と local allocation に関するライブラリを開発し、それをベースに実装
・SCALE 26 の Kronecker graph (点数 2^26, 枝数 2^30) で 11.15 GigaTEPS (TEPS は BFS における 1 秒間辺りの探索枝数) を達成
・ほぼ同じ計算機環境で Beamer の実装 (5.1 GTEPS) に比べ 2 倍強の高速化を達成


"NUMA-optimized Parallel Breadth-first Search on Multicore Single-node System"

has been accepted as a regular paper presentation. This year, we have received 259 submissions, only 45 are accepted as regular papers (acceptance rate 17.37%). Papers went through a rigorous review process. Each paper was reviewed by at least three program committee members (most of them are five and some even more). All the paper decisions are made from the weighted scoring of the reviewing reports.

Title:
NUMA-optimized Parallel Breadth-first Search on Multicore Single-node System

Author:
Yuichiro Yasui, Katsuki Fujisawa, and Kazushige Goto

Abstract―The breadth-first search (BFS) is one of the most important kernels in graph theory. The Graph500 benchmark measures the performance in traversed edges per second
(TEPS) for each supercomputer performing a BFS. Previous studies have proposed a hybrid approach that combines a wellknown top-down algorithm and an efficient bottom-up algorithm for large frontiers. This reduces some unnecessary searching of outgoing edges for a large frontier in BFS traversal of a smallworld graph such as a Kronecker graph. In this paper, we describe a highly efficient BFS using column-wise partitioning of the adjacency list while carefully considering the NUMA architecture system. We explicitly manage how each working thread accesses a partial adjacency list in local memory during BFS traversal. Our implementation has achieved a processing rate of 11.15 billion edges per second on a 4-way Intel Xeon E5-4640 system for a scale-26 problem of a Kronecker graph with 2^26 vertices and 2^30 edges.
コメント (2)
この記事をはてなブックマークに追加

Graph500, Green Graph 500 (June 2013)

2013-06-19 02:48:39 | Weblog
Graph 500 と Green Graph 500 が更新された。

◯ Graph 500 - http://www.graph500.org/results_jun_2013
上位を IBM - BlueGene/Q が独占するという状況に大きな変化なしだが、主な変更点は以下のエントリーだろう。
・2 位:mira (49152 nodes, SCALE40, 14328 GE/s) の更新(前回は 32768 node, SCALE39, 10461 GE/s)。
・6 位:Tianhe-2 (4096 nodes, SCALE36, 1427 GE/s 8192 nodes, SCALE 36, 2061.48 GE/s) で追加。
・13 位:Oakleaf-FX (4800 nodes, SCLAE38, 992.6 GE/s) の更新(前回は 4800 nodes, SCLAE38, 609.37 GE/s)。

なお 13 位の Oakleaf-FX は Graph CREST チーム(東工大チーム)の成果であり、
前回の 609.37 GE/s から 992.6 GE/s へ 1.6 倍の性能向上となっており、
前回と同様の計算機環境と SCALE なので実装やアルゴリズムによる高い性能向上が示された。
非 BlueGene/Q ということも注目して頂きたい。


◯ Green Graph 500 - http://green.graph500.org/lists.php
今回が第1回目のリスト発表となったが、案の定(?)、Big Data category と Small Data category に分けての発表に。
SCALE 30 がしきい値になっている模様で、無理にでも SCALE 30 を解かなかったことが正直悔やまれる。

● Big Data category
・1位:JUQUEEN が 5.41 MTEPS/W
・2位:Mira が 4.42 MTEPS/W
・3位:Sequoia が 3.55 MTEPS/W
このように Big Data category では上位を IBM - BlueGene/Q が独占するという Graph 500 と同様の結果に。



● Small Data category
続いて Small Data category では、私の実装が上位 5 エントリーを占め、
上位 12 エントリーでも私の実装が 11つを占めているという状況でこちらは予想通りの結果となっている。

解説すると、まず 1位の GraphCREST-Tegra は名前から連想されるように Android タブレット機での実験となっており、
Android NDK を用いてポーティングしているが、色々と細かい Linux との違いにより簡単ではなかった印象。
また 2, 3, 4, 5 位のうち 2位と3位 が低電力デスクトップ機、4位と5位がノートPC機とよく似た計算機構成で、
いずれも 53.82 MTEPS/W と 53.47 MTEPS/W 、52.02 MTEPS/W と 51.62 MTEPS/W で同等の性能となっている。
一方、サーバ機としては 6 位の TH-IVB-FEP/C (Tianhe-2 1node) に最高値 39.29 MTEPS/W となっている。
油冷サーバ機である 8 位の ULP2012 ultra-green oil-cooled server: GraphCREST の 30.41 MTEPS/W を超えてきたところを考えると、
Tianhe-2 は電力効率もかなり考慮されていると予想される。

コメント (2)
この記事をはてなブックマークに追加

Graph500 参照実装に Hybrid algorithm が追加。

2013-06-03 07:52:17 | Weblog
今回の Graph500 も締切である 6/9 が迫ってきている。
tar.gz の形では 2.1.4 が最新版であるが、
gitorious として https://www.gitorious.org/graph500/graph500 で最新版が公開されている。
なお最新の OpenMP 版の参照実装では Beamer's hybrid algortihm が選択され、
bfs_top_down_step 関数と bfs_bottom_up_step 関数が ./omp-csr/omp-csr.c に実装されている。

早速、以下の環境で試したところ、
性能は max_TEPS は 0.138 GTEPS から 0.506 GTEPS へ 4 倍ほど向上しているもののあまり高くなく、
こちらの top-down だけの結果 0.9 GTEPS の半分ほどに留まっている。


◯ reference 2.1.4 (top-down only)
SCALE: 25
nvtx: 33554432
edgefactor: 16
terasize: 8.58993459199999983e-03
A: 5.69999999999999951e-01
B: 1.90000000000000002e-01
C: 1.90000000000000002e-01
D: 5.00000000000000444e-02
generation_time: 1.23237174159999991e+01
construction_time: 3.05671973749999992e+01
nbfs: 64
min_time: 3.88694007799999985e+00
firstquartile_time: 4.68514209449999974e+00
median_time: 5.03964143450000002e+00
thirdquartile_time: 5.32009851299999958e+00
max_time: 5.88019123399999977e+00
mean_time: 4.98084942437500011e+00
stddev_time: 4.85448413602338535e-01
min_nedge: 5.36865498000000000e+08
firstquartile_nedge: 5.36865498000000000e+08
median_nedge: 5.36865498000000000e+08
thirdquartile_nedge: 5.36865498000000000e+08
max_nedge: 5.36865498000000000e+08
mean_nedge: 5.36865498000000000e+08
stddev_nedge: 0.00000000000000000e+00
min_TEPS: 9.13006867694670707e+07
firstquartile_TEPS: 1.01863404233317941e+08
median_TEPS: 1.06898666529981360e+08
thirdquartile_TEPS: 1.15519255795902520e+08
max_TEPS: 1.38120343310319483e+08
harmonic_mean_TEPS: 1.07785932128909156e+08
harmonic_stddev_TEPS: 1.32352296245960379e+06


◯ gitorious 版 reference (6/2) (hybrid algorithm)
SCALE: 25
nvtx: 33554432
edgefactor: 16
terasize: 8.58993459199999983e-03
A: 5.69999999999999951e-01
B: 1.90000000000000002e-01
C: 1.90000000000000002e-01
D: 5.00000000000000444e-02
generation_time: 3.86461791213000026e+02
construction_time: 2.06101513767999990e+02
nbfs: 64
min_time: 6.54244530000000074e-02
firstquartile_time: 6.65645294999999970e-02
median_time: 6.69244999999999979e-02
thirdquartile_time: 1.36217951174999996e+00
max_time: 1.74811406399999991e+00
mean_time: 6.78686857937500054e-01
stddev_time: 6.71586582494595130e-01
min_nedge: 0.00000000000000000e+00
firstquartile_nedge: 0.00000000000000000e+00
median_nedge: 0.00000000000000000e+00
thirdquartile_nedge: 5.36865498000000000e+08
max_nedge: 5.36865498000000000e+08
mean_nedge: 2.51655702187500000e+08
stddev_nedge: 2.70025835680461287e+08
min_TEPS: 0.00000000000000000e+00
firstquartile_TEPS: 0.00000000000000000e+00
median_TEPS: 0.00000000000000000e+00
thirdquartile_TEPS: 3.94570124163497090e+08
max_TEPS: 5.05953774048208296e+08
harmonic_mean_TEPS: 8.34498407303683162e+08
harmonic_stddev_TEPS: 1.15107849422285736e+08


◯ 計算機環境
Intel(R) Xeon(R) CPU E5-4640 0 @ 2.40GHz
4-way x 8-cores x 2-HT = 64 threads
512 GB RAM
gcc 4.4.7
コメント
この記事をはてなブックマークに追加

筑波大学「地理情報と視覚化」の研究会 2013(GODIVA研究会2013)

2013-02-18 11:42:27 | Weblog

GODIVA 2013 で Graph500 や YouTubeでお馴染みの数え上げアルゴリズム などについてお話させて頂きます。

Graph500 における並列 BFS の高速化技術と、knuth が Art of Computer Programming, Volume 4, Fascicle 1 で提案した ZDD を用いたパス列挙アルゴリズム Simpath の高速化の関連性について紹介させて頂きます。本手法は高性能数値計算に対して幅広く利用可能な高速化技術です。最近では半正定値計画ソルバ SDPA に適用してその効果を確認することができました。

 

筑波大学「地理情報と視覚化」の研究会 2013(GODIVA 研究会 2013)


日時:2013年2月26日(火曜日)
場所:筑波大学3B210(つくば市天王台1-1-1)
http://www.tsukuba.ac.jp/access/tsukuba_access.html
http://www.tsukuba.ac.jp/access/map_central.html
時間:13:00-16:30
プログラム:

1.高校生発表(90分)
1)日立北高校
2)緑岡高校
3)竜ヶ崎第一高校

2.研究者発表(30分)
 安井雄一郎(中央大学理工学部 & JST CREST)
    Graph500 における BFS 高速化技術を適用した並列パス列挙アルゴリズム


3.学生生発表(60分)
1)笹圭樹(社会工学類4年)
津波時における高台避難の可能性と減災効果に関する研究
2)盆子原歩,浜津桃子(大学院社会システム工学専攻1年)
高萩再生計画
3)石濱友裕(大学院コンピュータサイエンス専攻2年)
『slitherlink』の最適化モデル

コメント
この記事をはてなブックマークに追加

Intel コンパイラ -xHost オプション

2013-01-29 10:13:42 | Weblog

こちらで取り扱っている実験を Graph500 についても行ってみた。
どうせなので ICC の -xHost オプションだけではなく、GCC or ICC と -Ox の最適化の組合せを色々試してみることにした。

この実装でも -xHost の効果は大きいものの、上位を gcc が占めることになった。
メモリアクセスの流れを整える等のある程度汎用的な高速化を行った実装では icc < gcc といえるだろう。

また、gcc では最適化レベル毎に生成されるバイナリサイズが大きくなるのに対して、
icc では O1 が最も小さい(しかも median TEPS が高い)という結果になっており、少々予想しづらく感じる。




"compiler"    "median TEPS"          MB
"icc -O0"             5.245      1.8503
"icc -O1"             9.987      1.7305
"icc -O2"             9.977      1.8545
"icc -O3"             9.850      1.8552
"icc -xhost"         10.072      1.8084
"gcc -O0"             6.164      1.6580
"gcc -O1"            10.738      1.8706
"gcc -O2"            10.887      1.8792
"gcc -O3"            10.834      1.9028



◯ 計算サーバ: Intel Xeon SandyBridge-EP (64 HT-cores)
CPU : Intel Xeon E5-4640 (8-core 2.40GHz, 16MB cache, TDP:95w) x 4
Memory : 512GB ACTICA製HPC専用メモリ DDR3 1600Mhz (16GB x 32枚) x 32
OS : CentOS 6.3

コメント
この記事をはてなブックマークに追加

日本数式処理学会東北地区合同分科会

2013-01-28 10:20:05 | Weblog
以下の研究会で招待講演で話させて頂きました。


日本数式処理学会東北地区合同分科会開催のご案内
URL : http://www.jssac.org/Joint/Conf/joint2012.html

2012年3月に開催された日本数式処理学会定期理事会第3号議案 において,「今後3年もしくは5年程度の期間学会の主催による研 究会を東北地域で開催する」ことが議決されました。これを受け て,東北地域の復興と会員および分科会相互の研究内容の理解など を目的として,東北地域において,日本数式処理学会のシステム・ 基礎理論・教育の3分科会による 合同研究会を下記のように開催致します。 皆様のご参加をお待ち申し上げます。

日本数式処理学会東北地区合同分科会
開催日 2013 年 1 月 26日(土) ~ 27日(日)
場所 仙台青葉カルチャーセンター 602号室
宮城県仙台市青葉区一番町2-3-10 カルチャー仙台ビル
http://www.culture.gr.jp/sendaiaoba/


招待講演
安井雄一郎(中央大学)
メモリ階層構造を考慮した大規模グラフ処理の高速化

藤澤克樹(中央大学)
大規模最適化問題に対するソフトウェア開発と高速&安定計算 --理論からスパコンまで--

中田真秀(理化学研究所情報基盤センター)
高精度線形代数演算ライブラリMPACK 0.8.0の紹介
コメント
この記事をはてなブックマークに追加

Graph500 / GreenGraph500 Nov. 2012

2012-12-10 11:34:23 | Weblog
List の更新は 1 ヶ月弱前になる。


1. Graph500
前回に引き続き 40 コア、80 スレッド上での Hybrid Algorithm 実装でエントリーを行った。
GraphCREST-Wex40 (HPCTECH Corporation - Intel(R) Xeon(R) CPU E7- 4870 @ 2.40GHz (4 sockets, 40 cores) / 1 node) / Chuo University
SCALE 26 / 10.4953 GTEPS

様々な高速化テクニックを入れて前回の 1.5 倍程の性能にはなったものの、力及ばず 1node 6 位。
Convey 社の 1node 実装を採用している 4 台にぎりぎりに競り負けてしまった。
いずれにしても 4 FPGA マシンでの「SCALE 29 / 14.56 GTEPS」は
こちらの westmere 40 コア上の実装では max TEPS でも出ない値で、これを抜くのは現時点では難しい。



2. GreenGraph500
今回は様々な計算機で上位入選を狙っていたのだがリストが公開されず残念だった。
Graph500 では結果を CSV ファイルとして公開しているので、
非公式なリストを作成してみたところ1~5位を独占しているという結果。
手の内をバラしてしまったので、今回のような結果にならないだろう。

コメント
この記事をはてなブックマークに追加

Graph500 List Nov. 2012

2012-10-13 19:33:19 | Weblog
今回の Graph500 List の〆切は 10/22 だそうです。

Submissions

November 2012 List
The submission deadline for the November list is October 22, 2012.

You must be logged in to access the submission form. If you do not have an account, request one here.

If you already logged in you can reach the submission form here

The following information will be collected:

Computer Information:
Computer/System Name
Manufacturer
Computer Type/Model
Installation Site
Location
Year of Installation/Last Major Upgrade
Field of Use: government, university, industry, etc.
Field of Application: geophysics, automotive, etc.
Number of Nodes
Number of Cores
Main Memory Size
Total system power
Interconnection network
Graph 500 Implementation Used: reference, custom, etc.
Contact Name
Contact Email
Benchmark Information:
Problem Scale
GigaTEPS
Graph Construction Time
Full Benchmark Result

http://www.graph500.org/
コメント
この記事をはてなブックマークに追加

OSX 上で MacPorts 環境を整える。

2012-09-06 15:10:56 | Weblog
OSX 上で MacPorts 環境を整えるための手順。

○ MacPorts 環境を整える
1. Command Line Tools for Xcode をインストール
a) App Store から探す
b) Xcode の Preferences... > Downloads から Command Line Tools を選択

ライセンス認証が必要
$shell > sudo xcodebuild -license

ちなみに全て intall すると 7GB ほどになるので容量が逼迫しやすい MacbookAir では要注意。


2. MacPorts をインストール
後から更新するので dmg で良い。簡単。


3. ポート制限のある環境でも MacPorts を使用したい場合
"sudo port selfupdate" は Macports の更新と portindex の更新を一度に行うが、
rsync を使用しているため、某大学などポート制限がある場合、失敗してしまう。

そこで http 経由で更新ができるように /opt/local/etc/macports/source を編集する。
(rsync から始まる行をコメントアウトして、http から始まる行を追加する。)
# rsync://rsync.macports.org/release/tarballs/ports.tar [default]
http://www.macports.org/files/ports.tar.gz [default]

上記の設定の後、"sudo port selfupdate" の代わりに以下の a) b) を用いる。

a) Macports の更新
$shell > sudo port -f install macports

b) portindex の更新
$shell > sudo port -d sync


4. 必要が有れば、環境変数 http_proxy などの設定を行う。


○ MacPorts の使い方
例えば GCC 4.7 を install するなら以下のようにすれば良い
なぜか途中で glpk を install していて驚いた。
$shell > sudo port install gcc47
コメント
この記事をはてなブックマークに追加

1 node Graph500 その5

2012-09-04 10:54:52 | Weblog
大きな SCALE での性能が向上したので、再び blog 更新。



まずは WestmereEX での結果から。
max は 10 GTEPS を超えるのが当たり前になりつつある。
SCALE 27 以降の性能改善まであと一歩といったところ。

SCALE 26 時の median が 10.066 GTEPS かつ、有効電力が 1000.6 W であるので、10.060 GTEPS/kW となる。
これは 25位の convey の結果と同等。

○ 4-way Westmere-EX サーバ (20-cores x 4-NUMA-nodes = 80-threads)
Intel(R) Xeon(R) CPU E7-4870 @ 2.40GHz, 512 GB RAM




続いて、SandyBridge-EP での結果。
こちらは SCALE によって性能が上下せず非常に安定している。
クロックが低いにも関わらず非常に性能が良い。

SCALE 26 時の median が 5.607 GTEPS かつ、有効電力が 362.0 W であるので、15.489 GTEPS/kW となる。

○ 2-way SandyBridge-EP サーバ (16-cores x 2-NUMA-nodes = 32-threads)
Intel(R) Xeon(R) E5-2650 @ 2.00GHz, 256 GB RAM




お遊びでやったつもりが予想以上に GTEPS/kW が高く驚いた。
SCALE 21 時の median が 0.856 GTEPS かつ、AC アダプタ容量が 45 W であるので、単純に計算しても 19.022 GTEPS/kW となる。
思わぬ伏兵ができたので、これを鍛えて 20 GTEPS/kW 以上を狙うのも良いかもしれない。

○ MacbookAir 13inch (4-cores x 1-NUMA-nodes = 4-threads)
Intel(R) Corei5 2557M CPU @ 1.70GHz, 4 GB RAM
Macports GCC 4.5.4 を使用。
購入時 Lion でその後 Mountain Lion に update。
コメント
この記事をはてなブックマークに追加

1 node Graph500 その4

2012-08-31 17:21:27 | Weblog
またまた更新。version 3.26 に。
今度は WestmereEX だけではなく、MagnyCours でも実験。
絶対性能では WestmereEX なのだが、MagnyCours の方がスケーラビリティが良い。
もちろん WestmereEX での性能低下の原因を解決する策もあるので、修正できると思われる。

○ 4-way Westmere-EX サーバ (20-cores x 4-NUMA-nodes = 80-threads)
Intel(R) Xeon(R) CPU E7- 4870 @ 2.40GHz, 512 GB RAM


○ 4-way Magny-Cours サーバ ( 8-cores x 6-NUMA-nodes = 48-threads)
AMD Opteron(tm) Processor 6174 @ 2.20GHz, 256 GB RAM
コメント
この記事をはてなブックマークに追加

1 node Graph500 その3

2012-08-29 17:54:36 | Weblog
現在、絶賛高速化中で、ようやく Parallel BFS の挙動が分かってきた。
最新の実装は、現時点の最新のリストである Graph500 june 2012 list と比較すると 1 node で最も高速な実装となっている。
SCALE 26 で median 値が 9.69 GTEPS となり、
これまでの 25 位の SCALE 27 で 7.85 GTEPS に対して 2 GTEPS 弱の差をつけることができた。


----------------------------------------------------------------------
Parallel Breadth-First Search for Graph500 Benchmark version 3.24
----------------------------------------------------------------------
CPU name is Intel(R) Xeon(R) CPU E7- 4870 @ 2.40GHz
freq / RAM is 2400.107 MHz / 504.78 GB
#cpu, #nodes, #cores is 80 4 20
COMPILER is GCC (GNU C Compiler) version 4.4.6
----------------------------------------------------------------------
scale, edgefactor is 26 16
#threads, #NUMAs is 80 4
mpol_bind is ON(mmap with mbind(MPOL_BIND))
mem_interleave is OFF
switching parameter is 0.000035 (n ~= 2.348810e+03)
queue buffer size is 65536
----------------------------------------------------------------------
SCALE: 26
nvtx: 67108864
edgefactor: 16
terasize: 1.71798691839999997e-02
A: 5.69999999999999951e-01
B: 1.90000000000000002e-01
C: 1.90000000000000002e-01
D: 5.00000000000000444e-02
generation_time: 2.68578929901123047e+01
construction_time: 2.17296519279479980e+01
nbfs: 64
min_time: 1.02756023406982422e-01
firstquartile_time: 1.09368681907653809e-01
median_time: 1.10972046852111816e-01
thirdquartile_time: 1.15135550498962402e-01
max_time: 1.40076875686645508e-01
mean_time: 1.13488256931304932e-01
stddev_time: 7.59083816189232759e-03
min_nedge: 1.07373120400000000e+09
firstquartile_nedge: 1.07373120400000000e+09
median_nedge: 1.07373120400000000e+09
thirdquartile_nedge: 1.07373120400000000e+09
max_nedge: 1.07373120400000000e+09
mean_nedge: 1.07373120400000000e+09
stddev_nedge: 0.00000000000000000e+00
min_TEPS: 7.66529949170165730e+09
firstquartile_TEPS: 9.38029503046095467e+09
median_TEPS: 9.69146369931156921e+09
thirdquartile_TEPS: 9.84207161150045013e+09
max_TEPS: 1.04493261650201073e+10
harmonic_mean_TEPS: 9.46116570148694229e+09
harmonic_stddev_TEPS: 7.97284242052958459e+07


これまでは firstquartile ~ max だけの改善に留まっていたが、今回の更新で min が大きく改善され安定性が大幅に向上している。
当初、min が低いのは Hybrid Algorithm の切り替え失敗が原因であると予想していたのだが、
実際には負荷分散がうまくいっていないことが性能低下の主要因であったらしい。
4-way WestmereEX という構成は実コアとして 40 コア、HyperThreading で 80 コアと非常に多く、
負荷分散の重要性を再確認した。

ちなみにこの実装ではある程度大きい SCALE からはスレッド数を 80 と設定したときが最も良い性能となっており、
以下に示すいずれの結果もスレッド数を 80 に設定している。

○ 4-way Westmere-EX サーバ (20-cores x 4-NUMA-nodes = 80-threads)
Intel(R) Xeon(R) CPU E7- 4870 @ 2.40GHz, 512 GB RAM

○ Graph500
http://www.graph500.org/results_june_2012

コメント
この記事をはてなブックマークに追加

1 node Graph500 その2

2012-08-23 01:29:54 | Weblog
アイディアを片っ端から試して、TEPS 値を更新中。
前回に比べて y 軸が大きくなっているので比較の際は注意が必要。

firstquartile median thirdquartile max の差が小さくなっており、安定性が向上している模様。
min は hybrid algorithm の切り替え失敗に相当しており、パラメータをチューニングすれば向上すると思われる。
不可解な挙動に関する理由付けの目星は付いたので、後は裏を取る作業だけ。

○ 4-way Westmere-EX サーバ (20-cores x 4-NUMA-nodes = 80-threads)
Intel(R) Xeon(R) CPU E7- 4870 @ 2.40GHz, 512 GB RAM

コメント
この記事をはてなブックマークに追加