Accession Number:

ADA123327

Title:

A Study in Parallel Computation - The Traveling Salesman Problem

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1982-08-18

Pagination or Media Count:

28.0

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.

Subject Categories:

  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE