Analysis, Modeling and Optimization of Multiprocessing Execution Time

A new approach is presented for the analytical modeling of the execution times of a partitioned program running on parallel processors of a multiprocessor or distributed computed system. The model represents the execution time of the individual processors as well as the aggregate system both in the deterministic and stochastic contexts. The analytical model encompasses a broader class of multiprocessing situations and formulates a mode accurate analytical representation of the execution times than has hitherto been presented in recent literature. The representation expresses the processor execution times in terms of the program module run times, the internal intermodule communication times, interprocessor (external) times and the number of modules assigned to each processor. A criterion is derived on the optimal assignment policy for minimizing execution time, or its statistical mean in the stochastic representation.