• Calendar

January 29, Sunday
14:00 – 15:00

Efficient concurrent data structures are extremely important for obtaining good performance for most parallel programs. However, ensuring the correctness of concurrent data structure implementations can be very tricky because of concurrency bugs such as race conditions and deadlocks. In systems that use optimistic parallel execution such as boosted transactional memory systems and the Galois system, the implementation of concurrent data structures is even more complex because data structure implementations must also detect conflicts between concurrent activities and support the rollback of conflicting activities. At present, these types of concurrent data structures are implemented manually by expert programmers who write explicitly parallel code packaged into libraries for use by application programmers. This solution has its limitations; for example, it does not permit the customization or tuning of a data structure implementation for a particular application. In this talk, we present Autograph, which is the first concurrent data structure compiler that can synthesize concurrent relational data structure implementations for use by application programmers. The input to Autograph is a high-level declarative specification of an abstract data type (ADT); the output is a concurrent implementation of that ADT with conflict detection and rollback baked in. Our synthesizer is parameterized by a set of data structures called “tiles”, which are building blocks that the compiler composes to create the overall data structure. Application programmers can use a simple expression language to tune the composition of these tiles, thereby exercising high level, fine-grain control of data structure implementations. We have used Autograph to synthesize concurrent sparse graph data structures for a number of complex parallel graph benchmarks. Our results show that the synthesized concurrent data structures usually perform better than the handwritten ones; for some applications and thread counts, they improve performance by a factor of 2.