Volume 4 - Issue 4
Efficient parallel algorithm for sorting on the biswapped network
Abstract
Biswapped network (BSN) is a new topology for interconnection networks in multiprocessor systems. BSN is built of 2n copies of an n-node basic network and total nodes are 2n2, and its basic network may be hypercube, mesh and other networks, hence we can construct BSN-Hypercube and BSN-Mesh by using hypercube and mesh as basic network. Some topological properties of BSN have been investigated, and some algorithms have been developed on the BSN such as matrix multiplication etc. In this paper, we present efficient parallel sorting algorithm on the n-processor BSN whose basic network has Hamiltonian path, and if the basic network of BSN is mesh, sorting n unordered elements will complete in time √(2n) + O(n3/4).
Paper Details
PaperID: 55649097936
Author's Name: Wei, W., Xiao, W.
Volume: Volume 4
Issues: Issue 4
Keywords: Biswapped network (BSN), Cayley digraphs, Hamiltonian, Sorting
Year: 2008
Month: August
Pages: 1365-1370