The minimization of multiple valued logic expressions using parallel processors
Loading...
Authors
Oral, Sabri Onur
Subjects
Truncated sum
MVL (Multiple Valued Logic) minimization
Neighborhood Decoupling algorithms
MVL (Multiple Valued Logic) minimization
Neighborhood Decoupling algorithms
Advisors
Yang, Chyan
Butler, Jon T.
Schoenstadt, Arthur L.
Date of Issue
1991-09
Date
September 1991
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
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.
Type
Thesis
Description
Series/Report No
Department
Electrical and Computer Engineering
Electronic Warfare Academic Group
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
117 p.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
Copyright is reserved by the copyright owner