Polyhedral Representation of Dataflow Programs

点击翻译按钮获取中文摘要

Parallel programming has always been significantly harder than programming for a sequential (single core) computer, and this can severely impacting programmer productivity. Computer hardware has also become increasingly complex, and nowadays computers, from hand-held devices to supercomputers, consist of a variety of heterogeneous, programmable devices, including multicore CPUs along with a number of accelerators, such as GPGPUs (General Purpose Graphics Programming Units) and even programmable hardware (in the form of FPGAs - Field Programmable Gate Arrays). These developments make the programmer's task even more difficult.Partitioning a computation over a set of heterogeneous devices - giving each core in each device an appropriate amount of work so as to minimise the overall execution time - is now a major problem which may be described as the "granularity" problem. Providing automated support to address this problem is vital to improving (parallel) programmer productivity. The ideal solution would allow programmers to express their algorithms in a clear and concise form while allowing the resulting program to execute efficiently on _any_ heterogeneous computer (providing portability of both code _and_ performance).This PhD project is looking to integrate two promising approaches to address this problem. Task-based dataflow languages provide programmers with a high-level language in which to express their algorithms without over-constraining the possible implementations in low-level machine code: they provide useful information that compilers and run-time systems can exploit to produce fast running code. The Polyhedral model of computation is a mathematical formalism which allows the application of program transformations, from high-level to low-level, to produce efficient code for a particular computing device. This project is investigating program representations for task-based programming languages that will allow polyhedral techniques to be applied as generally as possible, while targeting multi-device, heterogeneous systems. This approach provides a promising route to solving the granularity problem and thus improve programmer productivity.