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

University Of Texas At Austin, Austin TX

Investigators

Abstract

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.