A Study in Parallel Computation - The Traveling Salesman Problem

Abstract
The Traveling Salesman Problem is solved on the Cm*, a multiprocessor system, using two implementations based on a branch and bound algorithm. One of these implementations is synchronous and has a granularity that increases wit the degree of parallelism, while the other is asynchronous and has a constant granularity. With increasing degree of parallelism, the first implementation requires increasing amount of computation to solve the problem, leading to a speedup that saturates at a low value. The second implementation requires nearly the same amount computation at all degrees of parallelism and has reasonable speedup characteristic. The difference between the speedup of this implementation and linear speedup is attributed to processors idling because of resource contention.

This publication has 0 references indexed in Scilit: