Abstract
For technological reasons, in a realistic parallel computer the processors have to communicate via a communication network with bounded degree. Thus the question for a “good” communication network comes up. In this paper we present such a network, a universal parallel computer (UPC) with the following properties:
-
(i)
It has optimal time-loss, namely O(log c) for simulating networks of degree c. (We also prove the lower bound Ω(log c) for the time-loss.)
-
(ii)
We introduce the broadcast-capability (how many processors can be reached by one processor in i steps?) and demonstrate its influence on the number of processors needed for a simulation of a network with n processors. E.g. for broadcast-capability O(c i) (e.g. networks with degree c), O(n 1+ε log n) processors are needed (ε>0 arbitrary) whereas O(n · polylog(n)) processors suffice for networks with polynomial broadcast-capability (e.g. k-dimensional grids).
-
(iii)
The UPC is potentially infinite and has multi-user capabilities, i.e., it can be arbitrarily partitioned into finite UPC's each with the above efficiency.
This construction generalizes a UPC described in [MadH2], where, given a fixed degree c, for each n a UPC M 0 is constructed which needs O(n 1+ε log n) processors to achieve constant time-loss for simulating networks with n processors and degree c.
Supported in part by DFG-grants Me 872/1–2 and We 1066/2-1
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
M. Ajtai, J. Komlós, E. Szemerédi, An O(n log n) sorting network, Proc. 15th ACM-STOC (1983) 1–9
M. Atallah, S. R. Kosaraju, Graph problems on a mesh-connected processor array, Proc. 14th ACM-STOC (1982) 345–353
K. E. Batcher, Sorting networks and their applications, AFIPS Conf. Proceedings 32 (1968), 307–314
Z. Galil, W.J. Paul, An efficient general-purpose parallel computer, JACM 30 (1983) 360–387
S. E. Hambrusch, VLSI algorithms for the connected component problem, SIAM Journal on Computing 12 (1983) 354–365
T. Leighton, Tight bounds on the complexity of parallel sorting, Proc. 16th ACM-STOC (1984) 71–80
F. Meyer auf der Heide, Efficiency of universal parallel computers, Acta Informatica 19 (1983) 269–296
F. Meyer auf der Heide, Efficient simulations among several models of parallel computers, SIAM Journal on Computing 15 (1986) 106–109
F. Meyer auf der Heide, Infinite cube-connected cycles, Information Processing Letters 16 (1983) 1–2
M. C. Pease, The indirect binary n-cube microprocessor array, IEEE Transactions on Computers C26–5 (1977) 458–473
F. Preparata, J. Vuillemin, The cube connected cycles: a versatile network for parallel computation, CACM 24 (1981) 300–309
J. H. Reif, L. G. Valiant, A logarithmic time sort for linear size networks, Proc. 15th ACM-STOC (1983) 10–16
H. Stone, Parallel processing with the perfect shuffle, IEEE Transactions on Computers C20-2 (1971) 153–161
R. Wanka, Über die Effizienz von Simulationen eingeschränkter Netzwerkklassen auf universellen parallelen Rechnern, Diplomarbeit, University of Dortmund, 1988
A. Waksman, A permuting network, JACM 15 (1968) 159–163
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1989 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Meyer auf der Heide, F., Wanka, R. (1989). Time-optimal simulations of networks by universal parallel computers. In: Monien, B., Cori, R. (eds) STACS 89. STACS 1989. Lecture Notes in Computer Science, vol 349. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0028978
Download citation
DOI: https://doi.org/10.1007/BFb0028978
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-50840-3
Online ISBN: 978-3-540-46098-5
eBook Packages: Springer Book Archive