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

University Of California-Riverside, Riverside CA

Investigators

Abstract

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.