La optimización del uso de memoria es un problema fundamental en la computación, especialmente crítico en entornos con recursos limitados o donde las asignaciones dinámicas de memoria son costosas. Este trabajo aborda la eliminación de asignaciones redundantes en el heap en el contexto de MLIR (Multi-Level Intermediate Representation), un framework de compilación utilizado para hardware heterogéneo, incluyendo aceleradores.
El problema se agudiza en arquitecturas como CPUs embebidas, DSPs o aceleradores personalizados, donde el acceso a la memoria principal es lento o la asignación de heap está restringida. Incluso en sistemas con heap disponible, las asignaciones pequeñas pueden degradar el rendimiento debido a la fragmentación y la presión sobre la caché. La solución propuesta es un planificador estático que consolida múltiples buffers en una única arena de memoria pre-asignada, calculando su layout en tiempo de compilación. Esto transforma asignaciones dinámicas en vistas de memoria con sobrecarga cero, un patrón de optimización clásico en compiladores para sistemas embebidos.
Arquitectura del Sistema
El planificador estático de memoria se implementa como un pase FunctionOpInterface en MLIR, procesando el cuerpo de cada función en seis pasos. Primero, se recolectan los memref.alloc candidatos y sus correspondientes memref.dealloc utilizando análisis de alias. Luego, se construyen descriptores para cada candidato, incluyendo tamaño, alineación, y los puntos de inicio y fin de su vida útil (timeStart, timeEnd), obtenidos mediante un escaneo de bloque O(n+m).
El corazón del planificador es un algoritmo de empaquetamiento de memoria, que puede ser una estrategia secuencial trivial o un algoritmo best-fit consciente de la superposición de vidas útiles. Este algoritmo recibe los descriptores y asigna offsets de bytes dentro de la arena. Una vez calculados los offsets, se crea una única memref<Nxi8> para la arena (o se utiliza una arena pasada como argumento de función). Finalmente, cada memref.alloc original se reemplaza por un memref.view que apunta a la sección correspondiente de la arena, y todos los memref.dealloc asociados se eliminan.
La estructura de datos central es AllocationCandidate, que encapsula el memref.alloc, sus deallocs potenciales (identificados a través de cadenas de alias), el offset de byte, tamaño y alineación. El análisis de alias se delega completamente a BufferViewFlowAnalysis, una infraestructura unificada de MLIR que modela el flujo de buffers a través de operaciones como arith.select, scf.if/scf.for, ramas cf y operaciones de vista (memref.view). Esta análisis utiliza interfaces como BufferViewFlowOpInterface, RegionBranchOpInterface, BranchOpInterface y ViewLikeOpInterface para una cobertura exhaustiva. La seguridad de la eliminación de deallocs se garantiza mediante un 'reverse-alias guard', que verifica que todos los allocs que un dealloc podría liberar estén gestionados por la arena.
Flujo de Planificación de Memoria Estática
- 1 Recolectar Candidatos Identificar `memref.alloc` y sus `memref.dealloc` asociados vía análisis de a...
- 2 Construir Descriptores Calcular (size, alignment, timeStart, timeEnd) para cada candidato.
- 3 Ejecutar Planificador Aplicar algoritmo (ej. best-fit) para asignar offsets de memoria.
- 4 Crear Arena Asignar una única `memref<Nxi8>` para la arena total.
- 5 Reescribir Operaciones Reemplazar `memref.alloc` con `memref.view` y eliminar `memref.dealloc`.
| Capa | Tecnología | Justificación |
|---|---|---|
| data-processing | MLIR (Multi-Level Intermediate Representation) | Framework de compilación que proporciona la IR y las herramientas de análisis para la optimización de memoria. |
| data-processing | BufferViewFlowAnalysis | Análisis unificado de alias para rastrear el flujo de buffers a través de diferentes tipos de operaciones en MLIR, esencial para identificar `deallocs` y garantizar la seguridad. vs DFS manual sobre el grafo use-def |
| data-processing | bestFitMemoryPlanner | Algoritmo de empaquetamiento de memoria que reutiliza slots de arena para asignaciones con vidas útiles no superpuestas. vs trivialMemoryPlanner (empaquetamiento secuencial) |
// Before: three separate heap allocations
%a = memref.alloc() : memref<1024xf32> // 4096 bytes
%b = memref.alloc() : memref<512xf32> // 2048 bytes
memref.dealloc %a : memref<1024xf32>
memref.dealloc %b : memref<512xf32>
// After: one arena, two views
%arena = memref.alloc() : memref<6144xi8>
%a = memref.view %arena[0][] : memref<6144xi8> to memref<1024xf32>
%b = memref.view %arena[4096][]: memref<6144xi8> to memref<512xf32>
// ... uses of %a and %b ...
memref.dealloc %arena : memref<6144xi8>Fundamentos Teóricos
El problema de la asignación estática de memoria y la reutilización de slots de memoria es un área bien estudiada en la optimización de compiladores, con raíces en la asignación de registros y la planificación de memoria para sistemas embebidos. Conceptos como el 'interval graph coloring' para la asignación de registros, donde los registros se asignan a variables cuyas vidas útiles no se superponen, son directamente aplicables a la asignación de slots de memoria. Algoritmos como 'first-fit' o 'best-fit' para la gestión de memoria dinámica tienen sus análogos en la planificación estática, donde el objetivo es minimizar el tamaño total de la arena.
La idea de consolidar múltiples asignaciones en una única región de memoria y acceder a ellas a través de 'views' o 'pointers' es un patrón clásico. Por ejemplo, el algoritmo 'minimalloc' es un ejemplo de un planificador de memoria que busca minimizar el tamaño total de la arena. Aunque el artículo no cita un paper específico, los principios subyacentes se encuentran en trabajos fundamentales sobre optimización de compiladores y sistemas operativos, como los de Aho, Sethi y Ullman en 'Compilers: Principles, Techniques, and Tools' (1986), que discuten la optimización del uso de memoria y la asignación de recursos en tiempo de compilación.