article

Free access

A multiprocessor network suitable for single-chip VLSI implementation

Authors:

M. R. Samatham,

D. K. PradhanAuthors Info & Claims

ACM SIGARCH Computer Architecture News, Volume 12, Issue 3

Pages 328 - 339

https://doi.org/10.1145/773453.808202

Published: 01 January 1984 Publication History

Abstract

This paper presents a multiprocessor network architecture suitable for VLSI implementation. The proposed class of architectures is based on De Bruijn graphs which are distinct from the well-studied shuffle-exchange graphs. Compared to these latter De Bruijn graphs possess a smaller diameter and a greater fault-tolerance. The proposed architectures are shown to be suitable for efficient execution of parallel algorithms such as the N-point fast Fourier transform (FFT). It is shown that any VLSI layout of the proposed networks requires an area of atleast Ω(N²/logN), thus, providing a lower bound which is greater than that for shuffle-exchange graphs. Two procedures for laying out these networks on a VLSI chip are presented. The first procedure produces an O(N²/logN)-area layout and has a time complexity of O(N). The second procedure also produces an O(N²/logN)-area layout with good aspect ratio close to unity (for small N).

References

[1]

H. S. Stone, "Parallel processing with the perfect shuffle", IEEE Transactions on Computers, Vol. C-20, No. 2, pp. 153-161, February 1971.

[2]

T. Lang, "Interconnection between processing and memory modules using the shuffle-exchange network", IEEE Transactions on Computers, Vol. C-25, No. 1, pp. 55-66, January 1976.

[3]

D. S. Parker, "Notes on shuffle-exchange type switching networks", IEEE Transactions on Computers, Vol. C-29, No. 3, PP. 213-222, March 1980.

[4]

C. Mead and L. Conway, Introduction to VLSI systems, Addison-Wesley, Reading, Massachusetts, October 1980.

Digital Library

[5]

C. D. Thompson and H. T. Kung, "Sorting on a mesh-connected parallel computer", Communications of ACM, Vol. 20, pp. 263-271, 1977.

Digital Library

[6]

F. P. Preparata and J. E. Vuillemin, "The cube-connected-cycles: a versatile network for parallel computation", Proceedings of the 20th annual IEEE symposium on Foundations of Computer Science, pp. 140-147 October 1979.

Digital Library

[7]

W. E. Leland, "Density and Reliability of interconnection topologies for multicomputers," Ph.D. dissertation, University of Wisconsin, Madison, May 1982.

Digital Library

[8]

D. K. Pradhan and S. M. Reddy, "A fault-tolerant communication architecture for distributed systems", IEEE Transactions on Computers, Vol. C-31, No. 9, PP. 863-870, September 1982.

[9]

N. G. De Bruijn, "A combinatorial problem", Koninklijke Nederlands, Academe Van Wetenschappen, Proc. Vol. 49, part 20, pp. 758-764, 1946.

[10]

M. Imase and M. Itoh, "Design to minimize diameter on building-block networks", IEEE Transactions on Computers, Vol. C-30, No. 6, pp. 439-443, June 1981.

[11]

M. L. Schlumberger, "De Bruijn communications networks", Ph.D. dissertation, Department of computer science, Stanford University, 1974.

Digital Library

[12]

C. D. Thompson, "A complexity theory for VLSI", Ph.D. dissertation, Department of computer science, Carnegie-Mellon University, 1980.

Digital Library

[13]

C. Mead and M. Rem, "Cost performance of VLSI computing structures", IEEE Journal of Solid State Circuits, Vol. SC-14, No. 2, pp. 455-462, April 1979.

[14]

D. Hoey and C. E. Leiserson, "A layout for the shuffle-exchange network", Proceedings of the 1980 IEEE International conference on Parallel Processing, August 1980.

[15]

F. T. Leighton, "Layouts for the shuffle-exchange graph and lower bound techniques for VLSI", Ph.D. dissertation, Department of mathematics, Massachusetts Institute of Technology, 1981.

[16]

F. T. Leighton and G. L. Miller, "Optimal layouts for small shuffle-exchange graphs", Proceedings of the VLSI 81 International conference, Edinburgh, U.K., August 1981.

[17]

C. E. Leiserson, "Area efficient graph layouts(for VLSI)", 21st Annual Symposium on Foundations of Computer Science, IEEE Coputer society, October 1980.

[18]

C. E. Leiserson, "Area efficient VLSI computation", Ph.D. dissertation, Department of Computer Science, Carnegie-Mellon University, November 1980.

Digital Library

[19]

C. M. Bender and S. A. Orszag, Advanced Mathematical Methods for Scientists and Engineers, McGraw-Hill Book company, New York, 1978.

[20]

M. R. Garey and D. S. Johnson, Computers and Interactability-A guide to the theory of NP-Completeness, W. H. Freeman and Company, San Francisco, 1979.

Digital Library

[21]

D. K. Pradhan, "On a class of fault-tolerant multiprocessor network architectures", Proceedings of 3rd International conference on Distributed Processing, Miami, Florida, October 1982.

[22]

D. K. Pradhan, "Interconnection Topologies for fault-tolerant Parallel and Distributed Architectures", Proceedings of 10th International Conference on Parallel Processing, IEEE Computer Society Publications, pp. 238-242, August 1981.

[23]

L. N. Bhuyan, D. P. Agrawal, "Performance Analysis of FFT Algorithms on Multiprocessor Systems", IEEE Transactions on Software Engineering, Vol. SE-9, No. 4, pp. 512-521, July 1983.

Digital Library

Cited By

Zapata ERivera FBenavides ICarazo JPeskin R(1990)Multidimensional fast Fourier transform into SIMD hypercubesIEE Proceedings E Computers and Digital Techniques10.1049/ip-e.1990.0031137:4(253)Online publication date: 1990
https://doi.org/10.1049/ip-e.1990.0031
Tyszer J(1988)A Multiple Fault-Tolerant Processor Network Architecture for Pipeline ComputingIEEE Transactions on Computers10.1109/12.870737:11(1414-1418)Online publication date: 1-Nov-1988
https://dl.acm.org/doi/10.1109/12.8707
Pradhan D(1985)Dynamically Restructurable Fault-Tolerant Processor Network ArchitecturesIEEE Transactions on Computers10.1109/TC.1985.167658334:5(434-447)Online publication date: 1-May-1985
https://dl.acm.org/doi/10.1109/TC.1985.1676583
Show More Cited By

Index Terms

A multiprocessor network suitable for single-chip VLSI implementation

Recommendations

A multiprocessor network suitable for single-chip VLSI implementation
ISCA '84: Proceedings of the 11th annual international symposium on Computer architecture

This paper presents a multiprocessor network architecture suitable for VLSI implementation. The proposed class of architectures is based on De Bruijn graphs which are distinct from the well-studied shuffle-exchange graphs. Compared to these latter De ...
A Torus-Based Hierarchical Optical-Electronic Network-on-Chip for Multiprocessor System-on-Chip

Networks-on-chip (NoCs) are emerging as a key on-chip communication architecture for multiprocessor systems-on-chip (MPSoCs). Optical communication technologies are introduced to NoCs in order to empower ultra-high bandwidth with low power consumption. ...
3-D Mesh-Based Optical Network-on-Chip for Multiprocessor System-on-Chip

Optical networks-on-chip (ONoCs) are emerging communication architectures that can potentially offer ultrahigh communication bandwidth and low latency to multiprocessor systems-on-chip (MPSoCs). In addition to ONoC architectures, 3-D integrated ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGARCH Computer Architecture News

ACM SIGARCH Computer Architecture News Volume 12, Issue 3

June 1984

348 pages

ISSN:0163-5964

DOI:10.1145/773453

Issue’s Table of Contents

ISCA '84: Proceedings of the 11th annual international symposium on Computer architecture
January 1984
373 pages
ISBN:0818605383
DOI:10.1145/800015
Chairman:
Dharma P. Agrawal

Copyright © 1984 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1984

Published in SIGARCH Volume 12, Issue 3

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
414
Total Downloads

Downloads (Last 12 months)67
Downloads (Last 6 weeks)9

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zapata ERivera FBenavides ICarazo JPeskin R(1990)Multidimensional fast Fourier transform into SIMD hypercubesIEE Proceedings E Computers and Digital Techniques10.1049/ip-e.1990.0031137:4(253)Online publication date: 1990
https://doi.org/10.1049/ip-e.1990.0031
Tyszer J(1988)A Multiple Fault-Tolerant Processor Network Architecture for Pipeline ComputingIEEE Transactions on Computers10.1109/12.870737:11(1414-1418)Online publication date: 1-Nov-1988
https://dl.acm.org/doi/10.1109/12.8707
Pradhan D(1985)Dynamically Restructurable Fault-Tolerant Processor Network ArchitecturesIEEE Transactions on Computers10.1109/TC.1985.167658334:5(434-447)Online publication date: 1-May-1985
https://dl.acm.org/doi/10.1109/TC.1985.1676583
Ganesan Pradhan (1993)Optimal broadcasting in binary de Bruijn networks and hyper-deBruijn networksProceedings of the 1993 Seventh International Parallel Processing Symposium10.1109/IPPS.1993.262803(655-660)Online publication date: 13-Apr-1993
https://dl.acm.org/doi/10.1109/IPPS.1993.262803
Chen CAgrawal DBurke J(1993)dBCubeIEEE Transactions on Parallel and Distributed Systems10.1109/71.2501154:12(1332-1344)Online publication date: 1-Dec-1993
https://dl.acm.org/doi/10.1109/71.250115
Chienhua Chen Agrawal DBurke J(1991)A class of hierarchical networks for VLSI/WSI based multicomputers[1991] Proceedings. Fourth CSI/IEEE International Symposium on VLSI Design10.1109/ISVD.1991.185128(267-272)Online publication date: 1991
https://doi.org/10.1109/ISVD.1991.185128
Chen CAgrawal DBurke J(1991)Design and WSI layout for DBCube networks[1991] Proceedings, Advanced Computer Technology, Reliable Systems and Applications10.1109/CMPEUR.1991.257411(363-367)Online publication date: 1991
https://doi.org/10.1109/CMPEUR.1991.257411
Pradhan D(1990)Application specific VLSI architectures based on De Bruijn graphs[1990] Proceedings of the International Conference on Application Specific Array Processors10.1109/ASAP.1990.145498(628-640)Online publication date: 1990
https://doi.org/10.1109/ASAP.1990.145498
Zedan H(1990)Key references in distributed computer systems 1959–1989Distributed Computer Systems10.1016/B978-0-408-02938-4.50016-4(193-295)Online publication date: 1990
https://doi.org/10.1016/B978-0-408-02938-4.50016-4
Samatham MPradhan D(1989)The de Bruijn Multiprocessor NetworkIEEE Transactions on Computers10.1109/12.2114938:4(567-581)Online publication date: 1-Apr-1989
https://dl.acm.org/doi/10.1109/12.21149
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents