A Zero-Suppressed BDD Package with Pruning and Its Application to GRM Minimization (Special Section on VLSI Design and CAD Algorithms)
スポンサーリンク
概要
- 論文の詳細を見る
Recently, various efficient algorithms for solving combinatorial optimization problems using BDD-based set manipulation techniques have been developed. Minato proposed 0-suppressed BDDs (ZBDDs) which is suitable for set manipulation, and it is utilized for various search problems. In terms of practical limits of space, however, there are still many search problems which are solved much better by using conventional branch-and-bound techniques than by using BDDs or ZBDDs,while the ability of conventional branch-and-bound approaches is limited by computation time. In this paper, an extension of APPLY operation, named APPRUNE (APply + PRUNE) operation, is proposed, which performs APPLY operation (ZBDD construction) and "pruning" simultaneously in order to reduce the required space for intermediate ZBDDs. As a prototype, a specific algorithm of APPRUNE operation is shown by assuming that the given condition for pruning is a threshold function,although it is expected that APPRUNE operation will be more effective if more sophisticated condition are considered. To reduce size of ZBDDs in intermediate steps, this paper also pay attention to the number of"cared" variables. As an application,an exact-minimization algorithm for generalized Reed-Muller expressions (GRMs) is implemented. From experimental results, it is shown that time and memory usage is improved 8.8 and 3.4times, respectively, in the best case using APPRUNE operation.Results on generating GRMs of exact-minimum number of not only product terms but also literals is also shown.
- 社団法人電子情報通信学会の論文
- 1996-12-25
著者
関連論文
- Datapath-Layout-Driven Design for Low-Power FPGA Implementation (特集:電子システムの設計技術と設計自動化)
- ASAver.1: An FPGA-Based Education Board for Computer Architecture/System Design
- A Zero-Suppressed BDD Package with Pruning and Its Application to GRM Minimization (Special Section on VLSI Design and CAD Algorithms)
- An Algorithm for Generating Generic BDDs (Special Section on VLSI Design and CAD Algorithms)
- An Exact Minimization of AND-EXOR Expressions Using Encoded MRCF (Special Section on VLSI Design and CAD Algorithms)