Resumen Técnico: La Selección Adaptativa de Filas se Encuentra con la Asincronía en el Método Kaczmarz Aleatorio

Planteamiento del Problema

El método de Kaczmarz Aleatorio (RK) es un resolvedor de acción por filas efectivo para problemas de mínimos cuadrados y reconstrucción tomográfica dispersos y de gran escala. Mientras que la selección adaptativa de filas (por ejemplo, mediante muestreo codicioso o ponderado por residuo) acelera la convergencia al priorizar ecuaciones con altos residuos, la ejecución asíncrona permite el paralelismo mediante actualizaciones libres de bloqueos (lock-free); la combinación de estos mecanismos crea un régimen no cubierto por la teoría existente.

Los marcos teóricos actuales asumen o bien un vector de residuo actual (para la selección adaptiva) o bien una distribución de muestreo fija (para el análisis asíncrono). En la práctica, en máquinas de memoria compartida, los trabajadores modifican el vector de residuo de forma concurrente. En consecuencia, los selectores adaptativos operan sobre distribuciones estancadas e imperfectas donde la discrepancia respecto al ideal crece con el número de actualizaciones en vuelo. Este artículo aborda la falta de una medición sistemática sobre cómo se comportan los métodos Kaczmarz de residuo ponderado y de selección codiciosa (greedy) bajo ejecución asíncrona con retrasos de hardware reales.

Metodología

El estudio instrumenta algoritmos Kaczmarz de residuo ponderado y de umbral codicioso (threshold-greedy) a través de 339 ejecuciones en un nodo de 96 núcleos. Los experimentos utilizan una familia de muestreo ponderada por potencia donde la probabilidad de seleccionar la fila $i$ es proporcional a $|r_i|^\ell$. El exponente $\ell$ interpola entre el muestreo uniforme ($\ell=0$) y la regla de Motzkin de residuo máximo ($\ell \to \infty$).

Configuración Experimental:

• Hardware: Un nodo ACES de 96 núcleos (Texas A&M) con hilos vinculados a núcleos (pinned).
• Retrasos: El estancamiento (staleness) se mide mediante brechas realizadas entre el despacho y el compromiso (dispatch-to-commit) en lugar de mediante retrasos sintéticos inyectados.
• Problemas de Prueba: Se utilizaron tres categorías: (1) un sistema denso benigno, (2) problemas tomográficos coherentes en dos escalas, y (3) 16 matrices de la suite SuiteSparse del test de Bai–Wu.
• Semántica de Lectura: Se compararon dos políticas:
  • Lecturas Consistentes: Los trabajadores capturan una instantánea del vector de residuo una vez por paso, tanto para el muestreo como para el cálculo de la actualización.
  • Lecturas Inconsistentes (Vivas): La función de distribución acumulada (CDF) de muestreo se construye a partir de lecturas atómicas en vivo, y el valor específico del residuo se vuelve a leer tras la selección de la fila.
• Validación: La implementación fue validada contra resultados secuenciales publicados y verificada mediante el recálculo de $b - Ax$ al término para asegurar que las divergencias fueran comportamientos numéricos y no condiciones de carrera de datos.

Contribuciones Clave y Hallazgos

1. El Límite de Estabilidad $\ell^*(T)$

El artículo identifica un límite de estabilidad en el plano $(\ell, T)$ (exponente de muestreo vs. número de hilos).

• Observación: A medida que la concurrencia ($T$) aumenta, el sistema tolera un muestreo menos agresivo (un $\ell$ más bajo).
• Mecanismo: Por debajo del límite, un muestreo más agresivo es estrictamente más rápido. Por encima del límite, el muestreador comienza a clasificar la "interferencia" (perturbaciones causadas por $\Theta(T)$ actualizaciones en vuelo) en lugar de la señal, lo que conduce a la divergencia.
• Implicación de Ajuste: El ajuste óptimo es una "carrera hacia un precipicio", donde uno debe seleccionar el $\ell$ más grande que permanezca justo dentro del límite de estabilidad para un $T$ dado.

2. Inestabilidad de la Selección Codiciosa por Umbral

La selección estándar codiciosa por umbral (GRK), que selecciona filas por encima de un corte de residuo, resulta ser incompatible con la ejecución asíncrona de alta concurrencia.

• Resultado: Con $T=96$, el GRK diverge en una fracción de un barrido (sweep) en todos los problemas de prueba, independientemente de la semántica de lectura. La concentración de la selección en los residuos más grandes hace que los trabajadores actualicen repetidamente los mismos vecindarios acoplados, amplificando la interferencia.

3. El Control del Tamaño de Paso como Mecanismo de Recuperación

La sub-relajación (reducir el tamaño del paso $\beta$) puede restaurar la convergencia para configuraciones que divergen con paso completo ($\beta=1$).

• Efectividad: Cada configuración que divergió con $\beta=1$ convergió cuando $\beta \le 0.5$.
• Costo: Esta recuperación incurre en un costo predecible. La penalización en el conteo de barridos es aproximadamente de $1.7\text{--}2.3\times$ mayor que la predicción sincrónica de $1/[\beta(2-\beta)]$, atribuida a una "prima de interferencia asíncrona".

4. Semántica de Modo de Lectura y Riesgo de Cola

Contrario a lo hallado en Jacobi asíncrono, la consistencia de lectura no gobierna el límite de estabilidad principal aquí, pero sí afecta el comportamiento de la cola.

• Divergencia: Las lecturas de instantánea consistente admitieron una divergencia rara, dependiente de la programación (1 en 36 ejecuciones en un problema tomográfico coherente), que las lecturas inconsistentes (vivas) nunca exhibieron.
• Eficiencia: Las lecturas inconsistentes son más económicas por paso (no requieren una copia completa del residuo) y no mostraron fallos de cola en las pruebas comparativas. El artículo concluye que las lecturas inconsistentes son la opción superior por defecto para regímenes de acoplamiento amplio.

5. Discriminadores Estructurales

El límite de estabilidad está estrictamente ordenado por el acoplamiento emparejado medio $\bar{\chi} = E|Q_{ij}|$, donde $Q = AA^\top$.

• Los indicadores espectrales (como las normas de las filas de Gram fuera de la diagonal) y la coherencia del peor caso fallaron en predecir la estabilidad.
• La estabilidad es una carrera entre la velocidad de convergencia y el crecimiento de la interferencia. Los problemas con mayor densidad de acoplamiento requieren un muestreo menos agresivo o un menor número de hilos para permanecer estables.

Significado y Reivindicaciones

El artículo afirma proporcionar el primer estudio sistemático de la selección de filas adaptativa bajo ejecución asíncrona con retrasos reales. Su principal significación radica en definir los límites prácticos de la combinación de estas dos técnicas de aceleración:

1. Ajuste Práctico: Establece que el ajuste de Kaczarc con muestreo adaptativo para el paralelismo no es simplemente maximizar la agresividad de la selección, sino que requiere navegar un precipicio de estabilidad dependiente de la concurrencia.
2. Guía Algorítmica: Demuestra que las reglas codiciosas estándar (GRK) son inestables a escala y que las lecturas inconsistentes son la estrategia de implementación preferida para Kaczarc en memoria compartida.
3. Seguridad de Implementación: Valida que la sub-relajación sirve como un confiable "control de seguridad" para recuperar la convergencia cuando la concurrencia obliga a reducir la agresividad del muestreo.
4. Dirección Futura: Los hallazgos motivan el desarrollo de un muestreador de dos niveles distribuido para desacoplar el estancamiento del muestreo de la estancidad de la iteración, abordando el cuello de botella de muestreo global de $O(m)$ observado en los experimentos.

Los autores mantienen la modestia, señalando que los fenómenos observados son propiedades de la iteración asíncrona en sí, no errores de implementación, y que la comprensión teórica del límite $\ell^*(T)$ y la prima de sub-relajación supercuadrática requiere mayor desarrollo.