Recentemente, fiquei interessado no problema geral de otimizar o uso da memória em uma situação em que há mais de um tipo de memória disponível e há uma troca entre a capacidade de um determinado segmento de memória e a velocidade de acesso a ele.
O exemplo familiar é um programa que decide quando ler / gravar no cache do processador, RAM e disco rígido (via memória virtual).
Estou particularmente interessado no caso especial em que a quantidade de dados (incluindo o próprio programa) que precisa ser carregada excede significativamente a capacidade do armazenamento mais rápido disponível (ou seja, a solução trivial de "basta carregar tudo" é inaplicável).
Eu descobri que uma página da Wikipedia descrevendo alguns algoritmos comuns de cache, que é quase o que eu quero. Infelizmente, estes são um pouco de baixo nível:
- Muitos, como LRU ou MRU, só fazem sentido se você tiver sub-rotinas que são acessadas várias vezes. Se eu tiver um programa com um grande número de sub-rotinas, algumas das quais nunca são acessadas em uma determinada execução e algumas delas são acessadas uma ou duas vezes, essa estratégia nunca funcionará porque não pode criar dados suficientes sobre o que é comumente usado e o que não é.
- Outros, como o CLOCK, parecem lidar com as peculiaridades da implementação, em vez de realmente atacar a raiz do problema.
- Sei que existe uma estratégia em que primeiro perfilamos um programa durante uma execução de teste e, em seguida, fornecemos o perfil para o sistema operacional otimizar adequadamente. No entanto, ainda precisamos resolver o problema de fornecer um "exemplo de uso" verdadeiramente representativo ao criar o perfil.
O que realmente quero aprender é o seguinte: quando abstraímos todos os detalhes técnicos de hardware e software e falamos em um contexto puramente teórico, é possível analisar de alguma forma a estrutura de um algoritmo, elaborar uma estratégia de cache eficaz para é baseado na compreensão de alto nível do que o algoritmo está fazendo?
fonte
Respostas:
Eu não conheço um método para analisar um determinado algoritmo arbitrário para criar uma política de cache em geral (isso soa bastante difícil), mas é basicamente isso que é feito (de maneira ideal, em um sentido assintótico) caso a caso. caso-base para os algoritmos mais alheios ao cache , analisando sua estrutura de dividir e conquistar. Os algoritmos que ignoram o cache são conhecidos por FFT, multiplicação de matrizes, classificação e alguns outros. Veja a página da Wikipedia e as referências nela.
fonte