ぼうメモ帳

2005-03-21 このエントリーを含むブックマーク

卒業式のため,今から会津へと向かいます.めんどくせー.

トラックバック - http://d.hatena.ne.jp/susumu/20050321

2005-03-20

大学院修了に伴い,データ配布もとである「ぼうWEB」の移行を開始しました.

新しいアドレスは次の通りです.

http://myanya.ifdef.jp/index.html

プログラマの数学

| プログラマの数学を含むブックマーク

プログラマの数学

タイトルと作者だけで買っちゃいました(2日前だけど).ネットを見たら,3月24日発売になってるんだけど,なぜか普通に手元にあります.会津とは違うなとしみじみ感じる今日この頃です.

感想を書いていましたが,発売日前ということもあり,また発売日前に書くには不適切な表現も含まれていたため,一時的に非表示にしました.3月24日を持って再び表示したいと思います.

1+2=3 足し算に潜む迷宮

| 1+2=3 足し算に潜む迷宮を含むブックマーク

1+2=3―足し算に潜む迷宮

上の「プログラマ数学」に関連して,私が好きなタイプコンピュータ系の本を一冊紹介します.

これは,1年以上前,TAの時間にS先生に紹介していただいた本です.S先生いわく,「タイトルだけで買ったけど楽しめた.いまのM君(私のことね)にちょうど良いと思うよ」とのことで,その足で売店に走って買いに行った本がこれです.

で,そのS先生とどうも趣味が合うらしく,S先生が面白い・良いと感じる本は大体私も面白い・良いと思うんですよね.いまさらながらに,S先生の下について勉強すれば,また違った自分がいるのかなと思うことがあります.きっと,技術研究一本に突き進んで,まだ埼玉には戻ってきていないでしょう.

また少し話が脱線しました.

この本の内容は,「1+2=3」という当たり前すぎる計算を,様々なコンピュータサイエンスの観点から説明します.計算モデルとかの話です.

プログラマ数学」とは異なり,この本は,普通に定義とか数式とかが散りばめられています.「ありがたみ」があります.どのページを開いても,定義を見つけられるほど,いっぱいあります.

しかし,その間に挟まれている文章(平文?地の文?)が読みやすいのが問題なのです.「ありがたみ」があるはずなのに,ついつい読めてしまうのです.

話としては,全体で5部(+おまけ)あります.「集合」,「関数」,「論理」,「代数」,「コンピュータハードウェア」です.集合の出だしを引用すると,

集合(set)とは,要素(element, member)の集まりです.

こんな感じです.いきなり集合の定義から始まりました.まるで教科書です.

このように,この本は基礎となる定義から始まり,一つずつボトムアップ理論を展開していきます.普通なら眠くなりますよね.ここからがこの本の凄いところ.

本書では,話の内容を「1+2=3」に限定しています.だから,読者は

「とりあえずよく分からないけど,1+2=3に必要なことを説明しているんだな」

と思わせ,しかも最後にはきっちり「1+2=3」になることを示しているので,

「あ〜,さっきのはこういうためにあったのか」

と思わせるように仕向けられているのです.

また,本論は1+2=3で終えているのですが,全体の3分の1を占める付録が,また色々と雑多なネタを仕込んでいる.1+2=3のタイトルで,なんでペトリネットが出てくるんだという感じ.

まとめると,「ありがたみ」が溢れてるんだけど,その「ありがたみ」が分からなくても読み進めることができ,しかも読み終えたときにその「ありがたみ」の意味に気づくことができる.さらに,マニアックネタも仕込まれていて,いろいろと想像させると.

どうも私はこういう良くも悪くもマニアックな本が好きだなあということで,先ほどの答えとさせていただきます.

トラックバック - http://d.hatena.ne.jp/susumu/20050320

2005-03-19

次期グラフシミュレータ(GraphSim3)に関する考察(6)

| 次期グラフシミュレータ(GraphSim3)に関する考察(6)を含むブックマーク

6回目です.だれだれです.疲れてきたので,この辺で一回止めておきます.

前回は,4番目と5番目について検討した.今回は,6番目と7番目について述べる.

  1. 不必要なコンストラクタ
  2. 入出力関数でのポート指定
  3. 入出力データの扱いづらさ
  4. 無駄なtry{}catch{}構文
  5. InterruptedExceptionの記述
  6. ステートマシンの分かりづらさ
  7. DefaultFunctionalModule

ステートマシンの分かりづらさ

手続き型言語なので仕方がないといえば仕方がない問題点.ステートマシンを記述するためには,「ステートを保持する変数」+「switch-case」文を使って,ガリガリステートを記述しなければならない.これは,一般的な手続き型言語と同じ.

で,なぜ問題かというと,PCAの機能回路はステートマシンにより記述される場合が多い.とくに,ストリームの並び替えや,ストリームパターンマッチングなどが多い.どれくらい多いかと言われると数字を出せないので困るが,本当に割合的に多い.

割合的に多ければ,それらにマッチした記述方法を提供しても良いのではないかというのが,いまの考え.だから,ある特定のステートマシンについては,特化した記法を導入することで,ステートマシンの分かりづらさを解消しようと言うこと.

DefaultFunctionalModule

いちいちこれを継承するのがだるい.あと,継承してしまうことで,Java唯一の継承ルートを潰してしまうのが勿体ない.

どういうものが理想か.一番の理想は,Runnableのような機構を導入することだ.Runnableは,継承を消費することなく,Thread処理を記述することができる.では,なぜ現状ではそれを実現できないのか.一重に名前空間の問題である.read/writeメソッドをどこから引っ張ってくるのかという問題を解消できない限り無理.

Runnableを実装するクラスが単独で記述されるとき,外部の名前空間を用いない場合,もしくはインスタンスを生成した後に,何らかの方法で外部から情報を与えるようにプログラムを書く.それが面倒なときは,インナークラス,もしくは無名クラスとすることで,コンテキストに存在する名前空間アクセスする.

read/writeメソッドは,その動作はコンテキスト依存する.そのため,コンテキスト情報を何らかの方法で与えなければならない.現状では,それをDefaultFunctionalModuleが行っていると言うわけ.

これをなくすことができれば,継承ルートを空けることができて,ハッピーになれそう.だから,問題点.ここまで来ると,私の求める美しさにのみ依存した問題っぽい雰囲気もないことはないけど...

次期グラフシミュレータ(GraphSim3)(予告)

| 次期グラフシミュレータ(GraphSim3)(予告)を含むブックマーク

まだまだ問題点は残ってるけど,言いたい事は言った.だから,次からは具体的な記述方法について考えてみることにする.すこし頭の中を整理して考えたいから,もう少し経ったらだけどね.

トラックバック - http://d.hatena.ne.jp/susumu/20050319

2005-03-14 実家にて,やっとネットにつながる俺

次期グラフシミュレータ(GraphSim3)に関する考察(5)

| 次期グラフシミュレータ(GraphSim3)に関する考察(5)を含むブックマーク

5回目です.かなりだれてきました.

2回目に,問題点を挙げた.前回は,3番目の入出力データの扱いづらさについて検討した.今回は,4番目の無駄なtry{}catch{}構文と,InterruptedExceptionの記述について述べる.

  1. 不必要なコンストラクタ
  2. 入出力関数でのポート指定
  3. 入出力データの扱いづらさ
  4. 無駄なtry{}catch{}構文
  5. InterruptedExceptionの記述
  6. ステートマシンの分かりづらさ
  7. DefaultFunctionalModule

無駄なtry{}catch{}構文とInterruptedException

無駄なtry{}catch{}構文とInterruptedExceptionを含むブックマーク

GraphSimの機能回路オブジェクトは,exec関数を実装しなければならない.exec関数は,機能回路の機能記述を行う.exec関数は,繰り返し呼ばれるため,ループ記述を行う必要ない.

さて,exec関数内では,二つの例外が発生する可能性がある.ひとつは,PCAExceptionである.もう一つは,InterruptedExceptionである.

PCAExceptionは,主に,ポート名のミスなどの入出力時の例外を発生させてきた.過去形である.これは,現在のGraphSim2では,PCAExceptionは絶対に発生しないことを意味する.なぜか.いままでPCAExceptionの発生理由としていたポート名のミスなどは,明らかにプログラムバグ,エラーである.そのバグを,プログラム内で例外として補足させることはありえない.バグであれば,フレームワーク側がバグであることを通知して,そしてシミュレーションを終了させる,それが適切な挙動である考え,PCAExceptionを発生させなくした.ではなぜ,いまだにPCAExceptionが残っているのか.それは,単純に過去の遺産,なごりだけだ.はっきり言って,無駄.

では,今後PCAExceptionが活躍する場面がでてくるかどうか.それは,はっきり言って分からない.すなわち,ユーザーが例外を受け取り何らかの例外処理を記述するようなシーンがあるかどうかである.しかし,想定される例外については,ただ例外処理を記述させるよりも,例外が発生するようなシーンの統計をフレームワーク側で保存し,シミュレーション終了後に解析結果としてユーザーに示すほうが有用であると考えている.

このような理由から,次期GraphSimでは,ユーザーが補足できると言う意味でのPCAExceptionを撤廃する.

次は,InterruptedExceptionである.InterruptedExceptionは,シミュレーション実行中に,シミュレーションが強制中断された場合に呼び出される.現状では,InterruptedExceptionは,捕獲しないことを推奨している.なぜならば,この例外はフレームワーク側で捕獲するのが必然であり,ユーザー側で捕獲してもそれほどメリットはないためである.

しかし,InterruptedExceptionを見える例外としている今,うっかり捕獲してしまう場合がある.現在のGraphSim2では,InterruptedExceptionを捕まえることを前提に書かれているコードが存在する.すなわち,本来発生すべき例外を受け取れなくなってしまうことがあるということだ.これは,あまり良いことではない.

そのため,InterruptedExceptionも,見えない例外にすべきと考えている.

トラックバック - http://d.hatena.ne.jp/susumu/20050314

2005-03-09

次期グラフシミュレータ(GraphSim3)に関する考察(4)

| 次期グラフシミュレータ(GraphSim3)に関する考察(4)を含むブックマーク

4回目です.少しだれてきました.

2回目に,問題点を挙げた.前回は,2番目の入出力関数でのポート指定の扱いづらさについて検討した.今回は,3番目の入出力データの扱いづらさについて述べる.

  1. 不必要なコンストラクタ
  2. 入出力関数でのポート指定
  3. 入出力データの扱いづらさ
  4. 無駄なtry{}catch{}構文
  5. InterruptedExceptionの記述
  6. ステートマシンの分かりづらさ
  7. DefaultFunctionalModule

入出力データの扱いづらさ

GraphSim2では,入出力データは,intを保持するDataObjectを用いて表現される.当時の私の考えでは,各機能回路群に合わせた基本データオブジェクトをDataObjectを継承して定義すれば良いと考えていた.しかし,その考えは甘かった.

画像処理用の回路を設計したとき,まずはアルゴリズム検証ということで,RGB888を1データとした機能回路群を設計した.ここまでは何事もなく順調に設計が進んで良かった.しかし,いざ設計したシステムを,PCA1上で動作させるためには,PCA1で扱えるデータ型である4ビット処理に変換しなければなりませんでした.

変換するときの方針を次のように立てました.

まず,各機能回路を,RGB888処理から4ビット処理に変換します.RGB888の計24ビットデータを,下位4ビットから6つに分割し,それに伴い処理も変更します.そして,各機能回路の入力側には,RGB888から4×6データへのエンコード回路を,出力側には,4×6データからRGB888へのデコード回路を置きました.

次に,対となるエンコード回路とデコード回路を取り除きました.これにより,エンコード回路とデコード回路を削除することができます.

これらを行う際には,もちろん毎回テストを行いました.

(続く)

続きです.上記の問題は,データ型に対する回路変換が必要なところです.当たりまえっちゃあ当たり前ですが,私が目標としているのは,構造を変えずに様々なプラットホームに対応できるようにするというものですので,データ変換のために無駄な機能回路を導入して構造を変えてしまう上記の流れは,納得いくものではありません.

この問題の解決策として,現在はデータの流れを指定するチャネルに,データを自動で変換のためのロジックを持たせることを考えています.

また,DataObjectは,intを保持するオブジェクトです.逆に言えば,intを保持しなければなりません.

昔,ネットワーク越しに文字列データを取ってきて,それをフィルタリングするような機能回路(コマンドラインシェルでのパイプのようなものを実現したかった)をモデリングしたことがあります.このとき,文字列を基本データとしたかったのですが,処理のためのデータ型がDataObjectを継承しなければならなかったため,かなり苦労したのを覚えています.DataObjectを入出力するのではなく,Objectを入出力しなければならないかなと感じました.

PCAのための機能回路には,多彩なビット演算を処理するものが多々あります.それらのビット演算を容易に記述することが難しいのも,DataObjectを利用してしまったときの弊害です.

まとめると,次期GraphSimでは,多彩なビット演算を容易に記述でき,かつ文字列などのプリミティブなオブジェクトも容易に扱え,しかもデータ型の自動変換をサポートできるような,基本データ型を設定したいと感じています.

トラックバック - http://d.hatena.ne.jp/susumu/20050309

2005-03-08

次期グラフシミュレータ(GraphSim3)に関する考察(3)

| 次期グラフシミュレータ(GraphSim3)に関する考察(3)を含むブックマーク

前回は,問題点を挙げた.問題点は,次の通りです.

  1. 不必要なコンストラクタ
  2. 入出力関数でのポート指定
  3. 入出力データの扱いづらさ
  4. 無駄なtry{}catch{}構文
  5. InterruptedExceptionの記述
  6. ステートマシンの分かりづらさ
  7. DefaultFunctionalModule

そして,1番目の不必要なコンストラクタについて述べた.今回は,2番目の入出力関数でのポート指定について述べる.

入出力関数でのポート指定

GraphSim2では,ポート指定に文字列を使う.こんな具合だ.

DataObject in = read( "input" );
write( "output1", in );
write( "output2", in );

read関数はポート名を引数を受け取り,そして指定されたポートに入力されているデータをFIFOで取り出す.write関数は,ポート名とデータオブジェクトを受け取り,指定されたポートからデータをFIFOで出力する.

この文字列によるポート指定の問題を挙げると,大きく次の二つがある.

  • 間違えやすい
  • 速度
間違えやすい

まず,「間違えやすい」の一言に尽きる."input"を"imput"と打ってしまうかもしれないということだ.GraphSim2では,このような問題が起きてしまったらどうするかというと,エラーメッセージを表示して,シミュレーションを中止する.このポート指定の間違いは,シミュレーションを開始してみなければ分からないところに問題がある.すなわち,間違ってポート名を指定している式を評価するまで,このバグは発見されないということだ.これでは不便だ.

このようなケアレスミスを防ぐためには,入力補完に代表されるエディタサポートが一番有効だと思っている.eclipse等でこの入力補完を有効にするためには,文字列ではなく,シンボルでポート名を指定しなければならない*1.そのため,私は自分で機能回路を定義するとき,次のような記述を用いている.

public class Tap extends DefaultFunctionalModule {
    public static final String IN = "in";
    public static final String OUT0 = "out0";
    public static final String OUT1 = "out1";
   
    public static final String[] ipNames = { IN };
    public static final String[] opNames = { OUT0, OUT1 };

    public ThroughBetween(){
        super( ipNames, opNames );
    }

    public void exec() throws InterruptedException {
        try{
            DataObject in = read( IN );
            write( OUT0, in );
            write( OUT1, in );
        }catch( PCAException e ){
            e.printStackTrace();
        }
    }
}

このような記述を用いることで,タイプミスというケアレスミスはほとんどなくなる.なぜならば,INやOUT0,OUT1のタイプミスを起こしても,コンパイル時に「そんなシンボルはないよ」というエラーが発生するからだ.

しかし,これは記述しなければならない項目を増やすことになり,少しばかりメンドクサイ.

速度

次に,速度の問題がある.

文字列を用いてポート名を指定しているということは,内部で,ポート名とデータ入出力用オブジェクトとのマッピングを行っていることを意味する.現在は,HashMapを用いている.

GraphSimでの機能回路は細粒度で記述されることが多い.これは,処理に対して,入出力の回数の比率が多いということを意味する.私が取った簡単なベンチマークでは,全体の処理時間におけるread/write関数の処理時間の割合は,最もひどいもの90%を超え,平均しても30〜40%はread/write関数だ.これは,入出力の方法を改良することで,すぐさま処理速度を1.5倍にできることを意味している.

まとめ

現在,上記の二つの問題点を解決できるポートの指定方法を考えている.

上記の問題を同時に解決するために,ポート指定に文字列ではなくシンボルを用い,さらにread/write関数とポートを静的に結びつけるための仕組みが必要である.

現段階で私が考える理想的な記述は,次のような感じである.

入出力ポートをシンボルを用いる場合.

DataObject in = IN.read();
OUT0.write( in );
OUT1.write( in );

各ポート専用の入出力関数を定義する場合.

DataObject in = readIN();
writeOUT0( in );
writeOUT1( in );

一つ目の記述をサポートするためには,ポートのためのシンボル定義が必要である.二つ目の記述をサポートするためには,一つ目と同様,入出力関数の定義が必要である.これらの共通の問題は,シンボル定義をどこで行うのかであり,これがGraphSim3を実装するうえで重要ポイントとなる.

*1:文字列の保管を有効にするようなエディタを書けば良いというのはなしね

トラックバック - http://d.hatena.ne.jp/susumu/20050308

2005-03-06

次期グラフシミュレータ(GraphSim3)に関する考察(2)

| 次期グラフシミュレータ(GraphSim3)に関する考察(2)を含むブックマーク

昨日の続き.今回は,GraphSim2での機能回路記述を考察する.

GraphSim2では,機能のみを記述することに主目的を置いた.すなわち,ユーザーに余計なことは書かせない,である.

まず,入力されるストリームから,0x1eから0x1fの間までを抜き出す機能回路である.

public class ThroughBetween extends DefaultFunctionalModule {
    public static final String[] ipNames = { "in" };
    public static final String[] opNames = { "out" };

    public ThroughBetween(){
        super( ipNames, opNames );
    }

    private boolean output_flag;
    public void init(){
        output_flag = false;
    }

    public void exec() throws InterruptedException {
        try{
            DataObject in = read("in");
            if( output_flag == false ){
                if( in.getValue() == 0x1e ){
                    output_flag = true;
                }
            }
            else {
                if( in.getValue() == 0x1f ){
                    output_flag = false;
                }
                else {
                    write( "out", in );
                }
            }
        }catch( PCAException e ){
            e.printStackTrace();
        }
    }
}

さて,このプログラムの目的に対して(私がいま感じている)問題点を挙げる.

  1. 不必要なコンストラクタ
  2. 入出力関数でのポート指定
  3. 入出力データの扱いづらさ
  4. 無駄なtry{}catch{}構文
  5. InterruptedExceptionの記述
  6. ステートマシンの分かりづらさ
  7. DefaultFunctionalModule

こんなところか.

不必要なコンストラクタ

ほとんどの機能回路記述のコンストラクタは同じであり,それはsuper(..., ...)である.なぜこのようなコンストラクタが必要かというと,機能回路ごとに入出力ポートは異なり,機能回路の抽象クラスであるDefaultFunctionalModuleで入出力ポートを管理するためには,その具象クラスから入出力ポートに関する情報を受け取らなければならないということだ.

そして,その情報の受け渡しにコンストラクタを用いたということになる.

この,入出力ポートの情報管理に何か良い手段はないかといま考えている.入出力ポートの明示的な宣言は必要である.そして,その宣言を自動的に抽象クラスへ渡す手段はないだろうか.

一つは,入出力ポートの情報を定義するためのメソッドを用いる方法である.しかし,入力ポート,出力ポートと2つのメソッドを定義しなければならないことになり,あまり利便性があがるとは思えない.

もう一つは,インターフェイスと機能実装の分離である.すなわち,入出力ポートを定義する名前(クラス名,インターフェイス名)をJava言語の文法の範囲内で記述し,その情報を元にDefaultFunctionalModuleが入出力を管理するのである.

下は,インターフェイスを用いた例である.なお,この表現法はまだ実現されていない.OneInputOneOutputで入出力ポートを管理する.そして,ThroughBetween機能回路は,そのインターフェイスの機能回路である.こういう記述.

この記述のメリットは,機能とインターフェイスを分離することができるということだ.また,コンストラクタを減らすことができるのは素晴らしい.

もっとも,新たにインターフェイスを定義しなければならなくなる.しかしこれは,典型的なインターフェイスをいくつか用意しておくことで回避できる.実際,アダマール変換回路を記述したときに,同じインターフェイスを使いまわしてこれに似たようなことを実現した.そのときの感想は,「便利」だ.なにしろ,いちいち変数定義をしなくてすみ,implement FooBarだけで済むからだ.しかもそのときは,同じ機能だが抽象度の違う機能回路を定義して,テストを容易化したため,なおさらそう感じた.

この記述のデメリットは,Javaでは継承関係はツリー構造にしかなり得ないため,入出力定義にインターフェイスしか用いることができないことだ.そのため,インスタンス変数しか記述することができず,インスタンス変数スーパークラスからは見えないということ.唯一の解法は,リフレクションを使うことか?

public interface OneInputOneOutput {
    public static final String[] ipNames = { "in" };
    public static final String[] opNames = { "out" };
}

public class ThroughBetween extends DefaultFunctionalModule implements OneInputOneOutput {

    private boolean output_flag;
    public void init(){
        output_flag = false;
    }

    public void exec() throws InterruptedException {
        try{
            DataObject in = read("in");
            if( output_flag == false ){
                if( in.getValue() == 0x1e ){
                    output_flag = true;
                }
            }
            else {
                if( in.getValue() == 0x1f ){
                    output_flag = false;
                }
                else {
                    write( "out", in );
                }
            }
        }catch( PCAException e ){
            e.printStackTrace();
        }
    }
}

今日はこの辺で.

トラックバック - http://d.hatena.ne.jp/susumu/20050306

2005-03-05

引越しの準備のときに,ばらばらな大きさのダンボールを使ってしまったから,いまになって後悔している.なんか,3次元パッキング問題を解いている感覚に襲われてしまったよ.

次期グラフシミュレータ(GraphSim3)に関する考察(1)

| 次期グラフシミュレータ(GraphSim3)に関する考察(1)を含むブックマーク

修了もほぼ確定したことだし,そろそろ研究室ではできなかった研究の話でもしようかと思う今日この頃.

私はM1の頃から,プラスティックセルアーキテクチャ(以降PCA)用機能シミュレータ「GraphSim(現GraphSim2)」の開発を行っていました.いろいろな寄り道をしたあげく,去年の夏前には,必要最小限のフレームワークを構築し,自分のPCA用回路の開発に役立てていました.

手前味噌で申し訳ありませんが,PCA回路を開発する際,機能シミュレーションには非常に役に立つと思います.それまでC言語などを用いて開発していましたが,C言語などを用いると,そこからのストリーム処理への変換,機能分割,機能結合を脳内で行わなければならず,その辺りにバグがあると,非常にややこしい世界に突入してしまいました.しかし,GraphSimを用いることで,機能分割,結合までのテストを行うことができます.

GraphSimでアルゴリズム*1の正しさを検証したら,あとは実際に各機能回路をレイアウトし,非同期回路として正しく動作するかどうかを単体テスト結合テストを行うだけになります.まあ,ここが一番難しいんですけどね.GraphSimを用いない場合,アルゴリズムバグか,各機能回路の実装バグかの判断したうえで,必要ならばアルゴリズムに立ち戻らなければならなくなります.それに対して,GraphSimを用いた場合,アルゴリズムバグは全部つぶすことができます.すなわち,アルゴリズムを構成する基本処理をキチンと機能回路として実現していれば,ほぼ全ての回路は正しく動作することになります*2

さて,このGraphSim,あまり使ってくれる方がいません.まあ,それは良いんです*3.しかし,現状のGraphSimはある種の完成形に近く,これに新しい機能を追加しようとしたときに,非常に困難を伴います.たとえば,「遅延情報を加味したスケジューリング」です.私はこれの実装に1ヶ月を費やしましたが,結局日の目を見ることはありませんでした.

さて,このGraphSimですが,拡張を企んでいます.完全に趣味で,無用の長物ができあがるのが目に見えていますが,これを弄ってるのが幸せなんだから仕方がない.それに,私はPCAに抱いた夢をいまだに忘れられません.PCAは,CPU+Memoryという現代の汎用処理情報機構を完全に時代遅れのものにしてしまう可能性を秘めています.

具体的な拡張方針として,次の3つの項目を考えています.

  1. スケジューリングが可能
  2. 動的再構成可能
  3. プラットホームの導入

スケジューリング可能

これは,非常に難しい問題です.

現状のGraphSimでは,ユーザーが自由にスケジューリングを行うことができません.この場におけるスケジューリングとは,各機能回路の動作順序のことを指します.なぜ難しいか.

GraphSimでは,1つの機能回路を1つのスレッドで動作させています.そして入出力を管理するChannelオブジェクトでブロッキングを行い,スレッドの停止・再開をコントロールしています.

このChannelオブジェクトを弄ることで,私はスケジューリングの管理を行おうとしました.しかしこれが難しい.暫定的には動作するのですが,時々,デッドロックが発生します.これは,もともとスケジューリングを想定しないクラス構成をとっていたため,付け焼刃では難しいということです.

私のイメージでは動くはずなんですけど... 完全に,私の力不足です.

動的再構成可能

現状のGraphSimを用いても,動的再構成を表現することはできます.しかし,APIを叩けばできるというだけです.

PCAでは,動的再構成には2種類あり,機能回路の動的再構成と,機能回路間の通信チャネルの動的再構成があります.これは,グラフにおいて,ノード(機能回路)の内容の書き換えと構造(通信チャネル)の書き換えにあたります.

まず,ノードの内容の書き換えですが,動作中の書き換えは行えません.一度,ノードの動作を止めて,書き換えて,再開させるという手続きが必要です.

また,構造の書き換えですが,これはGraphSimのAPIを叩く必要があります.しかし,PCA回路はAPIを叩くなんてことは行わず,相手ノードまでの通信経路をワームホールルーティングを用いて生成します.これでは,アルゴリズム記述と回路実現のギャップが生まれてしまいます.

特に後者の問題を解決したいと考えています.

プラットホームの導入

現状のGraphSimでは,プラットホーム依存しません.すなわち,PCA的ストリーム処理を記述することはできるが,現実のデバイスであるPCA−1,PCA−2に沿った回路を記述するためのサポートはありません.

私の目的は,プラットホームを変更するだけで,他の機能記述には一切の手をつけずにPCA−1,PCA−2,そして今後考えられる他の用途(例えばunixのようなコマンドライン的な処理)へと適用できるものを目指したいと考えています.

今日のところはこの辺で〜

*1:ここでは基本ストリーム処理の組み合わせにより実現される機能構成を指す.基本ストリーム処理とは,ストリームの分岐,合流,変換を指す.

*2:もしできない場合があるとすれば,私の見落としです.善処しますので報告願います

*3:本当はまったく良くないですけど.黒田研PCA班のみなさん,できればたくさん使ってくださいね〜

トラックバック - http://d.hatena.ne.jp/susumu/20050305

2005-03-04

部屋の掃除

部屋の掃除を含むブックマーク

朝一に起きて,引越しのための掃除のごみ×11袋をごみ出しに成功.快挙w

ImageBrowser

| ImageBrowserを含むブックマーク

URLを指定すると,そこに表示されている画像のみを表示するというソフトを作ってみた.オプションで,そこから辿れるリンク先にある画像も可能な限り表示することが可能.

現在適当デバッグ中.

トラックバック - http://d.hatena.ne.jp/susumu/20050304

2005-03-03 部屋を掃除中

本当に俺は,日曜日にこの家を出て行けるのか!?

..

...

無理です.ごめんなさい.

世の中にある全てのWEBページを収集することはできるのか?

世の中にある全てのWEBページを収集することはできるのか?を含むブックマーク

という問いがあったとき,私はできないと答えます.

もし次のページへのリンクだけを生成するようなCGIが世の中に一つでも存在すれば,収集することはできないことになります.

..

...

cgiは収集からはずそう.危険すぎる.

HTMLParserライブラリの勉強中

| HTMLParserライブラリの勉強中を含むブックマーク

http://htmlparser.sourceforge.net/

お題その1: Parserオブジェクトを使ってみる

プログラム
import org.htmlparser.*;
import org.htmlparser.util.*;

public class ParserTest {
	public static void main( String[] args ) throws ParserException {
		// パーサの生成
		Parser parser = new Parser( "http://zxp044.u-aizu.ac.jp" );
		// タグフィルタなしでパーシング
		parser.parse( null );
	}
}
コメント

Parser#parseは,標準出力からパース結果が出力されるだけ.

個人的には,パース結果の木構造でも返してくれるものだとばかり思ってたよ...

お題その2: Parser#visitAllNodesWithを使ってみる

プログラム
import org.htmlparser.*;
import org.htmlparser.util.*;
import org.htmlparser.visitors.*;
import org.htmlparser.tags.*;

public class ParserVisiterTest {
	public static void main( String[] args ) throws ParserException {
		// パーサーの生成
		Parser parser = new Parser( "http://zxp044.u-aizu.ac.jp/" );
		// リンクにのみ反応するvisitorを用いて,HTML内部を散策する
		parser.visitAllNodesWith( new NodeVisitor(){
			public void visitLinkTag( LinkTag linkTag ){
				System.out.println( "link: "+linkTag.getLink() );
			}
		} );
	}
}
コメント

これで,比較的自由に,HTMLフィルタリングを行うことができそう.

お題その3: サイト内からリンクされている「ほとんど」全てのページをリストアップする

プログラム
import org.htmlparser.*;
import org.htmlparser.util.*;
import org.htmlparser.visitors.*;
import org.htmlparser.tags.*;
import java.util.*;
import java.net.*;

public class ParserBrowsingTest {
	public static void main( String[] args )
	  		throws ParserException, MalformedURLException {
		
		// 探索を開始するルートディレクトリ
		final String root = "http://zxp044.u-aizu.ac.jp/";
		
		// 今まで辿ってきたWEBページへのリンク集
		final Set visited = new HashSet();
		
		// 今まで辿ってきたWEBページから張られているWEBページへのリンク集
		final List unvisited = new LinkedList();
		unvisited.add( "http://zxp044.u-aizu.ac.jp/" );

		// リンクにのみ反応するvisitorを用いて,WEBページを収集する
		// ただし,親ディレクトリへは行かないようにする
		while( !unvisited.isEmpty() ){
			
			// 未訪問のWEBページへのリンクを取得する
			String link = (String)unvisited.remove(0);
			
			// 未訪問のリンクが,httpプロトコルでなければ,パスする.
			if( !link.startsWith("http://") ) continue;
			
			// 未訪問のリンクが,HTMLへのアクセスでなければ,
			// パスする.
			// /でアクセスできるphpスクリプトも許してしまうが,
			// 無限ループに陥ることはない.
			if( !link.endsWith(".html")
			 && !link.endsWith(".htm") 
			 && !link.endsWith(".HTM")
			 && !link.endsWith(".HTML")
			 && !link.endsWith("/") ) continue;
			
			// 未訪問のリンクを訪問済みとする.
			visited.add( link );
			
			// 未訪問のリンクのためのパーサを生成する.
			Parser parser = null;
			try {
				parser = new Parser( link );
			}catch( ParserException e ){
				// 何らかの理由で,パーサ生成に失敗したとき,
				// そのリンクは無視する.
				continue;
			}
			
			// パーサを用いて,未訪問リンクからリンクされている,
			// 新しいリンクを取得する.
			try {
				parser.visitAllNodesWith( new NodeVisitor(){
					public void visitLinkTag( LinkTag linkTag ){
						String link = linkTag.getLink();
						// リンクが,訪問済みでなく,
						// かつ未訪問リンクリストにも登録されておらず,
						// かつルートよりも下に存在するならば,
						// 未訪問リンクとする.
						if( !visited.contains(link)
						 && !unvisited.contains(link)
						 && link.startsWith(root) ){
							unvisited.add( link );
						}
					}
				} );
			}catch( EncodingChangeException e ){
				// 文字コードの判定にミスったら,もう一度,リンク探査の旅に出る.
				parser.reset();
				parser.visitAllNodesWith( new NodeVisitor(){
					public void visitLinkTag( LinkTag linkTag ){
						String link = linkTag.getLink();
						if( !visited.contains(link)
						 && !unvisited.contains(link)
						 && link.startsWith(root) ){
							unvisited.add( link );
						}
					}
				} );
			}
		}
		
		// 最終的に,どこにページに訪れたかを表示する.
		for( Iterator i=visited.iterator(); i.hasNext(); /*DoNothing*/ ){
			System.out.println( (String)i.next() );
		}
	}
}
コメント

長いな.

cgiなどを真面目に扱うと頭が痛くなりそうだったので,スタティックなWEBページに対象を限定しました.

文字コードが変化した例外は,よく分からなかったので,適当に回避する.

あとは,永遠リンクを引っ張ってきます.

まとめ

とりあえず,サイト内の探索まではできるようになった.

今日は,ここまで.

しかし,ネットワークを意識せずにプログラミングできるなんて,なんて幸せライブラリなんだ.

wmwoosxwmwoosx 2008/12/07 01:53 DCX3wk <a href="http://aaeinkobldks.com/">aaeinkobldks</a>, [url=http://rshzmuhyzqgj.com/]rshzmuhyzqgj[/url], [link=http://jlixerfbkiuz.com/]jlixerfbkiuz[/link], http://fmpmaylkntml.com/

トラックバック - http://d.hatena.ne.jp/susumu/20050303

2005-03-02 このエントリーを含むブックマーク

体調を崩して,病院へ駆け込みました.昨日の事だけど.

どうにもこうにも,朝から調子が悪いから,体温を測ったら,40度をオーバーしてて,正直,パニクりましたよ.

病院で計りなおしたら,38.4度.少し落ち着きました.

風邪と診断されたけど...

まあいいや.

トラックバック - http://d.hatena.ne.jp/susumu/20050302
267983
Connection: close