MLB - その１。

ずいぶん、勘違いをしていたみたいなので、しっかり論文を読む事にした。

階層がいくつかあり、上位階層（下位階層よりかなり少ない）が下位階層のある範囲に格納した要素数をカウントしていて、最小ポテンシャル点を探索する際にヒントになるというものだと認識していた。レベルをいくつかにすべきかは、最大枝長で決めるという単に１レベルバケットを拡張したものかと思っていたのだが、実際にはそうではなかった。

「階層数＝レベル数」、「最大枝長で最大レベルは定まる」ことは同じだが、上位階層と下位階層の関係が異なっている。


まずは、基礎となっている部分から見いこう。図を用いた方がわかりやすいので、こちらを参照していただくとよいだろう。

まずは図の見方になるが、以下のようになっている。
・十進数の数字は MLB に格納された点のポテンシャルになっている。
・十進数の数字のビット表現（２進数表現）として、最下位ビット～最上位ビットとなっている。今回はそれぞれ 0 ～ 4 レベルとする。


次に挿入操作について。

１、まず最後に MLB から取り出した点のポテンシャルを覚えておく。
　　ex) 10

２、１のポテンシャルから、どれだけビットが変化したものを挿入するかをチェックする。
　　その際、変化したビットのうち、最大のレベルとそのビットを確認。
　　ex) 10 と 14 であれば、01010 と 01110 なので、2-level で、1 となる。

３、２で求めた レベルとビットから、挿入するバケットを決定する。
　　ex) 2-level, 1 --> B(2,1)


他の要素も同様に決定すると、B(0, 1), B(2, 1), B(3, 0) となる。

バケットベースのデータ構造。

マルチレベルバケットについて。

１、１レベルバケット法
最大枝長 U とする。大きさ nC が必要にみえるが、実際には (U+1)の大きさを持つ、循環リスト（キュー）で十分。格納するバケットを選択する際には、mod U で決定する。


２、２レベルバケット法
(bucket_size)^1/2 の大きさで、１レベルの (bucket_size)^1/2 の範囲に格納されている要素があるかどうかを判定する。


３、マルチレベルバケット法
１、２とはかなり雰囲気が異なる。有効ビットの動きにより格納するバケットを決定する。長さが違った点が同じバケットに格納された場合、ソートしているようである。


３についてはまだよくわかっていない。資料をあるだけ読もう。

ISO イメージ - Linux & Windows。

Linux での ISO イメージの作成の手段として dd を用いるのが簡単である。
mount も以下のようにして、簡単にマウントできる。

$ dd if=/dev/cdrom of=XXX.iso

# mount -t iso9660 -o loop "iso_file_name" "mount_point"


一方 Windows では市販ソフトや ImgBurn などのフリーソフトが、多く存在するが、ISO イメージをマウントするツールといえば、DAEMON Tools であった。実は MicroSoft からも以下のようなソフトが公開されている。Google でも「ISOイメージ　マウント」で、一番上に位置してはいるが、今回初めて知った。

どういった意図でこれが公開されているのかと思うほど、簡素なツールで、サポートページが英文ですら書かれていない。READ ME を見れば使い方は分かるが正直使いづらい。ただものすごく軽いので、そういう意味ではいいのかも。Windows XP のみ対応のようで、64bit 版では動作しないようだ。


Virtual CD-ROM Control Panel for Windows XP
解説ページ

CentOS 5.2 on DellVostro400。

Dell の Vostro 400 という新たなマシンを導入した。スペックは以下の通り。

CPU : Intel® CoreTM 2 Duo E8500（6MB L2 cache, 3.16GHz, 1333MHz FSB)
Memory : 4 GB
HDD : 250GB x 2

せっかくの HDD x 2 構成なので、CentOS 5.2 64bit を Install。

しかし、"Loading ata_piix driver ..." で止まってしまう。

Google で検索してみると、こちらを発見。
大変参考にさせていただきました。ありがとうございます。


knoppix は 5.0 でもいけたが、この作業は必要なのだろうか。
原因も良く分からないのだが、どうにかインストールは終了した。
普段 knoppix は使わないが、メディアに焼いておいて正解だった。

■手順■

[1] knoppix を 以下の boot option を設定し起動。
　　boot: linux irqpoll all-generic-ide noapic nolapic
　　
　　※ない場合、内蔵ディスクを認識できず、起動に失敗してしまう。

[2] knoppix を終了しディスクが取り出されるので、CentOS の DVD に入れ替えて、CentOS のインストールを開始する。

[3] CentOS も knoppix のときと同様に boot option を設定する。

[4] インストール完了後の再起動の際も、同じ boot option を与える。

[5] 起動後、/etc/grub.conf の kernel boot option に、同じものを記述する。

HugeTLB fs on PowerEdge2900。

mmap() を用いてファイル入力を高速化してからかなり実験がし易くなったため、まとめと確認ということで多めのクエリを実行してみた。また、HugeTLB も用いたものとの比較も行っている。

こちらのマシンでも環境を整えるために以下のような手順を行う。
こちらも Huge Page Size は 2MB であるので、実際に必要な 1.2 GB より多めに 768 page（1.5GB 分）を確保した。

su 権限で、以下のような手順で HugeTLB fs を mount する。
# mkdir /huge
# mount -t hugetlbfs hugetlbfs /huge -o rw,mode=0777
# echo 768 > /proc/sys/vm/nr_hugepages


また実行は以下のように、環境変数を設定する（su 権限は必要ない）
$ HUGETLB_MORECORE=yes LD_PRELOAD=libhugetlbfs.so ./a.out arg1 arg2 ...


グラフデータは同じであるが、クエリ数が１０という小さな実験に対しての記事があるが、こちらも penryn 系の Core 2 Duo マシンで行ったものである。PowerEdge2900 の CPU も 45nm プロセスで製造された penryn 系のコアなので、同じような割合で改善されているのが分かる。


[OS] CentOS 5.1 64-bit
[cpu] Intel(R) Xeon(R) CPU X5460 @ 3.16GHz
[memory] 48 GB

[graph] USA-road-d.USA.gr
[query] random p2p x 256



[Heap]
655.8 [sec] (x 1.00)
562.1 [sec] (x 1.17) (with HugeTLB)

[bucket]
417.7 [sec] (x 1.00)
345.7 [sec] (x 1.21) (with HugeTLB)


全米データでも、実際にヒープ内に格納されるのは、点数とポテンシャルを格納した高々 6000 程のデータである。点数分の逆ヒープ配列にもアクセスすることになるが、いずれにしてもバケット法よりもデータの局所性が高い。

バケット法では 点数+1 の 368856 程の要素の配列と、ノード数分の両方向リンクリストにアクセスしなければならない。これはヒープに比べてバケットのほうがデータアクセスが広域になることを示しており、よって TLB ミスによる影響を受けやすい。

こちらは libhugetlbfs というライブラリを用いて実行しているが、mmap() の扱いにも慣れてきたので自作の関数を作成すれば、より詳細な制御を行うことができるかもしれない。

最短路ソルバーのグラフ入力高速化。

現在の最短路ソルバーは、ハイスペックなサーバでも DIMACS フォーマットの全米データの読み込み（グラフと座標）に１分弱ほどもかかってしまう。Point-to-Point（１対１）タイプの１クエリ（始点・終点のペアが１組）で３，４秒しかかからないため、Web サービスでは実行時間のほとんどがデータ入力に要する時間である。


ちなみに全米グラフは 23947347 点、58333344 枝であるが、DIMACS フォーマットではグラフは 58333344 行（枝数）、座標データは 23947347 行（点数）とかなり巨大であるので、読み込みに時間がかかってしまうのも無理はない。

しかしながら、メモリ上にマッピングしたファイルの速さは良く分かったので、DIMACS フォーマットデータも mmap() でマッピングして読み込むという方法も試してみる価値はありそうである。

mmap() の使いかた その３。

最短路に用いる forward-star を構成したグラフのメモリデータ を書き出し、再利用するということを行っている。

以下のような配列の先頭のアドレスを格納したポインタを含む構造体でグラフデータを格納している。それらのポインタには動的に確保した領域の先頭のアドレスを格納することになるため、それぞれのデータは連続にならないため、そのまま mmap() したファイルへコピーはしにくい。


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

typedef struct {
　int x;
　int y;
} coord_t;

typedef struct {
　unsigned int node_num;
　unsigned int arc_num;
　unsigned int max_length;
　unsigned int min_length;
　coord_t before_min; // min coordinate before normalization
　coord_t after_max; // max coordinate after normalization
　
　unsigned int *point;
　arc_t *arc;
　coord_t *coord;
} graph_t;



簡単に考えられる打開策としては、それぞれ大きな固定長の配列にするというものがある。
つまり

　unsigned int *point;
　arc_t *arc;
　coord_t *coord;

を

　unsigned int point[large_node_num];
　arc_t arc[large_arc_num];
　coord_t coord[large_node_num];

と、してしまうことである。


しかしこれでは、小さなグラフでも同じだけの容量を食ってしまい、無駄が多くなる。また、large_node_num、large_arc_num をグラフのたびに変えてもいいのだが、グラフの数だけ実行バイナリを持たなくてはならなくなってしまい管理が面倒である。書き込みも読み取りも同じ形式で読まなければ、バスエラーとなってしまうからである。


しかしながら、今回のケースではすべて int としても良いので、大きな int 型の配列ですべて済ませてしまうことも可能である。

しかしながら書き込みは良いとしても、読み込みの際に mmap() にそのマッピングするサイズを指定しなくてはならないという新たな問題が出てくる。わざわざ実行する際に引数などを受け取るのもあまりよろしくないし、そもそも中身が分からない状態でそのグラフの点数、枝数を指定するというのはいかがなものかと。


よくよく考えてみるとそのサイズは、書き出したファイルのサイズに等しいので、stat 系の関数 fstat() を用いてサイズを取得することにした。

struct stat sb;

// fd : 書き出したファイルの fd
fstat(fd, &sb);
size = sb.st_size;


このようにすれば、どのようなグラフを持ってきても関数側で処理することができ、問題もなく快適である。

現在の shortest path online solver で、全米データ(USA) を選択すると１分ほどかかってしまうので、これを用いたいと思う。待ち時間は数秒になるだろう。

メモリイメージの保存/再利用 その２。

□保存方法□

１、fd = open(,,) によって保存先を開く。

２、必要サイズを算出する（ページサイズの倍数に切り上げ）

３、ファイルの必要サイズ先にシークし、0 を書き込む

４、open() の際に出力された fd を用いて、mmap() でマップする。

５、通常のポインタのようなアクセス方法で値を書き込む

６、msync() で同期をとった上で、munmap() でアンマップ、close() でファイルを閉じる。





□再利用□
１、fd = open(,,) によって保存先を開く。

２、必要サイズを算出する（ページサイズの倍数に切り上げ）

３、open() の際に出力された fd を用いて、mmap() でマップする。

４、通常のポインタのようなアクセス方法でグラフデータをコピーする。

５、munmap() でアンマップ、close() でファイルを閉じる。





□用いたおもな関数群□

#include ＜sys/types.h>
#include ＜sys/stat.h>
#include ＜fcntl.h>
int open(const char *pathname, int flags, mode_t mode);


#include ＜unistd.h>
int close(int fd);


#include ＜sys/types.h>
#include ＜unistd.h>
off_t lseek(int fd, off_t offset, int whence);


#include ＜unistd.h>
ssize_t read(int fd, void *buf, size_t count);


#include ＜unistd.h>
ssize_t write(int fd, const void *buf, size_t count);


#include ＜sys/mman.h>
void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *start, size_t length);


#include <sys/mman.h>
int msync(void *start, size_t length, int flags);

メモリイメージの保存/再利用 その１。

HugeTLB fs を用いる第一段階として、グラフデータをファイルへ書き出す部分のコーディングを行った。以前まではテキストデータであるグラフデータを実験のたびに読み込み、データを加工していたのだが、それでは Online Solver に対応できない。

そこで、加工し終わって後はダイクストラ法を解くだけとなっているグラフデータをファイルへ書き込んだものを作成しておき、実行するときはそのバイナリデータをマッピングすることで、グラフ入力の時間を大幅に省略することができる。


以下の２つのファイルを読み込む時間を計測してみた。

[全米データファイル]
USA-road-d.USA.gr, USA-road-d.USA.co

[バイナリデータ]
上の２つを forward-star に加工したデータ


[結果]
全米データファイル：51.0 秒
バイナリデータ　　： 0.3 秒


とても高速である。何度も同じデータを用いて実験する場合、始めの１回を適応することで、かなりの時間を省略することができる。Web サービスもこれでかなり良くなるだろう。HugeTLB fs でさらに高速になるだろう。

Shortest Path Online Solver。

最短路問題を解く Web サービスをこっそりと作成していたが、暫定的ではあるが公開することにした。現時点では DIMACS format に対応しているが、TIGER にも対応していければと思う。またグラフ読み込み時間を省略するために共有メモリ等の工夫をするべきであるといえる。


「使用方法」
１、表示サイズとグラフを指定する。

２、始点と終点をクリック（もしくは画像の座標を手入力）し、[submit] を押す。

３、出力は PNG なので、簡単に保存できる。（1600 x 1600）


※ グラフデータをメモリに常駐するところはまだなので、全米（USA）はファイル読み込み時間のせいで１分ほど時間がかかってしまうので、注意していただきたい。

※ 同じタイミング、同じグラフで実行すると待つことになるので、こちらも併せてお願いしたい。

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

バグ取り。

グラフデータによって、セグメンテーションエラーやバスエラーが起きてしまっていて、どうしたものかと思っていたのだが、動的にメモリを確保した範囲を越えてのアクセスしてしまっていたことが原因であった。

TIGER/Line では、点 ID が 0 ～ node_num-1 であるので、勘違いしてしまった。違ったところでエラーが起きてしまっていたので、原因を発見するのに思った以上に時間がかかってしまった。

基本的なことながら、動的確保と使用する範囲は気を付けよう。

Firefox 3.0 正式リリース。

「24時間以内に最もダウンロードされたソフトウェア」としてギネスブックの世界記録に挑戦する「Download Day」も行っているそうだ。日本時間 19 日の午前 2 時まで行っているそうで、もちろん協力させていただいた。

レンダリングも JavaScript も「史上最速」というだけあって、その効果を体感することができる。ここ最近 Firefox2 → Safari となってたのだが、Firefox2 → Safari → Firefox3 と戻ってきそうである。

アドレス空間のロック/アンロック。

#include ＜sys/mman.h>
int mlock (const void *addr, size_t len);
addr から len バイト分の仮想メモリ領域を物理メモリ上にロックする。



#include ＜sys/mman.h>
int mlockall (int flags);
カレントプロセスのアドレス空間内のページすべてを、物理メモリ上にロックする。

・MCL_CURRENT
プロセスのアドレス空間に現在マッピングされているページ、スタック、データセグメント、ファイルマッピングなどすべてをロックする。
・MCL_FUTURE
プロセスのアドレス空間へ今後マッピングされるページもすべてロックする。



#include ＜sys/mman.h>
int munlock (const void *addr, size_t len);
addr から len バイトの範囲に含まれるページをアンロックする。


#include ＜sys/mman.h>
int mlockall (void);
mlockall() の逆。


#include ＜unistd.h>
#include ＜sys/mman.h>
int mincore (void *start, size_t length, unsigned char *vec);

システムコールが発行された時点で、メモリ領域内のページが物理メモリ上に存在するかどうかを示すベクタを得られる。ページサイズでアラインメントされたアドレス start からメモリ領域の length バイト分までの各ページが、得られたベクタ vec の１バイトに対応している。vec には (length-1+page_size)/page_size バイト以上の領域が必要である。各バイトの最下位ビットが１ならば、対応するページが物理メモリ上に存在し、０であれば存在しないことを表している。



mlock() を用いれば、グラフデータがスワッピングすることを防ぐことができそうだが、共有メモリの扱いがよくわかっていないので、もう少し調べてみようと思う。

デーモン or 共有メモリ。

通常の実験でもグラフの入出力に要してしまう時間がかなりの割合をしめている。そのため、Web サービスで全米データを扱う際には、なんらかの形でメモリ上に格納し、グラフ読み込み時間を減らしたい。

考えられる方法として、以下どちらかと思っている。


１．共有メモリを利用する
OS を再起動するまでメモリに乗ってくれるので、扱いがかなり簡単であるといえる。
心配であるのはメモリアクセスに関するパフォーマンスに関する事である。
共有メモリの扱いが、通常確保する際と比べて優先度がいかほどか。


２．デーモンをつくる
グラフデータを格納したデーモンを走らせておく。
loop で待つことになるので、それがどれほどシステムに影響を及ぼすかというところ。
システムを運営させている間ずっと待機するために、あまり影響がでてくるようであれば、困ってしまう。



どちらも作成してみてから、比べるというのもありといえばありである。

Vista の互換モード。

研究とはだいぶずれてしまうが、趣味で KAWAI のスコアメーカーという楽譜作成ソフト頻繁に使っている。

ヴァージョン 2.1（1999年）と、とても古くマウスで音符を五線譜に置いていくだけというシンプルなつくりではあるのだが、とても使いやすく長年使ってきた。Finale （高価で多機能、本格的な楽譜作成ソフト）で作っているのかと思ったと言ってくれる方もいるほど、作りこめば見やすい楽譜を作ることも可能である。

しかしながら、Vista ではインストールはできるのだが起動しない。互換モードでもうまくいかない。

これを期に最新の スコアメーカー FX というシリーズを買ってみたのだが、多機能＆インターフェイスの変更により、旧フォーマットが使える以外、まったく違うソフトに見えた。使用感が異なると作業効率が下がるためにどうにか動かないかといろいろやってみたら、比較的に簡単に動作してくれた。


１．互換モード（95, 98/Me）でインストール

２．互換モード（95, 98/Me）で起動

起動することができ満足である。ただ、[ファイル]→[開く] ではうまく動かなかったので、ドロップ＆ドロップで開くようにしている。

ちなみにいろいろやりすぎで何が原因だったのか分からず仕舞いであった。もしかしたら１はいらないのかもしれない。