Document Type

Article

Publication Date

12-1994

Publication Title

IEEE Trans. Computers

Volume

43

Issue

12

Pages

1358-1364

Publisher Name

IEEE Computer Society

Abstract

This paper shows that a fat-pyramid of area Θ(A) requires only O(log A) slowdown to simulate any competing network of area A under very general conditions. The result holds regardless of the processor size (amount of attached memory) and number of processors in the competing networks as long as the limitation on total area is met. Furthermore, the result is valid regardless of the relationship between wire length and wire delay. We especially focus on elimination of the common simplifying assumption that unit time suffices to traverse a wire regardless of its length, since the assumption becomes more and more untenable as the size of parallel systems increases. This paper concentrates on simulation using transmission lines (wires along which bits can be pipelined) with the message routing schedule set up off line, but it also discusses the extension to on-line simulation. This paper also examines the capabilities of a fat-pyramid when matched against a substantially larger network and points out the surprising difficulty of doing such a comparison without the unit wire delay assumption.

Comments

Author Posting. © IEEE, 1994. This article is posted here by permission of IEEE for personal use, not for redistribution. The article was published in IEEE Trans. Computers, Volume 43, Issue 12, December 1994, http://dx.doi.org/10.1109/12.338095

This is a revised version of the conference paper that can be found at http://ecommons.luc.edu/cs_facpubs/116 (along with presentation slides).

Creative Commons License

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

Download

Share

COinS