ソルバーに要求されること - データ入力。

基本的に入力データは DIMACS フォーマットを用いているが、どこまでソフトウェア側でチェックするものなのか。グラフフォーマットのチェックは行ってはいるのだが、それ以上のことは行っていないので、もしかしたら途中でエラーが起きてしまうかもしれない。こういった部分はできれば別のアプリケーションを用いてチェックを行ってもらいたいと思う。

Heap VS MLB。

ヒープ法(Binary Heap)と、マルチレベルバケット法(Multi-Level-Bucket) の実行時間の差がなくなってきたという記事は書いたが、DIMACS 9th で公開されている USA-road-d.XXX.gr というグラフに関して実行時間を計測した。

実行環境は以下の通り。
CPU : Xeon X5460 3.16GHz (L2 6MB)
Mem : 48GB

これだけ競っていて、要求メモリが半分以下というのは大きいことだといえるだろう。しかしながら、アルゴリズムが異なり、実装方法も全くと言ってよいほど違う（MLB はポインタ多用、メモリ要求量大）２つの実装がこれほどまで似ている特性を持っているのは、不思議なことである。

PowerEdge 2900 クラスタ設置。

研究室に PowerEdge 2900 クラスタが設置された。先行導入された１台を加え１７台と言うという構成であるが、１台１台が５Ｕと大きいため、とても存在感がある。ちなみに初のラックマウントである。今までも確かにラック(重量棚)にマウントしていたが。

最短経路問題ソルバー(shortest path solver) 自体は、現在いい加減なスレッド並列のみの対応だが、全米データに対しての全体全最短路という巨大なクエリを解きたいという要求があれば、クラスタを用いるということも必要になるかもしれない。

最短路問題での計算量 - Binary Heap。

最短路問題に用いるバイナリヒープの関数は、挿入 insert()、キーの更新（単調減少） decrease_key()、最小ポテンシャル点を取り除く extract_min() の３つであるが、計算量はどれも log2(n) である。しかしながら、前回の記事に書いたように、extract_min() での swap() がそのほとんどを占めている。最短経路問題の特性を考慮すれば気づくことできるが、単純に log2(n) と書かれてしまうと誤った思い込みを持ってしまうこともあるように思える。最短路ソルバーの高速化を行っているうちに、計算量だけによって適切ではないような評価をされてしまっている手法がまだまだあるのではないかと考えるようになってきた。

計算量と実行時間。

計算量では、演算に対してのみコストが生じ、そのコストもすべて等しい場合を想定しているため、実行時間と大きく異なる場合がある。というのも、メモリロード・ストアのコストや、分岐ミスに対してのコストなど、実際に実装する際に必要となる部分を考慮していないためである。しかしながら、数桁倍の開きがある場合では、計算量を指標にすることは有効であると言える。そのため高速なソルバーを開発するのであれば、最も計算量が小さいものだけではなく、複数のアルゴリズムを解析し、その中から選択するといった方法が望ましいように思える。現在最も高速と思われていてもメモリバンド幅に完全に依存してしまうようなアルゴリズムでは、これからの CPU アーキテクチャの意向に合致しておらず、CPU の改善に対しての恩恵を受けることが難しくなるということも考えておかなければならない。

最短経路問題における探索候補点集合 - その２。

道路ネットワークグラフ（USA-road-d.XXX.gr）では、探索候補点集合内にある要素数はかなり少ない。

画像は USA-road-d.NY.gr において、点 ID 1 から点 ID 64346 までの P2P 最短路において、どのようにデータ構造内の要素数が変化したのか示したものだが、この２点はある程度離れているにもかかわらず、800 要素以下である。全米データであっても多くて 8000 程度と、少ない。

最大要素数は知っていたのだが、どのように増減するかは見たことがなかったので、参考のために調べてみることにした。Excel では大きなデータを扱えないので、10 探索刻みにデータ構造内の要素数を調べてみた。

要素数をうまく予測できるかということも考えもしたが、この様にしてみるとかなり難しいそうである。

MLB との差。

現在開発しているバイナリヒープをデータ構造に採用したソルバーと、Multi-Level-Bucket との実行時間の差はかなり小さいものになっている。

バイナリヒープのメモリ要求量は半分以下であるために、大きなグラフを格納することができるため、より大きな最短経路問題を解くことにできる。データ入出力など工夫によりグラフ格納時間を大きく削減することによって、ストレスなく実行することができる。

しかしながら、肝心の実行時間では優位に立っていないのでまだまだである。本当に高速になったとき、公開できればと思っている。

最短経路問題における探索候補点集合。

探索候補集合をどのデータ構造で実装するかというのは、最短経路問題における大きなテーマであるだろう。

バイナリヒープ(binary heap)、バケット(bucket) を比べていくと、集合に格納されるポテンシャル値の差がある程度ない場合（この表現を密とする）バケットの方が有効であることがいえるが、疎になるにつれて低速化してしまう。

逆にバイナリヒープは密であってもあまり低速化されないために、一定のグラフ特性を考慮しないソルバー（どのようなグラフに対しても高速）を開発をする場合は、こちらを選択するべきだろう。

しかしバイナリヒープには弱点（最小ポテンシャル点を取り出す操作の際に起きる大量のスワップ操作）があるためにどのようにこの部分を改善していくかがポイントである。

ボトルネックの検出 - その２。

今回は CPU クロックを変化させての実験を行った。環境は Intel(R) Xeon(R) CPU 5160 @ 3.00GHz で、2.00GHz と 3.00GHz の２通りに変化させ、実行時間がどのように変化するか調べた。

まず、１プロセスで実行させた場合、クロック変化の比率（x 1.50）に比べ、x 1.37 に留まってしまっているが、もちろん異なったダイ上のコアでの２プロセスで実行させても、ほぼ同じ比率 (x 1.36) である。しかしながら CPU 内での何らかの処理によって、クロック変化の比率分だけの効果を得られていないようだ。

また、L2 を共有したコア上での２プロセス実行させると、性能が明らかに低下する。しかしながら、クロックの変化により実行時間も変化する。それも x 1.29 と他の場合と比べそこまで低速化していない。このことから、メモリバンド幅だけに依存しているのではないことが推測される。メモリバンド幅が飽和しているのであれば、メモリバンド幅だけに依存し、クロックが変化しても実行時間は変化しないからだ。違ったアーキテクチャの CPU でも実験してみるといろいろわかるかるかもしれない。

                    2.00GHz   3.00GHz
1process  (x 1.37)    36.03     26.30 
other die (x 1.36)    36.45     26.81 
L2 shared (x 1.29)    43.51     33.78 

cpufreq-selector の使い方。

まずは、cpuspeed が動いているか確認し、動いていなければ、動かす。
/etc/rc.d/init.d/cpuspeed status
/etc/rc.d/init.d/cpuspeed start

変更したいクロック数を設定する。
/usr/bin/cpufreq-selector -f [clock]

cpuspeed が起動したままだと実行が不安定になるようなので、止めておく。
/etc/rc.d/init.d/cpuspeed stop


ここで実験をする。


実験が終わったら、クロック数を戻しておく。performance を指定すると最大クロック。
/usr/bin/cpufreq-selector -g performance
/etc/rc.d/init.d/cpuspeed stop

ボトルネックの検出 - その１。

grof は関数ごとの呼び出し回数・実行時間を計測してくれるとても便利なものである。gprof を用いて、ボトルネックを見つけていく。今回は p2p タイプを 10 クエリ解かせたので、dijkstra_with_heap が 10 回呼び出されている。各関数の説明は以下のようになっている。

・dijkstra_with_heap はダイクストラ法そのもので、関数の初めで作業領域を初期化している。
・heap_delete_min は次の探索点を決定する操作。ヒープから最少ポテンシャル点を削除する。
・heap_insert はヒープへ点を挿入する操作。
・heap_decrease はポテンシャルの更新に伴って、ヒープ内での位置を更新する。
・heap_node_swap ヒープ内で swap する関数


またヒープ法では swap の呼び出し回数と実行時間との関係は密接であるため、swap の最適化や、そもそも回数を減らすことが重要な課題と言える。そのため heap_node_swap() を 通常の関数、static inline と変化させることで、どの関数で swap が多く呼び出されているか見ていく。

すべて通常の関数

  %   cumulative   self                 self     total           
 time   seconds   seconds      calls   s/call   s/call  name    
 46.19     10.91    10.91         10     1.09     2.24  dijkstra_with_heap
 28.11     17.56     6.64  114552768     0.00     0.00  heap_delete_min
 16.87     21.54     3.99 1085558423     0.00     0.00  heap_node_swap
  2.86     23.17     0.68  114574250     0.00     0.00  heap_insert
  0.64     23.64     0.15    8103701     0.00     0.00  heap_decrease

heap_node_swap() のみ static inline で、インライン展開する。

  %   cumulative   self                self     total           
 time   seconds   seconds     calls   s/call   s/call  name    
 46.45     10.54    10.54        10     1.05     2.18  dijkstra_with_heap
 45.39     20.85    10.30 114552768     0.00     0.00  heap_delete_min
  3.37     22.55     0.77 114574250     0.00     0.00  heap_insert
  0.66     22.70     0.15   8103701     0.00     0.00  heap_decrease

heap_node_swap() に占めていた時間（3.99s）のうち、そのほとんどが heap_delete_min() に加算されているのがわかる。(6.64s→10.30s)
また heap_node_swap() の呼び出し回数を見ていく。

-----------------------------------------------
                0.02    0.00    4211496/1085558423     heap_decrease [11]
                0.11    0.00   29542100/1085558423     heap_insert [9]
                3.86    0.00 1051804827/1085558423     heap_delete_min [5]
[6]     16.9    3.99    0.00            1085558423     heap_node_swap [6]
-----------------------------------------------

やはりそのほとんどが heap_delete_min() から呼び出されているようだ。この部分をどうにか減らすことができれば、まだまだ高速化可能だといえる。insert, decrease が今よりも多少増えたとしても、heap_delete_min() 内の swap を大幅に減らせるようなデータ構造であれば純粋なヒープでなくても良いだろう。

経由地点あり最短路問題オンラインソルバー。

Shortest Path Online Solver

ついに経由地点あり最短路問題のオンラインソルバーも公開することとなった。

□使いかた□
１、経由点をクリックで選択し、[set] を押すことで確定することができる。
　　※ [clear] で経由点を１つ、[All clear] で全ての経由点を消すこともできる。

２、確定後、[submit] で実行することができる。

実行時間も表示しているので、是非お試しいただきたい。

経由地点あり最短路問題 - その３。

実はすでに試作版を開発しており、そろそろ公開という状況である。それに伴い、内部で動くソルバーをクエリ単位でも EPS へ書きだせるように改善を行った。

画像ファイルは、USA-road-d.NY.gr と USA-road-d.NY.co に対して、ランダムな P2P クエリを解いた結果である。こうみているとやはり同じような道路を使っているということが良く分かる。

Firefox ダウンロード数ギネス新記録を樹立。

いまさらな話題ではあるが、米国時間 2008 年 7 月 2 日、Firefox 3.0 の正式リリースから 24 時間内のダウンロード数が 8,002,530 を記録し、「24 時間で最も多くダウンロードされたソフトウェア」としてギネス世界記録と認定された。

しかし、各言語間で連携が取れていなかったために Spread Firefox から届いた「ギネス世界記録達成！」の通知メールには、“ダウンロード総数は 8,002,530,000,000 回（８兆回？）を突破しました。”と書かれてしまっていたようだ。

この記事を書いている段階では 28,340,281 と３倍以上にもなっており、今まで使っていなかったユーザも移行してきているのではないかと考えられる。


firefox 3 が出る前までは、safari を使っていたが、safari は文字・画像の描画のパフォーマンス（きれいで高速）がよくインターフェイスが気に入っていた。firefox 3 が出た今ではパフォーマンス・使いやすさを考えると Windows でも、もっぱら Firefox で、IE は Windows Update のみにしか使わなくなるだろう。

２プロセスで実行 - heap 法。

バケット法に行った実験と同様な実験をこちらにも行った。ヒープ法では、バケット法と比べ、全体的になだらかである。

「ダイが異なるコア同士」、「L2 を共有してはいないが同一ダイ上のコア同士」では、影響を見せない。前者から L2 上に作業領域がのっていること、後者から２プロセスでもバンド幅を使い切らないことがわかる。

同一ダイ上ではやはり低速化してしまうために、以下のサイズということがわかる。
3MB ≦ ヒープ ≦ 4MB

しかしながら、全米グラフでもヒープは最大でも 8000 要素ほどしか格納されていない。8000 x 16 = 2^17 = 128 KB なので、上は大きすぎる。ヒープ自体は密であるが、アクセスは疎になってしまうために、無駄なロードが原因だろう。