Parallelization of an algorithm for single row routing

Author

Lila L. Holt

Date of Award

5-1992

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

Jean R. S. Blair

Committee Members

David Straight, Heather Booth

Abstract

When routing printed circuit boards and IC chips, connecting the wires in a minimal space is essential. Single row routing is one approach designed to achieve this goal. However, the single row routing problem is NP-complete, and thus, research has focused on developing reasonable heuristics to solve the single row routing problem. This research focuses on parallelizing a given heuristic and attempts to determine if the parallelization can increase the efficiency when elapsed time is used as the metric. Many issues play a part in developing a parallel routine and are discussed along with three parallel versions which are implemented and tested. The results clearly indicate parallelization can be beneficial, but not for all test cases.

Recommended Citation

Holt, Lila L., "Parallelization of an algorithm for single row routing. " Master's Thesis, University of Tennessee, 1992.
https://trace.tennessee.edu/utk_gradthes/12137