The minimization of multiple valued logic expressions using parallel processors

Download
Author
Oral, Sabri Onur
Date
1991-09Advisor
Yang, Chyan
Butler, Jon T.
Schoenstadt, Arthur L.
Metadata
Show full item recordAbstract
The process of finding an exact minimization for a multiple-valued logic (MVL) expression requires an extensive search and enormous computation time. One of the heuristics to reduce this computation time is the Neighborhood Decoupling (ND) Algorithm by Yang and Wang. This algorithm finds near-optimal solutions for the given MVL expressions. The ND algorithm is an extension of HAMLET (Heuristic Analyzer for Multiple-valued Logic Expressions). The primary goal of this thesis is to reduce the computation time of the ND algorithm by using parallel processors. We developed a parallel version of the ND algorithm and tested it on a iPSC/2 (Intel Parallel Supercomputer). The parallel version of the ND algorithm actually executes in parallel a portion of the ND algorithm known as the clustering factor calculation. The number of nodes needed to run the programs in twice the number of input variables of the expression. The results indicate that the parallel version of ND algorithm halves the computation time compared to the sequential version. A secondary goal of this thesis is to initiate the parallelization of HAMLET and the study of parallel computers, i.e., iPSC/2. The experiences we obtained with iPSC/2 suggest an alternative algorithm. The ND algorithm searches the first branch of the search tree assuming that the optimum solution will be on that branch. We developed a multi-branch Concurrent ND (MCND) algorithm which concurrently searches multiple branches, hence increasing the probability of reaching the optimum.
Rights
Copyright is reserved by the copyright ownerCollections
Related items
Showing items related by title, author, creator and subject.
-
Field computation and nonpropositional knowledge
MacLennan, Bruce J. (Monterey, California. Naval Postgraduate School, 1987-09); NPS52-87-040Most current AI technology has been based on propositionally represented theoretical knowledge. It is argued that if AI is to accomplish its goals, especially in the tasks of sensory interpretation and sensorimotor ... -
Efficient grid based techniques for solving the weighted region least cost path problem on multicomputers
Ekin, Cengiz (Monterey, California. Naval Postgraduate School, 1992-12);This thesis explores the possibilities of developing fast grid parallel algorithms to solve the Weighted Region Least Cost Path problem. Two complimentary steps have been undertaken. First, an efficient sequential algorithm ... -
Real-time contour surface display generation
Zyda, Michael J. (Monterey, California. Naval Postgraduate School, 1984-09); NPS-52-84-013We present in this study the architectural specification and feasibility determination for a real-time contour display generator. We begin by examining a recently reported, highly decomposable algorithm for contour surface ...