HP Labs Technical Reports

Parallel Algorithms for Minimizing Multiple- Valued Programmable Logic Arrays

Tirumalai, Partha P.



Abstract: Implementing a multiple-valued logic function using a multiple-valued programmable logic array involves deriving a logic expression for the function. The process of finding an optimal expression requires an extensive search. This paper presents two parallel versions of a minimization algorithm: one for a shared memory and another for a distributed memory multiprocessor system. Both algorithms exploit the considerable parallelism available in the minimization problem. We discuss the communication, synchronization and load balancing issues under the two machine models. Limited access and the cost of the required computation prevented us from running the two parallel algorithms on the actual machines; however, we were able to run parallel algorithms for a different, but very similar, problem that required less computation. These results indicate that excellent speedups, in some cases superlinear (i.e., more than the number of processors), can be obtained from parallel implementations of this logic minimization algorithm.

Back to Index

[Research] [News] [Tech Reports] [Palo Alto] [Bristol] [Japan] [Israel] [Site Map][Home] [Hewlett-Packard]