The Fat-Pyramid: A Robust Network for Parallel Computation

Document Type

Conference Proceeding

Publication Date


Publication Title

Proceedings of the sixth MIT conference on Advanced research in VLSI




This paper shows that a fat-pyramid of area Theta(A) built from processors of size lg A requires only O(lg^2 A) slowdown in bit-times to simulate any network of area A under very general conditions. Specifically, there is no restriction on processor size (amount of attached memory) or number of processors in the competing network, nor is the assumption of unit wire delay required. This paper also derives upper bounds on the slowdown required by a fat-pyramid to simulate a network of larger area in the case of unit wire delay.

Creative Commons License

Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.

This document is currently not available here.