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.
| Identifer | oai:union.ndltd.org:uns.edu.ar/oai:repositorio.bc.uns.edu.ar:123456789/4423 |
| Date | 29 December 2015 |
| Creators | Pasciaroni, Alejandro |
| Contributors | Julián, Pedro, Mandolesi, Pablo Sergio |
| Publisher | Universidad Nacional del Sur |
| Source Sets | Universidad Nacional del Sur |
| Language | Spanish |
| Detected Language | Spanish |
| Type | Electronic Thesis or Dissertation, Text |
| Rights | 2 |
Page generated in 0.0026 seconds