Parallel implementation of the traveling salesmen problem on a sequent symmetry multiprocessor

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

Nonnumeric problems are highly sequential and known to be difficult to parallelize due to sequential evaluation of one state after another. In this paper, experiences parallelizing the Traveling Salesmen Problem are presented. Sources of parallelism are identified, based on which the TSP is parallelized. The parallel version is implemented in SISAL, a side-effect free functional language. To verify the effectiveness of the parallelization process, parallelism profiles are constructed with the help of SISAL. To further identify the effectiveness of the parallelization process, the parallel version is executed on a Sequent Symmetry shared-memory multiprocessor. Experimental results indicate that the parallel version can give 7 fold speedup using 20 processors. This study indicates that a moderate amount of parallelization effort with SISAL can effectively parallelize the TSP.

Original languageEnglish (US)
Title of host publicationIFIP Transactions A
Subtitle of host publicationComputer Science and Technology
PublisherPubl by Elsevier Science Publishers B.V.
Pages273-280
Number of pages8
EditionA-23
ISBN (Print)0444884645
StatePublished - Dec 1 1993
EventProceedings of the IFIP WG10.3 Working on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism - Orlando, FL, USA
Duration: Jan 20 1993Jan 22 1993

Other

OtherProceedings of the IFIP WG10.3 Working on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism
CityOrlando, FL, USA
Period1/20/931/22/93

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Parallel implementation of the traveling salesmen problem on a sequent symmetry multiprocessor'. Together they form a unique fingerprint.

Cite this