An optimal upper bound on the minimal completion time in distributed supercomputing
Lars Lundberg, Håkan Lennerstad · 1994
We first consider an MIMD multiprocessor configuration with n processors. A parallel program, consisting of n processes, is executed on this system—one process per processor. The program terminates when all processes are completed. Due to synchronizations, processes may be blocked waiting for events in other processes. Associated with the program is a parallel profile vector v¯, index i (1≤i≤n) in this vector indicates the percentage of the total execution time when i processes are executing.