IDEON合宿/2006春 | 計算理論とOverlay

総覧・未分類

  • bit アーカイブ bitのページ 共立出版のページには1996以前のdataがないんですね‥‥‥
    • 1997
      • KLICプログラミングコンテスト ― 並列処理技術への挑戦 溝口文雄・田中二郎 8 49

データフロー型

島田先生@名大 http://www.shimadalab.nuee.nagoya-u.ac.jp/member/shimada/publication.html

☆[Dennis74](文献1)の計算モデル。

Jack B. Dennis. First version of a data flow procedure language. In "Lecture Notes in Computer Science 19: Programming Symposium", pp 362-376. Springer-Verlag: Berlin, New York, 1974.

入手できない! つーか、LNCS19ってすげーな。

関数は入力により一意に定まり、他の関数の実行結果の影響(副作用)を受けな い→関数型言語向き。

モデルの限界: リンクには常に一つのトークンしか置けない →拡張: 静的計算モデル / 動的計算モデル

静的計算モデル: 発火のためには出力リンクが空である必要がある。

ループは容易に実現できるが、リカーションは無理

動的計算モデル: トークンにタグを持たせる

((u,c,s,i),v)
ここで、
 u: グラフ実行時のインスタンス
 c: グラフ内のループ
 s: 行き先のアクタ(ノード)
 i: ループの繰り返し回数
タグを操作する命令により、ループ・リカーション・パイプライン計算を
実現

アーキテクチャの話とかもある。

簡単なアーキテクチャ(静的計算モデル)

  • ネットワーク
  • 更新ユニット
  • キュー
  • プログラムメモリ
  • フェッチユニット
  • 演算ユニット
  • 制約1: 発火したアクタが入力側に空リンクを通知
  • 制約2: 同じサブルーチンを二箇所でcallしようとしてもコードを 共有できない(ループの各世代を並列化できない)

疑問: 出口が一つという制約はどこから出てきたのかな? まあ、入力値が異なる同じ関数をどう共有するかって、そりゃむづかしい かもね。

動的計算モデルの場合は、いろいろ複雑かも。

サーベイ論文

理論

実装・評価

  • (文献3): マンチェスター大学 / 連想記憶の性能が悪かった?
  • (文献4)Dennis : MIT静的エンジニアリングモデル / マイクロプログラム
    高級言語VAL
  • (文献不明)Arvind : LISPマシンとか高級言語Idとか。
  • (文献5)NEC NEDIPS 世界初の商用:
    独自アセンブラで書いてFORTRANからcall
  • (文献7)NTT DFM 信号処理用 単一代入型高級言語VALID
  • (文献8)群馬大 DFNDR 連想記憶が強力 負荷分散good/スケールしない
  • (文献9,10)電子技術総合研究所 SIGMA-1 / 言語DFC
    → DFCの設計は 信学会論文誌 J71-D, 3 1988 あるいはDFC-II
       IPSJ論文誌Vol.30 No.12 Dec.1989にある(有料315円)。

問題点とか

マクロデータフロー 関数レベルでのデータフロー

【データフローの限界】

 履歴依存性のある計算ができない
 リンク上にトークンがあるかどうかをテストできない(ので同期は受け身)
  計算の終了判定のオーバーヘッドが大きくなる
 並列にしすぎると待ち合わせ記憶とかカラー?などが足りなくなるので、
 並列性を制御したくなっている?

hunga先生のスライド:

http://www.am.ics.keio.ac.jp/comparc/others/tsld012.htm
EM-4/EM-Xってのもあるようだ。

【データフローマシンの問題点】

  • 純粋なデータフローマシン(Dennis)は無駄が多い
  • 色付きトークン等の導入でデータフローグラフの再利用
  • 構造の複雑化
  • 演算器レベルの処理時間とそれに要する時間の比率の問題
  • 局所性の無視

【Dennis先生曰く】

  • 超並列
  • CMOSカスタム
  • 関数型
  • フォールトデテクション

が次の課題(と20年前におっしゃっておられた)

論理型

ICOT TR(http://www.icot.or.jp/ARCHIVE/Museum/TRTM/tr-list-J.html): 033, 035, 050, 099, 114, 122, 165, 168, 187, 189, 268, 301, 414

ICOT TM(http://www.icot.or.jp/ARCHIVE/Museum/TRTM/tm-list-J.html): 098, 236

神奈川県立川崎図書館にあるらしい…

並列論理

  • 淵 一博 et.al., "並列論理型言語GHCとその応用", 共立出版

関数型

Reduction Machine

理研 brainway team

http://www.riken.jp/r-world/research/lab/nokagaku/brain/device/index.html

pdf置き場 (メンバー限定)

担当

  • doi
    • つっこまれまくるだろうけどいちおうサーベイ総論
    • Veenのサーベイ論文 (‥‥‥は間に合いそうにないかも)
  • 本もいくつか持ち込みます。 -- doi 2006-03-31 (金) 18:59:31
  • 可能なら TelegraphCQ: Continuous Dataflow Processing for an Uncertain World -- doi 2006-04-02 (日) 11:18:33


添付ファイル: filesurvey-on-non-neumann-arch.pdf 2004件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2006-04-04 (火) 01:44:37 (4249d)