問題

私は情報テーブルを含む外部のEEPROMを持つマイクロコントローラで作業しています。

多くの情報がありますが、かなり安定している場合、同じ情報サイクルをサイクルするように要求する可能性があります。

EEPROMからの読み取りは約1msかかり、サイクルあたり約30回行います。私たちのサイクルは現在約100msなので、大きな節約があります。

したがって、RAMキャッシュの実装を検討しています。マイクロコントローラのコアが8Mhzで動作しているので、ヒットは1msよりもかなり高速でなければなりません。

ルックアップには、16ビットデータを返す16ビットアドレスが含まれます。マイクロコントローラは32ビットです。

キャッシングに関する入力は非常に高く評価されます。特に、マークが完全に見つからず、リンクされたリストや既存のライブラリのような他のものを使用する必要があります。

ここに私が達成しようとしていると思うものがあります:

-aキャッシュは構造体の配列で構成されています。構造体には、アドレス、データ、およびこのデータがどのくらい頻繁にアクセスされたかを示すカウンタが含まれます(readCount)。

- 配列は通常アドレスでソートされます。アドレスを検索してデータを取得する効率的なlookup()関数があります(提案?)

キャッシュミスがあれば、 readCount で配列をソートして、キャッシュされた最小値を決定し、それを捨てます。私はその位置をEEPROMから調べた新しい値で埋めます。私はその後、アドレスごとに配列を並べ替えます。どのソートでも効率的な並べ替え(シェルソート? - 配列でこれを処理する方法がわからない)

-iは何とかすべての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);
    }
 

私はここで完全に間違ったトラックを降りていますか?どんな入力も感謝しています。

  ベストアンサー

繰り返しソートが高価に聞こえます。私はアドレスのハッシュテーブルとしてキャッシュを実装します。物事をシンプルに保つために、私はヒットを数えずに、ハッシュの衝突を見るとすぐに古いエントリを避けることから始めます:

 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
}
 

これが十分に効果的でないことを証明すれば、私はハッシュ関数をいじることから始めます。

  同じタグがついた質問を見る

ccachingembedded