SHF: Small: Efficient Parallel Execution of Irregular, Ordered Algorithms

今天的大多数计算机都是由称为核心的独立处理单元组成的集合，这些处理单元可以协作地执行应用程序，从而减少了产生该应用程序输出所需的时间。然而，目前的编程语言是为具有单个处理单元的顺序计算机开发的，它们不适合于对多核并行处理器进行编程，而现有的用于并行编程的语言和工具非常难以使用，需要对计算机硬件和系统软件的专业理解。该项目更广泛的意义和重要性在于，它旨在简化一类重要应用程序的并行编程，这些应用程序包括物理模拟(如战场模拟)和图形分析(如社会网络)。其智力优势在于，在多核处理器上高效并行化这些应用程序所需的抽象和系统软件远远超出了现有技术的水平，如果成功，将大大提高我们对如何有效利用多核并行计算机的理解。传统上，程序员依赖于一种称为任务依赖图的抽象来揭示应用程序中的并行性。然而，依赖图不能用于新兴的应用，例如物理系统的离散事件模拟，例如，碰撞粒子和使用异步变分积分器的变形材料的建模。这类应用的并行化是非常具有挑战性的，因为这类应用中的任务表现出复杂的行为：例如，由于基于模拟时间因果关系的排序约束，任务可能创建必须在现有任务之前执行的新任务，并且一个任务的执行可能改变现有任务之间的依赖关系。该项目背后的关键见解是，一种名为动态依赖图(KDG)的数据结构可用于跟踪此类应用程序中的依赖关系，允许以维护KDG的一些簿记费用为代价安全地并行执行。该项目开发的编程构造和系统实现将作为德克萨斯大学奥斯汀分校Galois系统的一部分公开发布。

Most computers today consist of a collection of individual processing units called cores that can execute an application co-operatively, reducing the time required to produce the output of that application. However, current programming languages were developed for sequential computers that have a single processing unit, and they are not ideal for programming multicore parallel processors, while existing languages and tools for parallel programming are very difficult to use, requiring expert understanding of the computer hardware and system software. This project's broader significance and importance is that it aims to simplify the parallel programming of an important class of applications that includes physical simulations, such as battle-field simulations, and analysis of graphs, such as social networks. The intellectual merit is that the abstractions and systems software needed to parallelize these applications efficiently on multicore processors goes well beyond the state of the art, and if successful, will lead to a significant improvement in our understanding of how multicore parallel computers can be exploited effectively. Traditionally programmers have relied upon an abstraction called Task Dependence Graph for exposing parallelism in applications. However, dependence graphs cannot be used for emerging applications such as discrete-event simulation of physical systems, e.g., colliding particles and modeling of deforming materials using asynchronous variational integrators. Parallelization of such applications is very challenging because of the complex behaviors exhibited by tasks in such applications: for example, tasks may create new tasks which must be executed before existing tasks due to ordering constraints based on simulation-time causality, and the execution of one task may change the dependences between existing tasks. The key insight behind the project is that a data structure called the Kinetic Dependence Graph (KDG) can be used to track dependencies in such applications, permitting safe parallel execution at the cost of some book-keeping expense to maintain the KDG. The programming constructs and systems implementations developed by the project will be released publicly as part of the Galois system from the University of Texas at Austin.