Design of trace-based split array caches for embedded applications

Resumo: Um sistema embarcado executa um único programa ou um conjunto pré-definido de programas repetidamente e, muitas vezes, seus componentes podem ser customizados para satisfazer uma especificação com requisitos referentes à área, desempenho e consumo de energia. Caches on-chip, em particular, são alvos de muitos algoritmos de customização por terem uma contribuição importante no desempenho e no consumo de energia de processadores embarcados. Várias aplicações embarcadas processam estruturas de dados cujos padrões de acesso distintos tornam difícil encontrar uma configuração para o cache que garanta desempenho e baixo consumo. Propomos, neste trabalho, uma metodologia para projetar caches de matrizes particionados que satisfaçam uma restrição de tamanho total e em cujas partições estão mapeadas as matrizes da aplicação. Estas partições exploram a diferença de localidade espacial entre as matrizes. Com base na simulação de rastros de acesso à memória para entradas típicas, definimos uma métrica que quantifica o uso que as matrizes fazem das metades das linhas de um cache de matrizes unificado, associativo por conjunto, que satisfaz uma restrição de tamanho. Esta métrica é usada para dividir as matrizes em dois grupos, que são mapeados em duas partições de cache, uma com mesmo tamanho de linha, e outra com metade do tamanho de linha do cache de matrizes unificado. Este procedimento é repetido para várias organizações de cache de matrizes unificados com um tamanho especificado. No final, os caches de matrizes particionados baseados em rastros de acesso à memória com menor tempo médio de acesso à memória são selecionados. Para um decodificador MPEG-2, dependendo do paralelismo dos acessos de dados, os resultados das simulações mostram que o tempo médio de acesso à memória de um cache de matrizes particionado baseado em rastros de 8K bytes apresenta uma redução de 26% a 60%, quando comparado com o cache de matrizes unificado, associativo por conjunto, de mesmo tamanho, com menor tempo médio de acesso à memória. Existe também uma redução de 46% no consumo de energia entre estes cachesAbstract: An embedded system executes a single application or a pre-defined set of applications repeatedly and, frequently, its components can be fine-tuned to satisfy a specification with requirements related to area, performance, and energy consumption. On-chip caches, in particular, are the target of several customization algorithms due to its important contribution to the performance and energy consumption of embedded processors. Several embedded applications process data structures whose access patterns turn it difficult to find a cache configuration that guarantees performance and low energy consumption. In this work, we propose a methodology for designing a split array cache that satisfies a total size constraint and in whose partitions the arrays of an application are mapped. Those partitions explore the difference in spatial locality among the matrices. Using traces of memory accesses, obtained for typical input patterns, we define a metric that quantifies the use of the two halves of the lines by array accesses in a unified array set-associative cache that satisfies a size constraint. We use this metric to split the arrays in two groups that are mapped to two cache partitions, one with the same line size, and the other with half line size of that of the unified array cache. This procedure is repeated for several unified array cache organizations of a specified size. In the end, the trace based split array caches with lowest average memory access time are selected. For a MPEG-2 decoder, depending on the parallelism of array accesses, simulation results show that the average memory access time of an 8K byte split array cache is reduced from 26% to 60% as compared to that of the unified set associative array cache of same size with the lowest average memory access time. There is also a reduction of 46% in the consumption of energ