학술논문
Packet routing on square meshes with row and column buses
Document Type
Conference
Author
Source
Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing Parallel and Distributed Processing, 1991. Proceedings of the Third IEEE Symposium on. :834-837 1991
Subject
Language
Abstract
General point-to-point communication among processors in the classical two-dimensional n*n square mesh architecture necessarily takes at least 2n-2 time steps. The authors investigate the problem of routing arbitrary permutations on an enhanced square mesh with separate broadcast buses along each of its rows and columns. They prove that any packet routing algorithm on this mesh takes Theta (2n/3) time steps. Further, they demonstrate a simple algorithm which, for any chosen 2/n