PDF de programación - Algoritmos paralelos para la identificación de cadenas de flujos de datos usando hardware reconfigurable

Tabla de contenido

Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.
2. Problema del reconocimiento de cadenas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1. Tipos de procesamiento para el reconocimiento de cadenas . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Reconocimiento de cadenas para la seguridad de redes informáticas . . . . . . . . . . . . . . . . .
3. Algoritmos para el reconocimiento de cadenas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1. Métodos de búsqueda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. Algoritmos con búsqueda por prefijo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1. Morris-Pratt (MP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2. Knuth-Morris-Pratt (KMP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3. Algoritmos con búsqueda por sufijo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1. Booyer-More (BM) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2. Wu-Manber (WM) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4. Algoritmos basados en autómatas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.1. Aho-Corasick (AC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.2. Expresiones regulares (RegExp) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5. Algoritmos con búsqueda por factor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5.1. Backward-Dawg-Matching (BDM) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6. Conclusiones sobre los algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4. Potencialidades de los FPGAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1. Arquitectura general de los FPGAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1. Arquitectura interna de los bloques programables . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.2. Arquitectura interna de las slices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. Capacidad de lógica reconfigurable y prestaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3. FPGA vs GPP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4. Capacidad de procesamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5. Utilización del área programable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6. Prestaciones de las arquitecturas de los dispositivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5. Algoritmos paralelos para el reconocimiento de cadenas en FPGA . . . . . . . . . . . . . . . . . . . . . . . .
5.1. Paralelismo aportado por los FPGAs al reconocimiento de cadenas . . . . . . . . . . . . . . . . . .
5.2. Autómatas en FPGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1. Aho-Corassick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.2. Expresiones regulares en FPGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3. Shift-and-compare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4. CAM y comparadores discretos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5. Hashing para reconocimiento de cadenas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.1. Arquitectura basada en técnicas de hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.2.
Filtros Bloom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6. Estrategias para la reducción de hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1. Recursos compartidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2. Prefiltrado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3. Detección y corrección del desalineamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.4. Uso de las prestaciones de los dispositivos FPGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7. Estrategias para el aumento de la capacidad de procesamiento . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1. Arquitecturas multibyte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2
3
4
5
6
7
7
8
8
9
9
9
10
11
12
12
13
14
14
15
15
15
17
18
19
20
20
21
22
22
23
25
27
27
29
29
30
31
31
32
33
33
34
34

7.2. Predecodificación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.3. Particionamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.4. Fan-out Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8. Compilación de diseño en FPGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9. Taxonomía y algunas consideraciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10. Propuesta para la disminución del costo en arquitectura multibyte . . . . . . . . . . . . . . . . . . . . . . . .
11. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.1. Análisis crítico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11.2. Posibles áreas de investigación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Referencias bibliográficas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Lista de figuras

1. Tipos de búsqueda, la parte sombreada indica los caracteres del texto que cotejan con un los de la cadena. . . . . . . .
2. Autómatas no determinístico NFA y determinístico DFA, el estado 0 es el estado inicial, los estados sombreados

son los estados finales [33]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. Autómata AC que reconoce las cadenas “GAT” y “CG”, una transición suplementaria se muestra con líneas

discontinuas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .

4. Autómata Factor Oracle, la palabra queda descrita por el autómata de forma inversa [33].
5. Arquitectura general de un FPGA, se muestra el arreglo de los diferentes tipos de bloques lógicos sobre la oblea

de silicio [45]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6. Arquitectura interna de un CLB de la famila Spartan-3, cada Slice recibe dos entradas de 4 bits cada una, CIN y

COUT son las entradas y salidas de la lógica dedicada al acarreo de bits [45]. . . . . . . . . . . . . . . . . . . . . . . . . . . .

7. Arquitectura interna de un Slice de Spartan-3, G y F, son las entradas de 4 bits a cada LUT correspondiente, la

salida se obtiene de el puerto de salida de cada flip-flop o directamente [45].

. . . . . . . . . . . . . . . . . . . . . . . . . . .

8. Computador de Von-Neumman, se compone de tres partes fundamentales, Memoria, Unidad de Control, Unidad

Aritmética Lógica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9. LUT como registro de desplazamiento, el tamaño del registro se configura por la entrada estándar de las LUT, la

salida es por D, MSC15 porporciona una salida para concatenar con otros registros [46]. . . . . . . . . . . . . . . . . . . .

10. Máquina Finita Estados, los estados son codificados como números binarios, la lógica del próximo estado se

encarga de decodificar el estado actual y generar el próximo estado a partir de la entrada.

. . . . . . . . . . . . . . . . . .
11. Máquina de reconocimiento de la expresión regular, ((a|b)∗)(cd) [35]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12. Bloques básicos: (a) un solo caracter, (b) r1|r2, (c) r1r2, (d) r1∗ [35].
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13. Arquitectura shift-and-compare: detecta la cadena CAT, a cada comparador se le asigna un pipeline con un

tamaño de acuerdo a la posición del caracter en la palabra [5]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14. (a) Memoria CAM, las pala