Analysis of Overheads Analysis of parallel algorithms is distinctly different from that of sequential algorithms because of the presence of overheads, following from the need to coordinate parallel activity. Overheads are of two fundamentally different kinds. Explicit overheads result from the need to add additional code to a parallel algorithm to handle coordination matters such as forks and message sends. Implicit overheads arise from delays spent waiting on synchronization events, such as joins, to occur. Much of this research aims to quantify the effects of such overheads, and to understand how they depend on various parameters of the workload distribution.
X n be random variables, representing execution times of tasks.
Work aimed at understanding the behavior of both S n and M n for large n , even if the task times are dependent, forms a fundamental part of this research upon which all analysis is based. Scheduling and Sequencing Parallel performance issues occur at the operating systems level in the design of multiprocessor schedulers. The design and analysis of simple scheduling policies having guaranteed performance bounds is an important part of this research. New applications of stochastic ordering relations to prove optimality of static scheduling policies and to develop bounds for dynamic policies are being extended as part of this work.