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
Publisher: Springer Verlag (Germany)
Book Volume: 30
Pages Range: 627-644
Journal Issue: 6
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.
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://dx.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