Data Transformation Acceleration using Deterministic Finite-State Transducers
Authors:
- 17 December 2022
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 141-150
Abstract
Data transformation tasks are a critical and costly part of many data processing and analytics applications. A simple computing model that can efficiently represent data transformation and be mapped to different platforms can provide programmers with the flexibility o f u sing different data representations and allow for exploiting different platforms, including general-purpose processors and accelerators.We propose extended Deterministic Finite State Transducers (DFST+s), a computing model that enables the compact expression of data transformations (a significantly terser expression compared to the DFSTs model, a traditional computational abstraction for data transformation), aiding their correct and efficient implementation. We define the TF ORM language to facilitate expressing the DFST+, and the TFORM virtual machine to enable a further compact expression, leading to a high performance and portable implementation. We propose two TFORM VM execution models and evaluate them using a variety of data transformations (from Apache Parquet file format and sparse matrices). Our results show both effective portability across CPU and a hardware accelerator, and performance increases of 1.7× and 11.7× geometric mean, respectively, over a custom CPU implementation of the same transformations.Keywords
Funding Information
- National Science Foundation
This publication has 26 references indexed in Scilit:
- Regular Programming for Quantitative Properties of Data Streams2016
- Fast LZW Compression Using a GPU2015
- DaRPC2014
- Efficient Sparse Matrix-Vector Multiplication on GPUs Using the CSR Storage Format2014
- Decoding billions of integers per second through vectorizationSoftware: Practice and Experience, 2013
- Weighted finite-state transducers in speech recognitionComputer Speech & Language, 2002
- Minimization algorithms for sequential transducersTheoretical Computer Science, 2000
- Compressing Integers for Fast File AccessThe Computer Journal, 1999
- THE EXPRESSION OF GRAPH PROPERTIES AND GRAPH TRANSFORMATIONS IN MONADIC SECOND-ORDER LOGIC1997
- On some applications of finite-state automata theory to natural language processingNatural Language Engineering, 1996