Exploiting Parallelism through Type Transformations for Hybrid Manycore Systems

Modern computing systems are becoming increasingly diverse, but the common feature of all emerging computing platforms is the increased potential for performing many computations in parallel, by providing large numbers of processor cores. Computer systems consisting of various different platforms have great potential for performing tasks fast and efficiently. However, programming such systems is a great challenge.

The era of performance increase through increased clock speeds has come to an end and we have entered a period where performance increases can only come from increased numbers of heterogeneous computational cores and their effective exploitation by software. Because of the immense effort required to adapt existing parallel software to novel hardware
architectures with present technology, there is a very real danger that future advances in hardware performance will have little impact on practical large-scale computing
using legacy software.

The specific challenge that we want to address in this proposal is how to exploit the parallelism of a given computing platform, e.g. a multicore CPU, a graphics processor (GPU) or a Field-Programmable Gate Array (FPGA), in the best possible way, without having to change the original program. These different platforms have very different properties in terms of the available parallelism, depending on the nature and organisation of the processing cores and the memory. In particular FPGAs have great potential for parallelism but they are radically different in architecture from mainstream processors. This makes them very difficult to program.

The key problem here is how to transform a program so that it will best use the potential for parallelism provided by the computing platform, and crucially, how to do this so that the resulting program is guaranteed to have the same behaviour as the original program.
Our proposed approach is to use an advanced type system called Multi-Party Session Types to describe the communication between the tasks that make up a computation.
To use a rough analogy, the computation could for instance be viewed as a car assembly line, where every unit performs a particular task such as painting, inserting doors, wheels, motor etc. Depending on the organisation and composition of the factory, the order in which these operations is performed will determine the speed with which a car can be assembled. However, when reordering the operations, one must of course ensure that changing the order does not lead to incorrect assembly.

To return to the computational problem, by using the Multi-Party Session Types to describe the communication, we have a formal way of reasoning about the transformations. By developing a formal language for the transformations we can prove their correctness. This is the main novelty of the proposal: the formal system for type transformations. The actual transformations can be viewed as "programs" in this formal language. They will be informed by the properties of the computing platform. To provide this link between the transformation and the platform, we will also develop a formal description of parallel computing platforms.

By building these formal systems into a compiler we will be able to transform programs to run in the most efficient way on hybrid manycore platforms.
The main benefit from the proposed research is that the programmer will not need to have in-depth knowledge of the highly complex architecture of a hybrid manycore platform. This will be of great benefit to in particular scientific computing, because it also means that programs will not need to be rewritten to run with best performance on novel systems.

To demonstrate the effectiveness of our approach we aim to develop a proof-of-concept compiler which will transform programs so that they can run on FPGAs, because this type of computing platform is the most different from other platforms and hence the most challenging.

Realising our vision will lead to a revolution in the programming of heterogeneous high-performance computing systems. Progress in this area is essential to maintain productivity on the next generation of heterogeneous parallel systems, in particular with the move towards exascale systems (1000x bigger than today's systems). To reduce power consumption, these systems will have to be heterogeneous. Achieving high performance on such systems with the existing programming tools and methodologies is proving increasingly difficult. Our proposed work will lead to highly novel compiler technologies, based on a sound formal foundation with guarantees for correctness and bounds for performance. It will allow scientists and other application developers to focus on implementing their ideas rather than on trying to achieve good performance.

In a nutshell, our compiler will automatically transform the program so that it will run optimally on any given heterogeneous parallel architecture. As a result, parallel systems and high-performance computing systems will become much more accessible, not only to scientists but also to industry. There is a clear need for more accessible high-performance computing (see e.g. http://www.supercomputingscotland.org/). Heterogeneous systems can provide supercomputing capabilities in a form factor suitable for SMEs and small academic research groups. Furthermore, supercomputing hardware changes very quickly, and our solution will make it easy to deploy applications on new platforms, where today this is a very complex and time consuming process.

The applications domain for our work is very broad. To illustrate the potential, we give a few examples based on our own cross-disciplinary research:
- Weather and Climate simulations: by increasing the performance, scientists can run simulation over larger areas, with higher resolution and for longer timescales. Each of these opens a wealth of new possibilities. For example, higher resolution is essential for accurately simulating and predicting severe weather events. Because of climate change, these events are becoming more frequent and more severe. Larger areas allow better long-range forecasts, and longer timescales allow more accurate climate simulations.
- Particle dispersion simulation: this type of simulation is used to e.g. predict dispersion of volcanic ash or radio-active particles. Increased performance will allow more accurate prediction of the dispersion, which in the case of volcanic ash means a reduced downtime for airplanes, and in the case of radio-active particles helps to protect the population.
- Railtrack simulation: simulation of in particular tracks for high-speed trains is essential to ensure the safety. Increased performance will allow more sophisticated simulation (in particular a more realistic model of the train itself). This is required to accurately model degradation of the tracks, which forces trains to run at reduced speeds an extended closure of tracks for repairs.

In terms of impact on industry, following sectors already use FPGA technology and could therefore benefit specifically from making FPGA platforms more accessible: financial computing (e.g. option pricing), biotechnology (esp. gene sequence matching) and drug companies (for molecular dynamics simulations).
Other sectors of industry that require supercomputing resources, and that will consequently benefit from the increased productivity offered by our solution, are renewable energy (through faster and more accurate weather predictions) and aerospace (for computational fluid dynamics simulations), to name a few.

Impact of our work will result primarily from adoption of our approach in industry and academia. The Pathways to Impact document explains how we will achieve this impact.