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

SHF：小型：Autograph：综合并发数据结构实现的系统

• 批准号: 1218568
• 负责人: Keshav Pingali
• 金额: $ 40万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-10-01 至 2016-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1218568&HistoricalAwards=false
• 关键词: SHF; Small; Autograph; System; Synthesizing

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.

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