Avaliação quantitativa do impacto da organização dos dados na execução de programas: estudos de caso no contexto da síntese física

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Ciência da Computação, Florianópolis, 2018.Em diversos domínios de aplicação, os programas precisam manipular grandes quantidades de dados e ao mesmo tempo, explorar a arquitetura de hardware da máquina hospedeira a fim de otimizar o desempenho. Por exemplo, game engines devem renderizar gráficos 3D com imagens de alta resolução, simular sistemas físicos realistas e também processar sistemas complexos de inteligência artificial num curto período de tempo. Para atender a esses requisitos, vários conceitos e padrões de projetos são aplicados durante o desenvolvimento de um jogo. Similarmente, as ferramentas de síntese física devem lidar com grandes quantidades de dados para resolver problemas relacionados ao projeto de circuitos com milhões de células. Os componentes pertencentes à síntese física podem ser representados utilizando-se o modelo de programação orientada a objetos (OOD). No entanto, usar esse modelo pode levar a objetos excessivamente complexos que resultam em desperdício de espaço de memória, o qual prejudica a exploração da localidade espacial na memória cache, consequentemente, degradando o tempo de execução do software. Este trabalho propõe uma organização eficiente dos dados para diferentes etapas da síntese física baseada no modelo orientado a dados (DOD). Diferentemente de OOD, o modelo DOD se concentra em como os dados são organizados na memória. Como consequência, DOD proporciona uma melhor exploração da localidade espacial da memória cache levando a uma redução no tempo de execução. Para avaliar o impacto da organização dos dados na memória cache, este trabalho compara o número de cache misses e o tempo de execução para quatro estudos de caso no contexto da síntese física, desenvolvidos com os modelos DOD e OOD, em versões sequenciais e paralelas. Os resultados experimentais mostraram que os estudos de caso usando DOD, e agrupamento dos dados quando apropriado, resultaram em reduções significativas em relação ao OOD no número de cache misses e no tempo de execução para 7 dos 8 cenários avaliados. No melhor cenário esta redução foi de até cinco ordens de grandeza no número de cache misses. No cenário menos favorável, o estudo de caso modelado com DOD executou tão rápido quanto o modelado com OOD.Abstract : In several application domains, programs have to deal with huge amount of data while exploiting the hardware architecture of the hosting machine. For example, modern game engines must render 3D graphics for high resolution images, model realistic physical systems, and also process complex artificial intelligence systems. To fulfill such requirements, several concepts and design patterns are applied during the game development. Similarly, physical design tools must handle huge amounts of data in order to solve problems for circuits with millions of cells. The physical design components may be represented by using the Object-Oriented Design (OOD) model. However, using this model may lead to overly complex objects that result in waste of cache memory space. This memory wasting harms the exploitation of locality by the cache memory and, consequently, degrades software runtime. This work proposes an efficient organization of the data for different physical design tasks based on the Data-Oriented Design (DOD) model. Unlike OOD, DOD model focuses on how the data is organized in the memory. As a consequence, DOD may better explore cache spatial locality and reduce the total runtime. In order to evaluate the impact of the data organization in the cache memory, this work compares the number of cache misses and runtime of four case studies in the context of physical design, developed with both the OOD and the DOD models, in sequential and parallel versions. The experimental results showed that the case studies using DOD, and data grouping when appropriate, resulted in significant reductions in comparison with OOD in the number of cache misses and runtime for 7 out of the 8 evaluated scenarios. In the best scenario, such reduction was up to five orders of magnitude in the number of cache misses. In the least favorable scenario, the case study modeled with DOD executed as fast as the one with OOD