Los algoritmos de procesamiento de cadenas son a menudo difíciles de paralelizar, pero ha habido cierto éxito. Por ejemplo, en [1], Zhao et. Alabama. muestra cómo los DFA (coincidencia de patrones, compresión, análisis, etc.) se pueden realizar en paralelo.
De mi lectura de la literatura, los algoritmos de procesamiento secuencial de cadenas son sustancialmente más avanzados que sus equivalentes paralelos (por ejemplo, matrices de sufijos). A menudo tienen una mejor eficiencia de trabajo y complejidad de tiempo. Sin embargo, suponiendo que tenga un buen algoritmo paralelo para su problema, debería mapearse perfectamente a una GPU.
Espero que la falta de buenos algoritmos paralelos para el procesamiento de cadenas se deba simplemente a la negligencia de la comunidad CS, y que con el tiempo se desarrollarán nuevos enfoques.
- ¿Por qué las listas enlazadas son más convenientes que las matrices en el dominio de la computación simbólica?
- ¿Por qué falla este método para encontrar la enésima posición de un nodo en una lista vinculada?
- ¿Hay algún algoritmo de ordenación que funcione en el orden de n?
- ¿Has visto algún trabajo hacia el cierre transitivo de la alineación de secuencias y las matrices de sustitución?
- ¿Cuáles son las partes fáciles de la informática y cuáles son las partes difíciles?
[1] Desafiando el ” Vergonzosamente secuencial ”:
Paralelización de computaciones basadas en máquinas de estado finito a través de la especulación basada en principios. Zhijia Zhao (Colegio de William y Mary); Bo Wu (Colegio de William y Mary); Xipeng Shen (Colegio de William y Mary). ASPLOS 14.
