Organização de Computadores
EP1
Experimentos com cache
Pedro Morhy Borges Leal
5893830
Dependendo do modo que um programa é desenvolvido ele pode aproveitar muito mal um
recurso muito importante do computador que é o cache. O cache serve de auxilio aos computadores
para realizar tarefas e acessar dados de um modo mais rápido. É uma memória muito rápida que fica
perto do processador para consultar dados e instruções que geralmente ocorrem com bastante
frequência em um programa.
No primeiro exemplo passado, o teste1.c, o main() realiza duas tarefas dependendo se o
usuário coloca algum argumento ao chamar o programa ou não. Se ele não colocar nenhum
argumento, o main() irá percorrer uma matriz linha a linha e definir cada elemento com o numero 0.
Caso contrário ele irá realizar a mesma tarefa porém percorrendo coluna por coluna.
A partir de testes utilizando a ferramenta time percebemos que a partir de um determinado
tamanho da matriz (baseado no SIZE) o tempo de execução das duas tarefas se diferenciam
bastante. A tabela abaixo mostra essa diferença:
SIZE Tamanho Matriz
Tempo Linhas
Tempo Colunas
Diferença Tempo
100
10K
0,004s
0,004s
0s
200
40K
0,004s
0,004s
0s
400
160K
0,005s
0,006s
0,001s
800
640K
0,010s
0,015s
0,005s
1,6K
2,56M
0,024s
0,061s
0,037s
3,2K
10,24M
0,077s
0,178s
0,101s
6,4K
40,96M
0,429s
2,557s
2,128s
Como podemos conforme vamos aumentando o SIZE o tempo de tarefa que percorre a
matriz por colunas começa a ficar bem maior que a tarefa que percorre a matriz por linhas. Isso
ocorre porque em C uma matriz é uma array de linhas, isso é, na memória cada elemento de uma
linha é guardado um ao lado do outro, e ao fim desta linha começa a nova linha e assim por diante.
Então quando um elemento é acessado dessa matriz, parte dos dados perto dessa matriz são
carregados junto no cache e o dados perto deste cache são os elementos da mesma linha.
Logo na tarefa que percorre a matriz por linhas utiliza muito bem os recursos do cache,
assim o processador não precisa buscar na memória mais devagar os dados da maioria dos
elementos. Enquanto na outra abordagem a partir de um certo SIZE o cache não é bem utilizado e o
processador precisa “ir buscar” na memória “lerda” os dados da matriz com uma frequência maior.
Além disso podemos perceber que na tarefa de colunas do SIZE 3,2K para o 6,4K há um
salto muito grande no tempo, maior do que o normal. Utilizando a ferramenta valgrind com a opção
cachegrind para analisar como o programa está utilizando o cache do computador para diferentes
SIZEs podemos perceber que aproximadamente do SIZE 3,4K ao SIZE 3,5K a porcentagem do
miss rate do L2, para cache de dados, cresce muito como aparece na tabela abaixo.
SIZE
D1(%)
200
400
800
1600
3200
3400
3450
3475
3500
3585
3600
3700
3710
3713
3800
3900
4000
4100
4200
4400
4800
5000
5500
5800
6000
6200
6400
8000
10000
L2d(%)
13,5
26,8
38,7
45,1
48
48,1
48,2
47,9
47,9
48,2
48,3
48,3
48,3
48,1
48,2
47,7
47,7
47,6
47,7
47,8
48
48,1
48,3
48,4
48,5
48,5
48,6
48,9
52,1
1,3
1,9
2,5
2,8
3
3
3
47,9
47,9
11,2
11,1
10,9
10,9
48,1
48,2
47,6
47,7
47,6
47,7
47,8
48
48,1
48,3
48,4
48,4
48,5
48,6
48,6
49
Os dados do valgrind para a tarefa “linhas” em ambas as colunas chegaram no máximo em
3%. Ou seja no cache 1 a diferença entre as duas já foi visível com SIZE menor que 200. Agora
para o cache L2 esse diferença só ocorre a partir do SIZE 3475. O computador utilizado para rodar
esse teste tem um cache L2 de 3 MB e um cache de nível 1 de 64 KB.
Com o SIZE 3475 a matriz fica com o tamanho de 12M de elementos o que é
aproximadamente 4 vezes o tamanho do cache. Foi testado também em uma maquina com o cache
de 2 MB para analisar se este padrão continuava, e de fato continuou. O SIZE neste caso que
aumentou bruscamente o miss rate foi 2635, então a matriz com tamanho aproximadamente 7M de
elementos e quase 4 vezes o tamanho do L2. Claro que não exatamente pois temos outras coisas a
considerar, mas chegamos um pouco a essa taxa.
O gráfico abaixo mostra o gráfico da tabela acima, podemos ver como é repentina a
mudança do miss rate do L2 e por alguma razão essa porcentagem sobre um pouco de alteração
logo depois e depois fica quase constante. A linha azul é a coluna D1 e a linha vermelha é a coluna
L2D.
O processador procura por um determinado dado no cache utilizando o endereço de
memória de onde ele está localizado na mémoria principal. No cache os dados são mapeados a
partir dos endereços de memória. Chamado de direct-mapped cache a estrutura do cache é indexada
pelos primeiros bits do endereço de memória. Então por exemplo os dados do endereço 101100
ficariam indexados na posição 100 enquanto os 101000 e 111000 ficariam indexados no 000. Vale
lembrar que nessa forma apenas um dado fica armazenado em cada posição, então no exemplo
anterior o ultimo utilizado ficaria armazenado na posição 000. Mas os processadores de hoje em dia
utilizam a associatividade em que para cada index do cache existem mais de uma posição.
O teste 2 serve para mostrar essa estrutura. O gráfico acima mostra a execução dele com
diversos tipos de deslocamento e o tempo que demorou para realizar a tarefa.
Além da questão já discutida anteriormente, que os elementos mais próximos de um
elemento de um vetor recentemente utilizado vão para o cache. Neste caso percebemos que nos
pulos de tamanho que são potência de 2 demoram mais dos que em sua volta. Isso se deve ao fato
de que esses números são dessa forma: 1...000000000. Ou seja, supomos que a posição 1 de um
vetor seja 1, quando pegamos esse valor colocamos ele no index 001 do cache, quando damos um
pulo de potência de 2 (números grandes), por exemplo 512, que é 1000000000 o próximo elemento
consultado terá endereço 1000000001(Obs.: estou desconsiderando que os endereços andam de 4
em 4 para facilitar a explicação, mas funcionaria do mesmo modo). Quando formos procurar esse
endereço no cache provavelmente não acharemos pois o ultimo elemento adicionado lá tem o
mesmo index que este (001), e então iremos adiciona-lo no cache. O próximo elemento também terá
fim 001 e assim por diante, ou seja, sempre iremos trocar os elementos do cache e nunca poderemos
nos beneficiar dele.
Abaixo, utilizando o valgrind para os pulos 2047, 2048, 2049 vemos a grande diferença
entre os da ponta com o do meio que é uma potência de 2.
Deslocamento L2D miss rate
2047
0,60%
2048
6,60%
2049
0,60%
Um outro problema para cache é quando utilizamos processos diferentes utilizando uma
memória compartilhada. Supondo que estamos trabalhando com dois cores diferentes e dois
processos que compartilham um certo dado, então temos um problema de race condition. Além tem
termos dois caches diferentes para cada processo, o sistema tem que tomar conta deste
compartilhamento de dados para não ocorrer problemas mas isso custa muito para o processador.
O teste3.c mostra isso, após rodar algumas vezes a média de tempo foi de 1,73 segundos,
que é bastante coisa. Uma tentativa de otimização foi fazer com que os dados que estavam sendo
compartilhados não fossem os numeros em si e sim os endereços de memória deles, assim o sistema
não precisaria atualizar o cache, que custa muito. A média de tempo foi te 1,53 segundos, diminuiu
um pouco mas continua muito alto. A questão aqui é o que o sistema está protegendo as variáveis
para problemas de race condition e para ficar mais rápido o melhor seria não compartilhar a
memória ou não dividir em dois processos paralelos.
Um exemplo realizado, o teste4.c, tem uma abordagem parecida com ao teste1.c porém ao
invez do caso não ótimo percorrer a matriz por colunas o que foi feito é que os elementos da matriz
são acessados de forma aleatória. E os testes provaram que desse modo também o cache não é bem
utilizado por que o sistema armazena os dados que estão próximos do elemento recém consultado
mas na próxima consulta não quer dizer que eles serão requisitados dado a abordagem aleatoria.
O tempo médio no caso normal deste programa foi de 0,830 segundos enquanto na outra foi
de 1,480 segundos, quase o dobro. Utilizando a ferramenta valgrind obtivemos os seguintes
resultados:
Caso normal:
• D1 miss rate: 0,2%
• L2d miss rate: 0,2%
Caso acesso aleatório:
• D1 miss rate: 3,9%
• L2d miss rate: 2,8%