A parallel algorithm for constructing binary decision diagrams

Author

Kimura, Shinji ; Clarke, Edmund M.

Author_Institution

Dept. of Electron. Eng., Kobe Univ., Japan

fYear

1990

fDate

17-19 Sep 1990

Firstpage

220

Lastpage

223

Abstract

A parallel algorithm for constructing binary decision diagrams is described. The algorithms treats binary decision graphs as minimal finite automata. The automation for a Boolean function with AND as its main operation (OR operation) is obtained by forming the intersection (union) of the regular sets associated with its operands. The union and intersection operations are implemented by a product construction on the minimal automata for the regular sets. After each product construction step the automaton must be reminimized. The parallel algorithm is designed so that it is possible to find the minimal representations for several Boolean operations in parallel. The level of each operation is determined. Operations at the same level can be performed in parallel without any communication between processors. If there are relatively few operations in one level, then the product generation step is divided into several suboperations and the results are merged

Keywords

Boolean functions; finite automata; logic CAD; parallel algorithms; Boolean operations; binary decision diagrams; intersection; minimal finite automata; parallel algorithm; product construction step; product generation; regular sets; union; Automata; Boolean functions; Computer science; Data structures; Input variables; Parallel algorithms; Parallel processing; Statistics; Testing;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Design: VLSI in Computers and Processors, 1990. ICCD '90. Proceedings, 1990 IEEE International Conference on

Conference_Location

Cambridge, MA

Print_ISBN

0-8186-2079-X

Type

conf

DOI

10.1109/ICCD.1990.130209

Filename

130209