Os compiladores são capazes de detectar acessos alternativos a matrizes e intercalá-los na memória?

7

É possível projetar um compilador que otimiza um loop no qual matrizes são acessadas de maneira alternativa? Por exemplo, assim:

// int[] a,b
int sum = 0;
for(int i = 0; i < n; i++)
{
  sum += a[i] + b[i];
}

Com o armazenamento seqüencial usual do array a[i]e b[i]podem estar distantes um do outro na memória. Portanto, acho que uma boa otimização do compilador detectaria isso a[i]e b[i]sempre será acessada no "mesmo tempo" e armazenaria as matrizes intercaladas, ou seja, a[0] b[0] a[1] b[1] ...para que um acesso à memória possa recuperar ambos a[i]e b[i].

compilers arrays program-optimization memory-management krammer
fonte
Bem-vinda! Eu tentei esclarecer sua pergunta; verifique se eu não a mutilei. Quanto ao seu conteúdo, tenho certeza de que os compiladores podem detectar casos simples, mas duvido que, em geral, haverá muitas matrizes usadas apenas dessa maneira. Além disso, não deve ser mais eficiente em uma RAM, em termos de tempo, armazenar a matriz dessa maneira. Pode haver outros efeitos em jogo, como a referência de Dave parece sugerir.
Raphael
Não tenho certeza de que a suposição subjacente aqui seja verdadeira na arquitetura moderna de cache; contanto que o cache seja amplo o suficiente para acomodar uma fração significativa de ambas as matrizes (e não sendo contestado por outros processos, é claro), o acesso ao layout ingênuo deve ser eficiente.
dmckee --- ex-moderador gatinho
@Raphael: Eu acho que sua edição adicionou requisitos inesperados à pergunta. Não acho que seja necessário a[i]e b[i]seja recuperado com uma operação de memória, mas eles estavam localizados nas proximidades na memória para melhor desempenho do cache.
Dave Clarke
@DaveClarke, na verdade, com um aspecto da pergunta, pretendia recuperar os valores correspondentes de aeb com uma operação de memória.
Krammer 6/09/12
11
Não estou conseguindo encontrar uma referência para confirmar. A Sun "quebrou" os benchmarks de especificações 179.art e 171.swim cerca de 10 a 15 anos atrás (ou seja, a otimização obteve valores melhores do que os garantidos pelo hardware). ISTR que foi com otimizações relacionadas.
AProgrammer

Respostas:

11

Foi realizado algum trabalho que corresponde à sua descrição. Por exemplo:

  • Intercalação de matriz direcionada ao compilador para reduzir a energia nas memórias de vários bancos. por Delaluz, V. Design Automation Conference, 2002. Anais do ASP-DAC 2002. 7ª Ásia e Pacífico Sul e 15ª Conferência Internacional sobre Design VLSI. Procedimentos.

descreve essa otimização.

Dave Clarke
fonte
Obrigado. Existe algum método para o mesmo para arquitetura utilizando loops vetorizados?
Krammer 6/09/12
No exemplo do OP, um compilador que faz essa otimização também pode usar o bloqueio para dar suporte ao SIMD. Essa transformação pode não ser uma otimização, pois alguns pré-buscadores de hardware não cruzam os limites da página. Isso também interage com a organização da memória, potencialmente evitando conflitos bancários com DRAM (conflitos bancários podem reduzir a largura de banda e aumentar o uso de energia) ou não explorar vários canais de memória.
Paul A. Clayton
1

A resposta curta nesse caso é que o paralelismo no nível de memória geralmente é suficiente para cobrir vários blocos de memória separados em um loop como esse; intercalar em um único fluxo realmente atrasaria o processo. Muitos algoritmos de armazenamento em cache e memória externa assumem algum grau de paralelismo como este.

A resposta mais longa e mais teórica é que o armazenamento em cache é como vários aspectos da execução do programa que parecem fáceis, mas provam ser difíceis de prever em geral. Por exemplo, um bloco de cache pode precisar ser buscado apenas se um determinado processo parar; um compilador que poderia prever que seria interessante, para dizer o mínimo.

O caso mais simples de otimizar uma sequência conhecida de acessos (sem a necessidade de prever) é por si só difícil:

Em particular, suponha que se receba uma sequência de acessos à memória e que seja necessário colocar os dados na memória para minimizar o número de falhas de cache para essa sequência. Mostramos que, se P ≠ NP, não é possível aproximar eficientemente a solução ótima, até uma taxa de aproximação muito liberal.

Petrank e Rawitz, A dureza do posicionamento consciente dos dados em cache

KWillets
fonte
-1

Seu exemplo não está completo, as matrizes não são declaradas em nenhum lugar, nem são inicializadas em qualquer lugar.

Eu suspeito que, em um contexto geral de programação, esse tipo de otimização seria "mais problemas do que vale a pena". A maioria das matrizes é acessada em mais de um local, portanto, um compilador frequentemente precisa adivinhar qual local é o mais importante. Além disso, muitas matrizes não poderiam ser modificadas dessa maneira porque elas passam sobre as fronteiras da unidade de compilação como parâmetros para funções ou como variáveis ​​globais. Finalmente, tornaria as informações de depuração mais complexas.

Peter Green
fonte
Primeiro parágrafo do anúncio: este site trata de ciência da computação, não de programação. Segundo parágrafo do anúncio: você pode dar um exemplo específico ou citar referências?
Raphael