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

今天的大多数电子设备都是由多核处理器构建的，多核处理器由四到八个小核(计算机)组成，它们相互协作执行计算任务。对这样的多核处理器编程比对单台计算机编程要困难得多，因此计算机科学的主要研究挑战之一是设计和实现使这一编程任务变得更容易的工具。Autograph项目专注于这个问题的一个方面，即实现可由多个内核同时安全地读写的数据结构。完成后，Autograph工具将允许多核程序员指定所需数据结构的属性，让工具自动合成并行数据结构。该工具将大大简化并行编程任务。Autograph的输入是所需并行数据结构的高级关系规范。Autograph的工作原理是组成一组称为Tiles的“构建块”数据结构，以实现并行数据结构。应用程序员可以控制使用哪些块来产生所需的数据结构。因此，应用程序编程人员可以快速生成并行数据结构实现并调整其性能，而不必编写显式并行代码。Autograph将(I)实现完整关系规范语言的完整系统，(Ii)构建能够从该语言生成并行C++图形数据结构的代码生成器，(Iii)扩展该编译器以生成分布式内存数据结构，(Iv)生成用于自动调优所生成的实现的工具，以及(V)研究Autograph在实现GraphBLAS中的使用。Autograph将在Galois等投机性并行化系统的环境中实现和演示，但它也将生成并发数据结构，用于不使用投机性的并行系统，如OpenMP或pThread。通过简化并行程序设计中最复杂的一个方面，即产生高性能的并行数据结构，Autograph将对并行程序设计的关键领域产生革命性的影响。

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.