Patti
Übersetzung unifikationsbasierter endlicher Automaten in Maschinenbefehle für einen superskalaren Pipeline-RISC-Prozessor
Originaltitel (Englisch): Patti: Compiling Unification-Based Finite-State Automata into Machine Instructions for a Superscalar Pipelined RISC Processor
Ein Compiler, der einen unifikationsbasierten linguistischen Formalismus – nichtdeterministische endliche Automaten, deren Übergänge mit typisierten Attribut-Wert-Matrizen beschriftet sind – direkt in PowerPC-Maschinencode übersetzt. Dank seines detaillierten Wissens über die Aufgabe kann er Optimierungen vornehmen, die mit allgemeinen Verfahren nur schwer erreichbar sind: Heuristiken zur statischen Sprungvorhersage, Steuerung des Daten-Caches und eine Anordnung der Maschinenbefehle, die einzelne Unifikationen parallel in der superskalaren Pipeline des Prozessors ausführt. Das Extrahieren von Nominalgruppen aus Texten von einigen tausend Wörtern dauerte auf einem Power Macintosh von 1997 Bruchteile einer Millisekunde – in der Grössenordnung von 21 Millionen Token pro Sekunde – schnell genug, dass Unifikation und Mustervergleich keine Engpässe mehr sind, und schnell genug, um linguistische Analyse für interaktive Anwendungen praktikabel zu machen.
Meine Diplomarbeit an der Universität des Saarlandes, betreut von Hans Uszkoreit und Manfred Pinkal. Sie beschreibt die Arbeit, die ich während eines Praktikums bei Apples Advanced Technology Group in Cupertino geleistet habe.
1999 folgte ein Vortrag zu den Kernideen.