Title :
Parallel Prefix Algorithm on BSN-Mesh
Author :
Wenhong Wei ; Qingxia Li ; Ming Tao
Author_Institution :
Sch. of Comput., Dongguan Univ. of Technol., Dongguan, China
Abstract :
A parallel algorithm for prefix computation of N=2n4 elements on a Biswapped network (BSN) whose basis network is n×n mesh network is presented. BSN is a recently proposed network model of parallel computing, which is built of 2n copies of an n-node basis network and its basic network may be Hypercube, Mesh and other networks, BSN-Mesh is Biswapped network whose basis network is Mesh network. In this paper, the parallel prefix algorithm proposed takes time on N processors N communication steps.
Keywords :
computational complexity; mesh generation; multiprocessor interconnection networks; parallel algorithms; BSN-Mesh; Biswapped network; mesh network; n-node basis network; network model; parallel computing; parallel prefix algorithm; prefix computation; time complexity; Algorithm design and analysis; Clustering algorithms; Educational institutions; Parallel algorithms; Program processors; Registers; Time complexity; Biswapped network; Parallel Prefix algorithm; Time complexity;
Conference_Titel :
Emerging Intelligent Data and Web Technologies (EIDWT), 2013 Fourth International Conference on
Conference_Location :
Xi´an
Print_ISBN :
978-1-4799-2140-9
DOI :
10.1109/EIDWT.2013.12
