Exploiting heterogeneous parallelism in software and hardware

Abstract

Modern computer hardware is becoming increasingly diverse, necessitating the consideration of heterogeneous parallelism. This means dividing algorithms into tasks running simultaneously which are not all identical, and may run on non-identical hardware. This has clear advantages, but has many issues, particularly in software development. A heterogeneous program is often directly implemented as a series of communicating sequential programs, but I argue that this approach is limiting and unhelpful. It leads to early and fixed decomposition of the program by the designer which then limits flexibility if this decomposition is later found to be sub-optimal. This also hurts portability; migrating to a system with different hardware may require a new parallelisation strategy which therefore means a complete reimplementation of all the synchronisation and communication in the program. My thesis is that heterogeneous parallelism is a powerful technique for generating high performance software on modern and future hardware, but that exploiting it practically requires a new optimisation paradigm. I present my novel design for an optimisation and parallelisation framework based on a guided transformation of a functional specification program into an efficient and optimised parallel implementation. I implement this in a tool called DKAR and show it is practical for case studies on the Loki architecture, a representative many-core architecture that I helped fabricate. Software developed by DKAR is competitive with hand generated code, despite a principled, error-free, and flexible development process. These transformations can make substantial changes to the specification, including true algorithmic transformation. I argue this represents the first practical formalisation of the notion of program optimisation and parallelisation, with potential applications in better defining existing algorithms in terms of transformation of a specification, as well as potentially discovering new algorithms with search techniques. Crucially, the faster development process with DKAR allows ideas to be explored rapidly compared with existing development methodologies, allowing more ideas to be tried, and providing flexibility in the face of changing platforms or requirements.