Downey's main research area is probabilistic analysis of algorithms and systems, with particular emphasis on modeling the performance of parallel algorithms. These areas are described in detail below. The goal of this research project is the development of analytic methods to evaluate the performance of parallel asynchronous algorithms and systems. In order to understand the origins and effects of overheads in parallel computation, such as synchronization delays, methods focus on probabilistic models of workloads and task processing times. 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.