Resumo Técnico: Seleção Adaptativa de Linhas Encontra a Assincronia no Kaczmarz Aleatorizado

Declaração do Problema

O método Kaczmarz Aleatorizado (RK) é um solver de ação de linha eficaz para problemas de mínimos quadrados esparsos e reconstrução tomográfica de grande escala. Embora a seleção adaptativa de linhas (ex: seleção gananciosa ou ponderada pelo resíduo) acelere a convergência ao priorizar equações de alto resíduo, e a execução assíncrona permita o paralelismo via atualizações sem bloqueio (lock-free), a combinação desses mecanismos cria um regime não coberto pela teoria existente.

Os frameworks teóricos atuais assumem ou um vetor de resíduo atual (para seleção adaptativa) ou uma distribuição de amostragem fixa (para análise assíncrona). Na prática, em máquinas de memória compartilhada, trabalhadores lock-free modificam o vetor de resíduo concorrentemente. Consequentemente, seletores adaptativos operam sobre distribuições estagnadas e imperfeitas, onde a discrepância em relação ao ideal cresce com o número de atualizações em trânsito. Este artigo aborda a falta de medição sistemática sobre como o Kaczmarz residualmente ponderado e o ganancioso (greedy) se comportam sob execução assíncrona com atrasos de hardware realizados.

Metodologia

O estudo instrumenta algoritmos Kaczmarz residualmente ponderados e de limiar ganancioso (threshold-greedy) através de 339 execuções em um nó de 96 núcleos. Os experimentos utilizam uma família de amostragem ponderada por potência onde a probabilidade de selecionar a linha $i$ é proporcional a $|r_i|^\ell$. O expoente $\ell$ interpola entre a amostragem uniforme ($\ell=0$) e a regra de Motzkin de resíduo máximo ($\ell \to \infty$).

Configuração Experimental:

• Hardware: Um nó ACES de 96 núcleos (Texas A&M) com threads fixadas aos núcleos (pinned).
• Atrasos: A estagnação (staleness) é medida via intervalos realizados de despacho-para-compromisso (dispatch-to-commit) em vez de atrasos injetados sinteticamente.
• Problemas de Teste: Três categorias foram utilizadas: (1) um sistema denso benigno, (2) problemas tomográficos coerentes em duas escalas, e (3) 16 matrizes SuiteSparse do conjunto de testes Bai–Wu.
• Semântica de Leitura: Duas políticas foram comparadas:
  • Leituras Consistentes: Trabalhadores capturam um snapshot do vetor de resíduo uma vez por passo, tanto para amostragem quanto para o cálculo da atualização.
  • Leituras Inconsistentes (Vivas): A CDF de amostragem é construída a partir de leituras atômicas vivas, e o valor específico do resíduo é relido após a seleção da linha.
• Validação: A implementação foi validada contra resultados sequenciais publicados e verificada recomputando $b - Ax$ ao término para garantir que as divergências fossem comportamentos numéricos e não condições de corrida de dados (data races).

Principais Contribuições e Descobertas

1. A Fronteira de Estabilidade $\ell^*(T)$

O artigo identifica uma fronteira de estabilidade no plano $(\ell, T)$ (expoente de amostragem vs. contagem de threads).

• Observação: À medida que a concorrência ($T$) aumenta, o sistema tolera uma amostragem menos agressiva (menor $\ell$).
• Mecanismo: Abaixo da fronteira, uma amostragem mais agressiva é estritamente mais rápida. Acima da fronteira, o amostrador começa a classificar a "interferência" (perturbações causadas por $\Theta(T)$ atualizações em trânsito) em vez do sinal, levando à divergência.
• Implicação de Ajuste: O ajuste ideal é uma "corrida para o abismo", onde deve-se selecionar o maior $\ell$ que permaneça logo dentro da fronteira de estabilidade para um dado $T$.

2. Instabilidade da Seleção Gananciosa de Limiar (Threshold-Greedy)

A seleção gananciosa de limiar padrão (GRK), que seleciona linhas acima de um corte de resíduo, mostra-se incompatível com a execução assíncona de alta concorrência.

• Resultado: Em $T=96$, o GRK diverge em uma fração de um sweep em todos os problemas de teste, independentemente da semântica de leitura. A concentração da seleção nos maiores resíduos faz com que os trabalhadores atualizem repetidamente os mesmos vizinhos acoplados, amplificando a interferência.

3. Controle do Tamanho do Passo como Mecanismo de Recuperação

A sub-relaxação (redução do tamanho do passo $\beta$) pode restaurar a convergência para configurações que divergem com passo total ($\beta=1$).

• Eficácia: Cada configuração que divergiu em $\beta=1$ convergiu quando $\beta \le 0.5$.
• Custo: Esta recuperação incorre em um custo previsível. O penalidade no número de sweeps é aproximadamente $1.7\text{--}2.3\times$ maior que a previsão síncrona de $1/[\beta(2-\beta)]$, atribuída a um "prêmio de interferência assíncrona".

4. Semântica de Modo de Leitura e Risco de Cauda

Ao contrário do observado em Jacobi assíncrono, a consistência de leitura não governa a principal fronteira de estabilidade aqui, mas afeta o comportamento de cauda.

• Divergência: Leituras de snapshot consistente admitiram uma divergência rara, dependente de escalonamento (1 em 36 execuções em um problema tomográfico coerente), que as leituras inconsistentes (vivas) nunca exibiram.
• Eficiência: Leituras inconsistentes são mais baratas por passo (não exigem cópia total do resíduo) e não mostraram falhas de cauda em testes equivalentes. O artigo conclui que as leituras inconsistentes são a estratégia padrão superior para regimes de amplo acoplamento.

5. Discriminadores Estruturais

A fronteira de estabilidade é estritamente ordenada pelo acoplamento médio par a par $\bar{\chi} = E|Q_{ij}|$, onde $Q = AA^\top$.

• Proxies espectrais (como normas de Gram-linha fora da diagonal) e coerência de pior caso falharam em prever a estabilidade.
• A estabilidade é uma corrida entre a velocidade de convergência e o crescimento da interferência. Problemas com maior densidade de acoplamento exigem amostragem menos agressiva ou menor contagem de threads para permanecerem estáveis.

Significância e Alegações

O artigo afirma fornecer o primeiro estudo sistemático de seleção de linhas adaptativa sob execução assíncrona com atrasos realizados. Sua principal significância reside em definir os limites práticos de combinar essas duas técnicas de aceleração:

1. Ajuste Prático: Estabelece que o ajuste do Kaczar de adaptativo para paralelismo não é meramente sobre maximizar a agressividade da seleção, mas requer navegar por um abismo de estabilidade dependente da concorrência.
2. Orientação Algorítmica: Demonstra que regras gananciosas padrão (GRK) são instáveis em escala e que leituras inconsistentes são a estratégia de implementação preferida para Kaczar de memória compartilhada.
3. Segurança de Implementação: Valida que a sub-relaxação serve como um "botão de segurança" confiável para recuperar a convergência quando a concorrência força uma redução na agressividade da amostragem.
4. Direção Futura: Os achados motivam o desenvolvimento de um amostrador de dois níveis distribuído para desacoplar a estagnação da amostragem da estagnação da iterada, abordando o gargalo de amostragem global de $O(m)$ observado nos experimentos.

Os autores mantêm a modéstia, observando que os fenômenos observados são propriedades da própria iteração assíncrona, e não erros de implementação, e que a compreensão teórica da fronteira $\ell^*(T)$ e do prêmio super-quadrático de sub-relaxação requer desenvolvimento adicional.