研究日誌。

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

Online Solver: 枠組み作り

2010-04-15 18:36:15 | Weblog


さて、上手に組まれた CSS で枠組みを作ってしまうという思惑である。
これを使うと、以下のようにお手軽に作ることができる。
それから今まで文法とかよくわからずに状態で html 書いていたが、今回である程度適切な(?)書き方の勉強になった。

<body>

<!-- HEADER -->
<div id="header">
  <div id="logo">
    <!-- ロゴ -->
  </div>
  <div id="menu">
    <!-- メニュー -->
  </div>
</div>

<!-- PAGE -->
<div id="page">

  <div id="content">
    <div class="post">
      <!-- 記事のタイトル -->
      <div class="entry">
        <!-- 記事 -->
      </div>
    </div>
  </div>

  <div id="sidebar">
    <!-- サイドバー -->
  </div>
</div>

<div id="footer">
  <!-- フッター -->
</div>

</body>

CSS free template

2010-04-14 06:21:59 | Weblog
現在、複数の最適化ソフトウェアを統合した Online Solver の枠組みを開発中だが、こういうときにどのようなデザインするかは非常に悩むところ。本質ではないのだが、作った後からでは難しくなりそうなのと、詳しい方が作ったクオリティの高いインターフェイスを使わない手はないなと思い、検索してみると以下のようなサイトがヒット。

どちらかというと blog style かと思うのだが、これだ!と思うデザインがあったのでひとまず選択。どれも同じような方針で作られているので、外観は CSS を変更すれば簡単に変えられそうでなんだか楽しい。

CSS free template

もうしばらくお待ちを。

REAL: ALT + Reach

2010-04-13 06:24:51 | Weblog
ALT にさらに Reach を加えたものが REAL と呼ぶらしい。

Reach では、各点に到達限界値を保持させて、Landmark などと同様に探索範囲の限定に用いる。到達限界は、各点が最短路に含まれる際に、最も長いパス長である。

そのため非常に多くの最短路問題を繰り返し計算しなければならず、前処理に非常に時間がかかってしまう。そこで、Shortcuts を用いて前処理の高速化を行うようだ。

Shortcuts はその名の通りバイパスとなる枝を追加する事で、これを用いる事で効率よく到達限界値を計算することができる。

ALT: A* + Landmark + Triangle inequality その2

2010-04-12 06:22:45 | Weblog
Landmark & Triangle inequality による探索範囲の限定について。

1. Landmark は 16 点程で十分。
2. 選び方が重要

Landmark さえ決定してしまえば、前処理は至って簡単で、単に各 Landmark から1対全最短路問題を解くだけ。つまり各点は Landmark 分だけ変数が増える事になる。

Triangle inequality はこの Landmark を用いて行う。

ALT: A* + Landmark + Triangle inequality その1

2010-04-11 06:18:42 | Weblog
まずはそれぞれの説明から。

● A*
探索の方向に傾斜を付けて、探索範囲を狭める。

● Landmark
16 点ほどの Landmark を用意し、探索方向を狭める

● Triangle inequality(三角不等式)
三角不等式により、探索方向を狭める

これらの特徴をうまく合わせたのが ALT となる。結局は探索の方向に傾斜を付ける A* algorithm なのだが、Landmark & Triangle inequality との組合せることで良い bound を得る事ができるようだ。

時空間ネットワークには前処理がいらない?

2010-04-10 06:21:33 | Weblog
避難経路探索では時系列ネットワーク上の最短路問題を複数回計算する必要がある。時系列ネットワークはいわば、静的な情報なので前処理を用いた高速な探索を行う事ができる。探索時間を短縮する事ができれば、静的な情報をあたかも動的な情報として扱う事ができるだろうと思い、ちょうど良い前処理を探していたのだ。

しかしながら、時空間ネットワークは非常に特殊な構造を持っていて、greedy algorithm でもほぼ最短路が出てしまうため、前処理による高速化は期待できないそうだ。なんでもダイクストラ法を走らせるためのポテンシャルの初期化すらボトルネックになるそうだ。

前処理(ALT) v.s. そのまま解く

2010-04-09 06:20:20 | Weblog
前処理アルゴリズムは複数存在するが、その多くは前処理後の性能を向上するために長時間の前処理が必要となる。またメモリ要求量が大きく扱いづらいと行った弱点も見られる。

そこで比較的シンプルなアルゴリズムである ALT に注目してみた。
Goldberg によるスライド(PDF)の32ページ目を貼付けてみる。



ここで Bidirectional-Dijkstra と ALT を比較してみよう。
               [Bi-DIJK]     [ALT]
 query-time    340.74 ms  → 12.05 ms   (x 28.28 )
prepro-time         0 min →     4 min  (+ 4 min.)
     memory        28 MB  →   132 MB   (+ 104 MB)
必要なメモリ要求量は Landmarks x #nodes x 4 で求められる。
(132 [MB] - 28 [MB]) / 16 [Landmarks] / 1.6M [nodes] ≈ 4

また、前処理にはクエリの数百倍(4 [min.] / 340.74 [ms] ≈ 700)の処理時間がかかるようだ。

ある一定時間以内の枝長の変化を考慮しての経路探索する際にどちらを選択するべきかを単純化してグラフ化すると次のようになる。例えば、10分で処理できるクエリ数は Bidirectional-Dijkstra の 1800 程に対して、ALT では 30000 にも及ぶ。


実際には結果を加工する時間が必要となるので、これほどまでの差にはならないだろう。

最短路問題:「探索範囲限定=高速」ではない

2010-04-06 18:40:03 | Weblog
これまでの実験から、「探索範囲限定=高速」ではないことは明らかである。

真剣に最適化したコードではないので、そもそも正しく比較できていないが、原因は以下のようなものが考えられるだろう。

・ダイクストラ法は非常にバンド幅が要求されるが、それ以上に要求している
・キャッシュメモリ上の有益なデータを押し出してしまう。

最短路問題: 双方向探索(bidirectional search) - 4

2010-04-05 00:23:09 | Weblog
forward, backward, bidirectional の比較実験。
Graph : USA-road-d.USA.gr (23,947,347 nodes 58,333,344 arcs)
Query : P2P x 10
Queue : 2-ary heap
CPU   : Intel(R) Xeon(R) CPU X5460 @ 3.16GHz

[time] 実行時間
[*-N] 探索した点数 (F:Forward, B:Backward, FB:Bidirectional)
[*-A] 探索した枝数 (F:Forward, B:Backward, FB:Bidirectional)


2-ary heap を使用した事もあるが、いずれも探索した枝数に実行時間が比例している事が分かる。しかしながら、bidirectional-search では、探索コストが少々高いことが伺えるだろう。


足裏

2010-04-04 18:38:54 | Weblog
はじめて足裏マッサージにしてもらう。バラエティ番組で良く悶絶するようなものを期待していったのだが、英国風だそうでソフトタッチ。それでも十分気持ちよかったです。くるぶし近くの靭帯損傷していることもあり、足が非常に疲れやすいので、たまにはこういうのもよいですね。

新宿御苑

2010-04-03 18:38:37 | Weblog
新宿御苑にて花見をしてきました。さすが御苑という事もあり、泥酔しているおっさんらがいなく、落ち着いた雰囲気。200円でこれだけの桜をゆったり見る事ができるので、凄くおすすめです!サクラ以外にも様々な植物が見れるので、1年中楽しめそうです♪

最短路問題: 双方向探索(bidirectional search) - 3

2010-04-02 22:02:32 | Weblog
さて前回の記事ではそこそこうまくいった例を示したが、それにしてももう少し性能が出てもいいのでは?という疑問が残る。思い当たる原因はいくつかあるのだが、まずはグラフの規模を疑い、今回は全米グラフを用いる。各クエリに対応した forward-search(F-time), backward-search(B-time), bidirectional-search(D-time) の実行時間をまとめる。

Graph : USA-road-d.USA.gr (23,947,347 nodes 58,333,344 arcs)
Query : P2P x 10
CPU   : Intel(R) Xeon(R) CPU X5460 @ 3.16GHz


Query[0] (17261435, 8424294) のように近い場合では、どれも同程度の実行時間で終了する。

Query[8] (18549540, 3230879) のようにうまく探索範囲を狭ませることのできる場合では、forward-search に比べて bidirectional-search の方が効率的ではある。冷静に考えると backward-search の方が良いが。

Query[9] (957498, 10453327) のように遠い場合では、探索範囲自体は狭まっているのだが、実行時間はむしろ増えてしまっている。

最短路問題: 双方向探索(bidirectional search) - 2

2010-04-01 21:39:55 | Weblog


始点から探索すると非常に大きな範囲を探索しなければならないことが、プロットした図から分かる。この例では終点から探索すると先ほどよりも多少狭くなり、両方向から探索するとさらに狭くなる。実行時間も「Forward > Backward > Bidirectional」となる。

bidirectional-search では forward-search と backward-search を交互に行うので、探索した点の数は同数、枝の数はほぼ同数となっている。この場合では backward の方に傾斜を付けた方が良さそうだが、事前に点の位置が分かっていないと難しいだろう。それよりも、Forward の半分程しか探索していないにも関わらず、これはちょっと遅すぎることが気になる。

Graph: USA-rowd-d.NY.gr (264,346 nodes 733,846 arcs)
Query: 始点 44721, 終点 4895
Queue: 2-ary heap

               scaned-nodes  scaned-arcs  execution-time
Forward             245,151      688,060        39 msec.
Backward            186,055      528,281        30 msec.
Bidirectional       131,858      364,756        29 msec.

[Bidirectional]
scaned-node     131,858 (= 65,929 + 65,929)
scaned-arcs     364,756 (= 185,430 + 179,326)
execution-time  29 msec.