************************************************************************* Parallel PBF BDD Package Version 0.1 Bwolen Yang School of Computer Science Carnegie Mellon University bwolen@cs.cmu.edu Last Modified: 8/98 ************************************************************************* Description ----------- This package is a parallel BDD implementation based on the partial breadth-first BDD consturction. This package uses posix thread interface and require shared memory support (in either hardware or software). It is targeted for small scale symmetric multi-processor (SMP) systems. For distributed shared memory (DSM) systems, I tested this on SGI's Origin 2000 and found this package performs poorly. For SMPs like SGI Power Challenge (8 procesoors), Sun's Ultra Enterprise 3000 (6 processors), DEC 8400 (4 processors), and 200MHz PentiumPro (2 processors) machines, PPBF gets close to speedups of 2 on 2 processors and around 3 on 4 processors and up to 4 on 8 processors. Note that only the combinational circuit operations are currently supported. Description of this implementation can be found in @INPROCEEDINGS(yang:ppopp97-pbdd, KEY="pbdd", AUTHOR="Bwolen Yang and David R. O'Hallaron", TITLE="Parallel Breadth-First {BDD} Construction", ORGANIZATION="", BOOKTITLE=PPOPP97, month="June", YEAR="1997", pages = "145-156", Annote = "") Platform Tested --------------- SGI PowerChallenge (using sproc interface). Default setup generates 32-bit code. (For 64-bit code, replace -32 flag with -64 flag in the Makefile.) Solaris (using pthread). Alpha/OSF (using pthread). Linux (using linuxthread-0.71). Software Requirement -------------------- This implementation is based on posix threads. For SGI, it also have interface for sproc(). The program "gmake" is required for building this package. Parameters ---------- All the tuneable parameters are in the files "bfxdInt.h" or "Makefile". This section contains a brief documentation on a few important parameters. Parameters in "Makefile" ------------------------ INCLUDE /* set special include directories. */ PTHREADLIBPATHS /* Library path for pthread (if not already in the default paths). */ PTHREADINCLUDE /* C include path for pthread (if not already in the default paths). */ PTHREADLIBS /* if using a pthread library, define this variable to include * all the related libraries. e.g., * PTHREADLIBS = -lpthread */ BFXD_DEBUG /* if defined, enable the debugging checks and outputs */ NDEBUG /* if defined, disable assertions used by "assert()". * see the manual page for assert (unix command "man assert") * for more detail */ BFXD_DO_STATS /* if defined, collect performance statistics for analysis */ Parameters in "bfxdInt.h" ------------------------- BFXDSEQUENTIAL /* define this FLAG to remove all parallel implementation */ BFXDMAX_NPROCS /* this parameter defines maximum number of threads supported. * Currently set to 16. */ Integration/Compilation ------------------------ All the interface functions are documented in the file "bfxd.h". Note that only the combinational circuit operations are currently supported. To interface with this package, you will need to include "bfxd.h" and have thread support. For examples of how to use this BDD package, please see adder.c -- n-bit adder mult.c -- n-bit multiplier To build this package, % gmake dep; gmake Upon successful compilation, an adder (executable "adder") and a multiplier (executable "mult") will be ready for execution. Run these programs without any command line arguments to obtain a brief help message. Note that adder is a very small circuit and do not use the parallel interface. Files ----- Makefile The file for the program "make" and is used to build this package. Makefile.app Sample make file for building applications. It is used for building adder and multiplier examples. README This file. adder.c Example program: adder. bddAPI.h Generic BDD interface file for building BDD applications. bfxd.h External interface header file. bfxdArray.c Generic dynamic array implementaiton. bfxdContext.c Context switch support mechanism for partial breadth-first BDD construction. This is also used for work stealing (load balancing) in the parallel implementaiton. bfxdDF.c DF BDD implementation. bfxdGC.c Garbage collection routines. bfxdHashTable.c Hash table implementation. bfxdInt.h Internal header file. bfxdMem.c Memory management file. bfxdMsg.c Implement message passing using shared memory interface. bfxdMutex.c Mutual exclusion implementation based on posix thread interface. bfxdMutexSGI.c Mutual exclusion implementation based on SGI's sproc() interface. bfxdOp.c Terminal case detecion and BDD node construction. bfxdOpQueue.c BF implementation. bfxdParUtil.c Utility functions for parallel implementation. bfxdPublic.c External interface functions. bfxdReduce.c New BF reduction phase based on multi-level hashing. This is experimental and not enabled. bfxdSwap.c BF expansion basic routine (sifting down the operator node). bfxdUtil.c Utility functions dd-ops.c dd-ops.h Part of generic BDD API for building BDD applications. mult.c Example program: multiplier. myassert.h my own version of assert.h. obj-O Object file directory ppbfPort.c PPBF's interface file for generic BDD API. util.c util.h Common utility functions. Other Useful Pakcages and Files ------------------------------- linuxthread: http://pauillac.inria.fr/~xleroy/linuxthreads/index.html On Linux systems, thread package may not come standard. linuxthread is a user level POSIX thread package. When using this thread package, be sure that PTHREADLIBPATHS PTHREADINCLUDEPATH in the Makefile of PPBF package is set correctly. bdd-trace-driver: http://www.cs.cmu.edu/~bwolen/software/ This package plays back BDD function-call traces on various BDD packages. To integrate the trace driver with PPBF, in the Makefile of the trace driver, please update PTHREADLIBPATHS PTHREADINCLUDEPATH INCLUDE BDDLIBPATHS to reflect your setup. Then % gmake ppbf-driver should create a trace driver that links with this PPBF package. ISCAS85 bdd-traces: http://www.cs.cmu.edu/~bwolen/software/ This package contains the ISCAS85 benchmark circuits converted into the trace format. By building the bdd-trace-driver (described above), ppbf-driver will be able to run these traces in parallel. Bugs ---- Gotta be a few more I haven't found yet. Though this package will not be supported, I would like to categorize the bugs and maybe one day, I will have time to come back and fix it. Acknowledgement --------------- This package is based a depth-first and breadth-first hybrid BDD package written by Yirng-An Chen (yachen@cs.cmu.edu) and I. Disclaimer ---------- This package is slightly changed from the version used in the PPOPP'97 paper to test various other optimizations. As these changes were done a while ago, I don't remember much of what changed. Also, this package is provided AS-IS and I will not be able to support this package well until after my Ph.D. thesis defense. However, please send me comments and bug reports. If I ever do get a chance, I will try to update this package. Lawyerese --------- If you will be using any of the included files and/or any part of any included file in another system, it is your responsibility and duty to ensure this notice appears with the included file and/or its parts and in the documentation for your system. /* * Copyright (c) 1998 Carnegie Mellon University. * All Rights Reserved. * * Permission to use, copy, modify, and distribute this software and * its documentation is hereby granted (including for commercial or * for-profit use), provided that both the copyright notice and this * permission notice appear in all copies of the software, derivative * works, or modified versions, and any portions thereof, and that * both notices appear in supporting documentation, and that credit * is given to Carnegie Mellon University in all publications reporting * on direct or indirect use of this code or its derivatives. * * THIS IMPLEMENTATION MAY HAVE BUGS, SOME OF WHICH MAY HAVE SERIOUS * CONSEQUENCES. CARNEGIE MELLON PROVIDES THIS SOFTWARE IN ITS "AS IS" * CONDITION, AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL * CARNEGIE MELLON UNIVERSITY BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * Carnegie Mellon encourages (but does not require) users of this * software to return any improvements or extensions that they make, * and to grant Carnegie Mellon the rights to redistribute these * changes without encumbrance. */