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

どこにボトルネックがあるかというチェックを行うために、以下のような３種類と１プロセスとの実行時間の比較を行った。

・L2 キャッシュを共有しているコア同士
・L2 キャッシュは共有していないが同じダイ上のコア同士
・異なるダイ上のコア同士

まず違うダイ上であれば、ほとんど影響を受けてないことがわかる。この部分からはメモリアクセスがボトルネックではないと判断できる。バケット法の作業領域は、L2 上に載っていることが考えられるだろう。

しかし、同一ダイ上で実行すると少なからず影響を受ける事となる。１プロセスでは超えなかったメモリバンド幅がここで多少なりとも超えてしまったのだろうか。
影響の度合いを考えると２倍を少し超えたくらいであろうか。

L2 キャッシュを共有しない場合では、他の場合と比べかなり低速化してしまう。同一ダイ上のコア同士の結果と比べても、低速化しているのははっきり分かる。バンド幅に加え、作業領域のサイズが L2 からあふれてしまっていることに原因があるのではないか。

作業領域は以下ほどだと推測できる。
3MB ≦ バケット法の作業領域 ≦ 4MB

コアの配置状況。

どのようにコアが配置されているかを把握する方法について。

マルチコア・プロセッサ上で、/proc/cpuinfo を見ると８コアであれば、０～７までのプロセッサ番号が付くことになる。しかし、それだけではどのように配置されているかわからない。単純に連番になっているのではなく、またプロセッサによって異なるので、その都度調べる必要がある。

例えばどちらも QuadCore Xeon x 2 で計 8 コアの構成ではあるが、番号の振り方が異なる。以下は少しわかりづらいかもしれないが、プロセッサ番号を表している。一番深い括弧から、L2 共有コア、同一ダイ上のコア、ノード上のコアとなっている。

１、Intel(R) Xeon(R) CPU E5345 @ 2.33GHz (L2 4MB)
　[[0,2], [4,6]], [[1,3], [5,7]]

２、Intel(R) Xeon(R) CPU X5460 @ 3.16GHz (L2 6MB)
　[[0,4], [2,6]], [[1,5], [3,7]]


さて、どのように調べるかなのだが、/proc/cpuinfo を確認すると、processor, physical id, core id が記されている。以下のように書き出すとわかりやすいのだが、processor はコアに対しての通し番号、physical id は ダイの通し番号、core id はダイ内での通し番号になっている。よって、上のような構成であることがわかる。

１、Intel(R) Xeon(R) CPU E5345 @ 2.33GHz (L2 4MB)

processor   physical id   core id
        0             0         0
        1             1         0
        2             0         1
        3             1         1
        4             0         2
        5             1         2
        6             0         3
        7             1         3

２、Intel(R) Xeon(R) CPU X5460 @ 3.16GHz (L2 6MB)

processor   physical id   core id
        0             0         0
        1             1         0
        2             0         2
        3             1         2
        4             0         1
        5             1         1
        6             0         3
        7             1         3

最短路ソルバーにおけるボトルネック。

最短経路問題では巨大なデータ（全米グラフはテキストデータで5800万行, 1.3Gbyte）を用いるために、メモリアクセスがボトルネックであると思っていたのだが、実はそうでなかった。

先日のゼミで指摘されたことだが、マルチコアで線形に性能が伸びるということは、メモリアクセスがボトルネックではないとのこと。しかしながら、コアを変化させて見ていくと性能が下がってしまうところがある。

よって、L2 キャッシュサイズがボトルネックであることがわかる。ただ、penryn 系コアの L2 キャッシュサイズは、6MB とかなり大きいので、現状に満足できない。まだまだ高速化できる。

データの局所性。

先日のゼミで得られたことはかなり多い。今までメモリアクセスコストに対しての認識はあったのだが、知識の結びつきがうまくいっていなかったようだった。いまだに理解していない部分も多くあるだろうが、今までにない視点で高速化について見る事が出来るようになったと思う。

ここから先は最短路ソルバーを例に挙げての話になるが、一般的な話であるのでプログラムの高速化全般に適応できると思われる。

まず、実行を大まかに捉えると「入力データ→出力データ」である。ようするに、入力データに何らかの加工をして出力データを作成することになる。

最短経路問題では、入力データは「グラフデータ」で、出力データは「始点からの距離行列・直前隣接点」になっている。どちらも巨大である。さらに今回の場合、入力データは「加工せずに入力としてのみ用いるデータ」であり、出力データは「加工するデータ」である。入力データ、出力データはどちらも巨大で、もちろんキャッシュには載らない。

最短路ソルバーで用いているダイクストラ法では、入出力共に巨大ではあるが一度にすべてのデータを用いるのではなく、ある地点では少量のデータを用いて加工している。そのため、その少量の作業領域が十分小さければ、メインメモリではなく L2 キャッシュ以上に配置される。作業領域サイズを減らすことが高速化につながる。しかしながら演算量・データの再利用が少ない場合には、あまり効果がなく、結局メモリアクセスコストがボトルネックとなってしまうだろう。

以上のことは言うのは簡単だが、実際に行うのは難しい。ダイクストラ法では実際の演算の演算量・データの再利用が少ないので、探索候補点集合を格納するデータ構造の動きに大きく左右されるだろう。再利用性が多く、局所性が高いデータ構造を用いるとよい。そういう意味では、バケット法ではなく、ヒープ法の方に歩があるといえる。

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

前記事のような工夫をきちんとしてから公開する事も大事だが、とりあえず公開してしまい、少しずつ改善するということもまた大事なことである。公開する事で問題点が浮き彫りになったり、新たに良いアイディア等も思いつくかもしれない。ある程度形になれば公開するつもりである。

この場合は、経由地点が１点の最短経路問題となっているが、近い点同士が同じようなルートを用いるということも分かるだろう。Highway Hierarchies などの前処理もこういった特性から考え出されたのだろう。

経由地点あり最短路問題。

現在は、Point-to-Point（p2p:１対１）、Single-Source（ss:１対全）の２タイプの問題を扱っているのだが、「経由地点を入力する事は可能か」と質問をいただいた。確かに実際にナビゲーションとして用いる際には必要な機能になるのだが、実は驚くほど容易にできる。


たとえば、「Ａ→Ｂ→Ｃ→Ｄ→Ｅ→Ｅ→Ｆ→Ｇ→Ｈ」という最短経路問題では、

クエリ数：７
Ａ→Ｂ、Ｂ→Ｃ、Ｃ→Ｄ、Ｄ→Ｅ、Ｅ→Ｆ、Ｆ→Ｇ、Ｇ→Ｈ

といった、P2P タイプのクエリを７つとけば良い。
クエリ間は独立しているために、並列に求解することが可能になる。


また、各枝長が対称（行き帰りが同じ長さ）であるなら、もう少し工夫する事も可能になる。

ダイクストラ法は１点から全点への最短路（ssタイプのこと）を求めることができるアルゴリズムであるので、以下のようにまとればクエリ数も半数程度となる。

クエリ数：４
Ｂを始点として、Ａ、Ｃのどちらにも到達したら終了
Ｄを始点として、Ｃ、Ｅのどちらにも到達したら終了
Ｆを始点として、Ｅ、Ｇのどちらにも到達したら終了
Ｇ→Ｈ


条件が増える事によって低速化してしまうことも考えられるが、１対全であっても高速に実行できるので、思い切って ss にしてしまってもよいだろう。

クエリ数：４
Ｂ、Ｄ、Ｆをそれぞれ始点とした１対全(ss)最短路問題
Ｇ→Ｈ



いずれこちらで公開する予定である。

Shortest Path Online Solver
http://opt.indsys.chuo-u.ac.jp/portal/

Shortest Path Solver 高速化。

ゼミの結果、まだまだ高速化が可能である事がわかり、モチベーションがとても上がった。ひとつずつ改善しては、実験の繰り返しで地道にいくつもりである。ただ実験を行うのではなく、高速化・低速化の原因を推測し、実験によって裏付けを取れるように注意深くいきたい。

改善点が大量に浮き彫りになってきたので、少しずつ消化していこうと思う。

ゼミ前まとめ。

・グラフに対して適切なデータ構造の選択
ヒープ法・バケット法の特性と、グラフの特性ではうまく合致する部分とそうでない部分がある。それらの特性を用いてなく高速に動作するデータ構造はどのようなものか。


・動的計画法の計算量
動的計画法では、計算量があらかじめ分からないため、どれほど高速化されているかなどの基準が見極めにくい。

最短経路問題におけるデータ構造。

前処理なし最短経路問題に対するソルバーの研究は、データ構造の改善であるかのにように、かなりの数が発表されている（画像）。

点に依存し実行時間にばらつきの少ない「ヒープ系データ構造」か、最大枝長に依存してしまうが、許容内であれば高速に実行する「バケット系データ構造」の２種類をうまく組み合わせたデータ構造がそのほとんどである。

しかしながら、あまり実装については考慮されていないようで、まだまだやれることはあるといえる。

MLB - その５。

前回が、Dijkstra 法の最も内側のループである「探索点の隣接枝を見ていく」部分についてだったが、今回は Dijkstra 法そのものについてみていく。

プリプロセッサ等が多く、元のソースは読みづらくなってしまっているため、以下のように必要なもののみに絞ってみた。するとずいぶん読みやすくなり、全体が把握しやすい。変数名の付け方など、自分以外の人が書いたソースを読む事はとても勉強になることである。

次回以降は、Insert()、Delete()、RemoveMin() という予定である。
回を重ねるごとに複雑になっていきそうだ。


/* 始点をバケットに格納する */
bckNew = DistToBucket(&(source->dist), DistToLevel(&(source->dist)));
Insert(source, bckNew);

do {
　　　/* バケットから最小ポテンシャル点を取り出す */
　　　currentNode = RemoveMin();
　　
　　　/* 終了条件 */
　　　if (currentNode == NULL) break;
　　　if (currentNode == sink) {
　　　　　reached = true;
　　　　　break;
　　　}
　　
　　　sp->cScans++;
　　　currentNode->where = IN_SCANNED;
　　　
　　　lastArc = (currentNode+1)->first - 1;
　　　
　　　/* 隣接枝をスキャンしていく */
　　　for (arc = currentNode->first; arc <= lastArc; arc++) {
　　　　　/* 前回ブログ参照 */
　　　}
} while (1);

余算→加算・減算 - その２。

前回では、改善比率のみを示したが今回はより詳細を見ていく。

まず環境から。

graph：USA-road-d.USA.gr
query：ramdom P2P x 32

CPU : Xeon X5460 3.16 GHz (cache size 6MB)
Mem : 48GB
OS : CentOS 5.2 x86_64
GCC : GCC 4.1.2


続いて、ルーチン呼出回数である。
32 クエリ分の合計値であるので、かなりの回数を呼び出されていることが分かる。
427,087,609(delete + insert) = 26,557,718(delete) + 400,529,891(insert)

平均値を出しても、やはり大きい。
13,346,488 [times/query] = 829,929 [times/query] + 12516559[times/query]

余算を行う回数は、この値 427,087,609 (ave. 13,346,488) と等しい。


また「余算→加算・減算」としたことにより、
430,365,619 回の加算・減算、427,087,609 回の分岐が増えることになる。

平均を求めると、次の回数分演算が増えることになる。
13,448,926 [count/query]、 13,346,488 [times/query]


よって、次のようになる。
13,346,488 回の余算　＞　13,448,926 回の加減算 ＋ 13,346,488 回の分岐


こんなにも演算数増えてるにも拘らず 2.67 ％ 改善されていることを考えると、いかに余算のコストが高いのかがよくわかる。しかしながら、このままでもどの部分がどれだけ効いているのか判らないので、別にサンプルプログラムを作成し、演算コストも計測してみよう。

余算→加算・減算 - その１。

通常の実装では、バケット法において数ヶ所余算を用いることとなる。
・点のポテンシャルから、バケットを決定する際
・空でないバケットを見つける操作（キューで実装しているため）

後者については、ループを分けることによって、すでに改善されている。


今回は１について。今まで手を付けなかったのは、単純に演算数・分岐が増えることになるためであっる。やはり余算コストの大きさを考えるとこちらも効いてくるだろうと思い、試してみることにした。


最短経路問題におけるバケット法（Dial's implementation）では、バケット内に格納されているポテンシャルの範囲はたかだか bucket_size しかないため、大きな変更もなく加算、減算で代用が可能である。

以下は、手持ちの中で最も大きなグラフである全米データに対しての改善比率である。

ランダムなクエリに対しての平均値である。

１、余算　　　　1.645 [sec/query]
２、加算・減算　1.601 [sec/query]


これによって、2.67 ％ ほど高速化されたわけだが、演算のコストはアーキテクチャによって異なるので、注意が必要である。

MLB - その４。

以下は, Goldberg 氏のソースコードの抜粋。
全角の「スペース・＜」が入っているので注意。

探索点から、各枝を見ていく部分である。

以前、「MLB では c(v) の値によって、MLB にするか F にするか選択する」と
書いたが実際には以下のように F は用いていない。

この部分はかなりシンプルで、自前で作成したものとかなり似ている。
コードを最適化すると、この形に行き着くのであろうか。

唯一異なるのは初期化の仕方で、タイムスタンプによって初期化が必要か判断しているようだ。
初期化の時間が気になっていたので、この方が良いのかもしれない。

/* 隣接枝をスキャンしていく */
for (arc = currentNode->first; arc <= lastArc; arc++) {
　newNode = arc->head;
　
　/* タイムスタンプが以前のクエリであるなら、初期化する */
　if (newNode->tStamp != sp->curTime) sp->initNode(newNode);
　
　/* 更新がある場合 */
　if (currentNode->dist + arc->len ＜ newNode->dist) {
　　/* 更新前のバケット位置 */
　　bckOld = BUCKET(newNode);
　　
　　/* ポテンシャル・直前点の更新 */
　　newNode->dist = currentNode->dist + arc->len;
　　newNode->parent = currentNode;
　　
　　/* 更新後のバケット位置 */
　　bckNew = DistToBucket(&(newNode->dist), DistToLevel(&(newNode->dist)));
　　
　　/* ポテンシャルの更新によるバケットの移動 */
　　if (bckOld != bckNew) {
　　　if (InBucket(newNode)) Delete(newNode, bckOld);
　　　Insert(newNode, bckNew);
　　}
　}
}

携帯交換。

携帯のカメラを使用していたら、急に操作不能になり電源を落としてみた。
その後何故か電源が入らなくなり、いろいろ試しやっと電源 ON 。
何かあると思い、DOCOMO ショップに向かい確認してもらうことにした。

しかし、確認作業のために電源を切ったのを最後に応答しなくなった。
作業前に、SD カードにバックアップをと促され、それで本当に助かった。


ちなみに最近の大学生は、「携帯＞＞パソコン」であるようだ。
ある授業で「ワードの開き方」について質問され、びっくりした。
昨年同じ授業で「ワードの保存方法」を聞かれたこともあるが、今年はさらにひどい。
そういった背景もあり、某学科では研究室の内容に興味を示してくれる学生が少ない。

MLB - その３。

今回は decrease-key と extract-min について。

■準備■
・点 v に対し、「c(v) = 最小枝長」とする。枝がない場合は「c(v) = infinity」。
・点 v に対し、d(v) はポテンシャル値。
・バケットを補助する集合 F を用意する。
・「μ = 最後に取り出したポテンシャル値」とする。
　（１レベルのように、mod bucket_size でなく、素のポテンシャル値）


■decrease-key
u が格納されている B(i,j) から点 u を削除し、
新たなポテンシャル d(u) を B(i,j) に挿入する


■extract-min
空でないレベルのうち、最も低いものを探す。レベル i とする。
レベル i のうち、空でない最初のバケットを探す。j とする。

if (i == 0) {
　B(i,j) から点 u を削除する。
}
else if (i > 0) {
　B(i,j) のすべての要素を確認し、最も小さな要素 u を B(i,j) を削除する。
}

μ = d(u) とし、点 u を次の探索点とする。

点μが増加すると、それまでに挿入していた点の整合性が保てなくなるために、バケットの位置を変える必要がある。


流れとしてはこのような形ではあるが、高速化するための工夫がいくつか存在するので、ソースコードも合わせて確認していこう。