Reducing task creation and termination overhead in explicitly parallel programs

There has been a proliferation of task-parallel programming sys-tems to address the requirements of multicore programmers. Cur-rent production task-parallel systems include Cilk++, Intel Thread-ing Building Blocks, Java Concurrency,.Net Task Parallel Library, OpenMP 3.0, and current research task-parallel languages include Cilk, Chapel, Fortress, X10, and Habanero-Java (HJ). It is desir-able for the programmer to express all the parallelism intrinsic to their algorithm in their code for forward scalability and portability, but the overhead incurred by doing so can be prohibitively large in today’s systems. In this paper, we address the problem of reducing the total amount of overhead incurred by a program due to exces-sive task creation and termination. We introduce a transformation framework to optimize task-parallel programs with finish, forall and next statements. Our approach includes elimination of redun