Manejo dinámico de accesos a memoria no lineales para paralelización especulativa

Abstract

El modelo del poliedro es un framework matemático orientado al análisis y transformación de loops particularmente aplicado a la paralelización. Si bien es poderoso, está originalmente limitado a ciclos que pueden ser precisamente analizados en tiempo de compilación. APOLLO (Automatic POLyhedral Loop Optimizer) es un framework que extiende la aplicación de este modelo mediante instrumentación en tiempo de ejecución a códigos que exhiben, por ejemplo, accesos a memoria mediante punteros o indirecciones, permitiendo asi su paralelización. Sin embargo, las condiciones que impone el modelo siguen presentes. En particular, los accesos a memoria deben tener un comportamiento completamente lineal. El trabajo presentado consiste en extender APOLLO de manera que pueda paralelizar loop nests en los que haya accesos a memoria, tanto de lectura como de escritura, no lineales. Esto fue logrado extendiendo el sistema de verificación y adaptandolo dinámicamente según el comportamiento observado durante la instrumentación. La efectividad de las extensiones fue evaluada empíricamente usando benchmarks conocidos.