Adaptive Parallel Programs PDF Download

Future multicore processors will be heterogeneous, be increasingly less reliable, and operate in dynamically changing operating conditions. Such environments will result in a constantly varying pool of hardware resources which can complicate the programmer's task of efficiently exposing an application's parallelism onto these resources. Coupled with this complexity is the diverse set of performance objectives, such as latency, throughout, energy, power and resources, that users may desire. This dissertation proposes to automate the process of exposing an application's parallelism, in order to alleviate programmers from the burden of this complexity. It develops Varuna, a system that dynamically, continuously, rapidly and transparently adapts an application's parallelism to best match the instantaneous capabilities and availability of the hardware resources and the characteristics of the application, while optimizing different performance objectives. To facilitate rapid parallelism adaptation, this dissertation develops a holistic and resource-agnostic scalability model based on Amdahl's law. Varuna first employs the model to rapidly estimates changes in efficiency during an application's parallel execution. It then uses formulae, derived from the model, to instantaneously determine the optimum degree of parallelism (DoP) to employ for different performance objectives and automatically guides the execution to the computed DoP. In order for Varuna to transparently guide the application's parallel execution to the computed DoP, this dissertation proposes to employ a novel primitive called a virtual task (vtask). Vtasks decouple application-level parallelism from hardware parallelism. They are progress-aware entities and give Varuna the flexibility needed to transparently control an application's parallel execution, without hampering its forward progress. Varuna is programming model independent. It retains the existing programming abstractions and can be applied to both task-based and multithreaded shared memory parallel applications. Further, it requires no changes to the application or the Operating System, and can tackle arbitrary parallel applications that use standard APIs. This dissertation demonstrates Varuna for three different shared memory parallel programming APIs: Pthreads, Intel Thread Building Blocks (TBB), and Prometheus. This dissertation evaluates Varuna in three different execution environments, isolated, multiprogrammed and asymmetric, using unaltered C/C++ Pthreads, TBB and Prometheus applications from various standard benchmark suites, on three different real hardware platforms with different microarchitectural resource capabilities. Regardless of the execution environment, Varuna always outperformed the state-of-the-art approaches for the performance objectives considered.