Automatic Binary Parallelisation

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

Since the turn of the century, multicore processors have become commonplace in general-purpose computing systems. Starting with IBM's POWER 4 in 2001, multicores soon became mainstream with the release of x86 chips from Intel and AMD targeting desktop and servers; ARM's Cortex-A9 MPCore pushed multicores into the mobile space soon after. The failure of Dennard scaling (whereby, with each technology generation, integrated circuits could contain more transistors operating at a higher frequency for the same power budget) forced manufacturers to switch their focus from high-cost extraction of instruction-level parallelism (ILP) to efficient execution of thread-level parallelism (TLP) to avoid hitting the "power wall". This enables greater performance for separate tasks running together, either from totally independent programs or collaborating threads in a parallel application.Unfortunately, writing parallel code is still seen as hard (John Hennessy called it "a problem that's as hard as any that computer science has faced"). The programming language and runtime communities have risen to this challenge by providing new languages and constructs to aid parallel programming, significantly boosting programmer productivity. Whilst important and useful for new applications, studies suggest that developers primarily use threads to structure their code, without fully exploiting the parallelism available from the underlying hardware. In addition, users of single-threaded applications where the source code is lost, unavailable or cannot easily be recompiled, are not able to take advantage of the TLP now available to them.Within this context, parallelisation of application binaries becomes a seductive proposition. Regardless of the source languages used to create the program, or the availability of the code, an application can be restructured within its binary form to split off tasks into separate threads, manage communication between them and combine their results back together when required. Although almost impossible to perform effectively by hand, automatic tools have the ability to extract the inherent parallelism lurking in many sequential applications through sophisticated analysis and transformations to keep tasks as independent as possible. This obviates the need to spend time and effort reworking code into parallel form and allows users to obtain the benefits of parallel processors without writing a single line of code, opening up the performance potential of multicore processors so it is available to all.This project represents a significant step towards a general-purpose binary parallelisation tool. To achieve its aims it will draw on prior research into binary analysis, compiler-based automatic parallelisation, dynamic binary translation, and software transactional memory. A concrete output from this work will be a tool capable of extracting and exploiting the thread-level parallelism available in sequential applications, to achieve speed-ups of at least 2x on commodity quad-core processors.