Efficient loop-level parallelism in Ada

Abstract

Parallelism in scientific applications can most often be found at the loop level. Although Ada supports parallelism via the task construct, its coarseness renders it unsuitable for this lightweight parallelism. In this work we propose Ada constructs to achieve efficient loop-level parallelism in ANSI-Ada. This is accomplished in two steps. First, we present an idiom that allows the specification of light-weight tasks. Second, we give an efficient implementation of this idiom that performs better than a standard Ada task. In addition, we present an idiom that makes the fetch and add synchronization primitive available at the Ada level. Our implementation of this idiom is more efficient in both time and space than previous results. In addition to providing universal synchronization, using fetch and add simplifies program analysis (e.g. proving the absence of race conditions in the implementation of a parallel algorithm). Since all of these idioms are written in standard Ada, they maintain the portability that is central to the mandated uses of the language.