Embedded C - How to create a cache for expensive external reads?

Question

I am working with a microcontroller that has an external EEPROM containing tables of information.

There is a large amount of information, however there is a good chance that we will request the same information cycle to cycle if we are fairly 'stable' - i.e. if we are at a constant temperature for example.

Reads from the EEPROM take around 1ms, and we do around 30 per cycle. Our cycle is currently about 100ms so there is significant savings to be had.

I am therefore looking at implementing a RAM cache. A hit should be significantly faster than 1ms since the microcontroller core is running at 8Mhz.

The lookup involves a 16-bit address returning 16-bit data. The microcontroller is 32-bit.

Any input on caching would be greatly appreciated, especially if I am totally missing the mark and should be using something else, like a linked list, or even a pre-existing library.

Here is what I think I am trying to achieve:

-A cache made up of an array of structs. The struct would contain the address, data and some sort of counter indicating how often this piece of data has been accessed (readCount).

-The array would be sorted by address normally. I would have an efficient lookup() function to lookup an address and get the data (suggestions?)

-If I got a cache miss, I would sort the array by readCount to determine the least used cached value and throw it away. I would then fill its position with the new value I have looked up from EEPROM. I would then reorder the array by address. Any sorting would use an efficient sort (shell sort? - not sure how to handle this with arrays)

-I would somehow decrement all of the readCount variables to that they would tend to zero if not used. This should preserve constantly used variables.

Here are my thoughts so far (pseudocode, apologies for my coding style):

#define CACHE_SIZE 50

//one piece of data in the cache
struct cacheItem
    {
    uint16_t address;
    uint16_t data;
    uint8_t readCount;
    };

//array of cached addresses 
struct cacheItem cache[CACHE_SIZE]; 

//function to get data from the cache
uint16_t getDataFromCache(uint16_t address)
    {
    uint8_t cacheResult;
    struct cacheItem * cacheHit; //Pointer to a successful cache hit



    //returns CACHE_HIT if in the cache, else returns CACHE_MISS    
    cacheResult = lookUpCache(address, cacheHit);

    if(cacheResult == CACHE_MISS)
        {
        //Think this is necessary to easily weed out the least accessed address
        sortCacheByReadCount();//shell sort?

        removeLastCacheEntry(); //delete the last item that hasn't been accessed for a while

        data = getDataFromEEPROM(address); //Expensive EEPROM read

        //Add on to the bottom of the cache
        appendToCache(address, data, 1); //1 = setting readCount to 1 for new addition

        //Think this is necessary to make a lookup function faster
        sortCacheByAddress(); //shell sort?     
        }
    else
        {
        data = cacheHit->data; //We had a hit, so pull the data
        cacheHit->readCount++; //Up the importance now
        }
    return data;
    }


//Main function
main(void)
    {
    testData = getDataFromCache(1234);
    }

Am I going down the completely wrong track here? Any input is appreciated.

Answer 1

There are my suggestions:

1. Replace oldest, or replace least recent policy would be better, as reolacing least accessed would quickly fill up cache and then just repeatedly replace last element.

2. Do not traverse all array, but take some pseudo-random (seeded by address) location to replace. (special case of single location is already presented by @ruslik).

My idea would be:

#define CACHE_SIZE 50

//one piece of data in the cache
struct cacheItem
    {
    uint16_t address;
    uint16_t data;
    uint8_t whenWritten;
    };

//array of cached addresses 
struct cacheItem cache[CACHE_SIZE]; 
// curcular cache write counter
unit8_t writecount = 0;

// this suggest cache location either contains actual data or to be rewritten;
struct cacheItem *cacheLocation(uint16_t address) {
    struct cacheLocation *bestc, *c;
    int bestage = -1, age, i;
    srand(address); // i'll use standard PRNG to acquire locations; as it initialized
                    // it will always give same sequence for same location
    for(i = 0; i<4; i++) { // any number of iterations you find best
        c = &(cache[rand()%CACHE_SIZE]);
        if(c->address == address) return c; // FOUND!
        age = (writecount - whenWritten) & 0xFF; // after age 255 comes age 0 :(
        if(age > bestage) {
            bestage = age;
            bestc = c;
        }
    }
    return c;
}

....
struct cacheItem *c = cacheLocation(addr);
if(c->address != addr) {
    c->address = addr;
    c->data = external_read(addr);
    c->whenWritten = ++writecount;
}

cache age will wrap after 255 to 0 but but it's hust slightly randomizes cache replacements, so it did not make workaround.

Answer 2

Sorting and moving data seems like a bad idea, and it's not clear you gain anything useful from it.

I'd suggest a much simpler approach. Allocate 4*N (for some N) bytes of data, as an array of 4-byte structs each containing an address and the data. To look up a value at address A, you look at the struct at index A mod N; if its stored address is the one you want, then use the associated data, otherwise look up the data off the EEPROM and store it there along with address A. Simple, easy to implement, easy to test, and easy to understand and debug later.

If the location of your current lookup tends to be near the location of previous lookups, that should work quite well -- any time you're evicting data, it's going to be from at least N locations away in the table, which means you're probably not likely to want it again any time soon -- I'd guess that's at least as good a heuristic as "how many times did I recently use this". (If your EEPROM is storing several different tables of data, you could probably just do a cache for each one as the simplest way to avoid collisions there.)

Answer 3

You said that which entry you need from the table relates to the temperature, and that the temperature tends to remain stable. As long as the temperature does not change too quickly then it is unlikely that you will need an entry from the table which more than 1 entry away from the previously needed entry.

You should be able to accomplish your goal by keeping just 3 entries in RAM. The first entry is the one you just used. The next entry is the one corresponding to the temperature just below the last temperature measurement, and the other one is the temperature just above the last temperature measurement. When the temperature changes one of these entries probably becomes the new current one. You can then preform whatever task it is you need using this data, and then go ahead and read the entry you need (higher or lower than the current temperature) after you have finished other work (before reading the next temperature measure).

Since there are only 3 entries in RAM at a time you don't have to be clever about what data structure you need to store them in to access them efficiently, or even keeping them sorted because it will never be that long.

If temperatures can move faster than 1 unit per examination period then you could just increase the size of your cache and maybe have a few more anticipatory entries (in the direction that temperature seems to be heading) than you do trailing entries. Then you may want to store the entries in an efficient structure, though. I wouldn't worry about how recently you accessed an entry, though, because next temperature probability distribution predictions based on current temperature will usually be pretty good. You will need to make sure you handle the case where you are way off and need to read in the entry for a just read temperature immediately, though.

Answer 4

Repeated sorting sounds expensive to me. I would implement the cache as a hash table on the address. To keep things simple, I would start by not even counting hits but rather evicting old entries immediately on seeing a hash collision:

const int CACHE_SIZE=32; // power of two

struct CacheEntry { 
    int16_t address;
    int16_t value
};

CacheEntry cache[CACHE_SIZE];

// adjust shifts for different CACHE_SIZE
inline int cacheIndex(int adr) { return (((adr>>10)+(adr>>5)+adr)&(CACHE_SIZE-1)); }

int16_t cachedRead( int16_t address )
{
    int idx = cacheIndex( address );
    CacheEntry * pCache = cache+idx;
    if( address != pCache->address ) {
         pCache->value = readEeprom( address );
         pCache->address = address;
    }
    return pCache->value
}

If this proves not effective enough, I would start by fiddling around with the hash function.

Answer 5

Don't be afraid to do more computations, in most cases I/O is slower. This is the simpliest implementation I can think of:

#define CACHE_SIZE 50

something   cached_vals[CACHE_SIZE];
short int   cached_item_num[CACHE_SIZE];    
char        cache_hits[CACHE_SIZE]; // 0 means free.


void inc_hits(char index){
    if (cache_hits[index] > 127){
        for (int i = 0; i < CACHE_SIZE; i++)
            cache_hits[i] <<= 1;
            cache_hits[i]++;    // 0 is reserved as "free" marker
    };
    cache_hits[index]++;
}:

int get_new_space(short int item){
    for (int i = 0; i < CACHE_SIZE; i++)
        if (!cache_hits[i]) {
            inc_hits(i);
            return i;   
        };
    // no free values, dropping the one with lowest count
    int min_val = 0;
    for (int i = 1; i < CACHE_SIZE; i++)
        min_val = min(cache_hits[min_val], cache_hits[i]);
    cache_hits[min_val] = 2; // just to give new values more chanches to "survive"
    cached_item_num[min_val] = item;
    return min_val;
};


something* get_item(short int item){
    for (int i = 0; i < CACHE_SIZE; i++){
        if (cached_item_num[i] == item){    
            inc_hits(i);
            return cached_vals + i;
        };
    };
    int new_item = get_new_space(item);
    read_from_eeprom(item, cached_vals + new_item);
    return chached_vals + new_item; 
};