The status of manip - a multicomputer architecture for solving, combinatorial extremum-search problems
Benjamin Wan-Sang Wah, Guojie Li, Chee-Fen Yu · ACM SIGARCH Computer Architecture News · 1984
In this paper, we report the status of study on MANIP, a parallel computer for solving combinatorial extremum-search problems. The most general technique that can be used to solve a wide variety of these problems on a uniprocessor system, optimally or sub-optimally, is the branch-and-bound algorithm. We have adapted and extended branch-and-bound algorithms with lower-bound tests for parallel processing. Three major problems are identified in the design: interconnection networks for supporting the selection of subproblems, anomalies in parallelism and virtual-memory support. A unidirectional ring network has been shown to be the most cost-effective selection network. We provide sufficient conditions so that anomalies can be eliminated under certain conditions and show that anomalies are unavoidable otherwise. Lastly, we develop a modified branch-and-bound algorithm so that the amount of memory space required under a best-first search is significantly reduced.