A parallel single row routing algorithm for hypercube multiprocessor

The authors develop a parallel single-row routing algorithm for a hypercube multiprocessor. The parallel algorithm is based on an earlier sequential O(n² log n) algorithm and an efficient allocation scheme. The algorithm uses a graph decomposition technique and modified cut-number to partition the problem into several subproblems. Each problem is solved on a different processor and solutions are merged in parallel. It is proved that the algorithm has a linear speedup of (n² log n)/N using N processors and that the allocation scheme is optimal. The experimental results show that the proposed algorithm achieves a speedup factor that is quite close to the theoretical bound while maintaining the quality of the solutions as compared to sequential algorithms