research-article

Performance Analysis of k-ary n-cube Interconnection Networks

Author:

William J. DallyAuthors Info & Claims

IEEE Transactions on Computers, Volume 39, Issue 6

Pages 775 - 785

https://doi.org/10.1109/12.53599

Published: 01 June 1990 Publication History

Publisher Site

Abstract

VLSI communication networks are wire-limited, i.e. the cost of a network is not a function of the number of switches required, but rather a function of the wiring density required to construct the network. Communication networks of varying dimensions are analyzed under the assumption of constant wire bisection. Expressions for the latency, average case throughput, and hot-spot throughput of k-ary n-cube networks with constant bisection that agree closely with experimental measurements are derived. It is shown that low-dimensional networks (e.g. tori) have lower latency and higher hot-spot throughput than high-dimensional networks (e.g. binary n-cubes) with the same bisection width.

References

[1]

{1} Ametek Corporation, Ametek 2010 product announcement, 1987.

Google Scholar

[2]

{2} K. E. Batcher, "Sorting networks and their applications," in Proc. AFIPS FJCC, vol. 32, 1968, pp. 307-314.

Google Scholar

[3]

{3} K. E. Batcher, "The Flip network in STARAN," in Proc. 1976 Int. Conf. Parallel Processing, pp. 65-71.

Google Scholar

[4]

{4} V. E. Benes, Mathematical Theory of Connecting Networks and Telephone Traffic. New York: Academic, 1965.

Google Scholar

[5]

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

Google Scholar

[6]

{6} S. Browning, "The tree machine: A highly concurrent computing environment," Dep. Comput. Sci., California Instit. Technol., Rep. 3760, 1980.

Google Scholar

[7]

{7} W. J. Dally, A VLSI Architecture for Concurrent Data Structures. Hingham, MA: Kluwer, 1987.

Digital Library

Google Scholar

[8]

{8} W. J. Dally and C. L. Seitz, "Deadlock-free message routing in multiprocessor interconnection networks," IEEE Trans. Comput., vol. C-36, no. 5, pp. 547-553, May 1987.

Digital Library

Google Scholar

[9]

{9} W. J. Dally and C. L. Seitz, "The torus routing chip," J. Distributed Syst., vol. 1, no. 3, pp. 187-196, 1986.

Crossref

Google Scholar

[10]

{10} W. J. Dally, "Wire efficient VLSI multiprocessor communication networks," in Proc. Stanford Conf. Advanced Res. VLSI, Losleben, Ed. Cambridge, MA: MIT Press, Mar. 1987, pp. 391-415.

Google Scholar

[11]

{11} W. J. Dally et al., "Architecture of a message-driven processor," in Proc. 14th ACM/IEEE Symp. Comput. Architecture, June 1987, pp. 189-196.

Digital Library

Google Scholar

[12]

{12} W. J. Dally and P. Song, "Design of a self-timed VLSI multicomputer communication controller," in Proc. IEEE Int. Conf. Comput. Design , 1987.

Google Scholar

[13]

{13} P. Kermani and L. Kleinrock, "Virtual cut-through: A new computer communication switching technique," Comput. Networks, vol. 3, pp. 267-286, 1979.

Google Scholar

[14]

{14} D. H. Lawrie, "Alignment and access of data in an array processor," IEEE Trans. Comput., vol. C-24, no. 12, pp. 1145-1155, Dec. 1975.

Google Scholar

[15]

{15} C. L. Leiserson, "Fat trees: Universal networks for hardware-efficient supercomputing," IEEE Trans. Comput., vol. C-34, no. 10, pp. 892-901, Oct. 1985.

Digital Library

Google Scholar

[16]

{16} C. A. Mead and L. A. Conway, Introduction to VLSI Systems. Reading, MA: Addison-Wesley, 1980.

Digital Library

Google Scholar

[17]

{17} M. C. Pease, III, "The indirect binary n-cube microprocessor array," IEEE Trans. Comput., vol. C-26, no. 5, pp. 458-473, May 1977.

Google Scholar

[18]

{18} G. F. Pfister and V. A. Norton, "Hot spot contention and combining in multistage interconnection networks," IEEE Trans. Comput., vol. C-34, no. 10, pp. 943-948, Oct. 1985.

Google Scholar

[19]

{19} C. L. Seitz, "Concurrent VLSI architectures," IEEE Trans. Comput. , vol. C-33, no. 12, pp. 1247-1265, Dec. 1984.

Google Scholar

[20]

{20} C. L. Seitz et al., "The hypercube communications chip," Dep. Comput. Sci., California Inst. Technol., Display File 5182:DF:85, Mar. 1985.

Google Scholar

[21]

{21} C. H. Sequin, "Single chip computers, The new VLSI building block," in Proc. Caltech Conf. VLSI, C. L. Seitz, Ed., Jan. 1979, pp. 435-452.

Google Scholar

[22]

{22} H. J. Siegel, "Interconnection network for SIMD machines," IEEE Comput. Mag., vol. 12, no. 6, pp. 57-65, June 1979.

Digital Library

Google Scholar

[23]

{23} H. S. Stone, "Parallel processing with the perfect shuffle," IEEE Trans. Comput., vol. C-20, no. 2, pp. 153-161, Feb. 1971.

Google Scholar

[24]

{24} H. Sullivan and T. R. Bashkow, "A large scale homogeneous machine," in Proc. 4th Ann. Symp. Comput. Architecture, 1977, pp. 105-124.

Digital Library

Google Scholar

[25]

{25} A. S. Tanenbaum, Computer Networks. Englewood Cliffs, NJ: Prentice-Hall, 1981.

Digital Library

Google Scholar

[26]

{26} C. D. Thompson, "A complexity theory of VLSI," Dep. Comput. Sci., Carnegie-Mellon Univ., Tech. Rep. CMU-CS-80-140, Aug. 1980.

Google Scholar

Cited By

View all

Zhuang HLi XChang JLiu X(2024)Paired 2-disjoint path covers of k-ary n-cubes under the partitioned edge fault modelJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104887190:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.jpdc.2024.104887
Li SLi XMa M(2024)Reliability assessment for k-ary n-cubes with faulty edgesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104886190:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.jpdc.2024.104886
Wang NMeng JTian Y(2024)Reliability analyses of regular graphs based on edge-structure connectivityDiscrete Applied Mathematics10.1016/j.dam.2024.06.023356:C(329-342)Online publication date: 30-Oct-2024
https://dl.acm.org/doi/10.1016/j.dam.2024.06.023
Show More Cited By

Index Terms

Performance Analysis of k-ary n-cube Interconnection Networks

Recommendations

On the Performance of k-ary n-cube Interconnection Networks
Performance Analysis of Finite Buffered Multistage Interconnection Networks

Multistage interconnection networks (MIN's) have a number of applications in the areas of computer and communication. While several analytical models have been proposed for the performance evaluation of MIN's, they are either not very accurate or too ...
Performance Analysis of Multistage Interconnection Networks with Hierarchical Requesting Model

Analyzes the performance of the multistage interconnection networks (MINs) for interconnecting N processors or N processors to N commonly shared memory modules in a multiprocessor system. A general model, called hierarchical requesting model, has been ...

Reviews

Reviewer: Roger Raymond Schell

Dally presents a valuable set of basic design considerations for the VLSI implementations of concurrent computers. He analyzes the theoretical impact of the physical constraints of VLSI systems, especially limited wire density, for interconnection networks. Based on reasonable assumptions and approximations, he derives detailed mathematical expressions for estimating the performance of a range of network alternatives. Both the average network latency and the throughput are estimated, and several interesting results are presented graphically. The primary conclusion is that, with VLSI constraints, networks with fewer wide channels provide lower latency and higher throughput than those with a larger number of narrow channels. The paper seems intended for readers with research background and interests who are reasonably conversant with the issues and terminology of VLSI communications networks. The needed definitions are often terse and in some cases only implicit, although Dally provides a relevant bibliography. The reader is left with the sense that the author is disproportionately emphasizing those factors that support his primary conclusions. His reasoning is carefully presented, however, and the mathematics, which is key to the paper, is accurate and precise without excessive detail or length. Overall, the paper is readable and informative.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

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 39, Issue 6

June 1990

133 pages

ISSN:0018-9340

Editor:
Ming T. Liu
Ohio State Univ., Columbus

Issue’s Table of Contents

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 June 1990

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

286
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhuang HLi XChang JLiu X(2024)Paired 2-disjoint path covers of k-ary n-cubes under the partitioned edge fault modelJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104887190:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.jpdc.2024.104887
Li SLi XMa M(2024)Reliability assessment for k-ary n-cubes with faulty edgesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104886190:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.jpdc.2024.104886
Wang NMeng JTian Y(2024)Reliability analyses of regular graphs based on edge-structure connectivityDiscrete Applied Mathematics10.1016/j.dam.2024.06.023356:C(329-342)Online publication date: 30-Oct-2024
https://dl.acm.org/doi/10.1016/j.dam.2024.06.023
Zhao YLi XLi JMa M(2024)Reliability of m-ary n-dimensional hypercubes under embedded restrictionDiscrete Applied Mathematics10.1016/j.dam.2024.02.016349:C(182-189)Online publication date: 31-May-2024
https://dl.acm.org/doi/10.1016/j.dam.2024.02.016
Li WLin LZhang ZHuang S(2023)The family of generalized variational network of cube-connected cyclesTheoretical Computer Science10.1016/j.tcs.2022.12.022944:COnline publication date: 25-Jan-2023
https://dl.acm.org/doi/10.1016/j.tcs.2022.12.022
Sun XFan JCheng BWang Y(2023)The t/m-diagnosis strategy of augmented k-ary n-cubesTheoretical Computer Science10.1016/j.tcs.2022.12.021945:COnline publication date: 4-Feb-2023
https://dl.acm.org/doi/10.1016/j.tcs.2022.12.021
Sun XFan JSabir ECheng BYu J(2023)Reliability of augmented k-ary n-cubes under the extra connectivity conditionThe Journal of Supercomputing10.1007/s11227-023-05141-279:12(13641-13669)Online publication date: 28-Mar-2023
https://dl.acm.org/doi/10.1007/s11227-023-05141-2
Varanasi LSrinivasarao B(2023)Design and evaluation of an energy efficient DiamondMesh topology for on-chip interconnection networksDesign Automation for Embedded Systems10.1007/s10617-022-09266-026:3-4(161-187)Online publication date: 2-Jan-2023
https://dl.acm.org/doi/10.1007/s10617-022-09266-0
Anselmo MFlores MMadonia M(2022)On k-ary n-cubes and isometric wordsTheoretical Computer Science10.1016/j.tcs.2022.10.007938:C(50-64)Online publication date: 26-Nov-2022
https://dl.acm.org/doi/10.1016/j.tcs.2022.10.007
Huang XF. Ramos ADeng Y(2022)Optimal circulant graphs as low-latency network topologiesThe Journal of Supercomputing10.1007/s11227-022-04396-578:11(13491-13510)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s11227-022-04396-5
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

On the Performance of k-ary n-cube Interconnection Networks

Performance Analysis of Finite Buffered Multistage Interconnection Networks

Performance Analysis of Multistage Interconnection Networks with Hierarchical Requesting Model

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations