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或pThreads。 通过简化并行编程最复杂的方面之一，即高性能并行数据结构的产生，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.