Seventh IEEE/ACIS International Conference on Computer and Information Science (icis 2008)
Parallel Sorting on the Biswapped Network
May 14-May 16
ISBN: 978-0-7695-3131-1
Biswapped network (BSN) is a recently proposed network model of parallel computing, which is built of 2n copies of an n-node basic network, 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. BSN uses a simple rule for connectivity to ensure its regularity and some topological properties of BSN have been investigated. In this paper, we present sorting algorithm on the n processors 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)^1(1/2)+O(n^(3/4)).
Index Terms:
Biswapped network (BSN), Cayley digraphs, Hamilton, Sorting.
Citation:
Wenhong Wei, Wenjun Xiao, Zhen Zhang, "Parallel Sorting on the Biswapped Network," icis, pp.439-443, Seventh IEEE/ACIS International Conference on Computer and Information Science (icis 2008), 2008