Dynamic Core Allocation for Malleable Jobs with Unknown Speed-up Parameters

Resumen Técnico: Asignación Dinámica de Núcleos para Trabajos Maleables con Parámetros de Aceleración Desconocidos

Planteamiento del Problema
Este artículo aborda el problema de la asignación dinámica de recursos en sistemas de computación multinúcleo que gestionan un flujo de trabajos "maleables". A diferencia de los trabajos "moldables", donde el número de núcleos asignados es fijo tras su llegada, los trabajos maleables permiten la redistribución dinámica de la capacidad de procesamiento durante su ejecución. El sistema consta de un número fijo de núcleos idénticos ($c$) y dos clases de trabajos observables. Cada clase de trabajo se caracteriza por una función de aceleración (speed-up) distinta y desconocida $s(z; p)$, donde $z$ es la capacidad asignada y $p$ es un parámetro desconocido que rige el grado de paralelizabilidad.

El objetivo es minimizar el número medio de trabajos en el sistema a largo plazo (equivalentemente, el tiempo de respuesta medio en estado estacionario). Existe un compromiso fundamental: asignar más núcleos acelera la finalización del trabajo, pero debido a los rendimientos decrecientes (por ejemplo, la Ley de Amdahl), la ganancia marginal disminuye a medida que se asignan más núcleos. Si bien se conocen políticas óptimas para tales sistemas cuando los parámetros de aceleración son fijos y conocidos (específicamente, la política EQUI para el reparto igualitario dentro de las clases y una fracción óptima entre clases derivada mediante Procesos de Decisión de Markov), este artículo aborda el escenario en el que los parámetros $p_1$ y $p_2$ son desconocidos y deben aprenderse a partir de datos operativos. Esta brecha está motivada por aplicaciones modernas como el entrenamiento de aprendizaje automático a gran escala en GPUs en la nube, donde las características de aceleración pueden variar debido a cargas de trabajo evolutivas o actualizaciones de hardware, lo que hace que las suposiciones estáticas sean poco realistas.

Metodología
Los autores proponen un marco iterativo de aprendizaje y control que alterna entre la estimación de parámetros y la optimización de la política.

1. Modelo del Sistema:

   • Los trabajos llegan mediante un proceso de Poisson con tasa $\lambda$. Los requisitos de servicio están distribuidos exponencialmente con tasa $\mu$.
   • Los trabajos pertenecen a la Clase 1 (probabilidad $\alpha$) o a la Clase 2 (probabilidad $1-\alpha$).
   • La función de aceleración $s(z; p)$ es lineal para $z \le 1$ y cóncava/no decreciente para $z > 1$. Se consideran dos modelos específicos: la Ley de Amdahl y un modelo de ley de potencia ($s(z; p) = \max\{z, 1\}^p$).
   • La política de asignación $\pi$ determina la fracción de núcleos asignados a los trabajos de la Clase 1 basándose en el estado actual del sistema $(n^{(1)}, n^{(2)})$. Dentro de cada clase, los núcleos se comparten equitativamente (política EQUI).

2. Estimación de Parámetros (Máxima Verosimilitud):

   • El núcleo del mecanismo de aprendizaje es un Estimador de Máxima Verosimilitud (MLE) basado en los tiempos de inter-salida dependientes del estado.
   • El proceso de salida para cada clase se modela como un proceso de Poisson dependiente del estado. La tasa de salida instantánea $\delta^{(i)}$ depende del número de trabajos $n^{(i)}$, los núcleos asignados $c^{(i)}$ y el parámetro desconocido $p_i$.
   • La función de verosimilitud se construye descomponiendo los intervalos de inter-salida en subintervalos donde el estado del sistema (y, por tanto, la tasa de salida) permanece constante. La log-verosimilitud se deriva explícitamente como una función de los tiempos de salida observados y la secuencia de estados del sistema.
   • Los autores demuestran que, bajo una política de asignación fija, estos MLE son fuertemente consistentes (convergen casi seguramente a los parámetros reales) a medida que aumenta el número de salidas observadas. Esta prueba se basa en la estructura regenerativa del sistema de colas y la continuidad Lipschitz de la función de aceleración con respecto a $p$.

3. Optimización de la Política (MDP):

   • Una vez estimados los parámetros, la política de asignación óptima se calcula resolviendo la ecuación de optimalidad de Bellman para un Proceso de Decisión de Markov (MDP).
   • El espacio de estados se define por el número de trabajos en cada clase. El espacio de acciones es la fracción de núcleos asignados a la Clase 1.
   • La función de coste es el número total de trabajos en el sistema. El MDP se resuelve mediante iteración de valor tras uniformizar el proceso de tiempo continuo en uno de tiempo discreto.

4. Algoritmos de Aprendizaje:
   El artículo propone dos algoritmos específicos que implementan este bucle:

   • Algoritmo 1a: Utiliza únicamente los datos recopilados durante la ventana de observación más reciente (definida por un número fijo de salidas $N_k$) para actualizar las estimaciones. Esto permite la adaptabilidad a entornos no estacionarios donde los parámetros pueden cambiar con el tiempo.
   • Algoritmo 1b: Utiliza todos los datos acumulados desde el tiempo $t=0$ para actualizar las estimaciones. Aunque esto suele producir una convergencia más rápida y una mayor precisión en entornos estacionarios, es menos adaptable a cambios en los parámetros.

Contribuciones Clave

• Extensión de los Modelos de Trabajos Maleables: El artículo extiende los modelos clásicos de asignación de núcleos para trabajos maleables al introducir un mecanismo de aprendizaje para parámetros de aceleración desconocidos, yendo más allá de la suposición de conocimiento a priori.
• Inferencia Estadística en Sistemas de Colas: Desarrolla un procedimiento específico de MLE para estimar las características de paralelización utilizando tiempos de inter-salida dependientes del estado, demostrando la consistencia fuerte bajo políticas fijas.
• Marco de Aprendizaje Integrado: Propone y analiza dos algoritmos iterativos (1a y 1b) que combinan la estimación estadística con la actualización de políticas basada en programación dinámica.
• Validación Numérica: A través de extensos experimentos numéricos, el artículo demuestra que los métodos propuestos logran estimaciones de parámetros precisas y un rendimiento del sistema cercano al óptimo tras periodos de observación relativamente cortos. También destaca un problema de "cuasi-identificabilidad", donde estimar los parámetros para trabajos con baja paralelización (bajo $p$) es más difícil que para trabajos altamente paralelizables.

Resultados

• Convergencia: Los experimentos numéricos confirman que los estimadores convergen a los parámetros reales. El Algoritmo 1b generalmente converge más rápido que el 1a en entornos estacionarios debido al uso de todo el historial de datos.
• Adaptabilidad: En un experimento no estacionario donde los parámetros de aceleración cambian en puntos temporales específicos, el Algoritmo 1a rastrea con éxito los parámetros evolutivos y ajusta la política de asignación en consecuencia, demostrando su utilidad en entornos dinámicos.
• Rendimiento: Las políticas aprendidas logran tiempos de respuesta medios cercanos al óptimo teórico que se alcanzaría si los parámetros reales fueran conocidos desde el principio.
• Asimetría en la Estimación: Los resultados indican que estimar el parámetro para la clase con menor paralelización (menor $p$) es inherentemente más difícil y lento de converger que para la clase con mayor paralelización, debido a la débil sensibilidad de la función de aceleración ante los cambios en la asignación de núcleos en ese régimen.

Significado
El artículo reclama su importancia al abordar una brecha crítica en la literatura: la suposición de que las funciones de aceleración son conocidas y estáticas. Al proporcionar un marco para aprender estos parámetros en línea, el trabajo ofrece una solución práctica para entornos de computación modernos y dinámicos (como el entrenamiento de IA en la nube) donde la eficiencia de los recursos es primordial pero las características del sistema son inciertas. Los autores señalan que, aunque el marco se extiende naturalmente a más de dos clases de trabajos, la complejidad computacional para resolver las ecuaciones de Bellman asociadas aumenta significativamente, destacando un compromiso entre la expresividad del modelo y la tratabilidad. El trabajo sienta las bases para futuras investigaciones sobre entornos no estacionarios, distribuciones de tiempo de servicio generales y métodos de aproximación escalables para sistemas de alta dimensión.