high performance computing on graphics processing units: hgpu.org

This thesis describes and analyzes the automatic generation of threads from a sequential MiniC program by translating the program to an equivalent dataflow graph and partitioning this dataflow graph. These threads are generated through different graph partitionings, including splitting the graph into its single nodes and calculating a minimum vertex-disjoint cover. The threads can be generated for different targets, namely a single-threaded C++ application, and an application parallelized with either OpenMP or OpenCL. Because the paths calculated from partitioning the graph may have deadlocks, those need to be resolved before generating an execution order respecting the data dependencies of adjacent paths. Two different methods to resolve deadlocks, one joining different paths and one splitting them, are presented. The aforementioned methods and targets are benchmarked individually to identify the best scheduling resulting in the best performance. Overall, the thesis shall develop, implement and evaluate approaches to generate threads from dataflow graphs to increase the performance by a static scheduling/compilation of the parallel operations of a sequential program.