Downloads & Free Reading Options - Results

Thesis advisor, Jon T. Butler

We propose a solution to the minimization problem of multiple-valued programmable logic arrays (PLA) that uses simulated annealing. The algorithm accepts a sum-of-products expression, divides and recombines the product terms, gradually progressing toward a minimal solution. The input expression can be user-specified or one produced by another heuristic. The process is termed simulated annealing because it has an analog in the statistical mechanical model of annealing in solids. That is, the slow cooling of certain solids results in a state of low energy, a crystalline state rather than an amorphous state that results from fast cooling. In a PLA, the crystalline state is analogous to a realization with a small number of product terms. Unlike recently studied minimization techniques (which are classified as direct cover methods), our technique manipulates product terms directly, breaking them up and joining them in different was while reducing the total number of product terms. Computer- aided design tool, multiple-valued logic, programmable logic array, heuristic minimization technique VLSI design tool.

We propose a solution to the minimization problem of multiple-valued programmable logic arrays (PLA) that uses simulated annealing. The algorithm accepts a sum-of-products expression, divides and recombines the product terms, gradually progressing toward a minimal solution. The input expression can be user-specified or one produced by another heuristic. The process is termed simulated annealing because it has an analog in the statistical mechanical model of annealing in solids. That is, the slow cooling of certain solids results in a state of low energy, a crystalline state rather than an amorphous state that results from fast cooling. In a PLA, the crystalline state is analogous to a realization with a small number of product terms. Unlike recently studied minimization techniques (which are classified as direct cover methods), our technique manipulates product terms directly, breaking them up and joining them in different was while reducing the total number of product terms. Computer- aided design tool, multiple-valued logic, programmable logic array, heuristic minimization technique VLSI design tool.

The process of finding a guaranteed minimal solution for a multiple- valued programmable logic expression requires an exhaustive search. Exhaustive search is not very realistic because of enormous computation time required to reach a solution. One of the heuristics to reduce this computation time and provide a near-minimal solution is simulated annealing. This thesis analyzes the use of loosely-coupled, course-grained parallel systems for simulated annealing. This approach involves the use of multiple processors where interprocess communication occurs only at the beginning and end of the process. In this study, the relationship between the quality of solution, measured by the number of products and computation time, and simulated annealing parameters are investigated. A simulated annealing experiment is also investigated where two types of moves are mixed. These approaches provide improvement in both the number of product terms and computation time.

The process of finding a guaranteed minimal solution for a multiple- valued programmable logic expression requires an exhaustive search. Exhaustive search is not very realistic because of enormous computation time required to reach a solution. One of the heuristics to reduce this computation time and provide a near-minimal solution is simulated annealing. This thesis analyzes the use of loosely-coupled, course-grained parallel systems for simulated annealing. This approach involves the use of multiple processors where interprocess communication occurs only at the beginning and end of the process. In this study, the relationship between the quality of solution, measured by the number of products and computation time, and simulated annealing parameters are investigated. A simulated annealing experiment is also investigated where two types of moves are mixed. These approaches provide improvement in both the number of product terms and computation time.

Title from cover

The process of finding a guaranteed minimal solution for a multiple-valued programmable logic expression requires an exhaustive search. Exhaustive search is not very realistic because of enormous computation time required to reach a solution. One of the heuristics to reduce this computation time and provide a nearminimal solution is simulated annealing. This thesis analyzes the use of loosely-coupled, course-grained parallel systems for simulated annealing. This approach involves the use of multiple processors where interprocess communication occurs only at the beginning and end of the process. In this study, the relationship between the quality of solution, measured by the number of products and computation time, and simulated annealing parameters are investigated. A simulated annealing experiment is also investigated where two types of moves are mixed. These approaches provide improvement in both the number of product terms and computation time.