Optimización de Fusión Scan-Scatter en Compiladores de Lenguajes Paralelos

La eficiencia en sistemas de computación paralela de alto rendimiento a menudo se ve limitada por el movimiento de datos entre la memoria y las unidades de procesamiento. La fusión de operaciones, también conocida como 'deforestación' en la literatura funcional, es una técnica de optimización de compiladores que aborda este problema fundamental al combinar múltiples operaciones de procesamiento de datos en una sola, eliminando la necesidad de almacenar resultados intermedios en memoria. Esto permite a los ingenieros estructurar programas de forma modular y abstracta sin incurrir en penalizaciones de rendimiento, un principio clave en el diseño de lenguajes de programación paralela.

En el contexto de lenguajes de programación data-parallel como Futhark, la fusión es crucial para alcanzar un rendimiento óptimo. Este artículo se centra en extender la 'álgebra de fusión' para incluir la combinación de operaciones de 'scan' (como sumas de prefijos) y 'scatter' (actualizaciones paralelas en memoria), un patrón común en algoritmos de filtrado y particionamiento. La motivación es evitar la materialización de arrays intermedios grandes, como los offsets calculados por un scan, que luego son consumidos por un scatter, lo que resulta en un uso ineficiente del ancho de banda de memoria.

Arquitectura del Sistema

La optimización de fusión en Futhark se implementa a nivel del Intermediate Representation (IR) del compilador. Inicialmente, la fusión map-map es un caso sencillo donde la salida de un map se convierte directamente en la entrada de otro, permitiendo la combinación de sus funciones lambda. La fusión horizontal combina operaciones paralelas sobre la misma entrada. El desafío principal surge con la fusión scan-scatter, ya que tradicionalmente no se considera una relación productor-consumidor fusible debido a la naturaleza de las dependencias.

La solución propuesta para scan-scatter involucra una refactorización del IR. En lugar de tener 'scatter' como una primitiva separada, se expresa en términos de 'acumuladores'. Un 'scatter xs is vs' se traduce internamente a una operación 'with_acc' que envuelve un 'map2' que realiza 'update_acc' en los índices 'is' con los valores 'vs'. Esta abstracción permite que el caso scan-scatter se subsuma bajo el caso scan-map, donde el resultado del scan se pasa a una función 'g' que luego realiza las actualizaciones del acumulador. La implementación de 'scan' en Futhark utiliza un 'decoupled lookback scan' en GPU y CPU para eficiencia. La clave es que el 'map2' dentro del 'with_acc' puede fusionarse con el 'scan' previo, eliminando la necesidad de materializar el array de offsets intermedio. Para el cálculo del 'filter_size', se utiliza un segundo 'scatter' que escribe el último elemento del array de offsets en una posición específica (índice 0 de un array de un solo elemento), que luego se recupera, evitando la materialización completa del array de offsets.

map (\y -> y + 2) (map (\x -> x * 2) xs)
=> map (\x -> (x * 2) + 2) xs

def filter [n] 'a (p: a -> bool) (as: [n]a) : []a =
  let keep = map (\a -> if p a then 1 else 0) as
  let offsets1 = scan (+) 0 keep
  let scratch = copy as
  let res =
    scatter scratch
      (map2 (\i k -> if k == 1 then i - 1 else -1) offsets1 keep)
      as
  let filter_size = if n == 0 then 0 else last offsets1
  in take filter_size res

def maposcanomap [n] 'a 'b 'c 'd
  (as: [n]a)
  (f: a -> (b, c))
  (op: b -> b -> b)
  (ne: b)
  (g: b -> c -> d) : [n]d =
  let (bs, cs) = unzip (map f as)
  let bs' = scan op ne bs
  let ds = map2 g bs' cs
  in ds

Fundamentos Teóricos

El concepto de fusión de programas tiene raíces profundas en la investigación de lenguajes funcionales y la optimización de compiladores, a menudo referido como 'deforestación'. Este término fue acuñado por Wadler en su paper "Deforestation: Transforming Programs to Eliminate Intermediate Trees" (1988), que describe cómo eliminar estructuras de datos intermedias generadas por funciones de orden superior. La idea central es que las transformaciones de programas pueden evitar la construcción explícita de estructuras de datos que solo se usan una vez y luego se descartan, mejorando así el rendimiento y reduciendo el consumo de memoria.

La optimización de scan-scatter se conecta con los principios de programación data-parallel y la eficiencia de algoritmos como el 'prefix sum' (scan con operador de suma), que es un pilar en la computación paralela. El uso de scans para calcular índices para operaciones de scatter es un patrón bien conocido en la implementación de algoritmos paralelos como el filtrado o la compactación de arrays, tal como se describe en la literatura sobre algoritmos paralelos eficientes para GPUs y CPUs multi-core. La dificultad de fusionar scan y scatter radica en las dependencias de control y datos, un problema que la solución de Futhark aborda mediante una abstracción de bajo nivel que alinea estas operaciones con un modelo de fusión más general, similar a cómo los compiladores de lenguajes funcionales buscan eliminar estructuras intermedias para mejorar la eficiencia.