More Web Proxy on the site http://driver.im/

research-article

Enhanced Hypercubes

Authors:

Nian-Feng Tzeng,

Sizheng WeiAuthors Info & Claims

IEEE Transactions on Computers, Volume 40, Issue 3

Pages 284 - 294

https://doi.org/10.1109/12.76405

Published: 01 March 1991 Publication History

Abstract

A hypercube with extra connections added between pairs of nodes through otherwise unused links is investigated. The extra connections are made in a way that maximizes the improvement of the performance measure of interest under various traffic distributions. The resulting hypercube, called the enhanced hypercube, requires a simple routing algorithm and is guaranteed not to create any traffic-congested points or links. The enhanced hypercube achieves noticeable improvement in diameter, mean internode distance, and traffic density, and it also is more cost effective than a regular hypercube. An efficient broadcast algorithm that can considerably speed up the broadcast process in enhanced hypercubes is provided.

References

[1]

{1} C. L. Seitz, "The Cosmic Cube," Commun. ACM, vol. 28, no. 1, pp. 22-33, Jan. 1985.

Digital Library

[2]

{2} W. D. Hillis, The Connection Machine. Cambridge, MA: MIT Press, 1985.

Digital Library

[3]

{3} Intel Corporation, iPSC System Overview, Jan. 1986.

[4]

{4} J. P. Hayes, T. N. Mudge, and Q. F. Stout, "Architecture of a hypercube supercomputer," in Proc. 1986 Int. Conf. Parallel Processing, Aug. 1986, pp. 653-660.

[5]

{5} W. C. Athas and C. L. Seitz, "Multicomputers: Message-passing concurrent computers," IEEE Comput. Mag., vol. 21, pp. 9-24, Aug. 1988.

Digital Library

[6]

{6} L. W. Tucker and G. G. Robertson, "Architecture and applications of the Connection Machine," IEEE Comput. Mag., vol. 21, pp. 26-38, Aug. 1988.

Digital Library

[7]

{7} W. T.-Y. Hsu, P.-C. Yew, and C.-Q. Zhu, "An enhancement scheme for hypercube interconnection networks," in Proc. 1987 Int. Conf. Parallel Processing, Aug. 1987, pp. 820-823.

[8]

{8} D. A. Reed and D. C. Grunwald, "The performance of multicomputer interconnection networks," IEEE Comput. Mag., vol. 20, pp. 63-73, June 1987.

Digital Library

[9]

{9} H. Sullivan and T. R. Bashkow, "A large scale homogeneous, fully distributed parallel machine, I," in Proc. 4th Symp. Comput. Architecture, Mar. 1977, pp. 105-117.

Digital Library

[10]

{10} D. A. Reed and H. D. Schwetman, "Cost-performance bounds for multimicrocomputer networks," IEEE Trans. Comput., vol. C-32, pp. 83-95, Jan. 1983.

[11]

{11} L. D. Wittie, "Communication structures for large networks of microcomputers," IEEE Trans. Comput., vol. C-30, pp. 264-273, Apr. 1981.

[12]

{12} P. W. Dowd and K. Jabbour, "Spanning multiaccess channel hypercube computer interconnection," IEEE Trans. Comput., vol. C-37, pp. 1137-1142, Sept. 1988.

Digital Library

[13]

{13} L. N. Bhuyan and D. P. Agrawal, "Generalized hypercube and hyperbus structures for a computer network," IEEE Trans. Comput., vol. C-33, pp. 323-333, Apr. 1984.

[14]

{14} J. P. Hayes et al., "A microprocessor-based hypercube supercomputer," IEEE Micro, vol. 6, pp. 6-17, Oct. 1986.

Digital Library

[15]

{15} J. C. Peterson et al., "The Mark III hypercube-ensemble concurrent computer," in Proc. 1985 Int. Conf. Parallel Processing, Aug. 1985, pp. 71-73.

[16]

{16} A. Esfahanian, L. M. Ni, and B. E. Sagan, "On enhancing hypercube multiprocessors," in Proc. 1988 Int. Conf. Parallel Processing, Aug. 1985, pp. 86-89.

[17]

{17} D. P. Agrawal and V. K. Janakiram, "Evaluating the performance of multicomputer configurations," IEEE Comput. Mag., vol. 19, pp. 23-37, May 1986.

Digital Library

[18]

{18} S. L. Johnsson and C.-T. Ho, "Optimum broadcasting and personalized communication in hypercubes," IEEE Trans. Comput., vol. 38, pp. 1249-1268, Sept. 1989.

Digital Library

[19]

{19} L. Lamport, R. Shostak, and M. Pease, "The Byzantine generals problem," ACM Trans. Programming Languages Syst., vol. 4, pp. 382-401, July 1982.

Digital Library

[20]

{20} T. K. Srikanth and S. Toueg, "Optimal clock synchronization," J. ACM, vol. 34, pp. 626-645, July 1987.

Digital Library

Cited By

Huang ZYang YZhang MYang X(2025)Assessing reliability in Complete Josephus Cube networks via strongly Menger edge-connectivityThe Journal of Supercomputing10.1007/s11227-024-06564-181:1Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s11227-024-06564-1
Liu HZhang MYang W(2024)On modified l-embedded edge-connectivity of enhanced hypercubesThe Journal of Supercomputing10.1007/s11227-023-05770-780:8(10357-10369)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s11227-023-05770-7
Anselmo MCastiglione GFlores MGiammarresi DMadonia MMantaci S(2023)Hypercubes and Isometric Words Based on Swap and Mismatch DistanceDescriptional Complexity of Formal Systems10.1007/978-3-031-34326-1_2(21-35)Online publication date: 4-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-34326-1_2
Show More Cited By

Index Terms

Enhanced Hypercubes
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Interconnection architectures
      2. Multicore architectures

Recommendations

Diagnosability of Enhanced Hypercubes

An enhanced hypercube is obtained by adding 2/sup n-1/ more links to a regular hypercube of 2/sup n/ processors. It has been shown that enhanced hypercubes have very good improvements over regular hypercubes in many measurements such as mean internode ...
Fault-Tolerant Meshes and Hypercubes with Minimal Numbers of Spares

This paper presents several techniques for tolerating faults in d-dimensional mesh and hypercube architectures. The approach consists of adding spare processors and communication links so that the resulting architecture will contain a fault-free mesh or ...
The vulnerability of the diameter of the enhanced hypercubes

Concern about fault tolerance in the design of interconnection networks has raised interest in the study of graphs such that deleting some vertices increases the diameter only moderately. For an interconnection network G, the (1)-fault diameterD(G) is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 40, Issue 3

March 1991

133 pages

ISSN:0018-9340

Editor:
Earl Swartzlander
Univ. of Texas at Austin, Austin

Issue’s Table of Contents

Copyright © Copyright © 1991 IEEE. All Rights Reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 March 1991

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Huang ZYang YZhang MYang X(2025)Assessing reliability in Complete Josephus Cube networks via strongly Menger edge-connectivityThe Journal of Supercomputing10.1007/s11227-024-06564-181:1Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s11227-024-06564-1
Liu HZhang MYang W(2024)On modified l-embedded edge-connectivity of enhanced hypercubesThe Journal of Supercomputing10.1007/s11227-023-05770-780:8(10357-10369)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s11227-023-05770-7
Anselmo MCastiglione GFlores MGiammarresi DMadonia MMantaci S(2023)Hypercubes and Isometric Words Based on Swap and Mismatch DistanceDescriptional Complexity of Formal Systems10.1007/978-3-031-34326-1_2(21-35)Online publication date: 4-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-34326-1_2
Chen MHabib MLin C(2022)Diagnosability for a family of matching composition networksThe Journal of Supercomputing10.1007/s11227-022-04949-879:7(7584-7608)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s11227-022-04949-8
Qiao HMeng JSabir E(2022)The edge fault-tolerant spanning laceability of the enhanced hypercube networksThe Journal of Supercomputing10.1007/s11227-022-04896-479:6(6070-6086)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1007/s11227-022-04896-4
Zhao YLi XMa M(2022)Embedded connectivity of some BC networksThe Journal of Supercomputing10.1007/s11227-022-04522-378:14(16605-16618)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s11227-022-04522-3
Liu Y(2022)Routing and Wavelength Allotment for Exchanged Folded Hypercube Communications Embedded in Bus-Topology WDM Optical NetworksMobile Networks and Applications10.1007/s11036-020-01712-227:1(109-117)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1007/s11036-020-01712-2
Arockiaraj MAbraham JShalini A(2022)Node set optimization problem for complete Josephus cubesJournal of Combinatorial Optimization10.1007/s10878-019-00443-938:4(1180-1195)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1007/s10878-019-00443-9
Li XDu YFan Y(2021)Fault Tolerance of Optical Hypercube Interconnection Networks with r-Communication PatternWireless Communications & Mobile Computing10.1155/2021/53587602021Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1155/2021/5358760
Liu Y(2018)Routing and wavelength assignment for exchanged crossed cubes on ring-topology optical networksSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-018-3071-722:20(6693-6703)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s00500-018-3071-7
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents