計算理論とOverlay/サーベイメモ
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[IDEON合宿/2006春]] | [[計算理論とOverlay]]
#contents
* 総覧・未分類 [#f361d31b]
- bit アーカイブ [[bitのページ:http://www.kyoritsu-pub.co.jp/bit/bit.html]]
共立出版のページには1996以前のdataがないんですね‥‥‥~
-- 1997
--- KLICプログラミングコンテスト ― 並列処理技術への挑戦 溝口文雄・田中二郎 8 49
- [[並列計算機のサーベイ(ics.keio):http://www.am.ics.keio.ac.jp/pbook/machine.html]]
* データフロー型 [#w76dd27f]
- [[Wikipedia(EN):http://en.wikipedia.org/wiki/Dataflow]]
- [[AIST 河並さん:http://staff.aist.go.jp/t-kawanami/research.html]]
- 島田 俊夫,
[[並列処理マシン:データフローマシン:http://fw8.bookpark.ne.jp/cm/ipsj/search_test.asp?from=&flag=6&keyword=IPSJ-MGN280112&page=&mode=PDF]],
情報処理
1987年1月 Vol.28 No.1
島田先生@名大
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しようとしてもコードを
共有できない(ループの各世代を並列化できない)
疑問: 出口が一つという制約はどこから出てきたのかな?
まあ、入力値が異なる同じ関数をどう共有するかって、そりゃむづかしい
かもね。
動的計算モデルの場合は、いろいろ複雑かも。
** サーベイ論文 [#edf26e0f]
- Arthur H. Veen, "[[Dataflow Machine Architecture:http://cs-people.bu.edu/gabep1/dataflow.pdf]]", ACM Computing Surveys, Vol.18, No.4, December 1986
** 理論 [#e4ba35cf]
** 実装・評価 [#e4a7dcba]
- (文献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円)。
** 問題点とか [#b767d8eb]
マクロデータフロー
関数レベルでのデータフロー
【データフローの限界】
履歴依存性のある計算ができない
リンク上にトークンがあるかどうかをテストできない(ので同期は受け身)
計算の終了判定のオーバーヘッドが大きくなる
並列にしすぎると待ち合わせ記憶とかカラー?などが足りなくなるので、
並列性を制御したくなっている?
hunga先生のスライド:
http://www.am.ics.keio.ac.jp/comparc/others/tsld012.htm
EM-4/EM-Xってのもあるようだ。
【データフローマシンの問題点】
- 純粋なデータフローマシン(Dennis)は無駄が多い
- 色付きトークン等の導入でデータフローグラフの再利用
- 構造の複雑化
- 演算器レベルの処理時間とそれに要する時間の比率の問題
- 局所性の無視
【Dennis先生曰く】
- 超並列
- CMOSカスタム
- 関数型
- フォールトデテクション
が次の課題(と20年前におっしゃっておられた)
* 論理型 [#a073347b]
- [[ICOT テクニカルメモ:http://www.icot.or.jp/ARCHIVE/Museum/TRTM/tm-list-E.html]]
-- TR0098 とか [[このパネルルセッション:http://www.icot.or.jp/ARCHIVE/Museum/FGCS/FGCS88jp-rpt/88jPANEL2.pdf]] とかなどは有用では?(shirou)
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
神奈川県立川崎図書館にあるらしい…
- [[東大近山研究室:http://www.logos.t.u-tokyo.ac.jp/www/root-j.html]]
** 並列論理 [#r852f68b]
- 淵 一博 et.al., "並列論理型言語GHCとその応用", 共立出版
* 関数型 [#s59fece8]
** Reduction Machine [#n33cb48e]
- wikipedia(EN): http://en.wikipedia.org/wiki/Graph_reduction_machine
* 理研 brainway team [#w957bb6f]
http://www.riken.jp/r-world/research/lab/nokagaku/brain/device/index.html
* pdf置き場 (メンバー限定) [#o5c76387]
- https://member.wide.ad.jp/wg/ideon/wide-confidential/200604/ideon-retreat/refs/
* 担当 [#ta1fa46e]
- doi
-- つっこまれまくるだろうけどいちおうサーベイ総論
-- Veenのサーベイ論文 (‥‥‥は間に合いそうにないかも)
-本もいくつか持ち込みます。 -- [[doi]] &new{2006-03-31 (金) 18:59:31};
-可能なら TelegraphCQ: Continuous Dataflow Processing for an Uncertain World -- [[doi]] &new{2006-04-02 (日) 11:18:33};
#comment
終了行:
[[IDEON合宿/2006春]] | [[計算理論とOverlay]]
#contents
* 総覧・未分類 [#f361d31b]
- bit アーカイブ [[bitのページ:http://www.kyoritsu-pub.co.jp/bit/bit.html]]
共立出版のページには1996以前のdataがないんですね‥‥‥~
-- 1997
--- KLICプログラミングコンテスト ― 並列処理技術への挑戦 溝口文雄・田中二郎 8 49
- [[並列計算機のサーベイ(ics.keio):http://www.am.ics.keio.ac.jp/pbook/machine.html]]
* データフロー型 [#w76dd27f]
- [[Wikipedia(EN):http://en.wikipedia.org/wiki/Dataflow]]
- [[AIST 河並さん:http://staff.aist.go.jp/t-kawanami/research.html]]
- 島田 俊夫,
[[並列処理マシン:データフローマシン:http://fw8.bookpark.ne.jp/cm/ipsj/search_test.asp?from=&flag=6&keyword=IPSJ-MGN280112&page=&mode=PDF]],
情報処理
1987年1月 Vol.28 No.1
島田先生@名大
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しようとしてもコードを
共有できない(ループの各世代を並列化できない)
疑問: 出口が一つという制約はどこから出てきたのかな?
まあ、入力値が異なる同じ関数をどう共有するかって、そりゃむづかしい
かもね。
動的計算モデルの場合は、いろいろ複雑かも。
** サーベイ論文 [#edf26e0f]
- Arthur H. Veen, "[[Dataflow Machine Architecture:http://cs-people.bu.edu/gabep1/dataflow.pdf]]", ACM Computing Surveys, Vol.18, No.4, December 1986
** 理論 [#e4ba35cf]
** 実装・評価 [#e4a7dcba]
- (文献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円)。
** 問題点とか [#b767d8eb]
マクロデータフロー
関数レベルでのデータフロー
【データフローの限界】
履歴依存性のある計算ができない
リンク上にトークンがあるかどうかをテストできない(ので同期は受け身)
計算の終了判定のオーバーヘッドが大きくなる
並列にしすぎると待ち合わせ記憶とかカラー?などが足りなくなるので、
並列性を制御したくなっている?
hunga先生のスライド:
http://www.am.ics.keio.ac.jp/comparc/others/tsld012.htm
EM-4/EM-Xってのもあるようだ。
【データフローマシンの問題点】
- 純粋なデータフローマシン(Dennis)は無駄が多い
- 色付きトークン等の導入でデータフローグラフの再利用
- 構造の複雑化
- 演算器レベルの処理時間とそれに要する時間の比率の問題
- 局所性の無視
【Dennis先生曰く】
- 超並列
- CMOSカスタム
- 関数型
- フォールトデテクション
が次の課題(と20年前におっしゃっておられた)
* 論理型 [#a073347b]
- [[ICOT テクニカルメモ:http://www.icot.or.jp/ARCHIVE/Museum/TRTM/tm-list-E.html]]
-- TR0098 とか [[このパネルルセッション:http://www.icot.or.jp/ARCHIVE/Museum/FGCS/FGCS88jp-rpt/88jPANEL2.pdf]] とかなどは有用では?(shirou)
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
神奈川県立川崎図書館にあるらしい…
- [[東大近山研究室:http://www.logos.t.u-tokyo.ac.jp/www/root-j.html]]
** 並列論理 [#r852f68b]
- 淵 一博 et.al., "並列論理型言語GHCとその応用", 共立出版
* 関数型 [#s59fece8]
** Reduction Machine [#n33cb48e]
- wikipedia(EN): http://en.wikipedia.org/wiki/Graph_reduction_machine
* 理研 brainway team [#w957bb6f]
http://www.riken.jp/r-world/research/lab/nokagaku/brain/device/index.html
* pdf置き場 (メンバー限定) [#o5c76387]
- https://member.wide.ad.jp/wg/ideon/wide-confidential/200604/ideon-retreat/refs/
* 担当 [#ta1fa46e]
- doi
-- つっこまれまくるだろうけどいちおうサーベイ総論
-- Veenのサーベイ論文 (‥‥‥は間に合いそうにないかも)
-本もいくつか持ち込みます。 -- [[doi]] &new{2006-03-31 (金) 18:59:31};
-可能なら TelegraphCQ: Continuous Dataflow Processing for an Uncertain World -- [[doi]] &new{2006-04-02 (日) 11:18:33};
#comment
ページ名: