SHF: Small: Autograph: A System for Synthesizing Concurrent Data Structure Implementations

University Of Texas At Austin, Austin TX

Investigators

Abstract

Most electronic devices today are built from multicore processors, which consist of four to eight small cores (computers) that cooperate to perform computational tasks. Programming such multicore processors is much more difficult than programming a single computer, so one of the major research challenges in Computer Science is to design and implement tools that make this programming task easier. The Autograph project focuses on one aspect of this problem, which is the implementation of data structures that can be read and written safely by multiple cores at the same time. When completed, the Autograph tool will permit multicore programmers to specify the properties of the desired data structure, leaving it to the tool to synthesize the parallel data structure automatically. This tool will simplify the parallel programming task substantially. The input to Autograph is a high-level relational specification of the desired parallel data structure. Autograph works by composing a set of "building-block" data structures called tiles to implement the parallel data structure. The application programmer can control which tiles are used to produce the desired data structure. Therefore, application programmers can quickly produce parallel data structure implementations and tune their performance without having to write explicitly parallel code. Autograph will (i) implement the full system for the complete relational specification language, (ii) build code generators that can produce parallel C++ graph data structures from this language, (iii) extend this compiler to produce distributed-memory data structures, (iv) produce tools for autotuning the generated implementations, and (v) investigate the use of Autograph in implementing a GraphBLAS. Autograph will be implemented and demonstrated in the context of speculative parallelization systems like Galois, but it will also produce concurrent data structures for use in parallel systems that do not use speculation, such as OpenMP or pThreads. By simplifying one of the most complex aspects of parallel programming, namely the production of high-performance parallel data structures, Autograph will have a transformative effect on the critical field of parallel programming.