Locality optimisation techniques for platforms

Abstract

Aplicações científicas simulam o mundo real através de modelos matemáticos. As simulações destes modelos necessitam de grande poder computacional, existente nas arquiteturas atuais. Contudo, para aceder a esse poder computacional, o programador necessita de desenvolver a aplicação de acordo com a plataforma de execução, o que introduz complexidade no desenvolvimento da aplicação. Nas abordagens tradicionais estas adaptações/otimizações estão misturadas no código do domínio originando dois problemas: primeiro, o código fica dependente da plataforma, sendo que a execução numa plataforma distinta obriga a uma reescrita do código; segundo, o código relativo à otimização mistura-se com o código do domínio, dificultando a perceção do mesmo. As linguagens orientadas ao objeto são reconhecidas por explicitar os conceitos do domínio no código. Porém, a sua utilização introduz tipicamente uma elevada sobrecarga na execução da aplicação limitando a sua utilização em aplicações cientificas. Isso explica o motivo pelo qual o Java, uma das linguagens orientadas ao objeto mais utilizadas, não é usada neste tipo de aplicações. Java utiliza a compilação dinâmica para remover as sobrecargas das linguagens orientadas ao objeto, quando os conceitos mais avançados não são utilizados (exemplo polimorfismo), como é, frequente, no caso das aplicações científicas. A abordagem apresentada nesta tese permite adiar a implementação das otimizações para fases posteriores do desenvolvimento, escondendo o mapeamento de dados. Por outro lado, permite especificar nas fases finais do desenvolvimento várias optimisações: o processamento em subdomínios, empacotamento de dados e ordenação dos dados em memória. Por fim, permite a execução paralela ocultando detalhes de implementação. Para isso separa o desenvolvimento em duas fases distintas: escrita do código de domínio e fase de otimização. A fase de otimização é adiada para fase final do desenvolvimento, o que permite uma fácil adaptação à plataforma de execução. A abordagem permite aplicar estas otimizações através de dois mecanismos: primeiro, alteração do mapeamento das coleções; e segundo, decomposição do problema em subproblemas. Ambas as otimizações são introduzidas no programa pelo programador de uma forma simples (pequeno custo de desenvolvimento) mantendo os conceitos de domínio. Primeiro, a alteração do layout baseia-se no conceito de procurador, cria um objeto temporário o que permite ao utilizador usar vários mapeamentos com a mesma API. Em segundo lugar, o mecanismo de decomposição de domínio suporta outras otimizações comuns: processamento de dados em blocos, empacotamento, execução paralela e dados privados aos fios de execução. O mecanismo é implementado por anotações de código, evitando alterações mais invasivas. A abordagem foi avaliada com um conjunto de casos de estudo: soma de um vector, daxpy, JECoLi, simulação de dinâmica molecular e multiplicação de matrizes. Este conjunto permitiu validar a abordagem em diferentes casos e a sobrecarga introduzida na execução. A adaptação do código de domínio para suportar a abordagem foi mais simples do que alterar o mapeamento de dados no código de domínio. Em todos os casos, a abordagem obteve uma performance similar às abordagens tradicionais. No caso do MD, exemplo que suporta mais otimizações, o uso da abordagem proporcionou um ganho de 50X no tempo de execução. Os outros casos de estudos obtiveram ganhos entre 20x e 40x. A JECoLi teve um ganho mais baixo (1,6x), já que neste caso apenas foi possível aplicar a otimização do mapeamento dos dados. Esses ganhos mostram a viabilidade da abordagem que permitiu obter códigos eficientes.

Scientific applications simulate the real world through mathematical models. The simulation of these models requires all the computational power available in current architectures. However, to take advantage of this computational power, the simulation code must be optimised, bringing it closer to the execution platform. This adaptation introduces a lot of complexity in application development. Traditionally the code is written according to the platform on which it will be executed. This approach has two problems: first, the code is dependent on the execution platform, and changing the execution platform requires code rewriting; second, the optimisation code is mixed with the domain code, making it difficult to understand. The Object-Oriented Paradigm (OOP) is known for bringing the code closer to the domain. However, its use typically introduces an overhead, preventing its use in scientific applications. This explains why Java, one of the most widely used OOP languages is not commonly used to develop scientific applications. On the other hand, modern OOP languages that rely on dynamic compilation (e.g., Java) can remove many overheads typical of OOP, when more advanced features are not used (e.g. polymorphism), which is the case of many scientific applications. This dissertation introduces an approach that allows developers to perform optimisation in the final development step. The approach enables multiple data layouts and allows the selection of the best layout according to the execution platform. On the other hand, the approach supports tiling, packing and sorting optimisations. Additionally, the approach supports parallel execution, hiding the implementation details related to optimisation. The approach separates the development of the domain code from its optimisation. The optimisation step is delayed until the final development step, which allows an easy adaptation to the execution platform. The supported optimisations rely on two mechanisms: first, changing the data collection layout and second, decomposing the problem into subproblems. Both optimisations are introduced in the program by the developer in a simple way (low development cost) and maintaining the domain concepts in the code. First, for hiding the data layout, the approach is based on the proxy pattern, creating a temporary object that accesses the data using the same API. Second, the domain decomposition mechanism enables several common optimisations: processing data in tiles, packing, parallel execution and thread private data. The technique was implemented by code annotations avoiding more invasive code changes. The approach was evaluated with a set of case studies: Sum, daxpy, JECoLi, MD and Matrix multiplication. This set allowed to verify the approach effectiveness in different cases and its execution overhead. The adaptation of the domain code to support the approach was simpler than transforming the layout in the domain code. In all cases, the approach obtained a performance similar to traditional approaches. In the MD case, the example that supports more optimisations, the use of the approach provided a gain of 50x in execution time. Other cases studies provided gains from 20x to 40x. The JECoLi case has the lowest gain (1.6x) since the gain was only due to layout change. These gains show the feasibility of the approach that delivered efficient optimised codes, adding low additional cost when compared with traditional approaches.