Algoritmos paralelos para la solución de problemas de optimización discretos aplicados a la decodificación de señales

Resumen

En diversas aplicaciones prácticas cada vez es más frecuente la presencia de problemas de optimización que involucran variables que deben tomar valores discretos, Debido a su naturaleza combinatoria, los problemas de optimización discretos presentan por lo general una complejidad computacional exponencial, y por tanto son mucho más complicados de resolver que los problemas continuos. El trabajo descrito en esta tesis se ha centrado en el estudio y solución al problema de encontrar el punto de una retícula más cercano a un punto dado. Dicho problema puede originarse, entre otras múltiples aplicaciones prácticas, en la detección de señales en sistemas de comunicaciones inalámbricos MIMO (Multiple Input - Multiple Output). Los problemas de optimización discretos no pueden abordarse con métodos de convergencia rápida basados en derivadas. En su lugar, la solución se obtiene mediante métodos como Ramificación y Poda, programación dinámica y búsquedas heurísticas. El trabajo presentado ha consistido, en primer lugar, en realizar un amplio estudio del estado del arte de los métodos de Búsqueda Directa (que son métodos de optimización no basados en derivadas) y de los métodos Sphere-Decoding (pertenecientes al esquema de Ramificación y Poda). En segundo lugar, se ha abordado la paralelización de estos métodos dirigida a distintas arquitecturas, bien sea arquitecturas con memoria compartida, memoria distribuida y esquemas híbridos; además de explorar, en el caso de la Búsqueda Directa, variantes asíncronas de paralelización. Adicionalmente se proponen mejoras en los propios algoritmos secuenciales. Se diseñaron e implementaron diversas variantes de métodos de Búsqueda Directa, las cuales tuvieron buenos resultados en la resolución del Problema Inverso Aditivo de Valores Singulares, pues lograron converger y obtener mejor precisión en la solución que los métodos basados en derivadas tipo Newton. De aquí surgió la idea de aplicar los algoritmos diseñados al problema de mínimos cuadrados discretos. Los resultados de la Búsqueda Directa en la decodificación de señales son alentadores, pues lograron alcanzar en la generalidad de las experimentaciones realizadas la solución óptima empleando tiempos menores que otras variantes conocidas de algoritmos de solución exacta. Por su parte, en los métodos Sphere-Decoding, se realiza un aporte al proponer el uso de la descomposición de valores singulares (SVD) para obtener radios que estrechen un poco más el espacio de búsqueda de la solución. Las rutinas logradas, tanto secuenciales como paralelas, presentan la característica de ser portables. Las librerías están diseñadas e implementadas con un alto grado de abstracción y encapsulamiento de modo que puedan ser usadas no sólo para solucionar el problema en cuestión, sino que permiten abordar cualquier problema de optimización numérica con estos métodos.