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

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

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.