Optimal tradeoffs between size and slowdown for universal parallel networks

Wanka R, Meyer auf der Heide F, Storch M (1997)


Publication Language: English

Publication Status: Published

Publication Type: Journal article, Original article

Publication year: 1997

Journal

Publisher: Springer Verlag (Germany)

Book Volume: 30

Pages Range: 627-644

Journal Issue: 6

DOI: 10.1007/s002240000071

Abstract

A parallel processor network is called n-universal with slowdown s if it can simulate each computation of each constant-degree processor network with n processors with slowdown s. We prove the following lower bound tradeoff: for each constant-degree n-universal network of size m with slowdown s,m·s = Ω(n log m) holds. Our tradeoff holds for a very general model of simulations. It covers all previously considered models and all known techniques for simulations among networks. For m ≥ n, this improves a previous lower bound by a factor of log log n, proved for a weaker simulation model. For m ≥ n, this is the first nontrivial lower bound for this problem. In this case this lower bound is asymptotically tight.

Authors with CRIS profile

How to cite

APA:

Wanka, R., Meyer auf der Heide, F., & Storch, M. (1997). Optimal tradeoffs between size and slowdown for universal parallel networks. Theory of Computing Systems, 30(6), 627-644. https://doi.org/10.1007/s002240000071

MLA:

Wanka, Rolf, Friedhelm Meyer auf der Heide, and Martin Storch. "Optimal tradeoffs between size and slowdown for universal parallel networks." Theory of Computing Systems 30.6 (1997): 627-644.

BibTeX: Download