// ************************************************************************** // // // // eses eses // // eses eses // // eses eseses esesese eses Embedded Systems Group // // ese ese ese ese ese // // ese eseseses eseseses ese Department of Computer Science // // eses eses ese eses // // eses eseses eseseses eses University of Kaiserslautern // // eses eses // // // // ************************************************************************** // // This module implements a simple main memory with a cache memory on top. // // The cache memory can be parameterized in terms of the size of its cache // // lines, the number of cache lines, the set associativity, and a penalty // // for cache misses, while hits are performed in zero time. // // The memory protocol is as follows: // // (1) CPU must apply for memory access by emitting reqMem until the memory // // grants access by emitting ackMem // // (2) After that, the CPU writes adrMem, the signals readMem and writeMem // // and in case of a store also dataMem until the memory has processed // // the transaction which is signaled by the memory using doneMem. // // (3) In case of a load instruction, the memory writes dataMem at the point // // of time, where dataMem holds. // // ************************************************************************** // macro DataWidth = 8; // bit-width of registers, i.e. data words macro MemSize = 10; // size of main memory in words, i.e. bv{DataWidth} macro NumOfLines = 2; // number of cache lines macro LineSize = 2; // size of cache lines in words, i.e. bv{DataWidth} macro SetAssoc = 2; // set associativity macro MissPenalty = 2; // additional time penalty for cache misses macro DivUp(n,m) = ((n-1)/m)+1; // compute n/m, but round towards infinity macro CacheSize = NumOfLines * SetAssoc * LineSize; macro LinesInMem = DivUp(MemSize,LineSize); macro TagSize = DivUp(LinesInMem,NumOfLines); macro LineIdRng = MemSize % NumOfLines; module CachedMemory(nat ?adrMem,event bv{DataWidth} dataMem, event ?readMem,?writeMem,?reqMem,!ackMem,!doneMem){ // ---------------------------------------------------------------------- // the following local variables define the cached memory: // ---------------------------------------------------------------------- [NumOfLines][SetAssoc]bool valid; [NumOfLines][SetAssoc]nat{TagSize} tagC; [NumOfLines][SetAssoc][LineSize]bv{DataWidth} lineC; [MemSize]bv{DataWidth} Mem; // ---------------------------------------------------------------------- // the following auxiliary variables are used: // ---------------------------------------------------------------------- nat{LinesInMem} lineAdr; // line address of word nat{LineSize} adrInL; // address of word in line nat{TagSize} tag; // expected tag of the line nat{NumOfLines} line; // index of line if in cache nat{SetAssoc} set; // set index in case of hit event hit,free; // true if word is in cache // ---------------------------------------------------------------------- // and here comes the behavior // ---------------------------------------------------------------------- loop { // ------------------------------------------------------------------ // wait one cycle for next instruction // ------------------------------------------------------------------ waitInstr: pause; // ------------------------------------------------------------------ // wait until a memory request appears, and immediately acknowledge // ------------------------------------------------------------------ memWait: immediate await(reqMem); emit(ackMem); // ------------------------------------------------------------------ // next check whether entire cache shall be written back or whether // a load/store instruction shall be performed // ------------------------------------------------------------------ if(readMem & writeMem) { // write back entire content of cache memory, // we assume that one line can be written per cycle for(l=0..NumOfLines-1) for(s=0..SetAssoc-1) { next(valid[l][s]) = false; let(adrOffset = (tagC[l][s] * NumOfLines + l) * LineSize) for(i=0..LineSize-1) next(Mem[adrOffset+i]) = lineC[l][s][i]; flush: pause; } emit(doneMem); } else if(readMem | writeMem) { // first determine index and tag of the cached line and the position in the line lineAdr = adrMem / LineSize; // line number of the requested word adrInL = adrMem % LineSize; // address of the word in its line tag = lineAdr / NumOfLines; // expected tag of the cached line line = lineAdr % NumOfLines; // index of the addressed line in cache // test whether a set contains the requested line in a valid state for(s=0..SetAssoc-1) if(tagC[line][s]==tag & valid[line][s]) { set = s; hit = true; } if(hit) { // in case of cache hit, we immediately transfer data from/to cache if(readMem) dataMem = lineC[line][set][adrInL]; else lineC[line][set][adrInL] = dataMem; emit(doneMem); } else { // in case of cache miss, the line has to be transferred from memory // first, find a free set or make one free if(!valid[line][0]) { set = 0; emit(free); } else { for(s=1..SetAssoc-1) if(valid[line][s-1] & !valid[line][s]) { set = s; emit(free); } } // if no line in the set is free, we write back the line in set 0, // shift all cache lines to the left, so that line SetAssoc-1 is free if(!free) { let(adrOffset = (tagC[line][0] * NumOfLines + line) * LineSize) for(i=0..LineSize-1) next(Mem[adrOffset+i]) = lineC[line][0][i]; for(s=1..SetAssoc-1) { next(valid[line][s-1]) = valid[line][s]; next(tagC[line][s-1]) = tagC[line][s]; next(lineC[line][s-1]) = lineC[line][s]; } set = SetAssoc-1; missLoc: pause; } // now, we read in the cache line from memory next(valid[line][set]) = true; next(tagC[line][set]) = tag; for(i=0..LineSize-1) next(lineC[line][set][i]) = Mem[lineAdr*LineSize+i]; readIn: pause; // due to cache miss, additional time is consumed for(i=1..MissPenalty) penality: pause; // finally, perform data transfer to bus if(readMem) next(dataMem) = lineC[line][set][adrInL]; else next(lineC[line][set][adrInL]) = dataMem; transfer: pause; emit(doneMem); } } } }