研究日誌。

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

stdbool.h

2010-02-28 12:47:41 | Weblog
bool 型は unsigned char で定義されているそう。
flag に使うなら 3 bit 残っていることになる。
/* /usr/include/curses.h */
typedef unsigned char NCURSES_BOOL;
#define NCURSES_BOOL bool

/* /usr/include/ncurses.h */
typedef unsigned char NCURSES_BOOL;
#define NCURSES_BOOL bool

/* /usr/include/stdbool.h */
#define false   (bool)0
#define true    (bool)1

第5回 SCOPE。

2010-02-27 00:11:43 | Weblog
どちらのお話も興味深く聞かせていただきました。船の最短路に登場してきたグラフの規模は確か 3万点 70万枝ほどの規模だったと思うので、近いグラフを選択して解いてみた。

使用したソルバは、Goldberg 氏の splib.tar に入っているもの。
●グラフ
USA-road-d.NY.gr
Nodes: 264346    Arcs: 733846

●1対全最短路問題の実行時間(Xeon X5460 3.16GHz / gcc-4.1.2)
[1] Bellman-Ford             : 1.63 sec.
[2] Dijkstra                 : 0.57 sec.
[3] Dijkstra with 4-ary heap : 0.05 sec.

EPS: alias で小サイズ。

2010-02-26 23:55:43 | Weblog
Graph: USA-road-d.USA.gr
Query: USA-10.p2p ( p2p x 10 )

(1) ダイクストラ法の実行時間
(2) (1) + EPS(パスのみの書き込み) への書き込み時間
(3) (2) の書き込みの際に "/n {newpath} def" により文字数の削減
(4) (1) + EPS(パスと全枝リストの書き込み) への書き込み時間
(5) (4) の書き込みの際に "/n {newpath} def" により文字数の削減
                   sec.    MB
(1) Dijkstra          23.55s   -
(2) EPS(path)         24.08s  776K
(3) EPS(path)*        24.45s  418K (-46%)
(4) EPS(arc & path)   32.15s  561M
(5) EPS(arc & path)*  30.59s  303M (-46%)
非常に効果もあるので、これはぜひ使用したい。
※添付の画像は NY のもの。注意を。

EPS: alias を定義する。

2010-02-25 23:33:07 | Weblog
まず header から復習。
おさらいから。
400 x 300 の EPS であれば、次のように記述するだろう。
%!PS-Adobe-3.0 EPSF-3.0
%%BoundingBox: 0 0 400 300

また次のように定義し直せば、文字数を減らす事ができる。
/a {arc}     def
/f {fill}    def
/l {lineto}  def
/m {moveto}  def
/n {newpath} def
/s {stroke}  def

以下、簡単な例だが並べて見たものだが、
最短路の出力結果は大きなファイルサイズになるので、これでも効果はある。
もちろん改行も文字なので、あまりにも多く使用するべきではない。
50 50 moveto 100 90 lineto 100 160 lineto 10 70 lineto stroke
50 50 m 100 90 l 100 160 l 10 70 l s

また、ついでに始点終点を●で印を付けると見やすそうなので、
n 280 100  1  0 360 a f s
newpath 280 100  1  0 360 arc fill stroke


最短路ソルバ: ライブラリ書き直し3.

2010-02-24 04:57:24 | Weblog
int foo(int flag, void *p) {
  if (flag & is64bit) {
    _foo_i64((int64_t *)p);
  } else {
    _foo_i32((int32_t *)p);
  }
}
もちろん処理が短めなら、以下のように書いている。
int foo(int flag, void *p) {
  if (flag & is64bit) {
    int64_t *p64 = p;
    /*  */
  } else {
    int32_t *p32 = p;
    /*  */
  }
}
としているが、どうにかこれをきれいにしたい。
うんうん唸ってもなかなか良い解決作が出てこない。

だからあんなにでかいのか！

2010-02-23 04:15:35 | Weblog
ヤマダ電器の入り口付近に設置してある入店の際にポイントカード・ルーレット装置の中身は、5インチベイカードリーダを装備した PC だったりする。我が大学の成績表を出してくれる装置（昨年やっと導入した）の中身はなんとコピー機。まるでコピー機のような印刷だなーって思っていたら、大正解。

コピー機といっても印刷機能しか使用していないので、もったいないですね。確かコピー機は機会自体も高くて、コピー代も高いはず。プリンターよりもランニングコストが高そう。

マイクはメーカーを揃えるべき。

2010-02-22 04:18:48 | Weblog
今回のライブはマイク練習一回で望んでしまったため、あまり音作りに時間を割くことはなかった。まあ逆にその段階ではないかもしれないが。vocal ensemble では使用するマイクはメーカーを統一するべきとのこと。

確かに monitor speaker ではかなり入っていると感じてたのだが、録音源を聞いてみるとあまり入っていない。ちなみに monitor が良く聞こえるのは自分だけではなくてグループのメンバーにも言われたこと。もしかしたら PA さんが音を大きくしてくれたのかもしれないが。

忘れないようにメモメモ。

ご来場ありがとうございました。

2010-02-21 04:00:26 | Weblog
四谷天窓での２回目のライブでした。ご来場ありがとうございました。ようやく緊張もなくなり、周りが見えて来れるようになったかと思います。お客さんとのコラボ、弾き語り出演者とのコラボと、新しい形式で実験的要素が多かったかと思いますが、とても楽しく終えることができほっとしています。

録音源を聞くと課題は目白押しで、練習のクオリティの半分くらいだろうか。本番で実力を出すこともまた実力。前回よりも改善はしていると思うが、まだまだ不完全燃焼感拭えないので、それを糧にこれからの練習に励むとしよう。

最短路ソルバ: ライブラリ書き直し2.

2010-02-20 04:50:49 | Weblog
まずは int argc, char **argv から、ソルバで使用する int optionid, char *filename を parse する部分。
typedef struct {
  char *grfile;
  char *cofile;
  ...
} option;
のように出現するファイルタイプをすべて含んだ構造体を定義するか非常に迷ったが、次のようにすることで落ち着いた。
int   arg_to_optionid(int argc, char **argv);
char *arg_to_filename(int argc, char **argv);
というのも、
int parse_graph_file(int grflag, char *grfile, graph *gr);
のような関数を思い浮かべたときに、結局は flag を使うことになるからで、一貫性を保つことを考えると後者の方がすっきりしていると感じる。この flag をライブラリ内で統一したものを使用することにしよう。

最短路ソルバ: ライブラリ書き直し1.

2010-02-19 04:43:06 | Weblog
ユーザー目線で最短路ソルバを書き直し中。とにかく誰でも使えるようにしたい。今のままでも使えはするが、これを内部ルーチンとすることを考えると少々使いにくいところがいくつか感じられる。

書きづらくしているポイントは、
1. グラフデータによって、32bit整数型/64bit整数型 の自動選択
2. 扱うファイルの種類がひたすら多い
となる。

1 に関しては C で書くために、プリプロセッサで別のオブジェクトファイルを分けて、template もどきの実装を行っている。これは汚いがしょうがないところ。今回のは 2 をどのように解決するかがポイントになる。

結局は flag をきちんと定義することになるのだが、これが以外と難しい。

AMD 仮想化。

2010-02-18 04:24:37 | Weblog
卒研のころ Windows ノートに QEMU で作成した vm-image を vmware player で起動させて開発など行っていた。

仮想マシン(VM)には非常にお世話になってるし、非常に興味もあるので参加してきた。個人的には、Hyper-V の話が聞きたかったが、やはり VM と AMD Opteron の位置づけというか関係という一般論だった。確かに VM をたくさん起動させるにはコア数が必要で、Intel Xeon 系に比べてコア単価の安い Opteron にアドバンテージがあるだろう。

宮原さんのお話が面白かったです。

VMware Player 3.x。

2010-02-17 04:28:51 | Weblog
default で iso-image から、インストールしてくれるようになったようだ。しかも VMwarePlayer でも vm-image を作成可能になっている。なかなか太っ腹だなと。太っ腹ついでに MacOSX 版も欲しいところ。

と考えてみたが、MacOSX 版の VMware Fusion は Windows 版に比べてお求めやすい価格設定なので、きっと無理だろう。ちなみに VMware Fusion では、WM 上の Application を Native の application のように実行できるらしい。DOCK への追加も可らしい。

試してみたいところ。

Mac は端末として完成度は高い。

2010-02-15 04:34:43 | Weblog
とくに作業する ノートPC と考えると、買ってすぐに色々できる Mac は便利。

1. windows
とにかく設定が面倒。
ssh のために putty、scp のために WinSCP、あとひたすら windows update。。
cygwin の install はとにかくやりたくない。
コマンドプロンプトが分からん。

2. Linux
windows を消してまで、インストールするのはなんだかもったいない気がする。
ちょっと youtube みたいなーって時に flash player を入れるのも面倒。
Vine や Fedora はかなり簡単に入るが。

3. MaxOS
最初から端末があるので、何もせずにある程度使える。
ただソフトウェアの追加など、迷うことあり。
nkf など当たり前なコマンドもなかったりする
terminal、ssh/scp、gcc が簡単に使えるのでかなり遊べる。