Evaluación de expresiones regulares sobre hardware reconfigurable

Abstract

Los últimos avances en redes y subsistemas de almacenamiento continúan aumentando la velocidad a la que los flujos de datos deben ser procesados tanto internamente como en redes de computadores. Una proporción relativamente alta de la carga computacional en este tipo de aplicaciones puede implicar hacer correspondencias con expresiones regulares. Dado que el conjunto de patrones a ser examinado se espera que continúe creciendo y cambiando a lo largo del tiempo, el hardware que lo procese debe ser reconfigurable, de forma que pueda adaptarse dinámicamente a los requerimientos de esta correspondencia de patrones. Las FPGAs son ideales para este propósito. En este trabajo, se ha creado un generador de código, programado en un lenguaje de alto nivel. Este generador de código toma un conjunto de expresiones regulares y crea el código VHDL que describe el sistema que realiza la correspondencia de patrones. La principal ventaja de este esquema es que es posible beneficiarse simultáneamente de las ventajas de las implementaciones software y hardware. Por tanto, se tiene la flexibilidad proporcionada por el uso del software para describir expresiones regulares y el rendimiento alcanzado cuando el producto final es una implementación hardware del sistema. [ABSTRACT] The latest developments on networks and memory subsystems, push up the speed requirements for applications that process data streams transmitted. A significant part of the computational cost of this type of applications may imply regular expressions matching. Since the number of patterns to be examined is expected to keep increasing and changing along the time, the hardware required to process them should be as much flexible as possible. This means that the hardware will be able to adapt itself dynamically to the requirements of pattern matching. Then, the FPGAs are the best solution for this objective. In this work, a code generator has been created. It has been programmed on a high level language. This code generator takes a set of regular expressions and creates the VHDL code that describes the system that performs the pattern matching. This code is synthesized by a commercial tool into a FPGA. The main advantage of this schema is that it possible to take advantage of the capabilities of software and hardware implementations. Therefore, we have the flexibility provided by the use of software to describe regular expressions, and the performance reached when the final product is a hardware implementation of the system.