Title :
Boolean function manipulation on massively parallel computers
Author :
Cabodi, G.P. ; Gai, S. ; Reorda, M. Sonza
Author_Institution :
Dipartimento di Autom. e Inf., Politecnico di Torino, Italy
Abstract :
A new algorithm for implementing the basic operations on BDDs (binary decision diagrams) on a massively parallel computer is presented. Each node is associated with a processor, and nodes belonging to the same level are evaluated together. An implementation of the algorithm on a Connection Machine CM2 has been done, and the prototype is being tested on a set of benchmark applications. Experimental results, showing the time required to perform the apply operation on BDDs of growing size demonstrate the exactness of the complexity analysis and the effectiveness of the approach
Keywords :
Boolean functions; computational complexity; parallel processing; performance evaluation; symbol manipulation; Boolean function manipulation; Connection Machine CM2; algorithm; benchmark applications; binary decision diagrams; complexity analysis; massively parallel computers; Boolean functions; Circuit testing; Concurrent computing; Data structures; Decision trees; Digital circuits; Input variables; Parallel algorithms; Sun; Tree graphs;
Conference_Titel :
Frontiers of Massively Parallel Computation, 1992., Fourth Symposium on the
Conference_Location :
McLean, VA
Print_ISBN :
0-8186-2772-7
DOI :
10.1109/FMPC.1992.234869
