Single row routing with indifference graphs on the DAP

The distributed array of processors (DAP) is a commercially available massively parallel machine which is often applied to numerically intensive problems which exploit its matrix manipulation abilities. It is shown that the DAP can be efficiently used to solve non-numerical problems as well. Specifically, a heuristic solution to the well-known single row routing problem in a VLSI is proposed. Instances of this problem are modeled using a subclass of interval graphs, and it is shown that this approach leads to efficient algorithms. sequential and parallel. Both algorithms were implemented, the sequential providing a benchmark by which to measure the speed-up of the parallel implementation on the DAP 510