Parallel Prefix Algorithm on BSN-Mesh
Wenhong Wei, Qing Li, Ming Tao · 2013
A parallel algorithm for prefix computation of N=2n4elements 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.