Modelado y mejora de localidad en códigos irregulares

Abstract

En este trabajo se presenta un modelo para determinar y mejorar la localidad asociada a la ejecución de códigos irregulares de álgebra matricial dispersa, El conjunto de códigos para los cuales el modelo es aplicable es el constituido por códigos que contiene indirecciones regidas por una matriz dispersa, para las que el agrupamiento de las entradas sobre el patrón de la matriz está relacionado con el grado de localidad, tanto espacial como temporal, de los accesos. Este conjunto engloba, entre otros, al producto de una matriz dispersa por un vector denso, al cálculo de la traspuesta de una matriz dispersa y al producto de una matriz dispersa por una matriz densa. El modelado de localidad parte del análisis de un conjunto de 28 parámetros dependientes del patrón de la matriz dispersa que rige los accesos indirectos. Mediante técnicas de estadística multivariante se ha reducido la dimensionalidad del espacio de localidad de 28 a 2 dimensiones mediante la selección de los dos parámtros estadísticamente más relevantes: coincidencias a nivel de entradas y coincidencias a nivel de bloques. Sobre la base de los dos parámetros seleccionados, proponeos cuatro funciones de distancia que, evaluadas sobre pares de filas (o columnas) de la matriz dispersa, cuantifican el grado de localidad en los accesos irregulares que dichas filas o columnas direccionan. El modelo de localidad desarrollado a partir de las funciones de distancia obtenidas presenta entre sus características las siguientes: . Puede ser aplicado tanto para la predicción de la localidad que presentan algunos accesos irregulares como para la optimización de dichos accesos por medio de permutaciones de la matriz dispersa que minimicen la localidad predicha. Para la solución del problema de optimización se han utilizado técnicos heurísticas basadas en la construcción de grafos. . El modelo puede ser aplicado a cualquier tipo de matriz dispersa,