Task graphs or dependence graphs are used in runtime systems toschedule tasks for parallel execution. In problem domains such asdense linear algebra and signal processing, dependence graphs can begenerated from a program by static analysis.  However, in problemdomains such as discrete-event simulation and simulation usingasynchronous variational integrators, the set of tasks and thedependences between tasks in a program are complex functions ofruntime values and cannot be determined statically.In this talk, we introduce a novel approach for exploiting parallelismin such programs. This approach is based on a data structure calledthe kinetic dependence graph (KDG), which consists of a dependencegraph together with update rules that incrementally update the graphto reflect changes in the dependence structure whenever a task iscompleted. We have implemented a simple programming model that allowsprogrammers to write these applications at a high level ofabstraction, and a runtime within the Galois system that builds theKDG automatically and executes the program in parallel. On a suite ofprograms that are difficult to parallelize otherwise, we have obtainedspeedups of up to 33 on 40 cores, out-performing third-partyimplementations in some cases.This is joint work with Amber Hassaan and Donald Nguyen at UT Austin.