State access patterns in tree structured parallel computations

Pattern-based frameworks for parallel programming provide a set of parallel patterns that solve recurrent problems. Typically these patterns are studied and implemented in their basic stateless form. In our work we classify and describe a set of access patterns for data structures that constitutes the shared state in tree structured parallel computations. These state management patterns can be composed with the computational ones to help the application programmer to abstract from the state declaration and access schedule issues related to the concurrent execution of parallel activities. We analyse the main properties of the computational structure and we present a general characterization of four state access patterns, according to the extent and way in which the state resource is structured and accessed. We study the parallel opportunities of the introduction in the computational pattern at hand of each one of the proposed state patterns, discussing possible implementation and synchronization schemes. We propose and develop a generic C++ parallel interface with stateful variants. Keeping the focus on the extracted properties for the computational structure and for the state management, we identify a comprehensive set of synthetic applications and we run them to study the effects of their potential and meaningful combinations. The experimental implementation and tests, performed on three state-of-the-art shared memory multicore architectures, assess the applicability and efficiency of the proposed approach in the context of tree structured parallel computations