Patti
Compiling Unification-Based Finite-State Automata into Machine Instructions for a Superscalar Pipelined RISC Processor
A compiler that turns a unification-based linguistic formalism — non-deterministic finite-state automata whose transitions are labeled with typed attribute-value matrices — directly into PowerPC machine code. Its fine-grained knowledge of the task enables optimizations that are hard to reach with general-purpose techniques: static branch-prediction heuristics, data-cache control, and scheduling that runs some unifications in parallel on the processor’s superscalar pipeline. Extracting noun groups from texts of a few thousand words took fractions of a millisecond on a 1997 Power Macintosh — on the order of 21 million tokens per second — fast enough that unification and pattern matching cease to be bottlenecks, and fast enough to put linguistic analysis within reach of interactive applications.
My diploma thesis at Saarland University, supervised by Hans Uszkoreit and Manfred Pinkal. It describes work I did during an internship at Apple’s Advanced Technology Group in Cupertino.
A talk on the core ideas followed in 1999.