Selección óptima de rutinas de álgebra lineal dispersa usando aprendizaje automático

Abstract

La resolución de sistemas triangulares con matrices dispersas (SpTrSv, Sparse Triangular Solve) es fundamental en computación científica. Existen múltiples algoritmos que implementan esta operación para GPU con rendimientos muy variables según la estructura de cada matriz, sin que ninguno sea óptimo universalmente. En este trabajo se desarrollan las bases para un sistema de selección automática del mejor algoritmo mediante aprendizaje automático, que minimice el tiempo total de preprocesamiento, predicción y ejecución. Se evaluaron 17 modelos de diferentes familias de aprendizaje automático: árboles de decisión (Random Forest, Extra Trees), boosting (Gradient Boosting, XGBoost, LightGBM, CatBoost), métodos lineales y redes neuronales. Los modelos se entrenaron con matrices de SuiteSparse usando Optuna para optimizar hiperparámetros. Para evaluar el rendimiento de los modelos se definió una nueva métrica, TAR, que mide el sobrecosto de ejecutar el algoritmo predicho sobre el óptimo. A su vez, se analizaron las características medidas de las matrices, planteándose diferentes subconjuntos de las mismas con distintos balances entre expresividad y complejidad de cálculo. Se propusieron tres nuevas características: distribución por 32 bandas horizontales, índice de Gini y P-ratio. También se desarrolló una técnica de etiquetado que permite identificar las matrices que tienen un comportamiento similar frente a dos algoritmos, evitando penalizar predicciones entre algoritmos equivalentes. Para expandir el conjunto de entrenamiento se implementó un sistema de generación de matrices sintéticas con Redes Generativas Adversarial. El proceso convierte matrices a imágenes de 128 × 128 pixeles donde cada píxel representa densidad de elementos distintos a cero, entrena una red para generar nuevas imágenes, y las expande a matrices dispersas. Se generaron 3500 matrices sintéticas validadas estadísticamente. Los resultados superan ampliamente las líneas base. Para una ejecución de SpTrSv, las elecciones de algoritmos con Gradient Boosting agregaron solo un 4% de diferencia con el tiempo óptimo, ampliamente mejor que el 872% de sobrecosto esperado eligiendo aleatoriamente los algoritmos, con similares resultados en otros escenarios. La evaluación muestra que el enfoque puede generar importantes mejoras en casos de uso típicos, donde se resuelven decenas de sistemas con la misma matriz.