Optimal Trade-Offs Between Size and Slowdown for Universal Parallel Networks
| Title | Optimal Trade-Offs Between Size and Slowdown for Universal Parallel Networks |
| Publication Type | Technical Report |
| Year of Publication | 1996 |
| Authors | der Heide, F. Meyer auf, Storch M., & Wanka R. |
| Other Numbers | 1061 |
| Abstract | A parallel processor network is called n-universal with slowdowns, if it can simulate each computation of each constant-degree processor network with n processors with slowdown s. We prove the following lower bound trade-off: For each constant-degree n-universal network of size m with slowdown s, m*s = ?(n log m) holds. Our trade-off 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 non-trivial lower bound for this problem. In this case, this lower bound is asymptotically tight. |
| URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1996/tr-96-052.pdf |
| Bibliographic Notes | ICSI Technical Report TR-96-052 |
| Abbreviated Authors | F. Meyer auf der Heide, M. Storch, and R. Wanka |
| ICSI Publication Type | Technical Report |