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.

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