二次記憶に格納された大きな共有二分決定グラフを扱うための幅優先アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1993-01-21
• タイトル: 二次記憶に格納された大きな共有二分決定グラフを扱うための幅優先アルゴリズム
• タイトル / 言語: en
• タイトル: A Secondary Storage Oriented Breadth - First Algorithm for Manipulating Very Large SBDD's
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 京都大学工学部情報工学教室
• 著者所属: 京都大学大型計算機センター
• 著者所属: 京都大学工学部情報工学教室
• 著者所属(英): en
• 著者所属(英): Department of Information Science Faculty of Engineering
• 著者所属(英): en
• 著者所属(英): Data Processing Center Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Information Science Faculty of Engineering
• 著者名: 越智, 裕之; 安岡, 孝一; 矢島, 脩三
• 著者名(英): Hiroyuki, Ochi; Koichi, Yasuoka; Shuzo, Yajima
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 共有二分決定グラフは論理照合、タイミング検証、順序機械の設計検証、テスト生成、論理合成などの分野で幅広く利用されている。しかし、扱う論理関数が複雑になると計算機の主記憶容量の制約を受けるため実用面で大きな障害となっていた。本稿では計算機の二次記憶上に格納された大きな共有二分決定グラフを効率良く操作するための幅優先アルゴリズムを提案する。ワークステーションSun SPARC Station 2上に実現して500MBのハードディスク領域を利用して行なった実験では、例えば14ビット乗算器の回路記述からこれの全ての出力論理関数を表す共有二分決定グラフを約7時間で生成することができた。本手法により、論理回路設計支援システムの可能性が大きく広がるものと期待される。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Boolean function manipulators based on Shared Binary Decision Diagrams (SBDD's) are widely utilized in formal design verification, etc. However, in many applications we have to give up to prove large-scale problems due to the limitation of the size of the main memory to store SBDD's. We propose a breadth-first algorithm for efficient manipulation of very large SBDD's stored in the secondary storage. This proposed algorithm is implemented on the workstation Sun SPARC Station 2. Using 500MB hard disk space, an SBDD for 14-bit multiplier is constructed in 7 hours from a circuit description, The developed technique for SBDD manipulation is expected to enable us much larger and more complex design.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10096105
• 書誌情報: 情報処理学会研究報告計算機アーキテクチャ（ARC）; 巻 1993, 号 6(1992-ARC-098), p. 25-32, 発行日 1993-01-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会