Diseño e implementación de arquitecturas para estructuras paralelas

Abstract

Este trabajo de investigación explora el diseño e implementación de arquitecturas paralelas que permiten el procesamiento en paralelo de datos. Se consideró, como caso de estudio, el procesamiento en tiempo real del algoritmo del filtro de partículas para aquellas aplicaciones que requieren miles de ellas. En estos casos el algoritmo presenta un cuello de botella en el tiempo de ejecución debido al remuestreo, la única operación del algoritmo cuyo procesamiento no puede ser paralelizado en forma directa. El estudio tuvo como objetivos la revisión bibliográfica sobre los algoritmos de remuestreo e implentación del filtro de partículas y por último la proposición de arquitecturas digitales para un elemento de procesamiento para luego considerar arquitecturas con procesamiento distribuido. Se revisionaron las estrategias de paralelización del algoritmo de remuestreo y se llevó acabo una evaluación cualitativa y cuantitativa del comportamiento de las mismas. La estrategia seleccionada para las arquitecturas propuestas es el remuestreo distribuido que se basa en la distribución del remuestreo en grupos de partículas. De la evaluación se concluye que si se aumenta la cantidad de partículas por grupo se reduce el error en la estimación pero no sucede lo mismo si se aumenta la cantidad de grupos de igual cantidad de partículas. Se propusieron tres arquitecturas digitales basadas en el remuestreo distribuido. Las dos primeras arquitecturas se basan en el modelo computacional Dataflow y la tercera arquitectura es un arreglo de procesadores de propósito general que integran una arquitectura Single Instruction Multiple Data (SIMD). El primer diseño prioriza la tasa de procesamiento mientras que los otros dos el área de silicio requerida. Para reducir el área del elemento de procesamiento se recurrió a la multiplexación en tiempo de ciertos recursos computacionales. Se realizó un análisis comparativo en términos de tiempo de ejecución y área de silicio de las arquitecturas propuestas. Se observa que el multiplexado en tiempo de recursos resulta exitosa en la reducción del área total. Por otra parte a igual número de grupos de procesamiento instanciados resultará conveniente el Diseño 1 si se prioriza la tasa de procesamiento y el Diseño 2 si la prioridad es minimizar el área de silicio. El Diseño 3 no presenta ventaja respecto al Diseño 1 a pesar de disponer de un diseño regular y un elemento de procesamiento más versátil.

This research work explores the design and implentation of digital architectures that allows parallel data processing. The particle filtering in real time is considered as case study specially for those applications that requires thousands of particles. In those cases the algorithm presents a bottle neck in the execution time of the filter due to the resampling operation which can not be parallelized in a straight way. The study had as objectives the bibliographic revision of resampling algorithms and particle filter implementation and the proposition of digital architectures for processing elements that integrate a distributed processing architecture. The bibliographic revision of strategies to parallelize resampling algorithms was carried out. Further a quantitative and qualitative evaluation of the strategies was made. The distributed resampling strategy was choosen for the architecture implementations. This strategy is based on the distribution of the resampling operation into groups of particles. From the evalution it is concluded that: the estimation error of the filter is improved by increasing the number of particles per group. However, increasing the number of groups with equal quantity of particles does not reduce the error estimation. Three digital architectures were proposed based on distributed resampling. The two first architectures are based on the dataflow computational model and the third one is an array of general purpose processors that conforms a Single Instruction Multiple Data architecture (SIMD). First design is focused on maximizing the data processing rate meanwhile the two other designs are focused on reducing the required silicon area. In order to reduce the silicon area a time multiplexing of hardware resources was implemented. A comparison in terms of execution time and silicon area was carried out for the three proposed architectures. From this analysis is possible to observe taht the time multiplexing of hardware resources was successful in reducing the silicon area. Comparing Design 1 and Design 2 it is concluded that: for an equal number of processing groups instantiated Design 1 results more appropiate when data processing rate is important meanwhile Design 2 is the best option when the design goal is to reduce the silicon area. Finally Design 3 does not presents any advantage compared to Design 1 despite its more versatile processing element and its regular design.