研究日誌。

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

全対全最短路問題 - その2

2010-04-30 02:14:57 | Weblog
最短路ソルバの version も 1.00 として、コア部分の高速化はまだまだ余地があるかもしれないが、形としてはほぼ完成といったところだ。

そこで DEBUG を含めてベンチマークを行った。
以前紹介した「GPU上で高速なブロック化フロイド・ワーシャル法」であるが、実験に用いたグラフが断定できたので、再度比較実験を行った。

これを 4.94sec. で解けるそうなので、思ったよりも性能が良い。

Random-13.0.0.gr ( 8192 nodes / 32768 arcs )
1. 円周上に点を配置
2. 円周上にサイクルを作成する ( 8192 arcs )
3. 残りの枝 ( 3m = 24576 arcs ) は、ランダム２点を選び張っていく

[GPU]
CPU : Intel(R) Core(TM) i7 CPU 940 @ 2.93GHz
GPU : nVIDIA GeForce GTX 280
OS : Windows XP x64
CUDA : 2.3

[CPU1]
CPU : Intel(R) Core(TM) i7 CPU 940 @ 2.93GHz (8cores)
GCC : 4.4.3

[CPU2]
CPU : Intel(R) Xeon(R) CPU X5550 @ 2.67GHz (8cores)
GCC : 4.4.3

           1      2      4      8 [sec.]
GPU    4.869
CPU1  10.222  5.104  3.218  2.901
CPU2  10.992  5.515  2.753  1.391





密グラフに対するダイクストラ法。

2010-04-29 01:52:29 | Weblog
「アルゴリズム・クイックリファレンス」には実験に用いたソースコードが添付されている。せっかくあるので、こちらで開発したプログラムと比較実験を行った。

用いた密グラフは TSPLIB の gr9882.tsp を変換したもので、非常に密。

graph : gr9882.tsp(TSPLIB) -> 9,882 nodes 48,822,021 arcs
Query : ss x 1
CPU   : Xeon X5460 3.16GHz

Dijkstra's algorithm with Priority Queue        12.73 sec.
Dijkstra's algorithm for Dense Graph            13.25 sec.
Optimized Dijkstra's algorithm for Dense Graph   0.51 sec.
Bellman-Ford algorithm                          43.82 sec.

msp-1.03(Dijkstra's algorithm with binary-heap)  0.30 sec.

密でもそこそこ性能出るようだ。

アルゴリズム・クイックリファレンス

2010-04-28 14:31:21 | Weblog
非常に興味深い本が O'Reilly Japan から発売されたので早速買ってみた。
単にアルゴリズムの羅列ではなく実装し、その特性を実際に検証しているといった、非常に好感の持てる内容。しかもそのソースコードを公開してくれているという、何ともコストパフォーマンスが高い本。

分量の制約からか、理論的計算量と実装後の性能に関して踏み込んだ議論がなされていないものの、その入り口付近まで最短で連れて行ってくれる印象を受ける。

実行後の性能を意識しつつ、アルゴリズムを学びたいといった視点ならば、間違いないと思える１冊。

PHP: １度だけ実行

2010-04-26 15:07:40 | Weblog
これを 
<meta http-equiv="refresh" content="1">
すると, ソルバ実行中のstdout/stderrをリアルタイムっぽく表示してくれる.
<?php
session_start();
if ( isset($_SESSION['status']) && $_SESSION['status'] == 'done' ) {
  header("Location: result.php");
  exit;
}

if ( isset($_POST['job']) ) {
  /* execute once */
  $command = solve_command();
  $buffer = uniq_name();
  system($command . " > " . $buffer . " 2>&1 " . "&");
  $_SESSION['command'] = $command;
  $_SESSION['buffer']  = $buffer;
  $_SESSION['status']  = 'running';
} else {
  $command = $_SESSION['command'];
  $buffer  = $_SESSION['buffer'];
  $fp = fopen($buffer, "r");
  if ( !$fp ) {
    die("cannot open buffering file.");
  }
  echo "<pre>";
  fpassthru($fp);
  echo "</pre>";
  $_SESSION['status'] = 'done';
}
?>


Online Solver: ソルバ実行その2

2010-04-25 14:06:07 | Weblog
一つ前の記事で、実行の大まかな流れを説明した。

この処理を次の4つのPHPファイルで実現している。
submit.php, execute.php, result.php, download.php


■ submit.php
問題、ソルバ、引数などを選択し、execute.php に渡す。
また、実行フラグ($_POST[])を立てておく。


■ execute.php
1. auto refresh (1sec.毎)
2. 実行フラグ($_POST[])が立っていれば...
- ソルバ実行
- 実行中フラグ($_SESSION[])を立てる

3. 実行フラグ($_POST[])が立っていなければ...
- 実行中フラグ($_SESSION[])が立っていれば、実行中なのでソルバのstdout/stderrを出力する
- 実行中フラグ($_SESSION[])が立っていなければ、実行終了なので、result.phpへ移行

※$_POST[]で取得した実行フラグは明示的に引き継がない限り、auto refresh で消されることがミソ。


■ result.php
実行が終了すれば、こちらに移行してくる。
出力ファイルへのリンクと、実行結果を表示。
ぱっと見では [execute.php] と [result.php] の違いはないので、
ユーザからすると、リンクが増えて auto refresh が止まったように見える。


■ download.php
リンクをクリックすると出力ファイルをダウンロードできる。

Online Solver: ソルバ実行その1

2010-04-24 14:04:09 | Weblog
大体動くものができたので紹介。

基本 PHP で作っている。もちろん javascript を使えば見栄え良く作る事もできるが、今回はとにかくどの環境でも利用できるようなものを目指す。

1. html の <option> で問題, ソルバ, 引数を選択する

2. ソルバ実行中のstdout/stderrを表示
- auto refresh を用いて, ほぼリアルタイム(1sec.間隔など)にstdout/stderrを表示する

3. 実行終了
- 実行終了すれば auto refresh をやめ(ページ遷移)、出力ファイルのリンクを張る。

Ubuntu 10.04 @ Wubi

2010-04-23 01:44:17 | Weblog
Let's Note CF-W8 に wubi 経由で構築した ubuntu 9.10 を 10.04 に upgrade した。GUI の upgrade tool を用いて非常に簡単に行う事ができた。OOo が 3.2 ということで起動画面に Oracle のロゴが。MS-Office 向けの ODF コンバータの有償化で色々注目されている模様。

Fedora はすでに 13 らしいだが、Ubuntu の更新頻度もなかなか。

emacs 23 @ Vine Linux 5.x

2010-04-22 01:23:41 | Weblog
Emacs のデフォルトの設定がフリーカーソル状態のようで、↓(下矢印キー)を押し続けるとどこまでもいってしまう。

(setq next-line-add-newlines nil)
でoffにできるようなのだが、うまく行かない。

M-x customize
でも設定してみたが、一時的に off になって開き直す元に戻ってしまう。


2010.06.05追記
/usr/share/emacs-23.1/site-lisp/vine-default-base.el
132: (setq next-line-add-newlines 0)
132: (setq next-line-add-newlines nil)

ステディカム

2010-04-20 01:43:42 | Weblog
「世界ふれあい街歩き」という番組を見る事があるのだが、徒歩のようにゆったりと手ぶれが全くと行っていい程気にならない映像が流れる。

すごく不思議でいたのだが、調べてみると「ステディカム」という体に固定する撮影方法を用いているようである。以前、テレビ局で担がせてもらい業務用は個々まで重いのかと驚いた事があったことをふと思い出した。

MacOSX: program_invocation_name

2010-04-18 01:50:26 | Weblog
extern char *program_invocation_name;
extern char *program_invocation_short_name;

は MacOSX では使用不可。
というか、結構対応していないものなのだなーと。

GNU Gnulibの372ページより。
This variable is missing on some platforms: MacOS X 10.3, FreeBSD 6.0, NetBSD 3.0, OpenBSD 3.8, AIX 5.1, HP-UX 11, IRIX 6.5, OSF/1 5.1, Solaris 10, Cygwin, mingw, Interix 3.5.

PHP: 注意点。

2010-04-17 18:36:48 | Weblog
● PHP の配列はすべて連想配列なので、each で取り出すのが良さそう。

● print_r() で配列内のすべての要素を表示

● here document 内では変数は使用できるが、関数は使用できない

● 拡張子を replace したい時に使用したいとき
function replace_suffix($filename, $newsfx) {
    $oldsfx = pathinfo($filename);
    $oldsfx = '.' . $oldsfx['extension'];
    return strtr($filename, array($oldsfx => $newsfx));
}

Online Solver: ソルバ部分

2010-04-16 01:46:23 | Weblog
CSS での枠組みを利用しながら、基本的に PHP で書いている。

なので、短ければ echo / print でがんばり、長ければ ヒアドキュメントで頑張ることとなる。このヒアドキュメントはちょっと作法が良くない気もするのですが、ひとまず作ってみる事にした。

今回から多くの問題/ソルバに対応するが、選択中の問題、ソルバを GET で渡し、実行時の引数などは POST で渡す予定である。