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
DOI Bookmark:
http://doi.ieeecomputersociety.org/10.1109/ICIS.2008.62
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
Usage of this product signifies your acceptance of the
Terms of Use.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||