2007 年まとめ。

今年に行った作業

・多倍長計算
あまり深くまでは行わなかったが、Cell の弱点である Double 計算を float-float で演算してみようとした。しかし float-float に変換する際や、演算自体も大きくなってしまい、効果は薄くなってしまった。もう一度やってみると面白いのかもしれない。

・Cell 用 BLAS
Cell は確かに高速だが、その制約の厳しさなど導入するには敷居が高い。特にアライメント揃っていないデータを SPE に転送できない、LS（ローカルストア）が 256KB など、通常の CPU に比べて癖がある。IBM から正式に発表されたが、こちらも「行数は～の倍数、列数は～の倍数」と使いづらい。

・Shortest Path 高速化
Dijkstra 法を高速化するために良いデータ構造などを検証した。今までの最短路の高速化に関してはどのデータ構造を用いるかという議論であったようだが、最短路問題は多くのデータを用いるので、実際にはどのようなデータアクセスをすればいいかを焦点にする方がよさそうである。メモリアクセスを最適化することでかなりのオーバーヘッドを軽減できるだろう。


いろいろ手をつけてはいるが、現在は ShortestPath 高速化をメインにしている。来年度は今年以上に時間を取れそう（授業がなくなる）なので、より頑張っていこうと思う。

最短路とデータ構造。

前回、ポテンシャルの更新の部分を見直したので、今度はデータ構造への入出力の動きをしっかり見ていこう。

以前データ構造は２分木を用いていた。２分木は扱うデータの特性を気にすることなく扱えるが、最短路で扱うデータにはある程度の幅があり、また取り出したい値というのは少しずつ大きくなっていくという性質がある。せっかくそのような性質があるのに考慮しないのはもったいないので、最近はバケット法（バケット用の配列のほかに prev, next のポインタをもっている）を用いている。

また、探索点になる点のポテンシャルの動きを観察してみたが、１回１回の差が非常に小さい。一番大きな場所が最初の１回目ということもあった。全米データを例にあげると枝は最短 1 最長 368855 であるのだが、この幅以上に点数 (23,947,347) や枝数 (58,333,344) が多いために差が小さくなっている(最大でも 20,000 程度であるがとてもまれであり、ほとんどが数十以下)のであろうか。このくらいであればもしかしたら、prev, next をなくしてみても良いのかもしれない。いろいろ試してみよう。

do while & 変数置き直し廃止。

point-to-point（始点１点　対　終点１点）の最短路を高速化するためにあれこれソースをいじっている。気になっていたこともあり、プログラムを大幅に変えることにした。高速化する部分はクエリを与えられてから始点からの距離を返すまでであるが、改善できそうな点として以下の３つがあげられる。

１．探索点から出ている枝の長さ・その先の点のポテンシャルを計算し、更新する部分
　　複数の配列を扱うため、アクセスが飛び飛びになりやすい。

２．データ構造からポテンシャルが最小のものを取り出す
　　先読みなら、ここをうまく扱うことになるだろう。


今回は特に１について、いくつかパターンを想定し実験してみた。具体的には、１のループの内側と外側で、別の変数を介してのコピーを試してみた。コピー処理を行うデータは次の２つの構造体である。どちらか一方、または両方にと場合分けをし実験を行った。前回の改善で、「枝の長さ・枝の先の点」を格納した変数は「int 型変数が２つの構造体」であるので、２つずつ（128 bit ずつ）行った。「ID・ポテンシャル・直前点」を格納した変数は「int 型変数が３つの構造体」であるので、もう一度 dammy 変数を用いてサイズを 128 bit にしてみたが、ほとんど効果は感じられなかった。いろいろ実験を行ったが効果を見れずに、どちらかと言って遅くなってしまった。

また１では枝の先にある点 ID・その点ポテンシャルを作業用の変数を用意し置き直してから処理を行っていたが、それも本当に必要なのかと疑問に感じたのでやめてみた。改善されたわけではないようだが、可視性がかなり上がり、実行時間にばらつきがなくなったようにも感じられる。なくてよいものならやめたほうがいいだろう。

いつも通りにこのようなクエリを解く実行時間を計測してみた。今回からは関数内で実行時間を計測しているので、関数呼び出しのオーバーヘッドは含まれていないのだが、500[msec] ほど短縮されている。変数置き直しをやめたことが影響しているだと思う。いろいろやってみたが、プラスになったのは、『変数置き直し廃止』と『while 文から do while 文に変更』した事で１回分 データ構造を触る回数を減らせたことくらいだろうか。今回からは Single-Source（始点１点　対　終点全点）も実験してみた。

[Point-to-Point Type Query]
p aux sp p2p 10
q 957498 10453327
q 19200797 7727679
q 13006257 40639
q 4314559 22779984
q 17261435 8424294
q 8077810 13186938
q 3048748 1475829
q 21869636 3531883
q 13446936 4981527
q 18549540 3230879

[Single-Source Type Query]
p aux sp ss 10
s 4760241
s 3054978
s 8745396
s 21201199
s 3353734
s 8475033
s 11338743
s 22686469
s 1176382
s 1455093

Vine Linux 4.2 が正式リリース。

New Note PC (Let's Note) にももちろん入れてある Vine Linux (VMware) が 4.2 にアップグレードされた。見やすいフォントが大変気に入っている。

アップグレードするためには apt-line を 4.2 に書き換えてから、以下のようにすればよい。
# apt-get clean all
# apt-get update -y
# apt-get upgrade -y

/etc/apt/sources.list にある apt-line を直接扱っても良いが、Synaptic にある[設定]→[レポジトリ]にあるディストリビューションのヴァージョンを変更するのでも良いようだ。

ログイン画面にも変更が反映され、アップグレードした感がある。

データの持ち方による実行時間２。

結果に２レベルバケットのものも含めたので、UP しておく。２レベルバケットは、C++ で書かれており、それが実行時間に影響が出てきているではないかと思う。C に書き直し、データを整理すれば改善されるだろう。

グラフを見るとわかるのだが、Intel 系と AMD 系で性能が異なり、Opteron では graph を格納する大きなデータ領域を配列にしてしまうとガクッと速度が落ちてしまう。メモリアクセスに強いはずの Opteron が落ちて、Xeon は そこまでではない。Xeon では、 Hardware Prefetch が働いているのだろうか。

急に話が変わるが、Office 2007 は、今までの GUI を使い慣れている方には使いづらいのだがとても奇麗なグラフが描ける。テンプレートも豊富だし、セルを変更するとグラフまで変更されるのは便利である。GUI さえ以前のものも選択できるようにすれば、よいのにと思ってしまう。

アライメント。

グラフデータは、次のように持っているが、ここで、点に関する情報の構造体は int 型で３つとなっており、アライメントをそろえることでより改善できるかどうか試してみた。


// 枝に格納する構造体
typedef struct {
　int head; // 枝の先の点
　int length; // 枝の距離
} arc_t;

// 点に格納する構造体
typedef struct {
　int incident; // その頂点から出ている枝数の累計数
　int potential; // 始点からの距離
　int prevNode; // パスを作るために必要
} node_t;

// 問題を格納する構造体
typedef struct {
　int nodeNum;　　// 問題の点数
　int arcNum;　　 // 問題の枝数
　int maxLength;　// 最長枝
　int minLength;　// 最短枝
　arc_t *arc;　　// 枝関係
　node_t *node;　 // 点関係
} graph_t;




具体的には、次のようにした。

（改善前）
typedef struct {
　int incident; // その頂点から出ている枝数の累計数
　int potential; // 始点からの距離
　int prevNode; // パスを作るために必要
} node_t;


（改善後）
typedef struct {
　int incident; // その頂点から出ている枝数の累計数
　int potential; // 始点からの距離
　int prevNode; // パスを作るために必要
　int dammy;
} node_t;


改善前　24.04 [s]
改善後　25.35 [s]

結果からすると、この改善はしないほうがよいようである。アライメントが 16 byte に揃っていても、不必要なデータのせいでアドレス計算の方に若干のオーバーヘッドがかかってしまっているのではないかと考えている。

データの持ち方による実行時間。

現在までの主な改善点であるデータの持ち方であるが、３パターンほど分けて実験を行った。「[1]グラフを格納する構造体」と、「[2]バケット法に用いるデータを格納する構造体」の２つの関してなのだが、どちらとも構造体の配列を持つほうが効率的であることが分かっている。

１、[1]、[2]ともに構造体の配列で持つ
２、[1]は構造体の配列、[2]はいくつかの配列で持つ
３、[1]、[2]ともにいくつかの配列で持つ

結果として、サイズの大きなグラフデータに関してとても効果的であったといえる。よく考えてみると納得がいく結果なのだが、このように実験をしてみるとより整理ができる。

実行環境は、以下の通りである。
Xeon : Xeon 2.33 GHz / 16 GB Memory
Opteron : Opteron 2.00 GHz / 4 GB Memory

9th DIMACS Implementation Challenge。

最短路についていろいろ書いてはいるが、ごちゃごちゃして自分にしか分からないようになってしまっていると感じていたので、ここら辺でまとめを書いておこうと思う。現時点で効果のあった改善点としては当り前なのだが、以下のようになる。

１、ソースを整理し、必要なものと不必要なものにわける。
２、アクセスのされかたを考慮して、データを持つ。

以下は現在までの実行時間である。Goldberg 氏の２レベルバケット法よりも実行時間が短縮されている。ただ、このクエリでしか試していないので、これからいろいろ試したいと思う。ちなみにプログラムは こちら より手に入れられるものを用いた。


[Graph data]
USA-road-d.USA.gr
23947347 nodes and 58333344 arcs

[Query data]
p aux sp p2p 10
q 957498 10453327
q 19200797 7727679
q 13006257 40639
q 4314559 22779984
q 17261435 8424294
q 8077810 13186938
q 3048748 1475829
q 21869636 3531883
q 13446936 4981527
q 18549540 3230879



実行結果は次のように記してある。
用いたデータ構造　　消費メモリ　　実行時間（ファイル読み込み除く）

Xeon 2.33GHz / Mem 16GB / gcc(4.1.2)
２分木　　　　　　725MB ～ 945MB 42.97[s]
１レベルバケット　910MB ～ 945MB 23.59[s]
２レベルバケット　2808MB　　　　　36.08[s]

Xeon 3.00GHz / Mem 8GB / gcc(4.1.2)
２分木　　　　　　725MB ～ 945MB 29.60[s]
１レベルバケット　910MB ～ 945MB 18.11[s]

データの持ち方。

大きなデータを扱う際などは、使われ方に応じて持つこととよい。というのもかなりの効果を得ることができるからである。以前までは以下のように構造体に配列の先頭を指すポインタを宣言し、後にメモリを動的確保していた。

typedef struct {
　int nodeNum;
　int arcNum;
　int maxLength;
　int minLength;
　int *head;
　int *length;
　int *incident;
　int *potential;
　int *prevNode;
} graph_t;

しかし最適化問題を実装する際には、複数の配列の同一 ID を参照する機会が多い。最短経路問題では、特に次の２つついてである。

１．接続点 (head[ ])と、その長さ(length[ ])
２．ポテンシャル(potential[])と、直前接点(prevNode[ ])と、
　　点から出ている枝・その長さを保存している ID (incident[ ])

しかしこのようなデータの持ち方をしてしまうと、せっかく同じタイミングでデータを参照するのに各配列に別々にアクセスしなければならない。そこで同じタイミングで参照するデータは近くに持つことが望ましい。

typedef struct {
　int head;
　int length;
} arc_t;

typedef struct {
　int incident;
　int potential;
　int prevNode;
} node_t;

typedef struct {
　int nodeNum;
　int arcNum;
　int maxLength;
　int minLength;
　arc_t *arc;
　node_t *node;
} graph_t;

このようにするだけでもかなり改善ができる。同じデータ型であれば配列のほうが良いと思われるが複雑なものであると混乱するので、まずはこのようにしてみるとよいだろう。

ソースの整理３。

バケット法についても、ソースの見直しを行った。気になっていた部分もなくなり、データの見直し等で高速化することはこれで一段落してしまっているのかもしれない。悪いところは順次消していこうと思う。

Xeon 2.33GHz / Mem 16GB / gcc(4.1.2)
２分木　　　　　　(725MB ～ 945MB) 42.97[s]
１レベルバケット　(910MB ～ 945MB) 23.59[s]

Xeon 3.00GHz / Mem 8GB / gcc(4.1.2)
２分木　　　　　　(725MB ～ 945MB) 29.60[s]
１レベルバケット　(910MB ～ 945MB) 18.11[s]

ソースの整理２。

再度ソースの整理を行った。今回は主にデータの持ちかたについてだが、どのような処理を行うか考慮して、「配列の構造体」にするか「構造体の配列」にするか決めた。

Xeon 3.0GHz / gcc(4.1.2)
２分木　　　　　　31.5[s]　→　29.6[s]
１レベルバケット　29.2[s]　→　20.0[s]

このように１レベルでも十分高速に実行できるといえるようである。２レベルの方はまだソースをいじることをしていないので、さらに高速化できるだろうがメモリの使用率が気になる。

やはりここは比較的に扱い易い１レベルを用いて、「先読み」等を行うのがいいと思われる。まずはサンプルプログラムを用いて、ロードと処理のバランスを調べていこう。

Dijkstra 法にもブロッキング。

最短路問題に使用するグラフの格納方法として Forward Star (名前が合っているか分らないが)を採用している。node 数分の配列１つと、arc 数分の配列２つによりグラフデータを格納することにしている。

ex)
tail / head / lentgh
1 2 1
1 3 2
2 1 4
2 4 2
3 2 2
3 4 3
4 2 2
4 3 3

ID / incident / head /length
0 - 2 1
1 0 3 2
2 2 1 4
3 4 4 2
4 6 2 2
5 - 4 3
6 - 2 2
7 - 3 3

この格納ならば枝のスキャンの部分は一般的な for 文となりデータの整理がし易い。明示的にループの回数は特定できるし、ループ内で使用するデータとそうでないものとを分けておけば、高速化できているのではないかと思い、実験してみた。効果がないのであれば、変数の置き直しによるオーバーヘッドにより低速化してしまうだろう。また、うまくいったら、SIMD 等でさらに高速化が期待できる。


今回実験に用いたデータは、DIMACS の NY とランダムに作成した 1000 個のクエリである。ひとつひとつは数十ミリ秒で実行してしまうので、差が出にくいかと思ったが、次のように若干であるが改善されている。誤差が積もっての結果かもしれないので、１回の処理が大きい、USA 等の大きなグラフでも実行みることにした。しかし、USA-road-d.USA.gr では期待を裏切られ、あまり効果が表れていない。

CPU : Xeon3.0GHz / Mem : 8GB

[USA-road-d.NY.gr]
通常　　　　　：52秒
ブロッキング後：49秒

[USA-road-d.USA.gr]
通常　　　　　：33秒
ブロッキング後：34.5秒



以下、違うマシンでの結果を改善されたと勘違いしました。
/*--------------------------------------------------
ただ、以前の 46 秒ほどに比べ、10 秒以上も改善されており、
なんというか今回の改善が直接効いているのではないのではないかと思う。

この前の BLOG のときと異なる点は、確認のためにスキャンしている枝数をカウントしているだけである。確信はないがこれが効いている可能性が高いため、データ・処理の流れが安定的ではないことで、実行がうまくいっていないのかもしれない。もう少し流れを追えば分かるかもしれない。
--------------------------------------------------*/

Let's Note。

研究費で Let's Note を買っていただいた。
新しいものを手に入れるとどうしてもテンションが上がる。
Core 2 Duo 1.8 GHz、メモリ 2GB を搭載した最新モデルである。

CF-Y7 という 14.1 型の一番大きな Let's Note ではあるが、
中身がホントに入っているのかと疑うほどかなり軽い。
以前、Dell で購入した Inspiron 700m とは比較にならないほどである。

また軽さだけでなく、
無線 LAN や 光学ドライブを個別に電源を落とすことができたり、
強度を保つためにあえて薄くしない点など、
よく考えられたノートパソコンであると感じた。


新たな相方と共に頑張っていこうと思います。