For decades, uniprocessor performance improvements made serial software run faster at no cost to the programmer. In recent years, however, uniprocessor performance has flattened out due to heat dissipation barriers. For the foreseeable future, multicore processors promise more cores, rather than faster cores, in successive hardware generations. Serial application performance therefore can no longer effortlessly piggyback on hardware performance gains. Only parallel software can exploit multicore hardware's full potential.
The problem is that parallel programming is far harder than serial programming. Reasoning about concurrency is formidably difficult even in shared-memory multithreaded programming, which partly preserves the style of sequential programming, due to the numerous possible interleavings of basic operations. Faulty reasoning can cause errors (data races) or nondetermination (deadlock), and such defects can easily survive testing with disastrous results in production. Conservative programming practices such as coarse-grained locks lower the risk of bugs in new software but reduce concurrency and therefore impair performance, negating the main benefit of parallelization.
In this category of projects, we seek for compiler techniques to make parallel programming easier while fully exploiting the computational power provided by multicore architectures.
Gadara: Dynamic Deadlock Avoidance for Multithreaded Programs
Deadlock is an increasingly pressing concern as the multicore revolution forces parallel programming upon the average programmer. Existing approaches to deadlock impose onerous burdens on developers, entail high runtime performance overheads, or offer no help for unmodified legacy code.
Gadara automates dynamic deadlock avoidance for conventional multithreaded programs. It employs whole-program static analysis to model programs, and Discrete Control Theory to synthesize lightweight, decentralized, highly concurrent logic that controls them at runtime. Gadara is safe, and can be applied to legacy code with modest programmer effort. Gadara is efficient because it performs expensive deadlock-avoidance computations offline rather than online.
Relevant Publications
Page last modified January 22, 2016.