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

Question

我正在使用具有包含信息表的外部 EEPROM 的微 Controller 。

信息量很大，但是如果我们相当“稳定”(例如，如果我们处于恒定温度)，我们很有可能会请求相同的信息循环来循环。

从 EEPROM 读取大约需要 1 毫秒，我们每个周期大约读取 30 次。我们的周期目前约为 100 毫秒，因此可以节省大量资金。

因此，我正在考虑实现 RAM 缓存。由于微 Controller 内核以 8Mhz 运行，因此命中应该明显快于 1 毫秒。

查找涉及返回 16 位数据的 16 位地址。微 Controller 是 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
}

如果这证明不够有效，我会开始摆弄散列函数。