Embedded C - Как создать кеш для дорогих внешних чтений?

Question

Я работаю с микроконтроллером, который имеет внешнюю EEPROM, содержащую таблицы информации.

Существует большое количество информации, однако есть большая вероятность, что мы будем запрашивать один и тот же информационный цикл, еслимы достаточно «стабильны» - например, если мы находимся при постоянной температуре.

Чтения из EEPROM занимают около 1 мс, а у нас около 30 за цикл.Наш цикл в настоящее время составляет около 100 мс, поэтому есть существенная экономия.

Поэтому я смотрю на реализацию кэш-памяти RAM.Удар должен быть значительно быстрее, чем 1 мс, поскольку ядро ​​микроконтроллера работает на частоте 8 МГц.

Поиск включает 16-битный адрес, возвращающий 16-битные данные.Микроконтроллер 32-битный.

Любой вклад в кэширование будет принят, особенно если я полностью пропускаю метку и должен использовать что-то еще, например, связанный список или даже ранее существующую библиотеку.

Вот что я пытаюсь достичь:

-Кэш, состоящий из массива структур.Структура будет содержать адрес, данные и какой-то счетчик, указывающий, как часто к этой части данных обращаются (readCount).

- Массив будет отсортирован по адресу в обычном порядке.У меня была бы эффективная функция lookup () для поиска адреса и получения данных (предложения?)

-Если я получил ошибку в кэше, я бы отсортировал массив по readCount, чтобы определить наименее используемое кэшированное значение ивыброси это.Затем я заполнил бы его позицию новым значением, которое я нашел в EEPROM.Затем я бы переупорядочил массив по адресу.Любая сортировка будет использовать эффективную сортировку (shell sort? - не знаю, как справиться с этим с массивами)

- я бы как-то уменьшил все переменные 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

Сортировка и перемещение данных кажутся плохой идеей, и неясно, что вы получите от этого что-то полезное.

Я бы предложил гораздо более простой подход.Выделите 4*N (для некоторых N) байтов данных в виде массива 4-байтовых структур, каждый из которых содержит адрес и данные.Чтобы найти значение по адресу A, вы посмотрите на структуру по индексу A mod N;если его сохраненный адрес - тот, который вам нужен, используйте соответствующие данные, в противном случае найдите данные в EEPROM и сохраните их там вместе с адресом A.Простой, простой в реализации, простой в тестировании, а также легкий для понимания и отладки позже.

Если местоположение вашего текущего поиска, как правило, близко к местоположению предыдущих поисков, это должно работать довольно хорошо - в любое времявы извлекаете данные, они будут по крайней мере из N мест в таблице, что означает, что вы вряд ли захотите их снова в ближайшее время - я думаю, это по крайней мере такая же хорошая эвристика, как и "сколько раз я недавно использовал это ".(Если ваша EEPROM хранит несколько разных таблиц данных, вы, вероятно, могли бы просто сделать кеш для каждой из них, как самый простой способ избежать там коллизий.)

Answer 3

Не бойтесь делать больше вычислений, в большинстве случаев ввод / вывод идет медленнее. Это самая простая реализация, о которой я могу подумать:

#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 4

Вот мои предложения:

1. Лучше заменить более старую политику или заменить политику с наименьшей из последних, так как повторная перестановка наименее доступной быстро заполнит кэш, а затем просто несколько раз заменит последний элемент.1005 *

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, но, однако,он просто немного рандомизирует замену кеша, поэтому не нашел обходного пути.

Answer 5

Вы сказали, что нужная вам запись из таблицы относится к температуре, и что температура имеет тенденцию оставаться стабильной. Пока температура не изменяется слишком быстро, маловероятно, что вам понадобится запись из таблицы, которая находится на расстоянии более 1 записи от ранее необходимой записи.

Вы должны быть в состоянии достичь своей цели, сохраняя всего 3 записи в оперативной памяти. Первая запись - это та, которую вы только что использовали. Следующая запись соответствует температуре чуть ниже последнего измерения температуры, а вторая - температуре чуть выше последнего измерения температуры. При изменении температуры одна из этих записей, вероятно, становится новой текущей. Затем вы можете выполнить любую задачу, которая вам нужна, используя эти данные, а затем продолжить и прочитать нужную вам запись (выше или ниже текущей температуры) после того, как вы закончите другую работу (перед чтением следующего измерения температуры).

Поскольку в ОЗУ одновременно находятся только 3 записи, вам не нужно знать, в какой структуре данных вам нужно их хранить, чтобы получить к ним эффективный доступ или даже хранить их отсортированными, потому что это никогда не будет таким длинным.

Если температура может изменяться быстрее, чем на 1 единицу за период исследования, вы можете просто увеличить размер своего кэша и, возможно, иметь несколько предварительных записей (в направлении, где температура, кажется, движется), чем конечные записи. Тогда вы можете сохранить записи в эффективной структуре. Я не буду беспокоиться о том, как недавно вы получили доступ к записи, потому что следующие прогнозы распределения вероятности температуры, основанные на текущей температуре, обычно будут довольно хорошими. Вам нужно будет убедиться, что вы справляетесь со случаем, когда вы далеко, и вам нужно сразу же прочитать в записи только что прочитанную температуру.