Coarse-grained graph compilation for embedded multiprocessors

This work addresses the challenges of mapping imaging and computer vision applications to embedded multiprocessor systems. Even though there is an abundance of data parallelism available for typical algorithms in this application domain, it is far from trivial to exploit this parallelism because of complex interactions between different optimization techniques. Furthermore, a given optimal solution will only be optimal on a specific hardware platform. On different platforms, it will not only show inferior performance, but might in the worst case, if for example local memories are smaller, not be feasible at all. Thus, cumbersome retargeting is required every time a novel platform emerges. In this work, we propose a programming model that enables the programmer to specify imaging and vision applications as a graph of kernels, independent of hardware details and without already prescribing a schedule, iteration order or buffer sizes. The goal of this work is to provide a coarse-grained graph compiler that can map this application graph in an automated process to an embedded multi-core architecture with small and explicitly managed program and data memories without caches. The proposed graph compiler optimizes the makespan of the application under these constraints. We call our tool a coarse-grained graph compiler because it schedules kernels and allocates data buffers in a similar fashion that a regular compiler schedules individual instructions and allocates individual registers. The output of our tool is a C program that is subsequently compiled by a regular “fine-grained” C compiler. In our programming model, kernel implementations are separated from application implementations. This makes applications portable across different hardware platforms with a different number of processors and memory sizes. At the same time, the kernels are defined with a stable interface and thus become portable across applications such that they can already be implemented and optimized by the hardware vendor and shipped together with the SDK for the platform. We show that this programming model is feasible for a range of different imaging applications, including complex filters. Our proposed compiler optimizes given applications for differently configured hardware platforms and produces target-specific source code that has been adapted to the available compute resources, local memory sizes and available memory bandwidth of the target architecture. We use a newly developed form of dataflow graphs, an SDF variant with added actor thresholds, to model data dependencies. The compiler performs optimizations to minimize transfers of intermediate data to external memory. Program and data memories will be used more efficiently by constructing a data pipeline across multiple processors. Pipelining is supported also in presence of multiple inputs, outputs, diverging and converging data flow. Additionally, a mapping heuristic was developed that can reduce buffer copies and a scheduling heuristic that generates terse, periodic schedules for hardware with limited control resources. We further provide a generic, evolutionary graph-partitioning heuristic to partition directed graphs into blocks of nodes with no cyclic interconnections such that the blocks can be topologically sorted. The heuristic is used as a sub-step in our graph compiler to break large applications into smaller functions that do not overload the embedded memory. The graph compiler uses the techniques described above to generate an initial solution. It then analyzes this solution to check whether the performance can be further improved on the current hardware platform, for example because hardware resources are underutilized. It then uses a set of candidate generation rules to create novel solutions candidates that better utilize the hardware, for example by switching from pure pipeline parallelism to a mix of data and pipeline parallelism. We perform several experiments on complex imaging applications including the Local Laplacian filter. The results show that our graph compiler can adapt the given applications for a variety of different hardware platforms by using different methods to implement parallelized solutions until one is found that fits to the characteristics of the given hardware platform.