Authors

null Chih-Ming Lai, null Jyh-Jong Tsay

Abstract

We study the problem of performing all-to-all broadcast on an n-alternating group graph AG/sub n/ with all-port and store-and-forward routing. The running time is [(n/sup 1/-2)/(4(n-2))+1] that is one step more than the trivial lower bound [(n/sup 2/-2)/(4(n-2))]. Our algorithm is based on some new properties of Hamiltonian paths of AG/sub n/ that are identified in this paper and are of independent interest. Similar properties have been used to design an algorithm for single-node scattering that achieves the same time bound.

Citation

  • Journal: Proceedings of IEEE International Symposium on Parallel Algorithms Architecture Synthesis
  • Year: 2002
  • Volume:
  • Issue:
  • Pages: 104–110
  • Publisher: IEEE Comput. Soc. Press
  • DOI: 10.1109/aispas.1997.581639

BibTeX

@inproceedings{Chih_Ming_Lai,
  series={AISPAS-97},
  title={{Communication algorithms on alternating group graphs}},
  DOI={10.1109/aispas.1997.581639},
  booktitle={{Proceedings of IEEE International Symposium on Parallel Algorithms Architecture Synthesis}},
  publisher={IEEE Comput. Soc. Press},
  author={Chih-Ming Lai and Jyh-Jong Tsay},
  pages={104--110},
  collection={AISPAS-97}
}

Download the bib file

References

  • (0)
  • Jung-Sing Jwo, Lakshmivarahan, S. & Dhall, S. K. Embedding of cycles and grids in star graphs. Proceedings of the Second IEEE Symposium on Parallel and Distributed Processing 1990 540–547 doi:10.1109/spdp.1990.143600 – 10.1109/spdp.1990.143600
  • Akers, S. B. & Krishnamurthy, B. A group-theoretic model for symmetric interconnection networks. IEEE Trans. Comput. 38, 555–566 (1989) – 10.1109/12.21148
  • Bertsekas, D. P., Özveren, C., Stamoulis, G. D., Tseng, P. & Tsitsiklis, J. N. Optimal communication algorithms for hypercubes. Journal of Parallel and Distributed Computing 11, 263–275 (1991) – 10.1016/0743-7315(91)90033-6
  • akers, The Star Graph: An Attractive Alternative to The N-Cube. Proceedings of the International Conference on Parallel Processing (1987)
  • Mendia, V. E. & Sarkar, D. Optimal broadcasting on the star graph. IEEE Trans. Parallel Distrib. Syst. 3, 389–396 (1992) – 10.1109/71.149958
  • Rescigno, A. A. Optimal polling in communication networks. Proceedings of 1994 6th IEEE Symposium on Parallel and Distributed Processing 224–231 doi:10.1109/spdp.1994.346163 – 10.1109/spdp.1994.346163
  • Fragopoulou, P. & Akl, S. G. Optimal communication algorithms on the star interconnection network. Proceedings of 1993 5th IEEE Symposium on Parallel and Distributed Processing 702–711 doi:10.1109/spdp.1993.395464 – 10.1109/spdp.1993.395464
  • jwo, Analysis of Interconnection Networks Based on Cayley Graphs Related to Permutation Groups (0)
  • Lakshmivarahan, S., Jwo, J.-S. & Dhall, S. K. Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey. Parallel Computing 19, 361–407 (1993) – 10.1016/0167-8191(93)90054-o
  • Jwo, J., Lakshmivarahan, S. & Dhall, S. K. A new class of interconnection networks based on the alternating group. Networks 23, 315–326 (1993) – 10.1002/net.3230230414