Stencil computation is notorious for having the performance limited by the main memory access. In current computers it implies underutilization of the central processing units. To cope with this limitation, multiple approaches relying on reordering the computation have been proposed, most notably variations of space-blocking and timeblocking. This work introduces a technique to speed up stencil computation, which is not based on space-blocking or time-blocking. Stencil computation implies multiple iterations of traversals through every domain point, with each iteration updating every point based on the previous values of the neighboring points. The technique introduced, named Aggregate Stencil-Loop Iteration (ASLI), works by updating the value of each domain point using the original stencil operator convolved with itself one or more times. The approach implies traversing the data domain fewer times than a straightforward iterative stencil implementation would, with each traversal performing more computation per data item fetched into registers. This more complex operator creates new opportunities for in-register data reuse and increases the FLOPs-to-load ratio. Computation and data reuse schemes are developed for its application to 1, 2, and 3- dimensional stencils. The Influence Table is presented to assist in the calculation of convolved coefficients. An integer sequence is derived. For 2D and 3D star-shaped stencils, the total number of FLOPs increases, but better interaction with the memory makes it beneficial even when compared with optimized non-ASLI implementations. ASLI is relatively easy to implement, allowing more scientists to productively extract better performance from supercomputing clusters. Performance results are shown for a variety of platforms, proving the soundness of the approach and exemplifying how it can be straightforwardly applied with existing techniques and solutions, helping to increase the performance of existing optimization methods. In order to better express ASLI and to enable comparison with other approaches, a methodology is outlined and new metrics are set forth for evaluating stencil implementations, and perhaps the scalability of memory access in a machine. ASLI can be regarded as the application of a broader principle, namely, Kernel Convolution, to the particular case of stencil computation. From this perspective, the Influence Table could promote the use of Kernel Convolution in other applications.

Computação do tipo estêncil é notória por ter o desempenho computacional limitado pela capacidade da memória de acesso rápido (RAM). Nos computadores atuais, isso implica subutilização da unidade central de processamento nesse tipo de computação. Para buscar amenizar a limitação, diversas abordagens de reordenação da computação foram propostas na literatura, notoriamente subtipos de space-blocking e time-blocking. Objetiva-se neste trabalho introduzir uma nova técnica para optimização de computação estêncil, diferente de space-blocking e time-blocking. Computação estêncil implica várias iterações de travessia por todos os pontos de um domínio, com cada iteração atualizando cada ponto com base no valor prévio dos pontos vizinhos. A técnica introduzida, ASLI (Aggregate Stencil-Loop Iteration, Iteração Agregada do Laço Estêncil), funciona atualizando os valores dos pontos do domínio com o operador estêncil original convoluído consigo uma ou mais vezes. Ela implica percorrer o domínio dos dados menos vezes que em uma implementação mais direta, do estado da arte, sendo que cada travessia efetua mais computação com os dados carregados nos registradores. Este operador mais complexo cria novas oportunidades de reúso de valores presentes nos registradores, e aumenta a razão de FLOPs por carregamento de dados da memória (load). Esquemas de reúso de computação e de dados são desenvolvidos para os casos de 1-, 2-, e 3- dimensões. A Tabela de Influência é apresentada como meio de auxiliar no cálculo de coeficientes convoluídos e deriva-se uma sequência numérica relacionada. Para operadores estêncil 2D e 3D com formato estrelar, a quantia total de FLOPs aumenta, mas uma melhor interação com o subsistema de memória torna a abordagem benéfica em comparação a implementacões não-ASLI. ASLI possui implementação relativamente simples, permitindo que mais cientistas aproveitem da capacidade de seus conglomerados de supercomputação com mais facilidade. Monstram-se resultados de desempenho para uma variedade de plataformas, provando-se a viabilidade da abordagem e que esta pode ser aplicada junto a técnicas e solucões correntes, ajudando a aumentar o desempenho de outros métodos já existentes na literatura. Para melhor exibição de ASLI e de sua comparação com outras abordagens, este trabalho esboça uma metodologia e novas métricas para avaliação de computação estêncil, e talvez também de escalabilidade de acesso à memória de computadores. Pode-se entender ASLI como a aplicação de um princípio mais amplo, a Convolução de Núcleo de Computação, ao caso particular de computação estêncil. Desse ponto de vista a Tabela de Influência poderia colaborar na disseminação da Convolução de Núcleo a outras aplicações.