The minimization of multiple valued logic expressions using parallel processors

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.