Vectorización de los algoritmos divide-y-vencerás
- Amor, Margarita
- Argüello Pedreira, Francisco
- Martín, María J.
- Blanco Heras, Dora
ISSN: 0214-932X
Año de publicación: 1996
Volumen: 29
Número: 3
Páginas: 28-37
Tipo: Artículo
Otras publicaciones en: Informática y automática: revista de la Asociación Española de Informática y Automática
Resumen
Existe un gran número de algoritmos obtenidos mediante la estrategia divide y vencerás, entre los que destacan las transformadas ortogonales, la ordenación bitónica, la evaluación polinómica y la resolución de sistemas tridiagonales, entre otros. En este trabajo presentamos una formulación unificada de estos algoritmos que facilita su vectorización. Los algoritmos se describen en términos de las permutaciones índice-dígito, cada una de las cuales tiene una implementación directa sobre el computador vectorial. Así, por ejemplo, definimos permutaciones índice-dígito para describir el flujo de datos desde la memoria a las unidades segmentadas del procesador y el reagrupamiento de los datos dentro de estas unidades. Esta formulación se aplica a las transformadas rápidas de Walsh y de Haar.