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.
展开▼
