Title :
Experiences of parallel processing with direct cover algorithms for multiple-valued logic minimization
Author :
Yang, Chyan ; Oral, Onur
Author_Institution :
Dept. of Electr. & Comput. Eng., US Naval Postgraduate Sch., Monterey, CA, USA
Abstract :
The implementation of the direct cover algorithm, a heuristic, on a real parallel computer system, Intel iPSC/2, is reported. A CAD tool, HAMLET, that is based on direct cover algorithms has been ported to iPSC/2. Parallel neighborhood decoupling (PND), a parallel version of ND that runs faster than ND, is used, as well as another parallel implementation of ND, multibranch ND (Multi-ND), which allows each processor to search one path of the search tree until the number of processors is exhausted. Searching in multiple branches guarantees a higher probability of reaching an exact solution. In addition, Multi-ND uses less communication than PND, since once a process is assigned a task it will remain isolated from the host until there is a need to report its solution. The results show that Multi-ND outperforms PND in both optimality and speed
Keywords :
many-valued logics; minimisation of switching nets; parallel processing; search problems; CAD tool; HAMLET; Intel iPSC/2; direct cover algorithms; multiple branches; multiple-valued logic minimization; optimality; parallel neighbourhood decoupling; parallel processing; parallel version; search tree; speed; CMOS logic circuits; Concurrent computing; Heuristic algorithms; Logic design; Logic devices; Minimization methods; Neodymium; Parallel processing; Programmable logic arrays; Very large scale integration;
Conference_Titel :
Multiple-Valued Logic, 1992. Proceedings., Twenty-Second International Symposium on
Conference_Location :
Sendai
Print_ISBN :
0-8186-2680-1
DOI :
10.1109/ISMVL.1992.186780
