Efficient sorting on the star graph interconnection network
Tóm tắt
Two algorithms for sorting n! numbers on an n-star interconnection network are described. Both algorithms are based on arranging the n! processors of the n-star in a virtual (n - 1)- dimensional array. The first algorithm runs in O(n
3 log n time. This performance matches that of the fastest previously known algorithm for the same problem. In addition to providing a new paradigm for sorting on the n-star, the proposed algorithm has the advantage of being considerably simpler to state while requiring no recursion in its formulation. Its idea is to sort the input by repeatedly sorting the contents of all rows in each dimension of the (n - 1>algorithm presented in this paper is more efficient. It runs in O(n
2) time and thus provides an asymptotic improvement over its predecessors. However, it is more elaborate as it uses an existing result for sorting optimally on an (n-1)-dimensional array.
Tài liệu tham khảo
S.B. Akers, D. Harel and B. Krishnamurthy, The star graph: An attractive alternative to the n-cube, in: Proceedings of the International Conference on Parallel Processing (1987) pp. 393-400.
S.B. Akers and B. Krishnamurthy, The fault tolerance of star graphs, in: Proceedings of the International Conference on Supercomputing, Vol. 3 (1987) pp. 270-276.
S.B. Akers and B. Krishnamurthy, A group theoretic model for symmetric interconnection networks, IEEE Transactions on Computers 38 (1989) 555-566.
S.G. Akl, Parallel Sorting Algorithms (Academic Press, Orlando, FL, 1985).
S.G. Akl, Parallel Computation: Models and Methods (Prentice-Hall, Upper Saddle River, NJ, 1997).
S.G. Akl, J. Duprat and A.G. Ferreira, Hamiltonian circuits and paths in star graphs, in: Advances in Parallel Algorithms, eds. I. Dimov and O. Tonev (IOS Press, Sofia, Bulgaria, 1994) pp. 131-143.
S.G. Akl and K. Qiu, Les réseaux d'interconnexion star et pancake, in: Algorithmique Parallèle, eds. M. Cosnard, M. Nivat and Y. Robert (Masson, Paris, 1992) pp. 171-181.
S.G. Akl and K. Qiu, A novel routing scheme on the star and pancake networks and its applications, Parallel Computing 19 (1993) 95-101.
S.G. Akl, K. Qiu and I. Stojmenović, Computing the Voronoi diagram on the star and pancake interconnection networks, in: Proceedings of the Canadian Conference on Computational Geometry (1992) pp. 353-358.
S.G. Akl, K. Qiu and I. Stojmenović, Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry, Networks, Special Issue: Interconnection Networks and Algorithms 23 (1993) 215-226.
K.E. Batcher, Sorting networks and their applications, in: Proceedings of the AFIPS Spring Joint Computer Conference (1968) pp. 307-314. (Reprinted in: Interconnection Networks for Parallel and Distributed Processing, eds. C.L. Wu and T.S. Feng (IEEE Computer Soc. Press, Silver Spring, MD, 1984) pp. 576-583.)
K. Brockmann and R. Wanka, Efficient oblivious parallel sorting on the MasPar MP-1, in: Proceedings of the Hawaii Conference on System Sciences, Vol. 1 (1997) pp. 200-208.
W.K. Chiang and R.J. Chen, The (n, k)-star graph: A generalized star graph, Information Processing Letters 56 (1995) 259-264.
P.F. Corbett and I.D. Scherson, A unified algorithm for sorting on multidimensional mesh-connected processors, Information Processing Letters 37 (1991) 225-231.
R. Cypher and J.L.C. Sanz, Optimal sorting on reduced architectures, in: Proceedings of the International Conference on Parallel Processing, Vol. 3 (1988) pp. 308-311.
M. Dietzfelbinger, S. Madhavapeddy and I.H. Sudborough, Three disjoint path paradigms in star networks, in: Proceedings of the IEEE Symposium on Parallel and Distributed Processing (1991) pp. 400-406.
M. Dowd, Y. Perl, L. Rudolph and M. Saks, The balanced sorting network, in: Proceedings of the Conference on Principles of Distributed Computing (1983) pp. 161-172.
P. Fragopoulou, Communication and fault tolerance algorithms on a class of interconnection networks, Ph.D. thesis, Department of Computing and Information Science, Queen's University, Kingston, ON (1995).
P. Fragopoulou and S.G. Akl, A parallel algorithm for computing Fourier transforms on the star graph, IEEE Transactions on Parallel and Distributed Systems 5 (1994) 525-531.
P. Fragopoulou and S.G. Akl, Optimal communication algorithms on star graphs using spanning tree constructions, Journal of Parallel and Distributed Computing 24 (1995) 55-71.
P. Fragopoulou and S.G. Akl, Fault tolerant communication algorithms on the star network using disjoint paths, in: Proceedings of the Hawaii International Conference on System Sciences, Vol. 2 (1995) pp. 5-13.
P. Fragopoulou and S.G. Akl, A framework for optimal communication on a subclass of Cayley graph based networks, in: Proceedings of the International Conference on Computers and Communications (1995) pp. 241-248.
P. Fragopoulou and S.G. Akl, Efficient algorithms for global data communication on the multidimensional torus network, in: Proceedings of the International Parallel Processing Symposium (1995) pp. 324-330.
P. Fragopoulou and S.G. Akl, Edge-disjoint spanning trees on the star network with applications to fault tolerance, IEEE Transactions on Computers 45 (1996) 174-185.
P. Fragopoulou, S.G. Akl and H. Meijer, Optimal communication primitives on the generalized hypercube network, Journal of Parallel and Distributed Computing 32 (1996) 173-187.
D.M. Gordon, Parallel sorting on Cayley graphs, Algorithmica 6 (1991) 554-564.
Y. Han and Y. Igarashi, Time lower bounds for sorting on multi-dimensional mesh-connected processor arrays, in: Proceedings of the International Conference on Parallel Processing, Vol. 3 (1988) pp. 194-197.
B.R. Heap, Permutations by interchanges, The Computer Journal 6 (1963) 293-294.
J.S. Jwo, S. Lakshmivarahan and S.K. Dhall, Embedding of cycles and grids in star graphs, in: Proceedings of the IEEE Symposium on Parallel and Distributed Processing (1990) pp. 540-547.
M. Kaufmann, J.F. Sibeyn and T. Suel, Beyond the worst-case bisection bound: Fast sorting and routing on meshes, in: Proceedings of the European Symposium on Algorithms, Lecture Notes in Computer Science, Vol. 979 (Springer, Berlin, 1995) pp. 75-88.
M. Kaufmann and J.F. Sibeyn, Randomized multipacket routing and sorting on meshes, Algorithmica 17 (1997) 224-244.
D.E. Knuth, The Art of Computer Programming, Vol. 3 (Addison-Wesley, Reading, MA, 1973).
M. Kunde, A general approach to sorting on 3-dimensionally mesh-connected arrays, in: Proceedings of the Conference on Parallel Processing (CONPAR), Lecture Notes in Computer Science, Vol. 237 (Springer, Berlin, 1986) pp. 329-337.
M. Kunde, Lower bounds for sorting on mesh-connected architectures, Acta Informatica 24 (1987) 121-130.
M. Kunde, Optimal sorting on multi-dimensionally mesh-connected computers, in: Proceedings of the Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 247 (Springer, Berlin, 1987) pp. 408-419.
M. Kunde, Routing and sorting in mesh-connected arrays, in: Proceedings of the Aegean Workshop on Computing, Lecture Notes in Computer Science, Vol. 319 (Springer, Berlin, 1988) pp. 423-433.
M. Kunde, Concentrated regular data streams on grids: Sorting and routing near the bisection bound, in: Proceedings of the Symposium on Foundations of Computer Science (1991) pp. 141-150.
M. Kunde, Routing and sorting on grids, Habilitationsschrift, Department of Computer Science, Technical University of Munich, Munich, Germany (1992).
M. Kunde, Block gossiping on grids and tori: Deterministic sorting and routing match the bisection bound, in: Proceedings of the European Symposium on Algorithms, Lecture Notes in Computer Science, Vol. 726 (Springer, Berlin, 1993) pp. 272-283.
M. Kunde, R. Niedermeier and P. Rossmanith, Faster sorting and routing on grids with diagonals, in: Proceedings of the Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 775 (Springer, Berlin, 1994) pp. 225-236.
M. Kunde, R. Niedermeier, K. Reinhardt and P. Rossmanith, Optimal average case sorting on arrays, in: Proceedings of the Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 900 (Springer, Berlin, 1995) pp. 503-514.
F.T. Leighton, Introduction to Parallel Algorithms and Architectures (Morgan Kaufmann, San Mateo, CA, 1992).
A. Menn and A.K. Somani, An efficient sorting algorithm for the star graph interconnection network, in: Proceedings of the International Conference on Parallel Processing, Vol. 3 (1990) pp. 1-8.
D. Nassimi and S. Sahni, Bitonic sort on a mesh-connected parallel computer, IEEE Transactions on Computers 27 (1979) 2-7.
M. Nigam, S. Sahni and B. Krishnamurthy, Embedding Hamiltonians and hypercubes in star interconnection graphs, in: Proceedings of the International Conference on Parallel Processing, Vol. 3 (1990) pp. 340-343.
F.P. Preparata and J.E. Vuillemin, The cube-connected cycles: A versatile network for parallel computation, Communications of the ACM 24 (1981) 300-309.
K. Qiu, The star and pancake interconnection networks: Properties and algorithms, Ph.D. thesis, Department of Computing and Information Science, Queen's University, Kingston, ON (1992).
K. Qiu and S.G. Akl, Load balancing, selection and sorting on the star and pancake interconnection networks, Journal of Parallel Algorithms and Applications 2 (1994) 27-42.
K. Qiu and S.G. Akl, On some properties of the star graph, Journal of VLSI Design, Special Issue on Interconnection Networks 2 (1994) 389-396.
K. Qiu, S.G. Akl and H. Meijer, On some properties and algorithms for the star and pancake interconnection networks, Journal of Parallel and Distributed Computing 22 (1994) 16-25.
K. Qiu, H. Meijer and S.G. Akl, Parallel routing and sorting on the pancake network, in: Proceedings of the International Conference on Computing and Information, Lecture Notes in Computer Science, Vol. 497 (Springer, Berlin, 1991) pp. 360-371.
K. Qiu, H. Meijer and S.G. Akl, Decomposing a star graph into disjoint cycles, Information Processing Letters 39 (1991) 125-129.
K. Qiu, H. Meijer and S.G. Akl, On the cycle structure of star graphs, Congressus Numerantium 96 (1993) 123-141.
S. Rajasekaran and D.S.L. Wei, Selection, routing and sorting on the star graph, in: Proceedings of the International Parallel Processing Symposium (1993) pp. 661-665.
S. Rajasekaran and D.S.L. Wei, Selection, routing, and sorting on the star graph, Journal of Parallel and Distributed Computing 41 (1997) 225-233.
K. Sado and Y. Igarashi, Some parallel sorts on a mesh-connected processor array and their time efficiency, Journal of Parallel and Distributed Computing 3 (1986) 398-410.
I. Scherson, S. Sen and A. Shamir, Shear-sort: A true two-dimensional sorting technique for VLSI networks, in: Proceedings of the International Conference on Parallel Processing (1986) pp. 903-908.
R. Sedgewick, Permutation generation methods, Computing Surveys 9 (1977) 137-164.
J.F. Sibeyn, Sample sort on meshes, in: Proceedings of the Euro-par Conference, Lecture Notes in Computer Science (Springer, Berlin, 1997), to appear.
S. Sur and P.K. Srimani, A fault tolerant routing algorithm in star graphs, in: Proceedings of the International Conference on Parallel Processing, Vol. 3 (1991) pp. 267-270.
C.D. Thompson and H.T. Kung, Sorting on a mesh-connected parallel computer, Communications of the ACM 20 (1977) 263-271.
R. Wanka, Fast general sorting on meshes of arbitrary dimension without routing, Technical Report No. 87, Department of Computer Science, Paderborn University, Paderborn, Germany (1991).
R. Wanka, Paralleles Sortieren auf mehrdimensionalen Gittern, Ph.D. thesis, Paderborn University, Paderborn, Germany (1994).