On new Classes of Multistage Interconnection Networks
Abstract
In this work a new generalized model for Multistage lnterconnection Networks (MINs) is proposed, extending the classes of existing MINs, such as SW- and CC-banyans. By introducing a labelling scheme for nodes in the network, a connection formula is established that makes it possible to describe an enormous number of new subclasses, extending substantially the choice of alternative topologies. To give a flavor of the great variety and advantage of some subclasses, their average distance is computed for networks of given size.
References
K. E. Batcher, "The Flip Network in STARAN," Proceedings of the 1976 International Conference on Parallel Processing, pp 65-71.
V. Cherkassky and M. Malek, "Analysis of CC-Banyan Networks," Proceedings of the 1986 International Conference on Parallel Processing, pp. 115-118.
J. de Melo and R.M. Jenevein, "SK-Banyans: A Unified Class of Banyan Networks," Proceedings of the 1986 International Conference on Parallel Processing, pp. 100-107.
Julio C. D. de Melo, A Unified Theory of Banyan Networks, Ph.D. Dissertation, University of Texas at Austin, 1989.
M. A. Franklin, "VLSI Performance Comparison of Banyan and Crossbar Communication Networks," IEEE Transactions on Computers, Vol. C-30, No. 4, April 1981, pp. 283-290.
L. R. Goke and G. J. Lipovski, "Banyan Networks for Partitioning Multiprocessor Systems," Proceedings of the First Annual Symposium on Computer Architecture, 1973, pp. 21-28.
R. M. Jenevein, D. Degroot and G. J. Lipovski, "A Hardware Support Mechanism for Scheduling Resources in a Parallel Machine Environment," Proceedings of the 8th. Annual International Symposium on Computer Architecture, May 1981, pp. 57-66.
D. H. Lawrie, "Access and Alignment of Data in an Array Processor," IEEE Transactions on Computers, Vol. C-24, No. 12, December 1975, pp. 1145-1155.
G. J. Lipovski and M. Malek, Parallel Computing, Theory and Comparisons, John Wiley & Sons, 1987.
B. L. Menezes and R.M. Jenevein, "KYKLOS : A Linear Growth Fault-tolerant Interconnection Network," Proceedings of the 14th. International Conference on Parallel Processing, 1985, pp. 498-502.
E. Opper, Fault-Diagnosis of Banyan Networks, Ph.D. Dissertation, University of Texas at Austin, 1984.
J. H. Patel, "Performance of Processor-Memory Interconnections for Multiprocessors," IEEE Transactions on Computers, Vol. C-30, No. 10, October 1980, pp. 771-780.
M. C. Pease, "The Indirect Binary n-Cube Microprocessor Array," IEEE Transactions on Computers, Vol. C-26, No. 5, May 1977, pp. 458-473.
U.V. Premkumar, A Theoretical Basis for the Analysis and Partitioning of Regular SW-Banyans, Ph.D. Dissertation, University of Texas at Austin, August 1981.
C. Wu and T. Feng, "On a Class of Multistage Interconnection Networks," IEEE Transactions on Computers, Vol C-29, No. 8, August.1980, pp. 694-702.
V. Cherkassky and M. Malek, "Analysis of CC-Banyan Networks," Proceedings of the 1986 International Conference on Parallel Processing, pp. 115-118.
J. de Melo and R.M. Jenevein, "SK-Banyans: A Unified Class of Banyan Networks," Proceedings of the 1986 International Conference on Parallel Processing, pp. 100-107.
Julio C. D. de Melo, A Unified Theory of Banyan Networks, Ph.D. Dissertation, University of Texas at Austin, 1989.
M. A. Franklin, "VLSI Performance Comparison of Banyan and Crossbar Communication Networks," IEEE Transactions on Computers, Vol. C-30, No. 4, April 1981, pp. 283-290.
L. R. Goke and G. J. Lipovski, "Banyan Networks for Partitioning Multiprocessor Systems," Proceedings of the First Annual Symposium on Computer Architecture, 1973, pp. 21-28.
R. M. Jenevein, D. Degroot and G. J. Lipovski, "A Hardware Support Mechanism for Scheduling Resources in a Parallel Machine Environment," Proceedings of the 8th. Annual International Symposium on Computer Architecture, May 1981, pp. 57-66.
D. H. Lawrie, "Access and Alignment of Data in an Array Processor," IEEE Transactions on Computers, Vol. C-24, No. 12, December 1975, pp. 1145-1155.
G. J. Lipovski and M. Malek, Parallel Computing, Theory and Comparisons, John Wiley & Sons, 1987.
B. L. Menezes and R.M. Jenevein, "KYKLOS : A Linear Growth Fault-tolerant Interconnection Network," Proceedings of the 14th. International Conference on Parallel Processing, 1985, pp. 498-502.
E. Opper, Fault-Diagnosis of Banyan Networks, Ph.D. Dissertation, University of Texas at Austin, 1984.
J. H. Patel, "Performance of Processor-Memory Interconnections for Multiprocessors," IEEE Transactions on Computers, Vol. C-30, No. 10, October 1980, pp. 771-780.
M. C. Pease, "The Indirect Binary n-Cube Microprocessor Array," IEEE Transactions on Computers, Vol. C-26, No. 5, May 1977, pp. 458-473.
U.V. Premkumar, A Theoretical Basis for the Analysis and Partitioning of Regular SW-Banyans, Ph.D. Dissertation, University of Texas at Austin, August 1981.
C. Wu and T. Feng, "On a Class of Multistage Interconnection Networks," IEEE Transactions on Computers, Vol C-29, No. 8, August.1980, pp. 694-702.
Published
1992-10-26
How to Cite
MELO, Julio C. D. de; JENEVEIN, Roy M..
On new Classes of Multistage Interconnection Networks. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 4. , 1992, São Paulo/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1992
.
p. 177-193.
DOI: https://doi.org/10.5753/sbac-pad.1992.22710.
