セレクト及びマージ頂点数の最小化によるパイプライン化依存性グラフの簡単化

籠谷 裕人  杉山 裕二  岡本 卓爾  

誌名
電子情報通信学会論文誌 D   Vol.J95-D   No.5   pp.1206-1215
発行日: 2012/05/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 論文
専門分野: 計算機システム
キーワード: 
非同期式制御回路,  パイプライン,  簡単化,  有限オートマトン,  

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




あらまし: 
非同期式制御回路の合成のための依存性グラフのパイプライン化アルゴリズムは既に提案されているが,このために複製されたセレクト及びマージの頂点数が多数存在するので,しばしば,パイプライン化依存性グラフの構成が複雑になる.本論文では,複製された頂点のうち冗長な組を単一化することによる依存性グラフの簡単化手法を提案する.まず,基本操作の頂点におけるトークン移動の並列性を損なうことなく,複製されたセレクト及びマージの頂点が単一化できる条件を導出している.次に,この条件を有限オートマトンの等価性により判定する方法を明らかにしている.最後に,この手法によりパイプライン化依存性グラフにおけるセレクト及びマージの頂点数を最小化するための手続きを与えている.