文献

J-GLOBAL ID：201202290694027623   整理番号：12A0707328

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

著者 (3件)： 籠谷裕人 (岡山大 大学院自然科学研究科) ,  杉山裕二 (岡山大 大学院自然科学研究科) ,  岡本卓爾 (岡山大 大学院自然科学研究科)
資料名： 電子情報通信学会論文誌 D  (IEICE Transactions on Information and Systems (Japanese Edition))
巻： J95-D  号： 5  ページ： 1206-1215  発行年： 2012年05月01日 
JST資料番号： S0757C  ISSN： 1880-4535  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

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

シソーラス用語： *グラフ ,  *簡素化 ,  有限オートマトン ,  *回路合成 ,  *非同期回路 ,  パイプライン処理 ,  *改変

分類 (1件)： グラフ理論基礎  (IA02020S)

引用文献 (11件)：

• C. Myers, Asynchronous Circuit Design, John Wiley & Sons, 2001.
• A. Taubin, J. Cortadella, L. Lavagno, A. Kondratyev, and A. Peeters, “Design automation of real-life asynchronous devices and systems,” Found. Trends Electron. Des. Autom., vol.2, pp. 1-133, Jan.2007.
• T. Nanya, Y. Ueno, H. Kagotani, M. Kuwako, and A. Takamura, “TITAC: Design of a quasi-delay-insensitive microprocessor,” IEEE Design & Test of Computers, vol.11, no.2, pp. 50-63, 1994.
• 籠谷裕人, 南谷 崇, “依存性グラフを用いた2相式非同期回路の合成,”信学論 (D-I), vol. J77-D-I, no.8, pp. 548-556, Aug.1994.
• 籠谷裕人, 杉山裕二, 岡本卓爾, “制御フローグラフを用いた非同期式パイプライン合成,”信学論 (D), vol. J90-D, no.5, pp. 1167-1177, May 2007.

タイトルに関連する用語 (7件)： セレクト ,  マージ ,  頂点 ,  パイプライン ,  依存性 ,  グラフ ,  簡単化