Finding Concurrencies in Three Layer Channel Routing Algorithm for its Parallel Operation in SIMD CRCW Model
作者:
BoseShefali,
SahaAnil Ranjan,
期刊:
IETE Journal of Research
(Taylor Available online 1993)
卷期:
Volume 39,
issue 4
页码: 205-215
ISSN:0377-2063
年代: 1993
DOI:10.1080/03772063.1993.11437121
出版商: Taylor&Francis
关键词: Serial merging;Parallel merging;SM SIMD;CRCW;Topological sorting Parallel BFS;Optimal algorithm
数据来源: Taylor
摘要:
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 fromO(n2)toO(n* logn) usingO(n)processors fornnets.
点击下载:
PDF (705KB)
返 回