Locality optimizations on irregular algorithms and data structures

Abstract

Estruturas de grafos baseadas em apontadores tem sido amplamente discutidas por várias comunidades científicas que tencionam usar este tipo de estruturas. Muitas destas áreas têm a necessidade de usar e implementar algoritmos complexos e sofisticados, como por exemplo, encontrar a árvore de expansão de custo mínimo de um grafo. Estes algoritmos têm um comportamento típicamente irregular no que toca aos padrões de acesso à memória. Como tal, o objetivo é otimizar estas implementações de estruturas de grafos visando aspetos que melhorem a localidade dos acessos à memória. O impacto da latência de memória tem sido continuamente atenuado através do uso de memórias cache nas arquiteturas de computadores atuais - as técnicas de otimização para estruturas regulares (ex., matrizes) são bem conhecidas neste âmbito, contudo estruturas irregulares inserem-se numa classe de problemas para os quais ainda não existem consolidadas representações eficientes.

Nesta dissertação é efetuado um estudo sobre as otimizações possíveis em algoritmos como métodos de ordenação heap-sort: são apresentadas uma implementação padrão de um algoritmo heap-sort e uma versão amigável da cache, originalmente apresentada por Emde Boas. Juntamente com os problemas de esforço de memória, existem também os problemas de algoritmos intensivos em linguagens de alto nível. Frameworks orientadas a objetos são normalmente baseadas em conceitos, linguagens e mecanismos abstratos de alto-nível, o que pode criar inconsistências quando combinadas com aspetos habituais da computação avançada (contiguidade de elementos em memória, localidade, eliminar a redundância do código-fonte, etc.). Aspetos como a gestão de objetos em memória (introduzidos por políticas como type-erasure e auto-boxing) e conceitos abstratos relativamente ao encapsulamento (uso ineficiente de APIs, em conjunto com mecanismos de tipos genéricos) são identificados como sendo problemáticos na resolução de sobrecarga e introdução de refinamentos nas implementações. É notada uma clara incompatibilidade entre aplicações irregulares intensivas e metodologias orientadas ao objeto, nomeadamente em Java. Otimizações e alterações ao código-fonte são propostas em aplicações que sofrem destas limitações de desempenho, com o intuito de diminuir a sobrecarga que a abstração introduz nas implementações. É feito um conjunto de experiências com aplicações intensivas ao ordenar elementos com o heap-sort e com o algoritmo sobre grafos para encontrar a árvore de expansão de custo mínimo, para que se possam introduzir otimizações como novas distribuições de dados nas estruturas para melhorar os padrões de acesso à memória, mais amigáveis da cache. Padrões eficientes de acesso à memória é o principal interesse tendo em consideração aspetos sobre a localidade, quer seja utilizando primitivas eficientes de distribuições de dados em memória, ou diminuindo a complexidade do código-fonte dos algoritmos e estruturas. As otimizações propostas melhoram o comportamento de cache verificado em versões iniciais, assim como o tempo de execução. Aspetos baixo-nível como misses nas caches L1 e L2 salientam o carácter amigável da cache das distribuições de dados e as melhorias no número de misses; os menores misses na TLB mostram as melhorias na complexidade das implementações.

Pointer-based graph structures has been discussed by the scienti c community that aims to use such structures on several areas. Many of these areas have the need to implement complex and, sometimes, extremely sophisticated algorithms, like nding the minimum spanning tree of a graph. These algorithms are well known for being hard to e ciently execute on current multicore machines due to irregular patterns of memory accesses. Thus, the objective is optimizing the implementation of graph structures aiming for better memory locality. Memory latency problems have been attenuated by using cache memories in nowadays computer architectures - the memory optimization techniques for regular data-structures (e.g., matrices) are well known, as for irregular data-structures insert themselves in areas where e cient representations are not yet well known. Optimization algorithms like sorting problems are studied through the use of heap-sort methods: we present a standard implementation and an optimized version originally presented by van Emde Boas. Along with the problems of memory straining we refer also to the problems of intensive algorithms in modern high-level languages. Object-oriented frameworks usually operate with high-level concepts and abstract mechanisms that may not combine well with core features of high performance computing (element contiguity, locality, eliminating code redundancy, etc.). We identify aspects like ine cient object-memory management (introduced by type-erasure and auto-boxing) abstract concepts regarding encapsulation (ine cient API usage alongside with generic mechanisms) as being problematic issues in the resolution of overheads of data-intensive algorithms. A mismatch is clearly noticed between irregular data-intensive applications and object-oriented in Java. We propose a series of optimizations and changes to the source code of applications that su er from bottlenecks related to these, in order to demean the setbacks imposed by abstractions. We perform tests on heap sorting and Prim's minimal spanning tree algorithm in order to introduce the improvements made in data layouts optimizing irregular memory accesses. E cient memory access patterns are the main concern in this thesis and good cache locality on modern memory architectures, whether by using e cient sorting techniques or improving pointer-chasing complexity in algorithms and data structures, are the main goals. The optimizations proposed are able to decrease the cache misses of applications and, most important, execution time. We analyse the low-level instruction counts in order to accurately show that instruction complexity decreases; L1 and L2 cache miss lower counts prove the e ciency of cache-friendly layouts and show the miss behaviour improvement; TLB low miss counts verify the improvement in address and memory management.