L. Lundberg, K. Klonowska, M. Broberg, and H. Lennerstad (Sweden)
Performance, Multiprocessor, Distributed system, Optimalbound, Computer architecture.
Consider a parallel program with n processes and a syn chronization granularity z. Consider also two multiproces sors: a multiprocessor with q processors and run-time reallocation of processes to processors, and a multiproces sor with k processors and no run-time reallocation. There is an inter processor communication delay of t time units for the system with no run-time reallocation. In this paper we define a function g(n,k,q,t,z) such that the minimum completion time for all programs with n processes and a granularity z is at most g(n,k,q,t,z) times longer using the system with no reallocation and k processors compared to using the system with q processors and run-time realloca tion. We assume optimal allocation and scheduling of pro cesses to processors. The function g(n,k,q,t,z) is optimal in the sense that there is at least one program, with n pro cesses and a granularity z, such that the ratio is exactly g(n,k,q,t,z). We also validate our results using measure ments on distributed and multiprocessor Sun/Solaris envi ronments.
Important Links:
Go Back
