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

Question

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

信息量很大，但是，如果我们相当“稳定”，例如，如果我们处于恒温状态，那么我们很有可能会要求相同的信息周期来循环。

从 EEPROM 读取大约需要 1 毫秒，每个周期大约读取 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
}

如果这证明不够有效，我会首先摆弄哈希函数。

Answer 2

不要害怕进行更多计算，大多数情况下 I/O 会更慢。
这是我能想到的最简单的实现：

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

Answer 3

对数据进行排序和移动似乎是一个坏主意，并且不清楚您是否能从中获得任何有用的东西。

我建议采用一种更简单的方法。分配 4*N（对于某些 N）字节的数据，作为 4 字节结构体的数组，每个结构体包含一个地址和数据。要查找地址 A 处的值，请查看索引 A mod N 处的结构；如果其存储的地址是您想要的，则使用关联的数据，否则从 EEPROM 中查找数据并将其与地址 A 一起存储在那里。简单，容易实现，容易测试，也容易后期理解和调试。

如果当前查找的位置往往靠近先前查找的位置，那么这应该会很好地工作 - 任何时候您驱逐数据时，它都将来自表中至少 N 个位置，这意味着您'我想这至少是一个和“我最近用了多少次这个”一样好的启发式方法。 （如果您的 EEPROM 存储多个不同的数据表，您可能只需为每个表创建一个缓存，作为避免冲突的最简单方法。）

Answer 4

你说你需要从表中选择哪一项与温度有关，并且温度往往保持稳定。只要温度变化不太快，那么您不太可能需要表中与先前需要的条目相距超过 1 个条目的条目。

您只需在 RAM 中保留 3 个条目就应该能够实现您的目标。第一个条目是您刚刚使用的条目。下一个条目是与刚刚低于最后一个温度测量值的温度相对应的一个条目，另一个条目是刚刚高于最后一个温度测量值的温度。当温度发生变化时，这些条目之一可能会成为新的当前条目。然后，您可以使用此数据执行所需的任何任务，然后在完成其他工作后（在读取下一个温度测量值之前）继续读取所需的条目（高于或低于当前温度）。

由于 RAM 中一次只有 3 个条目，因此您不必聪明地了解需要将它们存储在什么数据结构中才能有效地访问它们，甚至不必对它们进行排序，因为它永远不会那么长。

如果每个检查周期温度变化速度超过 1 个单位，那么您只需增加缓存的大小，并且可能比尾随条目有更多的预期条目（沿着温度似乎前进的方向）。不过，您可能希望将条目存储在有效的结构中。不过，我不会担心您最近访问条目的时间，因为基于当前温度的下一个温度概率分布预测通常会非常好。不过，您需要确保处理好您偏离的情况，并且需要立即读取刚刚读取的温度条目。

Answer 5

我的建议是：

1. 替换最旧的或替换最近最少的策略会更好，因为重新放置最少访问的策略会快速填满缓存，然后重复替换最后一个元素。

2. 不要遍历所有数组，而是采用一些伪随机（按地址播种）位置来替换。 （@ruslik 已经提出了单个位置的特殊情况）。

我的想法是：

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

缓存年龄将在 255 后回绕到 0，但它会稍微随机化缓存替换，因此它没有做出解决方法。