Finding Concurrencies in Three Layer Channel Routing Algorithm for its Parallel Operation in SIMD CRCW Model

Abstract

This paper explores the inherent parallelism in different steps of three layer channel routing algorithm based on merging method in Shared Memory SIMD computer using CRCW model. Overall algorithm is structured as set of sequential steps, implemented by calling several procedures, namely finding longest path of a directed graph, finding minimum or maximum value among a set, merging two nodes in a directed graph, searching a graph for a particular node. Studying the inherent parallelism, each procedure is restructured for parallel operation on SIMD model. The speed-up and complexity analysis is performed at each step considering unbounded parallelism. The overall complexity of this algorithm reduces from O(n²) to O(n* log n) using O(n) processors for n nets.

Indexing terms:

• Serial merging
• Parallel merging
• SM SIMD
• CRCW
• Topological sorting Parallel BFS
• Optimal algorithm