負閉路探索手法の性能評価

• Item type: SIG Technical Reports(1)
• 公開日: 2006-07-03
• タイトル: 負閉路探索手法の性能評価
• タイトル / 言語: en
• タイトル: Performance Evaluation of Negative Cycle Detection Algorithms
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京工業大学理工学研究科集積システム専攻
• 著者所属: 東京工業大学理工学研究科集積システム専攻
• 著者所属: 東京工業大学理工学研究科集積システム専攻
• 著者所属(英): en
• 著者所属(英): Department of Commumcations and lntegrated Systems, Tokyo lnstitute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Commumcations and lntegrated Systems, Tokyo lnstitute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Commumcations and lntegrated Systems, Tokyo lnstitute of Technology
• 著者名: 石田, 勉; 小平, 行秀; 高橋, 篤司
• 著者名(英): Tsutomu, lSHIDA; Yukihide, KOHIRA; Atsushi, TAKAHASHI
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: クロックの入力タイミングを制御することで高性能な回路実現を目指す準同期式回路では，回路の制約グラフに負閉路が存在するとき，クロックスケジュールをどのように定めても回路は正常に動作しない．制約グラフの各枝重みはクロック周期により変化するため，制約グラフに負閉路が存在しない最小のクロック周期が，回路が動作可能な最小クロック周期となる．回路が動作可能な最小クロック周期は回路設計において繰り返し計算されるので，効率的な負閉路探索手法が必要となる．本研究では，負閉路探索手法として知られる改良ベルマンーフォード法とビットスケーリング法，どちらが回路の制約グラフに有効であるか性能評価を行なった．実験により，改良ペルマンーフォード法はピットスケーリング法より高速に制約グラフ中の負閉路を発見することを確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: ln semi-synchronous circuits，clock input timings are controlled in order to improve the performance. Clock input timings of a circuit that realize the correct circuit functionality exist if and only if the constraint graph of the circuit contains no negative cycle. Since the edge weight of the constraint graph of a circuit depends on the clock period, the minimum clock period in which the constraint graph contains no negative weight cycle is the minimum feasible clock period of the circuit．Since the minimum feasible clock period of a circuit is calculated repeatedly in circuit synthesis, an efficient negative cycle detection algorithm is requested. In this paper, we evaluate two negative cycle detection algorithms, enhanced Bellman-Ford algorithm and scaling algorithm, in terms of the efficiency to the constraint graph of benchmark circuits. In experiments, we show that the enhanced Bellman-Ford algorithm is more suitable for the constraint graph of benchmark circuits than the scaling algorithm．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2006, 号 71(2006-AL-107), p. 45-50, 発行日 2006-07-03
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会