Computational Properties of Mesh Connected Trees: Versatile Architectures for Parallel Computation

Recently, the mesh connected trees (MCT) network has been proposed as a possible architecture for parallel computers. MCT networks are obtained by combining complete binary trees using the cross product operation. This paper focuses on structural, embedding, routing, and layout properties of the MCT networks. We show that MCT networks are computationally more powerful than grids and complete binary trees, and at least as powerful as meshes of trees (MOT). Analysis of VLSI complexity shows thai the additional power is obtained without asymptotically increasing the layout area with respect to the grid of at least 3 dimensions or to the MOT of any number of dimensions. A variation of the basic architecture with same maximum vertex degree and same asymptotic area complexity is also investigated. This variation contains the torus as a subgraph as well as the MOT, further increasing the computational power of the basic architecture. These results suggest that the basic MCT network and its variant are suitable architectures for a large class of massively parallel computations.