AEDs III 08/06/2011

// Hoje apareceu o professor Meira! sinal de perigo!
Hoje o professor vai falar sobre o tp5 parece.

Ele disse que quem não vir nesta aula não vai conseguir fazer ! o.O !

Esta aula de hoje não está em lugar algum! essa aula foi uma aula que eu inventei! :D - disse ele (eu acho)

Perspectiva historica:
Originalmente os pcs eram bastante simples =]. Com um processador e um disco ( que na epóca era um tambor ).
E se voce estudar isso melhor verá que se tratava de uma maquina de turing =].

Nos pcs de hoje é tudo mais complexo tem chacehes, memória etc...
Nessa hierarquia de memória existem alguns compromissos:
Quanto maior a memória maior a latencia, mas o custo/byte é menor. tanto porque usa-se menos silicio quanto porque o acesso em grandes quantidades até vem a compensar.

Essa é a Hierarquia de Memória!

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

O que nos levou a isso?
Foi a localidade de referencia.

E então notou-se dois tipos de localidade de referencia,
A temporal diz que se voce acessou um dado em um instante voce provavelmente acessará ela num futuro próximo, e vice-versa.
A espacial diz que se voce acessou um dado agora, existe uma alta probabilidade de voce acessar um vizinho daquele dado.

Alguns exemplos:
1: Um dos elementos mais básicos de um programa são os loops.
   Podem até ser vistos como a materialização da indução matematica no contexto de programação.
   E ele usa tanto localidade de referencia temporal quanto espacial, pois normalmente acessa-se arranjos e varia-se contadores.

Então perceba que a cada coisa que voce faz ao programar, voce tem diferentes graus de referencia temporal e espacial.
E o professor disse que é bom voce ter essa referencia!
Porque as máquinas hoje são feitas para tirar vantagem delas!
Hoje as máquinas normalmente tem 99% de acerto na busca por dados de memória, sem ter de acessar o disco.

Então veja, essa localidade já está na máquina!, Se o programa tem uma boa localidade temporal, voce vai ter uma resposta rápida e uma execução rápida.

Agora falando sobre a localidade espacial entra o conceito de paginação.
Quando voce acessa um dado, voce não carrega um único dado, voce carrega uma página de X bytes, e para cada nível da hierarquia voce tem uma tamanho de página maior
proporcionalmente ao tamanho do armazenamento.

Qual o beneficio da existencia desse mecanismo? Eles são uma resposta direta a necessidade de localidade espacial.
Por exemplo ao acessar sequencialmente um arranjo voce nào pode gastar 100 ciclos para acessar cada posição. Voce tem de carregar o arranjo todo para uma
posição mais rápida da hierarquia de memória antes de passear por todo ele.

Agora percebam que com páginas muito pequenas, eu desvalorizo a localidade espacial, porém eu valoriso a localidade temporal pois um mesmo cache poderá possuir
mais dados acessados recentemente.

E se ele for grande de mais hávera menor diversidade na cash e com isso hávera um problema chamado de fragmentação.
Que é trazer dados para a cache que não são usados para nada.

E disperdiça o espaco que voce poderia estar usando para valorisar a localidade temporal.

 * * * * * * * * * * * * * * * * * * * * * * * * *

Agora como isso aparece na vida dagente?

Isso aparece no tp5! uahh hoasahidahi - disse o professor meira =]

A cada decisão que se toma voce deve detectar a localidade referencia e considera-la na decisão.

 * * * * * * * * * * * * * * * * * * * * * * * * *

Agora veremos como quantificar essa localidade de referencia.

CONCEITO:
Working set é o conceito de que voce tem um grupo de dados que pertencem a suas ferramentas de trabalho. Esse é o seu working set.

Existe mais um conceito relecionado a localidade temporal e espacial que é a popularidade,
CONCEITO:
Popularidade é a frequência com que um dado é acessado.

Para explicar isso o professor demonstrou o conceito de distancia de pilha de acesso temporal:
As menos acessadas vão ficando no fundo da pilha, e a cada acesso voce pega a variavel acessada e joga para o topo da pilha.

Desenhando-se um gráfico cumulativo de acessos voce pode dizer que 25% deles são acessados com a distancia de pilha 0,
37% com distancia <= 1
75% com distancia <= 2
100& com distancia <= 3
// Ele também desenhou um não cumulativo que não citei, mas quero citar quando passar este texto a limpo.

(o professor desenhou um grafico com isso acima )

Agora quanto a referencia espacial

Ela é em função da disposição espacial ou seja, a disposição dos dados importa, se voce coloca dados alinhados pode ser melhor que dados espalhados.
Mas ao mesmo tempo podem haver diferentes distribuições de dados espalhados que podem gerar melhor ou pior localidade espacial dependendo da situação.

Ele desenhou então um grafico de localidade espacial mostrando a distancia dos dados a,b,c,d sendo que estão os 4 ordenados sequencialmente.
Então se caminho de b para a andei -1 se caminho de b para d caminhei 2 e assim por diante,

E mostrou que segundo uma sequencia de acessos que ele sugeriu,

Podia-se desenhar um gráfico mostrando o número de vezes que precisei caminhar, -3,-2,-1,0,1,2,3

Em seguida sugeriu uma paginação de 1 dado por página e mostrou que dessa forma o único beneficio é para os casos de 0 de caminhamento.

Mostrou em seguida que para paginas 2, voce começa a aproveitar melhor o -1 e 1, apesar de ainda haverem algumas falhas para estes 2.

Recapitulando:
Uma grande melhoria na velocidadde dos pcs é a hierarquia de memória que possui 3 compromsissos capacidade, latencia e custo.
isso existe por causa da localidade de referencia
existem 2 tipos desta, espacial e temporal
As maquinas hoje beneficiam estas localidades.
Uma quantificação destas localidades podem ser feitas por distancia de pilha e distancia de acesso respectivamente.
Ambos não são precisos se voce não conseguir saber como exatamente é a maquina sobre a qual seu programa vai rodar,
mas voce pode usar essas quantificações para descobrir qual a melhor máquina para executar determinado programa.