嵌入式C - 如何为昂贵的外部读取创建缓存？

Question

我正在使用一个带有包含信息表的外部EEPROM的微控制器.

存在大量信息,但是如果我们相当"稳定",我们很可能会要求相同的信息周期循环 - 例如,如果我们处于恒定温度.

EEPROM读取大约需要1ms,每个周期大约需要30次.我们的周期目前约为100毫秒,因此可以节省大量成本.

因此,我正在考虑实现RAM缓存.由于微控制器内核以8Mhz运行,因此命中速度应明显快于1ms.

查找涉及返回16位数据的16位地址.微控制器是32位的.

任何关于缓存的输入都将非常受欢迎,特别是如果我完全错过了标记并且应该使用其他东西,如链接列表,甚至是预先存在的库.

以下是我认为我想要实现的目标:

- 由一组结构组成的缓存.该结构将包含地址,数据和某种计数器,指示访问此数据的频率(readCount).

- 数组通常按地址排序.我会有一个有效的lookup()函数来查找地址并获取数据(建议？)

- 如果我遇到缓存未命中,我会通过readCount对数组进行排序,以确定最少使用的缓存值并将其丢弃.然后,我将用从EEPROM中查找的新值填充其位置.然后我会按地址重新排序数组.任何排序都会使用有效排序(shell排序？ - 不知道如何使用数组处理这个)

- 我会以某种方式将所有readCount变量减少到如果不使用它们将倾向于零.这应该保留经常使用的变量.

到目前为止,这是我的想法(伪代码,为我的编码风格道歉):

#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);
    }

我在这里走错了轨道吗？任何输入都表示赞赏.

Answer 1

重复排序对我来说听起来很昂贵.我会将缓存实现为地址上的哈希表.为了简单起见,我首先不计算命中数,而是在看到哈希冲突时立即驱逐旧条目:

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
}

如果这证明不够有效,我会从摆弄哈希函数开始.