research-article

The Twisted N-Cube with Application to Multiprocessing

Authors:

Abdol-Hossein Esfahanian,

Lionel M. Ni,

Bruce E. SaganAuthors Info & Claims

IEEE Transactions on Computers, Volume 40, Issue 1

Pages 88 - 93

https://doi.org/10.1109/12.67323

Published: 01 January 1991 Publication History

Publisher Site

Abstract

It is shown that by exchanging any two independent edges in any shortest cycle of the n-cube (n

References

[1]

{1} J. R. Armstrong and F. G. Gray, "Fault diagnosis in a Boolean n -cube array of microprocessors," IEEE Trans. Comput. , vol. C-30, no. 8, pp. 587-590, Aug. 1981.

Google Scholar

[2]

{2} H.-J. Bandelt and H. M. Mulder, "Infinite median graphs, (0,2)-graphs, and hypercubes," J. Graph Theory , vol. 7, pp. 487-497, 1983.

Crossref

Google Scholar

[3]

{3} S. N. Bhatt and C. F. Ipsen, "How to embed trees in hypercubes," Res. Rep. YALEU/DCS/RR-443, Dep. Comput. Sci., Yale Univ., Dec. 1985.

Google Scholar

[4]

{4} J. E. Brandenburg and D. S. Scott, "Embeddings of communication trees and grids into hypercubes," Tech. Rep., Intel Scientific Computers, 1985.

Google Scholar

[5]

{5} T. F. Chan and Y. Saad, "Multigrid algorithms on the hypercube multiprocessor," IEEE Trans. Comput. , vol. C-35, no. 11, pp. 969-977, Nov. 1986.

Crossref

Google Scholar

[6]

{6} W. J. Dally, "Performance analysis of k -ary n -cube interconnection networks," IEEE Trans. Comput. , pp. 775-785, June 1990.

Digital Library

Google Scholar

[7]

{7} E. Dekel and S. Sahni, "Binary trees and parallel scheduling algorithms," IEEE Trans. Comput. , pp. 307-312, Mar. 1983.

Digital Library

Google Scholar

[8]

{8} P. Erdos and J. Spencer, "Evolution of the n -cube," J. Comput. Math. Appl. , vol. 5, pp. 33-39, 1979.

Crossref

Google Scholar

[9]

{9} A. H. Esfahanian, "Generalized measures of fault-tolerance with application to n -cube networks," IEEE Trans. Comput. , to be published.

Crossref

Google Scholar

[10]

{10} E. T. Fathi and M. Krieger, "Multiple microprocessor systems: What, why, and when," IEEE Comput. Mag. , vol. 16, pp. 23-35, Mar. 1983.

Digital Library

Google Scholar

[11]

{11} S. Foldes, "A characterization of hypercubes," J. Discrete Math. , vol. 17, pp. 155-159, 1977.

Crossref

Google Scholar

[12]

{12} D. C. Grunwald and D. A. Reed, "Benchmarking hypercube hardware and software," Tech. Rep. UIUCDCS-R-86-1303, Dep. Comput. Sci., Univ. of Illinois at Urbana-Champaign, 1986.

Google Scholar

[13]

{13} D. C. Grunwald and D. A. Reed, "Networks for parallel processors: Measurements and prognostications," in Proc. Third Conf. Hypercube Concurrent Comput. Appl. , vol. I, 1988, pp. 610-619.

Digital Library

Google Scholar

[14]

{14} J. L. Gustafson, "Increasing hypercube communication on low-dimensional problems," Hypercube Multiprocessors 1987 , SIAM, pp. 244-250, 1987.

Google Scholar

[15]

{15} F. Harary, Graph Theory . Reading, MA: Addison-Wesley, 1972.

Google Scholar

[16]

{16} S. Hart, "A note on the edges of the n -cube," J. Discrete Math. , vol. 14, pp. 157-163, 1976.

Digital Library

Google Scholar

[17]

{17} S. Hedetniemi, "On classes of graphs defined by special cutsets of lines," The Many Facets of Graph Theory , Lecture Notes in Mathematics, vol. 110, Springer-Verlag, 1969, pp. 171-189.

Crossref

Google Scholar

[18]

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

Google Scholar

[19]

{19} K. Hwang and F. A. Briggs, Computer Architecture and Parallel Processing . New York: McGraw-Hill, 1984.

Digital Library

Google Scholar

[20]

{20} K. Hwang and J. Ghosh, "Hypernet: A communication-efficient architecture for constructing massively parallel computers," IEEE Trans. Comput. , vol. C-36, no. 12, pp. 1450-1467, Dec. 1987.

Crossref

Google Scholar

[21]

{21} J. C. Kuhl, "Fault diagnosis in computing networks," Tech. Rep., Dep. Elec. Comput. Eng., Univ. of Iowa, Iowa City, Iowa, 1980.

Google Scholar

[22]

{22} Y. Lan, A. H. Esfahanian, and L. M. Ni, "Multicast in hypercube multiprocessors," J. Parallel Distributed Comput. , pp. 30-41, Jan. 1990.

Digital Library

Google Scholar

[23]

{23} M. Mulder, " n -cube and median graphs," J. Graph Theory , vol. 4, pp. 107-110, 1980.

Crossref

Google Scholar

[24]

{24} D. K. Pradhan, "Interconnection topologies for fault-tolerant parallel and distributed architectures," in Proc. 10th Int. Conf. Parallel Processing , Aug. 1981, p. 238-242.

Google Scholar

[25]

{25} L. N. Praha, "On cubes and dichotomic trees," Casopis Pro Pestovani Matematiky , roc. 99, 1974.

Google Scholar

[26]

{26} J. C. Peterson, J. O. Tuazon, D. Lieberman, and M. Pniel, "The Mark III hypercube-ensemble concurrent computer," in Proc. 1985 Int. Conf. Parallel Processing , Aug. 1985, pp. 71-73.

Google Scholar

[27]

{27} Y. Saad and M. H. Schultz, "Topological properties of hypercubes," Tech. Rep., YALEU/DCS/RR-389, Dep. Comput. Sci., Yale Univ., June 1985.

Google Scholar

[28]

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

Digital Library

Google Scholar

[29]

{29} K. N. Venkataraman, G. Cybenko, and D. W. Krumme, "Hypercube embedding is NP-complete," Hypercube Multiprocessor 1986 , SIAM, SIAM, Philadelphia, PA, pp. 148-157, 1986.

Google Scholar

Cited By

View all

Wang DZhao L(2023)The twisted-cube connected networksJournal of Computer Science and Technology10.1007/BF0294652614:2(181-187)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF02946526
He SHao RCheng E(2018)Strongly Menger-edge-connectedness and strongly Menger-vertex-connectedness of regular networksTheoretical Computer Science10.1016/j.tcs.2018.04.001731:C(50-67)Online publication date: 30-Jun-2018
https://dl.acm.org/doi/10.1016/j.tcs.2018.04.001
Zhang ZDeng YMin GXie JHuang S(2017)ExCCC-DCNIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2016.260942828:4(1046-1060)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TPDS.2016.2609428
Show More Cited By

Index Terms

The Twisted N-Cube with Application to Multiprocessing
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Interconnection architectures
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Paths and connectivity problems
      2. Trees

Recommendations

Fault-tolerant graphs for hypercubes and tori
HICSS '95: Proceedings of the 28th Hawaii International Conference on System Sciences

Motivated by the design of fault-tolerant multiprocessor interconnection networks the paper considers the following problem: given a positive integer t and graph H, construct a graph G from H by adding a minimum number /spl Delta/(t,H) of edges such ...
A New Graph Approach to Minimizing Processor Fragmentation in Hypercube Multiprocessors

The authors propose a new approach for subcube and noncubic processor allocations forhypercube multiprocessors. The main idea is to represent available processors in thesystem by means of a prime cube graph (PC-graph). The PC-graph maintains theinter-...
On Subgraphs in Distance-Regular Graphs

Terwilliger [15] has given the diameter bound d ≤ (s − 1)(k − 1) + 1 for distance-regular graphs with girth 2s and valency k. We show that the only distance-regular graphs with even girth which reach this bound are the hypercubes and the doubled Odd ...

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 1

January 1991

125 pages

ISSN:0018-9340

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

Issue’s Table of Contents

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 January 1991

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wang DZhao L(2023)The twisted-cube connected networksJournal of Computer Science and Technology10.1007/BF0294652614:2(181-187)Online publication date: 22-Mar-2023
https://dl.acm.org/doi/10.1007/BF02946526
He SHao RCheng E(2018)Strongly Menger-edge-connectedness and strongly Menger-vertex-connectedness of regular networksTheoretical Computer Science10.1016/j.tcs.2018.04.001731:C(50-67)Online publication date: 30-Jun-2018
https://dl.acm.org/doi/10.1016/j.tcs.2018.04.001
Zhang ZDeng YMin GXie JHuang S(2017)ExCCC-DCNIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2016.260942828:4(1046-1060)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TPDS.2016.2609428
Cheng D(2017)Cycles embedding in folded hypercubes under the conditional fault modelDiscrete Applied Mathematics10.1016/j.dam.2017.02.020224:C(60-68)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1016/j.dam.2017.02.020
Kuo CCheng Y(2017)Cycles embedding in folded hypercubes with conditionally faulty verticesDiscrete Applied Mathematics10.1016/j.dam.2016.12.008220:C(55-59)Online publication date: 31-Mar-2017
https://dl.acm.org/doi/10.1016/j.dam.2016.12.008
Zhu X(2017)A Hypercube Variant with Small DiameterJournal of Graph Theory10.1002/jgt.2209685:3(651-660)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1002/jgt.22096
Kuo CStewart I(2016)Edge-pancyclicity and edge-bipancyclicity of faulty folded hypercubesTheoretical Computer Science10.1016/j.tcs.2016.02.029627:C(102-106)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.1016/j.tcs.2016.02.029
Kuo C(2016)Vertex-fault-tolerant cycles embedding in 4-conditionally faulty folded hypercubesDiscrete Applied Mathematics10.1016/j.dam.2016.01.002205:C(80-85)Online publication date: 31-May-2016
https://dl.acm.org/doi/10.1016/j.dam.2016.01.002
Wang XLiang JQi DLin W(2016)The twisted crossed cubeConcurrency and Computation: Practice & Experience10.1002/cpe.370728:5(1507-1526)Online publication date: 10-Apr-2016
https://dl.acm.org/doi/10.1002/cpe.3707
Kuo C(2015)Pancyclicity and bipancyclicity of folded hypercubes with both vertex and edge faultsTheoretical Computer Science10.1016/j.tcs.2015.08.018602:C(125-131)Online publication date: 18-Oct-2015
https://dl.acm.org/doi/10.1016/j.tcs.2015.08.018
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Fault-tolerant graphs for hypercubes and tori

A New Graph Approach to Minimizing Processor Fragmentation in Hypercube Multiprocessors

On Subgraphs in Distance-Regular Graphs

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations