首页   按字顺浏览 期刊浏览 卷期浏览 Finding Concurrencies in Three Layer Channel Routing Algorithm for its Parallel Operati...
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)



返 回