Jump to content

  • Log In with Google      Sign In   
  • Create Account


Cache Model Critique


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
No replies to this topic

#1 Pieisgood   Members   -  Reputation: 202

Like
0Likes
Like

Posted 27 April 2014 - 12:30 AM

I've been thinking about memory access patterns and thought about a small model to represent cache oblivious memory layouts.

 

Def: A Computer has several levels of cache. We represent the set of caches as C

 

C = { c1, c2, c3, ... , cn } where cn is the n-th cache level of the computer. 

 

Computer caches, we assume, follow two basic principles.

 

1: Memory sizes for each cache increases monotonically. 

 

size-1 < size-2 < size-3 < ... < size-n

 

2: Cache access times also increase monotonically.

 

time-1 < time-2 < time-3 < ... < time-n

 

Given this definition of a cache and it's access principles, we define access patterns as a directed acyclic graph. 

 

Each node in the graph lists the cache level accessed. 

 

We then use the graph as a probabilistic graph with which to base to the expected access times for running our algorithm.

 

 

Has anyone ever worked with a similar model or abstraction? Can you tear this apart and tell me what's wrong or could be improved?



Sponsor:



Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS