Title Alternative An Efficient Algorithm to Determine Equivalence of Pipelined Dependency Graphs for Their Simplification
FullText URL j100-d_6_616.pdf
Author Kagotani, Hiroto| Sugiyama, Yuji| Okamoto, Takuji|
Abstract  依存性グラフに基づいた非同期式パイプライン制御回路の設計方法が提案されている.この設計法の最終段階においては,依存性グラフと縮小した依存性グラフの等価性を何度も繰返し判定することにより,簡単化した依存性グラフが得られる.しかし,この判定には多数の状態をもつオートマトンを扱うため,その計算量は極めて大きい.本論文では,この等価性判定のための新たな効率的なアルゴリズムを提案する.まず,基本操作の実行順序の半順序をコンパクトに表現するために,基本操作直結因果関係グラフ O˙ を定義する.次に,分 岐系列ごとに O˙ の高々二つの部分グラフが一致するとき,かつそのときに限り,二つの依存性グラフが等価であることを証明する.更に,等価性の判定に必要な分岐系列のサイズと数が有限であることを証明する.最後に,上述の原理を用いたアルゴリズムの計算量が従来法に比べて大幅に小さいことを示す.
Keywords 非同期式制御回路 パイプライン 簡単化 因果関係
Note 本研究は,JSPS 科研費 JP24500065,JP16H01723 の助成を受けたものである.
Published Date 2017-06-01
Publication Title The IEICE Transactions on Electronics
Volume volumeJ100-D
Issue issue6
Publisher 電子情報通信学会
Start Page 616
End Page 626
ISSN 18810225
NCID AA12712944
Content Type Journal Article
language 日本語
OAI-PMH Set 岡山大学
Copyright Holders Copyright (c) by IEICE
File Version publisher
DOI 10.14923/transinfj.2016JDP7108
Official Url https://search.ieice.org/|