Actor-based Parallelization and FPGA Dynamic Reconfiguration Architecture for Non-linear Pattern Matching

Non-linear pattern matching is a generalization of pattern matching that permits multiple occurrences of the same variable, with broad applications in duplicate detection, structural equivalence verification, and constraint satisfaction. However, achieving practical performance has been difficult due to the combinatorial explosion of the search space. This paper proposes two complementary approaches to this problem. First, we present a work-stealing scheme that partitions the search space and processes it in parallel using the actor model. Second, we present a conceptual design of an FPGA dynamic reconfiguration architecture specialized for pattern structures. Even in a baseline implementation without low-level optimizations, we measured throughput improvements of 120x to 2,700x over the Egison interpreter.