Parallel patterns + macro data flow for multi-core programming

Abstract—Data flow techniques have been around since the early ’70s when they were used in compilers for sequential lan-guages. Shortly after their introduction they were also considered as a possible model for parallel computing, although the impact here was limited. Recently, however, data flow has been identified as a candidate for efficient implementation of various program-ming models on multi-core architectures. In most cases, however, the burden of determining data flow “macro ” instructions is left to the programmer, while the compiler/run time system manages only the efficient scheduling of these instructions. We discuss a structured parallel programming approach supporting automatic compilation of programs to macro data flow and we show experimental results demonstrating the feasibility of the approach and the efficiency of the resulting “object ” code on different classes of state-of-the-art multi-core architectures. The experimental results use different base mechanisms to implement the macro data flow run time support, from plain pthreads with condition variables to more modern and effective lock- and fence-free parallel frameworks. Experimental results comparing efficiency of the proposed approach with those achieved using other, more classical, parallel frameworks are also presented. Index Terms—macro data flow, structured programming, multi-core, shared memory, lock-free queues I