Optimal tradeoffs between size and slowdown for universal parallel networks

Beitrag in einer Fachzeitschrift
(Originalarbeit)


Details zur Publikation

Autor(en): Wanka R, Meyer auf der Heide F, Storch M
Zeitschrift: Theory of Computing Systems
Verlag: Springer Verlag (Germany)
Jahr der Veröffentlichung: 1997
Band: 30
Heftnummer: 6
Seitenbereich: 627-644
ISSN: 1432-4350
Sprache: Englisch


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.



FAU-Autoren / FAU-Herausgeber

Wanka, Rolf Prof. Dr.
Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung)


Zitierweisen

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: 

Zuletzt aktualisiert 2018-11-08 um 02:16