Automatic Binary Parallelisation

自世纪之交以来，多核处理器在通用计算系统中已经变得司空见惯。从2001年IBM的POWER 4开始，随着英特尔和AMD针对桌面和服务器发布x86芯片，多核很快成为主流；此后不久，ARM的Cortex-A9 MPCore将多核技术推向了移动领域。登纳德缩放（Dennard scaling）的失败（即，随着每一代技术的发展，集成电路可以在相同的功率预算下以更高的频率运行更多的晶体管）迫使制造商将他们的重点从高成本的指令级并行性（ILP）提取转向高效执行线程级并行性（TLP），以避免撞上“功率墙”。这为同时运行的独立任务提供了更高的性能，无论是来自完全独立的程序还是并行应用程序中的协作线程。不幸的是，编写并行代码仍然被认为是困难的（John Hennessy称之为“计算机科学所面临的任何困难的问题”）。编程语言和运行时社区通过提供新的语言和结构来帮助并行编程，从而显著提高了程序员的工作效率，从而迎接了这一挑战。虽然对于新应用程序很重要也很有用，但研究表明，开发人员主要使用线程来构建代码，而没有充分利用底层硬件提供的并行性。此外，源代码丢失、不可用或无法轻松重新编译的单线程应用程序的用户无法利用现在提供给他们的TLP。在这种情况下，应用程序二进制文件的并行化成为一个诱人的主张。不管用于创建程序的源语言是什么，也不管代码的可用性如何，应用程序都可以在其二进制形式中进行重构，以将任务拆分为单独的线程，管理它们之间的通信，并在需要时将它们的结果组合在一起。尽管手工有效地执行几乎是不可能的，但是自动化工具能够通过复杂的分析和转换来提取潜伏在许多顺序应用程序中的固有并行性，从而尽可能地保持任务的独立性。这避免了花费时间和精力将代码重写为并行形式的需要，并允许用户无需编写一行代码即可获得并行处理器的好处，从而打开了多核处理器的性能潜力，因此所有人都可以使用它。这个项目代表了迈向通用二进制并行化工具的重要一步。为了实现其目标，它将借鉴先前对二进制分析、基于编译器的自动并行化、动态二进制翻译和软件事务性内存的研究。这项工作的具体成果将是一个能够提取和利用顺序应用程序中可用的线程级并行性的工具，从而在商用四核处理器上实现至少2倍的加速。

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.