CAREER: Transducer-Centric Parallelization for Scalable Semi-Structured Data Processing

半结构化数据是通过Web交换数据的事实标准，也是许多基于文档的数据存储的默认数据类型。随着其数量的快速增长，在并行处理器上处理半结构化数据变得至关重要，并行处理器已经变得无处不在并且越来越强大。然而，半结构化数据的数据并行处理仍然是一个根本的挑战，由于其固有的嵌套结构。半结构化数据的分区很容易破坏嵌套级别的格式良好的性质，使数据难以处理。为了应对这一挑战，本研究提出了检查用于处理半结构化数据的基本计算模型--下推转换器，并设计了一个以转换器为中心的并行化范例。这使得能够为使用半结构化数据的软件应用程序自动生成数据并行处理例程。由于半结构化数据的基础作用，从这项研究中获得的见解将促进研究进展超越程序并行化。第一个组件检查固有的依赖性下推换能器执行和设计了一系列的基本机制，打破他们利用其特殊的属性，如“有限状态”和“有界堆栈访问”。第二和第三部分的重点是提高并行化效率，无论是利用下推转换器的过渡结构和半结构化数据的语法，或通过采用积极的推测执行计划。这项研究的最后一个组成部分是开发算法和软件工具，以自动生成并行下推传感器，用于半结构化数据的常用处理例程。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估。

Semi-structured data is the de facto standard for exchanging data over the web and the default data type for many document-based data stores. With its fast growth in volume, it becomes critical to process semi-structured data on parallel processors, which have become ubiquitous and increasingly powerful. However, data-parallel processing of semi-structured data remains a fundamental challenge, due to its inherent nested structure. A partitioning of semi-structured data can easily break the well-formed nature of nested levels, making the data hard to process. To address the challenge, this research proposes to examine the basic computation models used for processing semi-structured data -- pushdown transducers, and designs a transducer-centric parallelization paradigm. This enables automatic generation of data-parallel processing routines for software applications that consume semi-structured data. Because of the fundamental role of semi-structured data, the insights gained from this research will facilitate research advancement beyond program parallelization.Transducer-centric parallelization consists of four components. The first component examines inherent dependences in pushdown transducer executions and designs a series of basic mechanisms to break them by leveraging their special properties, such as 'finite-state' and 'bounded stack access'. The second and third components focus on improving the parallelization efficiency either by exploiting the transition structures of pushdown transducers and the grammars of semi-structured data, or by adopting an aggressive speculative execution scheme. The last component of this research develops algorithms and software tools to automatically generate parallel pushdown transducers for commonly used processing routines of semi-structured data.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.