Authors

B. Bose, B. Broeg, null Younggeun Kwon, Y. Ashir

Abstract

In this paper, we consider various topological properties of a k-ary n-cube (Q/sub n//sup k/) using Lee distance. We feel that Lee distance is a natural metric for defining and studying a Q/sub n//sup k/. After defining a Q/sub n//sup k/ graph using Lee distance, we show how to find all disjoint paths between any two nodes. Given a sequence of radix k numbers, a function mapping the sequence to a Gray code sequence is presented, and this function is used to generate a Hamiltonian cycle. Embedding the graph of a mesh and the graph of a binary hypercube into the graph of a Q/sub n//sup k/ is considered. Using a k-ary Gray code, we show the embedding of a k(n/sub 1/)/spl times/k(n/sub 2/)/spl times/…/spl times/k(n/sub m/)-dimensional mesh into a Q/sub n//sup k/ where n=/spl Sigma//sub i=l//sup m/n/sub i/. Then using a single digit, 4-ary reflective Gray code, we demonstrate embedding a Q/sub n/ into Q/sub [n/2]//sup 4/. We look at how Lee distance may be applied to the problem of resource placement in a Q/sub n//sup k/ by using a Lee distance error-correcting code. Although the results in this paper are only preliminary, Lee distance error-correcting codes have not been applied previously to this problem. Finally, we consider how Lee distance can be applied to message routing and single-node broadcasting in a Q/sub n//sup k/. In this section we present two single-node broadcasting algorithms that are optimal when single-port and multi-port I/O is used. >

Citation

  • Journal: IEEE Transactions on Computers
  • Year: 1995
  • Volume: 44
  • Issue: 8
  • Pages: 1021–1030
  • Publisher: Institute of Electrical and Electronics Engineers (IEEE)
  • DOI: 10.1109/12.403718

BibTeX

@article{Bose_1995,
  title={{Lee distance and topological properties of k-ary n-cubes}},
  volume={44},
  ISSN={0018-9340},
  DOI={10.1109/12.403718},
  number={8},
  journal={IEEE Transactions on Computers},
  publisher={Institute of Electrical and Electronics Engineers (IEEE)},
  author={Bose, B. and Broeg, B. and Younggeun Kwon and Ashir, Y.},
  year={1995},
  pages={1021--1030}
}

Download the bib file

References

  • chiu, resource allocation in hypercube systems. Proc Fifth Distributed Memory Computing Conf (1990)
  • chen, fault-tolerant resource placement in hypercube computers. Proc 1991 Int?l Conf Parallel Processing (1991)
  • Borkar, S. et al. iWarp: an integrated solution to high-speed parallel computing. Proceedings. SUPERCOMPUTING ’88 330–339 doi:10.1109/superc.1988.44670 – 10.1109/superc.1988.44670
  • Bhuyan & Agrawal. Generalized Hypercube and Hyperbus Structures for a Computer Network. IEEE Trans. Comput. C–33, 323–333 (1984) – 10.1109/tc.1984.1676437
  • berlekamp, Algebraic Coding Theory (1968)
  • Seitz, C. L. et al. The architecture and programming of the Ametek series 2010 multicomputer. Proceedings of the third conference on Hypercube concurrent computers and applications Architecture, software, computer systems, and general issues - vol. 1 33–37 (1988) – 10.1145/62297.62302
  • Ramanathan, P. & Chalasani, S. Resource placement with multiple adjacency constraints in k-ary n-cubes. IEEE Trans. Parallel Distrib. Syst. 6, 511–519 (1995) – 10.1109/71.382319
  • golomb, algebraic coding and the lee metric. Error Correcting Codes (1968)
  • leighton, Introduction to Parallel Algorithms and Architectures Arrays �Trees�Hypercubes (1992)
  • reddy, i/o embeddings in hypercubes. Proc 1988 Int?l Conf Parallel Processing (1988)
  • Dally, W. J. et al. The message-driven processor: a multicomputer processing node with efficient mechanisms. IEEE Micro 12, 23–39 (1992) – 10.1109/40.127581
  • Roth, R. M. & Siegel, P. H. A Family of Bch Codes for the Lee Metric. Proceedings. IEEE International Symposium on Information Theory 35–35 doi:10.1109/isit.1993.748350 – 10.1109/isit.1993.748350
  • seitz, submicron systems architecture project semiannual technicalreport. Technical Report (1988)
  • dally, the j-machine: a fine-grainconcurrent computer. Information Processing 89 (1989)
  • Livingston, M. & Stout, Q. F. Distributing resources in hypercube computers. Proceedings of the third conference on Hypercube concurrent computers and applications Architecture, software, computer systems, and general issues - vol. 1 222–231 (1988) – 10.1145/62297.62324
  • Ni, L. M. & McKinley, P. K. A survey of wormhole routing techniques in direct networks. Computer 26, 62–76 (1993) – 10.1109/2.191995
  • oed, the cray research massively parallel processor system: cray t3d. (1993)