Técnicas de optimización de la localidad para códigos irregulares sobre arquitecturas multiprocesador y multithreading

Zusammenfassung

En esta tesis se han propuestos diversas técnicas de optimización de la localidad en códigos irregulares de álgebra metricial dispersa. Las propuestas se han realizado para diferentes arquitecturas paralelas. Los códigos de álgebra matricial dispersa se encuentran presentes en gran cantidad de problemas reales. Su baja localidad, junto con el carácter poco predecible en los accesos que generan, provocan que su aprovechamiento dela jerarquía de memoria sea escaso. Las técnicas propuestas reordenan las estructuras de datos (matrices dispersas) que determinan la localidad del código bajo estudio guiadas por un modelo de localidad desarrollado previamente por miembros de nuestro grupo de investigación. Este modelo se utilizó en trabajos anteriores para guiar técnicas de mejora de la localidad en sistemas monoprocesador. En dicho modelo se proponen cuatro funciones de distancia que, evaluadas sobre pares de filas (o columnas) de la matriz dispersa considerada, cuantifican el grado de localidad en los accesos irregulares que dichas filas o columnas direccionan. En esta tesis mostramos que el modelo de localidad es lo suficientemente general como para permitir la aplicación de las dientes técnicas de reordenamiento a matrices dispersas sin limitaciones en las características de sus patrones de dispersidad, así como a diferentes sistemas multiprocesador (de memoria compartida y distribuida) y a arquitecturas multithreading.