履歴依存性を許すデータ駆動図式

西川 博昭  寺田 浩詔  浅田 勝彦  

誌名
電子情報通信学会論文誌 D   Vol.J66-D   No.10   pp.1169-1176
発行日: 1983/10/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(642.1KB)>>
論文を購入




あらまし: 
本論文は,高度並列処理システムにおけるプログラムの記述法として,履歴依存処理を含めて実行時の副作用を回避でき且つ問題に内在する並列処理構造を陽に反映する並列プログラム図式を提案している.本図式は,階層的あるいは再帰的なブロック構造を持つデータ駆動図式である.即ち,本図式は,履歴を持つ処理記述を許すが,これによる非決定性を回避可能な仕様を持つ.更に,図式によって記述されるプログラムは,トークンの流れに関して,厳密なデータ駆動規則に従って実行され,且つ副作用を生じないことが保証されている.本論文では,まずデータ駆動図式の生成規則とその解釈および実行規則について述べる.次に,制御構造として,連接,選択,再帰を用いて記述されたプログラムが副作用なしであることを等価な実行系列を持つペトリネットにおける到達可能木を用いて示す.更に,履歴依存処理の記述のため拡張されたデータ駆動図式についても同様の検証性が保証されることを示すと共に,図式中の履歴の具体的実現例として,副作用を回避できる参照・更新規則を持つタグ付き記憶セルを提案している.