Parallelization of an algorithm for single row routing

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.