Scalable Processing of Contemporary Semi-Structured Data on Commodity Parallel Processors - A Compilation-based Approach
Scalable Processing of Contemporary Semi-Structured Data on Commodity Parallel Processors - A Compilation-based Approach
复制标题
商品并行处理器上当代半结构化数据的可扩展处理 - 基于编译的方法
DOI：
10.1145/3297858.3304008
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Zhao, Zhijia
中科院分区：
文献类型：
--
作者：
Jiang, Lin;Sun, Xiaofan;Farooq, Umar;Zhao, Zhijia
JSON（JavaScript Object Notation）及其衍生物在现代计算基础设施中至关重要。然而，现有的软件通常无法以可扩展的方式处理这种类型的数据，主要有两个原因：（i）处理通常需要构建消耗内存的解析树;（ii）在处理数据流时存在固有的依赖性，从而防止任何数据级并行化。面对这些挑战，开发人员往往不得不构建ad-hoc预解析器来分割数据流，以减少内存消耗，提高数据并行性。然而，这一战略需要更多的方案拟订工作。此外，预解析本身对于并行化来说是不平凡的，因此引入了新的串行瓶颈。为了解决这个难题，这项工作引入了一个可扩展的，但完全自动化的解决方案-编译系统，即JPStream，编译标准的JSONPath查询到并行可执行文件与有限的内存占用。首先，JPStream采用了流处理设计，将查询和解析结合到一个过程中，而不生成任何内存中的解析树。为了实现这一点，JPStream使用了一种新颖的联合编译技术，将查询和JSON语法一起编译到一个自动机中。此外，JPStream利用自动机的“可枚举性”来打破依赖关系，并对转换规则进行推理，以修剪不可行的状态。它还具有一个运行时，可以从输入中学习结构约束，以增强修剪。使用标准JSONPath查询对真实世界的JSON数据集进行的评估表明，JPStream可以显着降低内存消耗，最高可达95%，同时在多核和众核处理器上实现接近线性的加速。
JSON (JavaScript Object Notation) and its derivatives are essential in the modern computing infrastructure. However, existing software often fails to process such types of data in a scalable way, mainly for two reasons: (i) the processing often requires to build a memory-consuming parse tree; (ii) there exist inherent dependences in processing the data stream, preventing any data-level parallelization. Facing the challenges, developers often have to construct ad-hoc pre-parsers to split the data stream in order to reduce the memory consumption and increase the data parallelism. However, this strategy requires more programming efforts. Moreover, the pre-parsing itself is non-trivial to parallelize, thus introducing a new serial bottleneck. To solve the dilemma, this work introduces a scalable yet fully automatic solution - a compilation system, namely JPStream, that compiles standard JSONPath queries into parallel executables with bounded memory footprints. First, JPStream adopts a stream processing design that combines the querying and parsing into one pass, without generating any in-memory parse tree. To achieve this, JPStream uses a novel joint compilation technique that compiles the queries and the JSON syntax together into a single automaton. Furthermore, JPStream leverages the "enumerability'' of automaton to break the dependences and reason about the transition rules to prune infeasible states. It also features a runtime that learns structural constraints from the input to enhance the pruning. Evaluation on real-world JSON datasets with standard JSONPath queries shows that JPStream can reduce the memory consumption significantly, by up to 95%, meanwhile achieving near-linear speedup on multicore and manycore processors.
登录
查看更多内容
ASPEN：用于下推自动机的可扩展 SRAM 架构
DOI：
10.1109/micro.2018.00079
发表时间：
2018
期刊：
2018 51st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO
影响因子：
--
作者：
Angstadt, Kevin;Subramaniyan, Arun;Sadredini, Elaheh;Rahimi, Reza;Skadron, Kevin;Weimer, Westley;Das, Reetuparna
通讯作者：
Das, Reetuparna
AT-GIS：使用关联传感器的高度并行空间查询处理
DOI：
--
发表时间：
2016
期刊：
SIGMOD Conference
影响因子：
--
作者：
Peter Ogden;David B. Thomas;P. Pietzuch
通讯作者：
P. Pietzuch
为 FSM 计算启用可扩展性敏感的推测并行化
DOI：
10.1145/3079079.3079082
发表时间：
2017
期刊：
Proceedings of the International Conference on Supercomputing
影响因子：
--
作者：
Junqiao Qiu;Zhijia Zhao;Bo Wu;Abhinav Vishnu;S. Song
通讯作者：
S. Song
JSON 数据的并行且可扩展的处理器
DOI：
--
发表时间：
2018
期刊：
International Conference on Extending Database Technology
影响因子：
--
作者：
C. Pavlopoulou;E. Carman;T. Westmann;M. Carey;V. Tsotras
通讯作者：
V. Tsotras
MicroSpec：用于 FSM 计算的以推测为中心的细粒度并行化
DOI：
10.1145/2967938.2967965
发表时间：
2016
期刊：
2016 International Conference on Parallel Architecture and Compilation Techniques (PACT)
影响因子：
--
作者：
Junqiao Qiu;Zhijia Zhao;Bin Ren
通讯作者：
Bin Ren