按年被提到
20192019 · 1 次2026
编程语言与编译器›编译器与运行时优化·arXiv:1905.13415 · cs.DB

ParPaRaw: Massively Parallel Parsing of Delimiter-Separated Raw Data

Elias Stehle, Hans-Arno Jacobsen · 2019
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2019-06-28 · 最近 2021-12-29
2不同的人
2活跃月份
2讨论串
12被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Parsing is essential for a wide range of use cases, such as stream processing, bulk loading, and in-situ querying of raw data. Yet, the compute-intense step often constitutes a major bottleneck in the data ingestion pipeline, since parsing of inputs that require more involved parsing rules is challenging to parallelise. This work proposes a massively parallel algorithm for parsing delimiter-separated data formats on GPUs. Other than the state-of-the-art, the proposed approach does not require an initial sequential pass over the input to determine a thread's parsing context. That is, how a thread, beginning somewhere in the middle of the input, should interpret a certain symbol (e.g., whether to interpret a comma as a delimiter or as part of a larger string enclosed in double-quotes). Instead of tailoring the approach to a single format, we are able to perform a massively parallel FSM simulation, which is more flexible and powerful, supporting more expressive parsing rules with general applicability. Achieving a parsing rate of as much as 14.2 GB/s, our experimental evaluation on a GPU with 3584 cores shows that the presented approach is able to scale to thousands of cores and beyond. With an end-to-end streaming approach, we are able to exploit the full-duplex capabilities of the PCIe bus and hide latency from data transfers. Considering the end-to-end performance, the algorithm parses 4.8 GB in as little as 0.44 seconds, including data transfers.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论ejbs · 2019-06

“> They did not include the time it took to transfer the input file from memory to the GPU To give some context: PCIe 3.0 x16 achieves about 11-12 GB/s. So, transfers for benchmarked 53MB file would add ~4.8 ms (per direction, assuming pinned host memory) Now, they could also pursue a streaming approach, processing in "micro-batches". I.e., pipelining in…”

CUDA Grep原评论 ↗
评论criticaltinker · 2021-12

“DFAs and NFAs may seem like academic novelties but they are amazingly powerful for certain problems. For example, naively searching a string of length N for P different substrings will yield an algorithm that has roughly O(N * P) worst case time complexity. But implementing that algorithm as a DFA yields an efficient construction that has O(N) worst cas…”

LaTeX Finite Automata and State Diagrams with Tikz原评论 ↗