Faculté informatique et communications IC, Département d'informatique, Institut d'informatique fondamentale IIF (Laboratoire d'intelligence artificielle LIA)

An FPGA-based syntactic parser for large size real-life context-free grammars

Ciressan, Cristian Raul ; Rajman, Martin (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2001 ; no 2522.

Ajouter à la liste personnelle
    Summary
    This thesis is at the crossroad between Natural Language Processing (NLP) and digital circuit design. It aims at delivering a custom hardware coprocessor for accelerating natural language parsing. The coprocessor has to parse real-life natural language and is targeted to be useful in several NLP applications that are time constrained or need to process large amounts of data. More precisely, the three goals of this thesis are: (1) to propose an efficient FPGA-based coprocessor for natural language syntactic analysis that can deal with inputs in the form of word lattices, (2) to implement the coprocessor in a hardware tool ready for integration within an ordinary desktop computer and (3) to offer an interface (i.e. software library) between the hardware tool and a potential natural language software application, running on the desktop computer. The Field Programmable Gate Array (FPGA) technology has been chosen as the core of the coprocessor implementation due to its ability to efficiently exploit all levels of parallelism available in the implemented algorithms in a cost-effective solution. In addition, the FPGA technology makes it possible to efficiently design and test such a hardware coprocessor. A final reason is that the future general-purpose processors are expected to contain reconfigurable resources. In such a context, an IP core implementing an efficient context-free parser ready to be configured within the reconfigurable resources of the general-purpose processor would be a support for any application relying on context-free parsing and running on that general-purpose processor. The context-free grammar parsing algorithms that have been implemented are the standard CYK algorithm and an enhanced version of the CYK algorithm developed at the EPFL Artificial Intelligence Laboratory. These algorithms were selected (1) due to their intrinsic properties of regular data flow and data processing that make them well suited for a hardware implementation, (2) for their property of producing partial parse trees which makes them adapted for further shallow parsing and (3) for being able to parse word lattices.
    Résumé
    Le sujet de cette thèse est situé au mi-chemin entre le traitement automatique du langage naturel et (TALN) et la conception de circuits numériques. Le but de cette thèse est la conception d’un coprocesseur pour améliorer le temps de l’analyse syntaxique du langage naturel. Le coprocesseur doit faire l’analyse syntaxique du langage naturel réel et est conçu pour être utile dans plusieurs applications TALN qui ont des contraintes de temps ou qui utilisent beaucoup des données. Plus claire, les trois buts de cette thèse sont: (1) de proposer un efficient coprocesseur à base d’FPGA pour l’analyse syntaxique du langage naturel qui prend des entrées de la forme des treillis de mots, (2) d'implémenter un coprocesseur dans un outil matériel prêt à être intégré dans un ordinateur et (3) d'offrir une interface (i.e. librairie de composants) entre l'outil matériel et les éventuels logiciels de traitement automatique du langage naturel qui vont s'exécuter sur l'ordinateur. La technologie FPGA (Field Programmable Gate Array) a été choisie comme support pour l'implémentation du coprocesseur grâce à son habilité d'exploiter de façon efficace tous les niveaux de parallélisme existant dans les algorithmes implémentés, tout en gardant un prix raisonnable. La dernière raison réside dans l'attente de voir les futurs coprocesseur génériques contenir des ressources réconfigurables. Dans un tel contexte, un module (IP core) qui implémente un analyseur syntaxique non contextuel prêt à être configuré dans les ressources réconfigurables du processeur générique serait un support pour toute application basée sur des analyses syntaxiques non contextuelles qui s'exécute dans ce processeur générique. L'algorithme analyse syntaxique de la grammaire non contextuelle qui a été implémenté est l'algorithme CYK standard aussi bien qu'une de ses versions améliorées. Cette version améliorée de l'algorithme CYK a été développée dans le Laboratoire d'Intelligence Artificielle de l'EPFL. Ces algorithmes ont été sélectionnés (1) grâce à leurs propriétés intrinsèques liées au flux de données et au traitement des données régulières qui font d'eux des bons candidats pour l'implémentation matérielle, (2) pour leur capacité à produire des arbres syntaxiques partiels qui les rend adaptés pour des futures analyses syntaxiques de surface et (3) pour leur habilité à faire l'analyse syntaxique des treillis de mots.