返回Google圖書搜尋

Secondary Storage Oriented Breadth-first Manipulation of Very Large Shared Binary Decision Diagrams

Kyōto Daigaku. Joho Kogaku KyoshitsuHiroyuki Ochi

出版	Department of Information Science, Faculty of Engineering, Kyoto University, 1992
URL	http://books.google.com.hk/books?id=U7RUHAAACAAJ&hl=&source=gbs_api

註釋Abstract: "Boolean function manipulators based on Shared Binary Decision Diagrams (SBDD's) are utilized in various applications of Computer-Aided Design (CAD) of digital systems, including formal design verification, test generation, logic synthesis and so on. We propose an efficient algorithm for manipulating very large SBDD's stored in the secondary storage. In contrast to conventional algorithms that are based on depth-first manipulation which causes the random access of the memory, the proposed algorithm is based on breadth-first manipulation. This breadth-first algorithm is effective to reduce the overhead due to the access to the secondary memory, because it requires [sic] small number of the accesses for large data blocks in the contiguous space of the secondary memory. 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."