Algoritmo esquecido de cache - Cache-oblivious algorithm
Na computação , um algoritmo esquecido de cache (ou algoritmo transcendente de cache) é um algoritmo projetado para tirar vantagem de um cache de processador sem ter o tamanho do cache (ou o comprimento das linhas de cache , etc.) como um parâmetro explícito. Um algoritmo de esquecimento de cache ideal é um algoritmo de esquecimento de cache que usa o cache de forma otimizada (em um sentido assintótico , ignorando fatores constantes). Assim, um algoritmo esquecido de cache é projetado para funcionar bem, sem modificação, em várias máquinas com tamanhos de cache diferentes ou para uma hierarquia de memóriacom diferentes níveis de cache e tamanhos diferentes. Algoritmos esquecidos do cache são contrastados com o bloqueio explícito , como na otimização de aninhamento de loop , que divide explicitamente um problema em blocos com o tamanho ideal para um determinado cache.
Algoritmos de cache-alheio ideais são conhecidos pela multiplicação de matrizes , transposição da matriz , triagem , e vários outros problemas. Alguns algoritmos mais gerais, como Cooley – Tukey FFT , são otimamente esquecidos do cache sob certas escolhas de parâmetros. Como esses algoritmos são ótimos apenas em um sentido assintótico (ignorando fatores constantes), um ajuste adicional específico da máquina pode ser necessário para obter um desempenho quase ideal em um sentido absoluto. O objetivo dos algoritmos esquecidos do cache é reduzir a quantidade necessária de ajuste.
Normalmente, um algoritmo esquecido de cache funciona por um algoritmo recursivo de divisão e conquista , onde o problema é dividido em subproblemas cada vez menores. Eventualmente, atinge-se um tamanho de subproblema que cabe no cache, independentemente do tamanho do cache. Por exemplo, uma multiplicação de matriz esquecida de cache ideal é obtida dividindo-se recursivamente cada matriz em quatro submatrizes a serem multiplicadas, multiplicando as submatrizes primeiro em profundidade . Ao ajustar para uma máquina específica, pode-se usar um algoritmo híbrido que usa o bloqueio ajustado para os tamanhos de cache específicos no nível inferior, mas de outra forma usa o algoritmo esquecido do cache.
História
A ideia (e o nome) para algoritmos esquecidos do cache foi concebida por Charles E. Leiserson já em 1996 e publicada pela primeira vez por Harald Prokop em sua tese de mestrado no Instituto de Tecnologia de Massachusetts em 1999. Houve muitos predecessores, geralmente analisando problemas específicos ; estes são discutidos em detalhes em Frigo et al. 1999. Os primeiros exemplos citados incluem Singleton 1969 para uma Fast Fourier Transform recursiva, idéias semelhantes em Aggarwal et al. 1987, Frigo 1996 para multiplicação de matriz e decomposição LU, e Todd Veldhuizen 1996 para algoritmos de matriz na biblioteca Blitz ++ .
Modelo de cache idealizado
Os algoritmos esquecidos do cache são normalmente analisados usando um modelo idealizado do cache, às vezes chamado de modelo esquecido do cache . Este modelo é muito mais fácil de analisar do que as características de um cache real (que têm associatividade complicada, políticas de substituição, etc.), mas em muitos casos está provavelmente dentro de um fator constante de desempenho de um cache mais realista. É diferente do modelo de memória externa porque os algoritmos esquecidos do cache não sabem o tamanho do bloco ou o tamanho do cache .
Em particular, o modelo cache-oblivious é uma máquina abstrata (ou seja, um modelo teórico de computação ). É semelhante ao modelo da máquina RAM que substitui a fita infinita da máquina de Turing por uma matriz infinita. Cada localização dentro da matriz pode ser acessada em tempo, semelhante à memória de acesso aleatório em um computador real. Ao contrário do modelo de máquina RAM, ele também apresenta um cache: um segundo nível de armazenamento entre a RAM e a CPU. As outras diferenças entre os dois modelos estão listadas abaixo. No modelo esquecido de cache:
- A memória é dividida em blocos de objetos cada.
- Uma carga ou armazenamento entre a memória principal e um registro da CPU agora pode ser atendida a partir do cache.
- Se um carregamento ou armazenamento não puderem ser atendidos a partir do cache, isso é chamado de perda de cache .
- Uma falha de cache resulta no carregamento de um bloco da memória principal para o cache. Ou seja, se a CPU tenta acessar a palavra e está contendo a linha , ela é carregada no cache. Se o cache estava cheio anteriormente, uma linha também será despejada (consulte a política de substituição abaixo).
- O cache contém objetos, onde . Isso também é conhecido como suposição de cache alto .
- O cache é totalmente associativo: cada linha pode ser carregada em qualquer local do cache.
- A política de substituição é ótima. Em outras palavras, assume-se que o cache recebe toda a sequência de acessos à memória durante a execução do algoritmo. Se for necessário remover uma linha de cada vez , ele examinará sua sequência de solicitações futuras e removerá a linha que for acessada mais distante no futuro. Isso pode ser emulado na prática com a política de uso menos recente , que se mostra dentro de um pequeno fator constante da estratégia de substituição ideal off-line
Para medir a complexidade de um algoritmo executado dentro do modelo esquecido de cache, medimos o número de perdas de cache que o algoritmo experimenta. Como o modelo captura o fato de que acessar elementos no cache é muito mais rápido do que acessar coisas na memória principal , o tempo de execução do algoritmo é definido apenas pelo número de transferências de memória entre o cache e a memória principal. Isso é semelhante ao modelo de memória externa , que possui todos os recursos acima, mas os algoritmos de cache esquecidos são independentes dos parâmetros de cache ( e ). O benefício de tal algoritmo é que o que é eficiente em uma máquina sem memória cache provavelmente será eficiente em muitas máquinas reais, sem o ajuste fino de parâmetros específicos da máquina real. Para muitos problemas, um algoritmo de esquecimento de cache ideal também será ideal para uma máquina com mais de dois níveis de hierarquia de memória .
Exemplos
O algoritmo esquecido de cache mais simples apresentado em Frigo et al. é uma operação de transposição de matriz fora do local ( algoritmos no local também foram desenvolvidos para a transposição, mas são muito mais complicados para matrizes não quadradas). Dado m × n matriz A e n x m matriz B , que gostaria de armazenar a transposta de um em B . A solução ingênua atravessa uma matriz na ordem da linha principal e outra na coluna principal. O resultado é que, quando as matrizes são grandes, obtemos uma perda de cache em cada etapa da travessia por coluna. O número total de falhas de cache é .
O algoritmo esquecido de cache tem complexidade de trabalho ideal e complexidade de cache ideal . A ideia básica é reduzir a transposição de duas matrizes grandes na transposta de (sub) matrizes pequenas. Fazemos isso dividindo as matrizes pela metade ao longo de sua dimensão maior até que apenas tenhamos que realizar a transposição de uma matriz que caberá no cache. Como o tamanho do cache não é conhecido pelo algoritmo, as matrizes continuarão a ser divididas recursivamente mesmo após esse ponto, mas essas subdivisões adicionais estarão no cache. Uma vez que as dimensões m e n são pequenas o suficiente para que um array de entrada de tamanho e um array de saída de tamanho caibam no cache, as travessias de linha e coluna principais resultam em trabalho e perda de cache. Usando essa abordagem de dividir para conquistar, podemos atingir o mesmo nível de complexidade para a matriz geral.
(Em princípio, pode-se continuar dividindo as matrizes até que um caso base de tamanho 1 × 1 seja alcançado, mas na prática, usa-se um caso base maior (por exemplo, 16 × 16) para amortizar a sobrecarga das chamadas de sub-rotina recursivas.)
A maioria dos algoritmos esquecidos do cache contam com uma abordagem de dividir e conquistar. Eles reduzem o problema, de modo que ele eventualmente caiba no cache, não importa o quão pequeno seja o cache, e terminam a recursão em algum tamanho pequeno determinado pela sobrecarga da chamada de função e otimizações semelhantes não relacionadas ao cache, e então usam algum acesso eficiente ao cache padrão para mesclar os resultados desses pequenos problemas resolvidos.
Como a classificação externa no modelo de memória externa , a classificação esquecida do cache é possível em duas variantes: funnelsort , que se assemelha ao mergesort , e à classificação da distribuição inconsciente do cache , que se assemelha ao quicksort . Como suas contrapartes de memória externa, ambos atingem um tempo de execução de , que corresponde a um limite inferior e, portanto, é assintoticamente ideal .
