Polyhedral Representation of Dataflow Programs
Lead Research Organisation:
University of Manchester
Department Name: Computer Science
Abstract
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.
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.
Organisations
People |
ORCID iD |
| Graham Riley (Primary Supervisor) | |
| Nuno Nobre (Student) |
Studentship Projects
| Project Reference | Relationship | Related To | Start | End | Student Name |
|---|---|---|---|---|---|
| EP/N509565/1 | 01/10/2016 | 30/09/2021 | |||
| 1965733 | Studentship | EP/N509565/1 | 01/10/2016 | 31/01/2021 | Nuno Nobre |
| Description | Although task-parallel programming models provide some benefits to programmers by abstracting away the intricacies of the hardware and producing fast running code, they also raise some new questions. In particular, under certain conditions, it might be impossible to decide, a priori, whether or not a given program of this kind will run on a machine with some resource constraints. It is possible however to build an algorithm based on the polynomial-extended polyhedral model to, on a best-effort basis, try to decide whether or not the program will run. If the program gives us a positive answer, we have a certificate of execution, otherwise, we simply do not know. In any case, the certificate for the programs for which our algorithm works is useful in many cases like memory-constrained execution on GPUs. In addition, these task-parallel programming models usually require careful scheduling and task management decisions at runtime. In particular, the choice of which tasks to run at a specific time and at which granularity is non-trivial. We have shown that polyhedral techniques can help the programmer in these program design choices, even if the optimised code generating process is not fully automated when targeting the OpenStream language. |
| Exploitation Route | Companies or institutions behind compilers and runtime systems for task-parallel languages like OpenStream or OpenMP might benefit from the automatic optimisation techniques under study. In addition, having the ability to a priori certify the successful execution of a program under specific resource constraints might be of use in the context of memory-constrained devices like GPUs which are widely used to accelerate numerical applications. |
| Sectors | Digital/Communication/Information Technologies (including Software) |