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 language | English (US) |
|---|---|
| Title of host publication | IFIP Transactions A |
| Subtitle of host publication | Computer Science and Technology |
| Publisher | Publ by Elsevier Science Publishers B.V. |
| Pages | 273-280 |
| Number of pages | 8 |
| Edition | A-23 |
| ISBN (Print) | 0444884645 |
| State | Published - 1993 |
| Event | Proceedings of the IFIP WG10.3 Working on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism - Orlando, FL, USA Duration: Jan 20 1993 → Jan 22 1993 |
Other
| Other | Proceedings of the IFIP WG10.3 Working on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism |
|---|---|
| City | Orlando, FL, USA |
| Period | 1/20/93 → 1/22/93 |
All Science Journal Classification (ASJC) codes
- General Engineering