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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 18, 1982
Accession Number
ADA123327

Entities

People

  • Joseph Mohan

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Access Time
  • Algorithms
  • Artificial Intelligence
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Dynamic Programming
  • Experimental Data
  • Iterations
  • Mathematical Programming
  • Multiprocessors
  • Operating Systems
  • Operations Research
  • Parallel Computing
  • Parallel Processing

Fields of Study

  • Computer science

Readers

  • Mathematics or Statistics
  • Parallel and Distributed Computing.