Efficient parallel algorithm for sorting on the biswapped network
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).