非同期式制御回路合成のための依存性グラフパイプライン化アルゴリズムの検証

籠谷 裕人  杉山 裕二  

誌名
電子情報通信学会論文誌 D   Vol.J93-D   No.11   pp.2343-2353
発行日: 2010/11/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 論文
専門分野: 計算機システム
キーワード: 
非同期式パイプライン,  依存性グラフ,  アルゴリズム,  正当性,  完全性,  

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




あらまし: 
本論文では,依存性グラフで与えられた非同期式プロセッサの仕様をもとに,パイプライン化された依存性グラフを生成するパイプライン化アルゴリズムの正当性と完全性を検証している.正当性については,アルゴリズムの適用によって計算結果の等しい等価な依存性グラフが生成されることをアルゴリズムの正当性と定義し,いくつかの中間的なグラフを導入して,等価性の推移律により証明している.完全性については,仕様上並列化してはならない依存性グラフ上の頂点対を明確にした上で,これら以外の頂点対がすべて並列化されることをアルゴリズムの完全性と定義し,動的な並列動作を静的に表現するためのグラフを導入することにより証明している.