Data-Parallel String-Manipulating Programs

String-manipulating programs are an important class of programs with applications in malware detection, graphics, input sanitization for Web security, and large-scale HTML processing. This paper extends prior work on Bek, an expressive domain-specific language for writing string-manipulating programs, with algorithmic insights that make Bek both analyzable and data-parallel. By analyzable we mean that unlike most general purpose programming languages, many algebraic properties of a Bek program are decidable (i.e., one can check whether two programs commute or compute the inverse of a program). By data-parallel we mean that a Bek program can compute on arbitrary subsections of its input in parallel, thus exploiting parallel hardware. This latter requirement is particularly important for programs which operate on large data: without data parallelism, a programmer cannot hide the latency of reading data from various storage media (i.e., reading a terabyte of data from a modern hard drive takes about 3 hours). With a data-parallel approach, the system can split data across multiple disks and thus hide the latency of reading the data.

A Bek program is expressive: a programmer can use conditionals, switch statements, and registers—or local variables—in order to implement common string-manipulating programs. Unfortunately, this expressivity induces data dependencies, which are an obstacle to parallelism. The key contribution of this paper is an algorithm which automatically removes these data dependencies by mapping a Bek program into a intermediate format consisting of symbolic transducers, which extend classical transducers with symbolic predicates and symbolic assignments. We present a novel algorithm that we call exploration which performs symbolic loop unrolling of these transducers to obtain simplified versions of the original program. We show how these simplified versions can then be lifted to a stateless form, and from there compiled to data-parallel hardware.

To evaluate the efficacy of our approach, we demonstrate up to 8x speedups for a number of real-world, Bek programs, (e.g., HTML encoder and decoder) on data-parallel hardware. To the best of our knowledge, these are the first data parallel implementation of these programs. To validate that our approach is correct, we use an automatic testing technique to compare our generated code to the original implementations and find no semantic deviations.