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
Year of publication: 1996
Volume: 29
Issue: 3
Pages: 28-37
Type: Article
More publications in: Informática y automática: revista de la Asociación Española de Informática y Automática
Abstract
A large number of algorithms have been obtained by means of the divide and conquer strategy. Among them we find those for the orthogonal transforms, bitonic ordering, polynomic evaluation and for the solution of tridiagonal systems. In this work we present a unified formulation of these algorithms which facilitates their vectorization. The algorithms are described in terms of index-digit permutations, each one of which has a direct implementation on the vector computer. Thus, for instance, we define index-digit permutations for the description of the data flow from the memory to the segmented units of the processor and the regrouping of the data within these units. This formulation is applied to fast Walsh and Haar transforms.