Hybrid Static / Dynamic Optimisations for Many-Cores: Breaking the Memory Wall

Fueled by an exponential growth in computing capacities, society's reliance on information and computer systems has grown to encompass most activities and aspects of our lives. Mobile computing devices alone are set to outnumber humans in 2014, each such device providing more computational power than the supercomputers used to put men on the moon. Yet despite this exponential growth, society still hungers for more: consumers want new and improved smartphones and computers; scientists want to run more precise simulations, solve bigger problems or get results faster; we explore new computationally intensive technologies to bring forward the next generation of tools, from self-driving cars to robotic surgery. However, the "free lunch" is over: processors are no longer getting faster. Hard physical limits, such as energy and power density, have brought this success story to an abrupt end. To avoid this impasse, all major manufacturers are now offering an exponentially increasing number of processing units, or cores, per chip.

With ubiquitous parallel hardware and stagnating single processor performance, the only way forward is to improve the scalability and efficiency of parallel execution. In this context, the critical impediment to performance is the widening gap between the computing capabilities of many-core architectures and their limited off-chip memory bandwidth: the memory wall. Traditional solutions attempt to reduce off-chip communications by improving data locality, which means that computations are scheduled in such a way that intermediate results are not sent back to main memory and then re-loaded on chip. Common approaches are either static, with an optimising compiler determining a program schedule such that all intermediate results fit within the available cache memory, or dynamic, when a runtime environment builds the schedule during execution.

The main criticism of these techniques is that: (1) static approaches are very limited in scope, only applicable to restricted classes of computations; and (2) dynamic approaches are unaffordable, as finding the optimal schedule is generally more expensive than the gain. Current state-of-the-art approaches favour inexpensive dynamic heuristics, albeit imprecise and sub-optimal. The research hypothesis of this project is that near-optimal dynamic schedules can be built efficiently, provided that the work is partitioned between the compiler and the runtime system. Alone, the compiler cannot optimise many important programs due to static analysis shortcomings when dealing with recursion or complex, dynamically allocated, data structures. However, if the compiler performs best effort static optimisations and prepares the ground by providing the runtime environment with tractable subproblems, which are cheap to solve with the accurate information typically available during execution, then such a hybrid optimisation scheme becomes profitable and will lead to significant performance and scalability gains.

The outcome of this project will deliver performance and scalability gains to software development companies that target multi- and many-core architectures, and as a consequence, it will also enhance consumer experience on computers and mobile devices equipped with new chips, providing faster and less power-hungry applications, an essential gain on smartphones and tablets. The mobile economy is not only one of the fastest growing economic sectors, but it represents a fundamental societal shift.

The most direct beneficiaries, financially speaking, are chip manufacturers. They will increasingly struggle to sell chips as more cores often provide no performance gains to existing applications. One of their main issues will be to find a way to show that new chips, with more cores, have an edge over previous generations, and this crucially depends on the capability of programmers to exploit vast numbers of additional cores. This project will enhance the scalability of parallel programs, which is as relevant to established chip manufacturers, such as ARM, IBM, Intel or Qualcomm, as to start-ups that produce massively parallel many-core processors like Kalray's MPPA architecture.