2006年10月

クラスタ上で死んでるマシン及び元気の無いマシンを判定するのはどうやるのが一番楽なのか？　実験始める前にマシンの選択をしておかないと mpirun が元気の無いマシンも使っちゃうので結果が変になる．やはり一度こういうことをするプログラムを書いておくべきだな．

一部データと設定を除きほぼ元通り．ただ，Meadow さんを新しくしたら .emacs で文句を言われるようになったり色の設定が見難くなってたり…　ついでに .tex を開くと自動的に落ちてくれたり…（自前のスクリプトのせいだったことが判明）．ま，そんなことはどうでも良くてリカバリディスク出すために埃をかぶったせいか咽をやられた気配．

意外と細々した設定やらソフトやらが多かったらしい．いまだ復旧できず．cygwin で自前コンパイルしたのとか吹っ飛んでるし，LaTeX のパッケージとかも吹っ飛んでるし，サービスの登録も吹っ飛んでるし，プリンタも吹っ飛んでるし．

サルベージしそこなったデータが存在していることに気づき急いで救出に向かったのだが…　救出途中にHDDケース内からまた高周波の鳴き声が聞こえてきて…　データ抜き出せん．

結論：とりあえず HDD がぶっ壊れてた．

ソフトケース内で起動しっぱなしになってたから熱で軸受けがやられたか？

昨日，バックアップの途中でまた読み込みエラー＆再起動できず．KNOPPIX で覗こうにもアクセスしに行ったきり帰ってこない．ついでに AC アダプタも出力がとてつもなく不安定になってたことが判明．つーことで，新しい HDD と HDDケース，ついでに AC アダプタを購入．痛い出費だ．んで，早速ノートPC分解．こういうとき小型機(Let's note W2D)は面倒すぎる．全部で 29個のねじと，キーボードにバックプレートを外してようやく HDD が交換可能．結局半日かかってデータの完全サルベージと HDD の換装（40G -> 80G）が終了．これから環境の再構築にかかる．

とりあえず，一体どのパーツが悪さをしていたのだろうか？

電源を入れ WindowsXP へログオンして暫く，デスクトップになかなかアイコンが描画されないなぁと思っていたら突然ブルースクリーンに．ネタを見せるための起動でブルースクリーンという別ネタにたどり着いたまでは良かったのだが，そのまま暫く放置してたら「ピーーィ．キューウィーァ，ビーピーィ」とか騒ぎ出した．これはやばいかなと思って再起動したら HDD のアクセスランプが付きっぱなしで，相変わらずの油が切れかけた回転軸のような高周波「ピーィ，キューィ」なノイズ．BIOS 画面で確認したところ IDE のマスターに何も付いていない．起動しようとしても no system みたいな表示で停止．HDDヤバイ？

ということで，ＨＤＤ吹っ飛んだかと思っていたのだが，しばらくバッテリ抜いてほっといたら復活してた．バンザイ．とりあえずさっさとデータを吸出して RAR で固める．データ用ディスクのみで全部で ９万ファイルぐらい．今のところ問題なく吸い出せているのでチップセットか何かが熱暴走してたみたい．

まとめ：「肝を冷やさないためにも，もっとこまめにバックアップしましょう．」

うーん，GWT の widget から element を抜き出して javascript に渡した後にその element に対応するもとの widget を知るにはどうしたらよいか？　これが出来ないと仕事が進まないので失速中．やっぱ JSNI 使わないほうが楽なのかなぁ…

中で「パチパチパチパチ...」とか鳴いてる．鳴き止んだのを叩いたり動かしてみるとまた泣き出したりする．コンデンサ破裂気味？

The Gwigle Game という google の検索結果から検索に使った言葉を答えるゲームをやった．とりあえず final と書かれたページまで行ったので一通り正解し終えた気がする．面倒というか分かりにくかったのは株の情報から検索ワードを当てさせる問題とか「もしかして」で訂正される前の間違った綴りを当てさせる問題とかで，これらのいやらしい問題もあって結局二日かかってしまった...

Drag and Drop が標準では実装されてない．マウスイベント取れるから自前で実装できるけれど面倒．Developper forum のほうにコードがあるからもって来ればいいのだがマウスを押したとこからドラッグが始まってくれてもちょっと困るので...　毎度のごとく多少動いたらドラッグ開始に書き換えねば．ついでにドラッグしてるものは半透明にしたいので...

 filter: alpha(opacity=25);
 -moz-opacity:0.25;
 opacity:0.25;

あたりの設定を style に入れときゃいいのかな．先は長い．

更なる高速化のためにSSE2に手を出してみる．CIPスキームの最内ループの元がこんなもん：

  double const *v = VV + (La+Lb)*(k-1) + La;
  double *v2 = VV + (La+Lb)*(k-1);
  for(double const*const ve = VV + (La+Lb)*(k-1) + La + STEPLEN; ve != v; v2+=2, v+=2){
    v2[0] = CA2 * v[-2] + CA1 * v[-1] + C0 * *v + CB1 * v[1];
    v2[1] = DA2 * v[-2] + DA1 * v[-1] + D0 * *v + DB1 * v[1];
  }

配列をインターリーブして使ってるが，長さ 2 のベクトルを一つ左の値と現在地の値で更新している．ちょうど 128bit のデータになってるから SSE2 にぴったりなので，SSE2を使ったコードが下．当然のごとく配列の alignment を 16byte に合わせておく．

__m128d A2 = _mm_setr_pd(CA2, DA2);
__m128d A1 = _mm_setr_pd(CA1, DA1);
__m128d A0 = _mm_setr_pd(C0 , D0 );
__m128d B1 = _mm_setr_pd(CB1, DB1);
double const *v = VV + (La+Lb)*(k-1) + La;
double *v2 = VV + (La+Lb)*(k-1);
__m128d pv = _mm_load_pd(v-2);
for(double const*const ve = VV + (La+Lb)*(k-1) + La + STEPLEN; ve != v; v2+=2, v+=2){
  __m128d r = _mm_shuffle_pd(pv,pv,_MM_SHUFFLE2(0,0));
  __m128d op = _mm_shuffle_pd(pv,pv,_MM_SHUFFLE2(1,1));
  r = _mm_mul_pd(r, A2);
  op = _mm_mul_pd(op, A1);
  r = _mm_add_pd(r,op);
  pv = _mm_load_pd(v);
  op = _mm_shuffle_pd(pv,pv,_MM_SHUFFLE2(0,0));
  op = _mm_mul_pd(op, A0);
  r = _mm_add_pd(r,op);
  op = _mm_shuffle_pd(pv,pv,_MM_SHUFFLE2(1,1));
  op = _mm_mul_pd(op, B1);
  r = _mm_add_pd(r,op);			
  _mm_store_pd(v2, r);
}

xmm レジスタがもう一本あればもう少しスマートなのだが...　上のコードより場合によっては下のほうが速い．アセンブラ上は定数のうち一つをメモリから取るようになるが，並列に実行できる命令が増えるので速いのかな？

  __m128d op1 = _mm_shuffle_pd(pv,pv,_MM_SHUFFLE2(0,0));
  __m128d op2 = _mm_shuffle_pd(pv,pv,_MM_SHUFFLE2(1,1));
  op1 = _mm_mul_pd(op1, A2);
  op2 = _mm_mul_pd(op2, A1);
  __m128d r = _mm_add_pd(op1,op2);
  pv = _mm_load_pd(v);
  op1 = _mm_shuffle_pd(pv,pv,_MM_SHUFFLE2(0,0));
  op2 = _mm_shuffle_pd(pv,pv,_MM_SHUFFLE2(1,1));
  op1 = _mm_mul_pd(op1, A0);
  op2 = _mm_mul_pd(op2, B1);
  op1 = _mm_add_pd(op1,op2);
  r = _mm_add_pd(r,op1);

うーむ，ここら辺になると Pentium4 の仕様を良く調べないと全く分からない．

次なる最適化は SSE2 の SIMD 命令の使用だ，と．128bit レジスタが8本使えるからいろいろレジスタだけで出来そう．調べてみると xmmintrin.h, emmintrin.h, pmmintrin.h が SSE, SSE2, SSE3 を使うためのヘッダファイルらしい．インテルのコンパイラのリファレンスを見ないと細かい部分がどう使うのか良くわからないが使えるものは使ってみよう．ちなみに g++ に -msse2 のオプションをつけないと怒られた．

ある点の更新に左右の固定範囲の点の値を使う場合ようなスキーム全般に対して，先の例と同様のキャッシュを効くようにするループ変形を可能とする方法を思いついた．

ということで，とある人間が書いたCIPスキームとやらのプログラムを変形してみた．結果としてメモリを少々余計に喰うがやっぱ３倍速くなった．さて，忘れないうちに原理をまとめとくか．

キャッシュにヒットし続けるようにループを分割してみた（簡単のため配列の使い方も少し変えてる）．３倍から５倍程度速くなった．あとは sse2 の命令とか使ってみたいところだけどうまく使える形にプログラムを変形できない…　むりかなぁ？

初期の単純なネストループ：

        for(int p = R; p >0; p--) {
            int q = (ISROOT()) ? p-1: 0;
            double *u = U+q;
            double *v = u++;
            register double cv = *v;
            for(double const *e = U+Len+p; u != e; u++,v++){
                register const double cu = *u;
                *v = (1 - MU) * cu + MU * cv;
                cv = cu;
            }
        }

内側のループを分割してキャッシュ上のデータにアクセスしまくる：

        double *uu = U;
        for(int p = R; p >0; p--) {
            int q = (ISROOT()) ? p-1: 0;
            double *u = uu+q;
            double *v = u++;
            register double cv = *v;
            for(double const *e = uu+p; u != e; u++,v++){
                register const double cu = *u;
                *v = (1 - MU) * cu + MU * cv;
                cv = cu;
            }
        }
        double const *uue = uu + Len - STEPLEN;
        // iteration - STEPLEN * floor(Len/STEPLEN) steps
        for(; uu < uue; uu+=STEPLEN) {
            for(int p = R; p >0; p--) {
                double *u = uu+p-1;
                double *v = u++;
                register double cv = *v;
                for(double const *e = uu+STEPLEN+p; u != e; u++,v++){
                    register const double cu = *u;
                    *v = (1 - MU) * cu + MU * cv;
                    cv = cu;
                }
            }
        }
        // last - rest steps
        int rlen = Len - STEPLEN * (Len/STEPLEN);
        for(int p = R; p >0; p--) {
            double *u = uu+p-1;
            double *v = u++;
            register double cv = *v;
            for(double const *e = uu+rlen+p; u != e; u++,v++){
                register const double cu = *u;
                *v = (1 - MU) * cu + MU * cv;
                cv = cu;
            }
        }

多少の余計な計算を必要とするが，数回分の通信をまとめてやってしまう．今回のプログラムは値の更新に左の値しか使わないので楽．ＣＰＵの力がある場合は２倍から３倍くらい速くなった（１６回位まとめて）．次はキャッシュでも考えて…　

ループ始めに毎回通信：

    MPI_Request reqs1, reqr1;
    for(int t = 0; t < T; t++){
        if(!ISLAST())
            MPI_Isend(U + Len, 1, MPI_DOUBLE, Rank + 1, TAG1, MPI_COMM_WORLD, &reqs1);
        if(!ISROOT())
            MPI_Irecv(U      , 1, MPI_DOUBLE, Rank - 1, TAG1, MPI_COMM_WORLD, &reqr1);
        else
            U[0] = 1;
    
        if(!ISLAST())
            MPI_Wait(&reqs1, MPI_STATUS_IGNORE);
        if(!ISROOT())
            MPI_Wait(&reqr1, MPI_STATUS_IGNORE);
        register double *u = U;
        register double pu = *u++;
        for(double const *e = u+Len; u != e; u++){
            register double cu = *u;
            *u = (1 - MU) * cu + MU * pu;
            pu = cu;
        }            
    }

ループ始めに R 回分通信しとく：

    MPI_Request reqs1, reqr1;
    for(int t = 0; t < T; t+=R){
        if(!ISLAST())
            MPI_Isend(U + Len, R, MPI_DOUBLE, Rank + 1, TAG1, MPI_COMM_WORLD, &reqs1);
        if(!ISROOT())
            MPI_Irecv(U      , R, MPI_DOUBLE, Rank - 1, TAG1, MPI_COMM_WORLD, &reqr1);
        else
            U[R-1] = 1;
       
        if(!ISLAST())
            MPI_Wait(&reqs1, MPI_STATUS_IGNORE);
        if(!ISROOT())
            MPI_Wait(&reqr1, MPI_STATUS_IGNORE);
        for(int p = 0; p < R; p++) {
            int q = (ISROOT()) ? R-1 : p;
            double *u = U+q;
            register double pu = *u++;
            for(double const *e = u+Len+R-q-1; u != e; u++){
                register const double cu = *u;
                *u = (1 - MU) * cu + MU * pu;
                pu = cu;
            }
        }
    }

遅そうなプログラムの最適化でもしようかねぇ．とりあえずシーケンシャル部分から書き換え．無駄に配列使わず上書きで行く．次は通信をまとめてみようか？

配列２本を使う：

        for(int i = 1; i <= Len; i++)
            V[i] = (1 - MU) * U[i] + MU * U[i - 1];      
        double *tmp = U; U = V; V = tmp;

こんなものは一本で十分：

        register double *u = U;
        register double pu = *u++;
        for(double const *e = u+Len; u != e; u++){
            register double cu = *u;
            *u = (1 - MU) * cu + MU * pu;
            pu = cu;
        }            
 

これで一回のスッテプでのメモリアクセスが一箇所になった．良し．

新宿のタカシマヤにて購入，たぶん１０００円．岡山の日本酒で漬けた梅酒．やっぱりおいしい．アルコール度数が６度程度と低いのでいくらでも飲める．梅乃宿のと比べると度数が低いということもあるけど良い感じのさっぱり感があるかなと．次は同じところの白桃酒でも試してみようか？

テンメンジャンがまだあったのでジャージャー麺を大量生成．４人前を２食に分けて喰う．ボケてテンメンジャン入れていためる前にスープを突っ込み味が…　まあ，気にせず喰えたのでよしとしよう．

久々にLAN内にDNSをおいてみる．あんまり意味無いけどURLの長さが縮まったのでよしとしよう．次はルータにやらせてる DHCP を移行しようか？

インクリメントだと桁数に指数的になってしまうので筆算のように計算するスクリプトを書いてみた．メイン部分はキャリーと足される二つの数の全パターンについて次のキャリーと一桁の答えを生成する正規表現マッチ連発部分．普通にやると全部で200通りになってしまうので少々まとめて40通りに抑えたが…　手で書くのは面倒なのでプログラムに機械生成させて手を抜く．もっとスマートなプログラムが出来ないかなぁ？

sum.sed，gen.java

インクリメントとデクリメントが出来るので頑張れば出来るだろうけど高速に実装できないかなぁと．ちょっと調べてもあまり見つからない…．さすがに bc の機能を置き換えるのはむりかな．

sed は s コマンドしか使えないというのも悲しいので他のコマンドも含めてちゃんと学習しなおす．

とりあえず，sed にはパターンスペースとホールドスペースという二つのバッファがあって，それぞれ改行文字でセグメントという単位に区切られる．s コマンド以外は，これら二つのバッファに対して queue の操作みたいなことを行うか，ラベルへのジャンプをするのが基本．sed の基本的な文法は

「条件」「コマンド」
「条件」「コマンド」
…

で，上から順にパターンスペースが条件にマッチしたらコマンドが実行される．

条件抜粋：

数字

指定行番号

$

最終行である

条件1,条件2

条件1が成立した行から条件2が成立した行まで． ある種のフラグとして利用可能

条件!

条件が成立しない

/正規表現/

正規表現にマッチ

使うコマンドの抜粋：

p

パターンスペースを改行つきで出力

P

パターンスペースの最初のセグメント（改行で区切られたもの）を出力

q

パターンスペースを改行つきで出力して終了

{

次の } までを命令として実行

s/正規表現/文字列/

正規表現にマッチする部分を文字列に置き換える（最初のみ）

s/正規表現/文字列/g

正規表現にマッチする部分を文字列に置き換える（全部）

y/文字列1/文字列2/

文字列1 の各文字を文字列2の対応する文字に置換

d

パターンスペースを削除後に新しい行をパターンスペースに読み先頭へジャンプ

D

パターンスペースの最初のセグメントを削除し先頭に戻る．パターンスペースが空なら次の行を読みこむ

N

一行読みパターンスペースに追加（改行も生きてる）

h

パターンスペースの内容をホールドスペースに読み込む

H

パターンスペースの内容をホールドスペースへ追加

g

ホールドスペースの内容をパターンスペースに読み込む

G

ホールドスペースの内容をパターンスペースに追加

x

パターンスペースとホールドスペースの内容の入れ替え　

b ラベル

ラベルへジャンプ．ラベルなしで先頭へジャンプ

t ラベル

直前の s で置換されたらジャンプ（正規表現条件と s と b で置換可能）

:ラベル

ジャンプ先のラベル

i\ 文字列

文字列を出力．行頭の空白や改行には \ をつける

TIPS:

• /正規表現/{ 命令列 } という書き方を見ると awk を思い出せる
• スクリプトの最後にジャンプが無いときは p と d が挿入される
• s コマンドとかで正規表現が省略されると直前の正規表現が使われる
• コマンドはセミコロンで区切ると一行で書ける

とりあえず，セグメントに区切って複数のデータを持ち運びつつ，s を使って必要な部分を抜き出して加工すると．何かのアルゴリズムを sed で実装するための導出規則がほしいところだ．

お好み焼きに比べて作るのが面倒であることを認識する．店員さんのすばらしい手さばきで作っていただいたのだが見てただけだと堤防の崩し具合が良くわからんな．次回は自作にチャレンジしてみよう．

おそらく多くの人間が同じことをするので繋がらなくなるのだろうが繋がらないなぁ．ソフトは 403 が返ってくるって文句言うだけだし．良い機会だから asf とかのストリームの勉強でもしてみようか？

奈良県の梅乃宿酒造の「梅乃宿の梅酒」．宇宙酒と一緒に買った一つで飲んでみた．一つ前のあらごし梅酒の元になるのだろうか．とりあえずアルコール度数１７％と高めだけど香も味もはっきりした梅酒ということで文句なし．あらごしに比べると酸味が少ないのである意味のみやすいかも．酔いやすいけど．ちなみに日本酒でつけているとのこと．当り．

昨日の雨にダメージを受けたのであに濁点をつけるべく頑張ってみる．結局フォントとしては存在しないので半角カナに逃げてみるしかないのかなと．どっかに濁点付けまくったフォントとか落ちてないかなぁ．かなだけでいいので．

ビデオ会議風に輪講をやってもらえると非常にありがたいのだが…　そうも行かないので雨風の中秋葉原へ．途中２回ほど傘がおちょこになりかなり濡れる羽目になった．毎週金曜日だけは晴れてほしいものだ．どうでもいいけどUSB-シリアルケーブルが３５００円もして高いなぁと思う．自前で作れば AVR+α とケーブル代で安くなりそう．ドライバ書くのが面倒だけど．

Amazon で注文しといたいわゆる Dragon Book の第二版がとどいた．第一版に比べて並列関係の最適化の章が増えているというのが購入の理由．日本語版の古いやつを買うよりは値引きのために安くお買い得だというのも理由だったりするが…　とりあえず頭から読むか，英語で少々面倒だけど．

書き方がたくさんありすぎてどう書けばよいか分からず．再利用は考えないけどメンテナンスはしやすい書き方ってどういうものだろう？　とりあえず anonymous type で突っ走る．

お話にならないくらい遅くて面白い．１フレームの処理に何秒かかっているのやら．XViD, Lame, MPlayer のコンパイルは成功したのにこれらはムダだったことに…　こんなに遅いと FFRecord で音声を圧縮しながら録画は無理そうだなぁ．ある意味予想通りなのだけど予想を裏切る結果がほしかった．

GLAN TANKでTV録画 を参考にPX-TV402UをGLAN TANKにつなげて録画してみる．とりあえず録画できて予約システムの VRS もうまく動かせた．しかし，CATV と VHF を共に使おうと思うと ntsc-bcast-jp と ntsc-cable-jp を切り替えないとならんので…　そこらへんを含めてソースをいじる．仕組みが単純なのでテレビ王国の My番組表に対応するように書き換えてみようかなぁ．

何を血迷ったか雨の中グラタンこと挑戦者の GLAN TANK を買って来てしまう．HDD には Maxtor の新しめの 250G を選択．本当は 300G がほしかったが雨の為探すのを断念．メインマシンより良い HDD を積んだ NAS ってのもどうかと思うけど…　んで，ついでに Plextor の PX-TV402U も買ってきた．何をしようとしているのかばれる構成である．とりあえずセットアップだけさっさとすませて起動したのでよしとする．