diff options
Diffstat (limited to 'src/mem/cache/tags/iic.cc')
| -rw-r--r-- | src/mem/cache/tags/iic.cc | 649 |
1 files changed, 0 insertions, 649 deletions
diff --git a/src/mem/cache/tags/iic.cc b/src/mem/cache/tags/iic.cc deleted file mode 100644 index b9e582c29..000000000 --- a/src/mem/cache/tags/iic.cc +++ /dev/null @@ -1,649 +0,0 @@ -/* - * Copyright (c) 2002-2005 The Regents of The University of Michigan - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are - * met: redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer; - * redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution; - * neither the name of the copyright holders nor the names of its - * contributors may be used to endorse or promote products derived from - * this software without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT - * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, - * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT - * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, - * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY - * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT - * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE - * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - * - * Authors: Erik Hallnor - */ - -/** - * @file - * Definitions of the Indirect Index Cache tagstore. - */ - -#include <algorithm> -#include <cmath> -#include <string> -#include <vector> - -#include "base/intmath.hh" -#include "base/trace.hh" -#include "debug/Cache.hh" -#include "debug/IIC.hh" -#include "debug/IICMore.hh" -#include "mem/cache/tags/iic.hh" -#include "mem/cache/base.hh" -#include "sim/core.hh" - -using namespace std; - -/** Track the number of accesses to each cache set. */ -#define PROFILE_IIC 1 - -IIC::IIC(IIC::Params ¶ms) : - hashSets(params.numSets), blkSize(params.blkSize), assoc(params.assoc), - hitLatency(params.hitLatency), subSize(params.subblockSize), - numSub(blkSize/subSize), - trivialSize((floorLog2(params.size/subSize)*numSub)/8), - tagShift(floorLog2(blkSize)), blkMask(blkSize - 1), - subShift(floorLog2(subSize)), subMask(numSub - 1), - hashDelay(params.hashDelay), - numTags(hashSets * assoc + params.size/blkSize -1), - numSecondary(params.size/blkSize), - tagNull(numTags), - primaryBound(hashSets * assoc) -{ - // Check parameters - if (blkSize < 4 || !isPowerOf2(blkSize)) { - fatal("Block size must be at least 4 and a power of 2"); - } - if (hashSets <= 0 || !isPowerOf2(hashSets)) { - fatal("# of hashsets must be non-zero and a power of 2"); - } - if (assoc <= 0) { - fatal("associativity must be greater than zero"); - } - if (hitLatency <= 0) { - fatal("access latency must be greater than zero"); - } - if (numSub*subSize != blkSize) { - fatal("blocksize must be evenly divisible by subblock size"); - } - - // debug stuff - freeSecond = numSecondary; - - warmedUp = false; - warmupBound = params.size/blkSize; - numBlocks = params.size/subSize; - - // Replacement Policy Initialization - repl = params.rp; - repl->setIIC(this); - - //last_miss_time = 0 - - // allocate data reference counters - dataReferenceCount = new int[numBlocks]; - memset(dataReferenceCount, 0, numBlocks*sizeof(int)); - - // Allocate storage for both internal data and block fast access data. - // We allocate it as one large chunk to reduce overhead and to make - // deletion easier. - unsigned data_index = 0; - dataStore = new uint8_t[(numBlocks + numTags) * blkSize]; - dataBlks = new uint8_t*[numBlocks]; - for (unsigned i = 0; i < numBlocks; ++i) { - dataBlks[i] = &dataStore[data_index]; - freeDataBlock(i); - data_index += subSize; - } - - assert(data_index == numBlocks * subSize); - - // allocate and init tag store - tagStore = new IICTag[numTags]; - - unsigned blkIndex = 0; - // allocate and init sets - sets = new IICSet[hashSets]; - for (unsigned i = 0; i < hashSets; ++i) { - sets[i].assoc = assoc; - sets[i].tags = new IICTag*[assoc]; - sets[i].chain_ptr = tagNull; - - for (unsigned j = 0; j < assoc; ++j) { - IICTag *tag = &tagStore[blkIndex++]; - tag->chain_ptr = tagNull; - tag->data_ptr.resize(numSub); - tag->size = blkSize; - tag->trivialData = new uint8_t[trivialSize]; - tag->numData = 0; - sets[i].tags[j] = tag; - tag->set = i; - tag->data = &dataStore[data_index]; - data_index += blkSize; - } - } - - assert(blkIndex == primaryBound); - - for (unsigned i = primaryBound; i < tagNull; i++) { - tagStore[i].chain_ptr = i+1; - //setup data ptrs to subblocks - tagStore[i].data_ptr.resize(numSub); - tagStore[i].size = blkSize; - tagStore[i].trivialData = new uint8_t[trivialSize]; - tagStore[i].numData = 0; - tagStore[i].set = 0; - tagStore[i].data = &dataStore[data_index]; - data_index += blkSize; - } - freelist = primaryBound; -} - -IIC::~IIC() -{ - delete [] dataReferenceCount; - delete [] dataStore; - delete [] tagStore; - delete [] sets; - delete [] dataBlks; -} - -/* register cache stats */ -void -IIC::regStats(const string &name) -{ - using namespace Stats; - - BaseTags::regStats(name); - - hitHashDepth.init(0, 20, 1); - missHashDepth.init(0, 20, 1); - setAccess.init(0, hashSets, 1); - - /** IIC Statistics */ - hitHashDepth - .name(name + ".hit_hash_depth_dist") - .desc("Dist. of Hash lookup depths") - .flags(pdf) - ; - - missHashDepth - .name(name + ".miss_hash_depth_dist") - .desc("Dist. of Hash lookup depths") - .flags(pdf) - ; - - repl->regStatsWithSuffix(name); - - if (PROFILE_IIC) - setAccess - .name(name + ".set_access_dist") - .desc("Dist. of Accesses across sets") - .flags(pdf) - ; - - missDepthTotal - .name(name + ".miss_depth_total") - .desc("Total of miss depths") - ; - - hashMiss - .name(name + ".hash_miss") - .desc("Total of misses in hash table") - ; - - hitDepthTotal - .name(name + ".hit_depth_total") - .desc("Total of hit depths") - ; - - hashHit - .name(name + ".hash_hit") - .desc("Total of hites in hash table") - ; -} - - -IICTag* -IIC::accessBlock(Addr addr, Cycles &lat, int context_src) -{ - Addr tag = extractTag(addr); - unsigned set = hash(addr); - Cycles set_lat; - - unsigned long chain_ptr = tagNull; - - if (PROFILE_IIC) - setAccess.sample(set); - - IICTag *tag_ptr = sets[set].findTag(tag, chain_ptr); - set_lat = Cycles(1); - if (tag_ptr == NULL && chain_ptr != tagNull) { - int secondary_depth; - tag_ptr = secondaryChain(tag, chain_ptr, &secondary_depth); - set_lat += Cycles(secondary_depth); - // set depth for statistics fix this later!!! egh - sets[set].depth = set_lat; - - if (tag_ptr != NULL) { - /* need to move tag into primary table */ - // need to preserve chain: fix this egh - sets[set].tags[assoc-1]->chain_ptr = tag_ptr->chain_ptr; - tagSwap(tag_ptr - tagStore, sets[set].tags[assoc-1] - tagStore); - tag_ptr = sets[set].findTag(tag, chain_ptr); - assert(tag_ptr!=NULL); - } - - } - set_lat = Cycles(set_lat * hashDelay + hitLatency); - if (tag_ptr != NULL) { - // IIC replacement: if this is not the first element of - // list, reorder - sets[set].moveToHead(tag_ptr); - - hitHashDepth.sample(sets[set].depth); - hashHit++; - hitDepthTotal += sets[set].depth; - tag_ptr->status |= BlkReferenced; - lat = set_lat; - if (tag_ptr->whenReady > curTick() && - cache->ticksToCycles(tag_ptr->whenReady - curTick()) > set_lat) { - lat = cache->ticksToCycles(tag_ptr->whenReady - curTick()); - } - - tag_ptr->refCount += 1; - } - else { - // fall through: cache block not found, not a hit... - missHashDepth.sample(sets[set].depth); - hashMiss++; - missDepthTotal += sets[set].depth; - lat = set_lat; - } - return tag_ptr; -} - - -IICTag* -IIC::findBlock(Addr addr) const -{ - Addr tag = extractTag(addr); - unsigned set = hash(addr); - - unsigned long chain_ptr = tagNull; - - IICTag *tag_ptr = sets[set].findTag(tag, chain_ptr); - if (tag_ptr == NULL && chain_ptr != tagNull) { - int secondary_depth; - tag_ptr = secondaryChain(tag, chain_ptr, &secondary_depth); - } - return tag_ptr; -} - - -IICTag* -IIC::findVictim(Addr addr, PacketList &writebacks) -{ - DPRINTF(IIC, "Finding Replacement for %x\n", addr); - unsigned set = hash(addr); - IICTag *tag_ptr; - unsigned long *tmp_data = new unsigned long[numSub]; - - // Get a enough subblocks for a full cache line - for (unsigned i = 0; i < numSub; ++i){ - tmp_data[i] = getFreeDataBlock(writebacks); - assert(dataReferenceCount[tmp_data[i]]==0); - } - - tag_ptr = getFreeTag(set, writebacks); - - tag_ptr->set = set; - for (unsigned i = 0; i < numSub; ++i) { - tag_ptr->data_ptr[i] = tmp_data[i]; - dataReferenceCount[tag_ptr->data_ptr[i]]++; - } - tag_ptr->numData = numSub; - assert(tag_ptr - tagStore < primaryBound); // make sure it is in primary - tag_ptr->chain_ptr = tagNull; - sets[set].moveToHead(tag_ptr); - delete [] tmp_data; - - list<unsigned long> tag_indexes; - repl->doAdvance(tag_indexes); -/* - while (!tag_indexes.empty()) { - if (!tagStore[tag_indexes.front()].isCompressed()) { - compress_blocks.push_back(&tagStore[tag_indexes.front()]); - } - tag_indexes.pop_front(); - } -*/ - - tag_ptr->re = (void*)repl->add(tag_ptr-tagStore); - - return tag_ptr; -} - -void -IIC::insertBlock(Addr addr, BlkType* blk, int context_src) -{ -} - -void -IIC::freeReplacementBlock(PacketList & writebacks) -{ - IICTag *tag_ptr; - unsigned long data_ptr; - /* consult replacement policy */ - tag_ptr = &tagStore[repl->getRepl()]; - assert(tag_ptr != NULL); - assert(tag_ptr->isValid()); - - DPRINTF(Cache, "Replacing %x in IIC: %s\n", - regenerateBlkAddr(tag_ptr->tag,0), - tag_ptr->isDirty() ? "writeback" : "clean"); - /* write back replaced block data */ - replacements[0]++; - totalRefs += tag_ptr->refCount; - ++sampledRefs; - tag_ptr->refCount = 0; - - if (tag_ptr->isDirty()) { -/* PacketPtr writeback = - buildWritebackReq(regenerateBlkAddr(tag_ptr->tag, 0), - tag_ptr->req->asid, tag_ptr->xc, blkSize, - tag_ptr->data, - tag_ptr->size); -*/ - Request *writebackReq = new Request(regenerateBlkAddr(tag_ptr->tag, 0), - blkSize, 0, Request::wbMasterId); - PacketPtr writeback = new Packet(writebackReq, MemCmd::Writeback); - writeback->allocate(); - memcpy(writeback->getPtr<uint8_t>(), tag_ptr->data, blkSize); - - writebacks.push_back(writeback); - } - - // free the data blocks - for (int i = 0; i < tag_ptr->numData; ++i) { - data_ptr = tag_ptr->data_ptr[i]; - assert(dataReferenceCount[data_ptr]>0); - if (--dataReferenceCount[data_ptr] == 0) { - freeDataBlock(data_ptr); - } - } - freeTag(tag_ptr); -} - -unsigned long -IIC::getFreeDataBlock(PacketList & writebacks) -{ - unsigned long data_ptr; - - /* find data block */ - while (blkFreelist.empty()) { - freeReplacementBlock(writebacks); - } - - data_ptr = blkFreelist.front(); - blkFreelist.pop_front(); - DPRINTF(IICMore,"Found free data at %d\n",data_ptr); - return data_ptr; -} - - - -IICTag* -IIC::getFreeTag(int set, PacketList & writebacks) -{ - unsigned long tag_index; - IICTag *tag_ptr; - // Add new tag - tag_ptr = sets[set].findFree(); - // if no free in primary, and secondary exists - if (!tag_ptr && numSecondary) { - // need to spill a tag into secondary storage - while (freelist == tagNull) { - // get replacements until one is in secondary - freeReplacementBlock(writebacks); - } - - tag_index = freelist; - freelist = tagStore[freelist].chain_ptr; - freeSecond--; - - assert(tag_index != tagNull); - tagSwap(tag_index, sets[set].tags[assoc-1] - tagStore); - tagStore[tag_index].chain_ptr = sets[set].chain_ptr; - sets[set].chain_ptr = tag_index; - - tag_ptr = sets[set].tags[assoc-1]; - } - DPRINTF(IICMore,"Found free tag at %d\n",tag_ptr - tagStore); - tagsInUse++; - if (!warmedUp && tagsInUse.value() >= warmupBound) { - warmedUp = true; - warmupCycle = curTick(); - } - - return tag_ptr; -} - -void -IIC::freeTag(IICTag *tag_ptr) -{ - unsigned long tag_index, tmp_index; - // Fix tag_ptr - if (tag_ptr) { - // we have a tag to clear - DPRINTF(IICMore,"Freeing Tag for %x\n", - regenerateBlkAddr(tag_ptr->tag,0)); - tagsInUse--; - tag_ptr->status = 0; - tag_ptr->numData = 0; - tag_ptr->re = NULL; - tag_index = tag_ptr - tagStore; - if (tag_index >= primaryBound) { - // tag_ptr points to secondary store - assert(tag_index < tagNull); // remove this?? egh - if (tag_ptr->chain_ptr == tagNull) { - // need to fix chain list - unsigned tmp_set = hash(tag_ptr->tag << tagShift); - if (sets[tmp_set].chain_ptr == tag_index) { - sets[tmp_set].chain_ptr = tagNull; - } else { - tmp_index = sets[tmp_set].chain_ptr; - while (tmp_index != tagNull - && tagStore[tmp_index].chain_ptr != tag_index) { - tmp_index = tagStore[tmp_index].chain_ptr; - } - assert(tmp_index != tagNull); - tagStore[tmp_index].chain_ptr = tagNull; - } - tag_ptr->chain_ptr = freelist; - freelist = tag_index; - freeSecond++; - } else { - // copy next chained entry to this tag location - tmp_index = tag_ptr->chain_ptr; - tagSwap(tmp_index, tag_index); - tagStore[tmp_index].chain_ptr = freelist; - freelist = tmp_index; - freeSecond++; - } - } else { - // tag_ptr in primary hash table - assert(tag_index < primaryBound); - tag_ptr->status = 0; - unsigned tmp_set = hash(tag_ptr->tag << tagShift); - if (sets[tmp_set].chain_ptr != tagNull) { // collapse chain - tmp_index = sets[tmp_set].chain_ptr; - tagSwap(tag_index, tmp_index); - tagStore[tmp_index].chain_ptr = freelist; - freelist = tmp_index; - freeSecond++; - sets[tmp_set].chain_ptr = tag_ptr->chain_ptr; - sets[tmp_set].moveToTail(tag_ptr); - } - } - } -} - -void -IIC::freeDataBlock(unsigned long data_ptr) -{ - assert(dataReferenceCount[data_ptr] == 0); - DPRINTF(IICMore, "Freeing data at %d\n", data_ptr); - blkFreelist.push_front(data_ptr); -} - -/** Use a simple modulo hash. */ -#define SIMPLE_HASH 0 - -unsigned -IIC::hash(Addr addr) const { -#if SIMPLE_HASH - return extractTag(addr) % iic_hash_size; -#else - Addr tag, mask, x, y; - tag = extractTag(addr); - mask = hashSets-1; /* assumes iic_hash_size is a power of 2 */ - x = tag & mask; - y = (tag >> (int)(::log((double)hashSets)/::log((double)2))) & mask; - assert (x < hashSets && y < hashSets); - return x ^ y; -#endif -} - - -void -IICSet::moveToHead(IICTag *tag) -{ - if (tags[0] == tag) - return; - - // write 'next' block into blks[i], moving up from MRU toward LRU - // until we overwrite the block we moved to head. - - // start by setting up to write 'blk' into blks[0] - int i = 0; - IICTag *next = tag; - - do { - assert(i < assoc); - // swap blks[i] and next - IICTag *tmp = tags[i]; - tags[i] = next; - next = tmp; - ++i; - } while (next != tag); -} - -void -IICSet::moveToTail(IICTag *tag) -{ - if (tags[assoc-1] == tag) - return; - - // write 'next' block into blks[i], moving up from MRU toward LRU - // until we overwrite the block we moved to head. - - // start by setting up to write 'blk' into blks[0] - int i = assoc - 1; - IICTag *next = tag; - - do { - assert(i >= 0); - // swap blks[i] and next - IICTag *tmp = tags[i]; - tags[i] = next; - next = tmp; - --i; - } while (next != tag); -} - -void -IIC::tagSwap(unsigned long index1, unsigned long index2) -{ - DPRINTF(IIC,"Swapping tag[%d]=%x for tag[%d]=%x\n",index1, - tagStore[index1].tag<<tagShift, index2, - tagStore[index2].tag<<tagShift); - IICTag tmp_tag; - tmp_tag = tagStore[index1]; - tagStore[index1] = tagStore[index2]; - tagStore[index2] = tmp_tag; - if (tagStore[index1].isValid()) - repl->fixTag(tagStore[index1].re, index2, index1); - if (tagStore[index2].isValid()) - repl->fixTag(tagStore[index2].re, index1, index2); -} - - -IICTag * -IIC::secondaryChain(Addr tag, unsigned long chain_ptr, - int *_depth) const -{ - int depth = 0; - while (chain_ptr != tagNull) { - DPRINTF(IIC,"Searching secondary at %d for %x\n", chain_ptr, - tag<<tagShift); - if (tagStore[chain_ptr].tag == tag && - (tagStore[chain_ptr].isValid())) { - *_depth = depth; - return &tagStore[chain_ptr]; - } - depth++; - chain_ptr = tagStore[chain_ptr].chain_ptr; - } - *_depth = depth; - return NULL; -} - -void -IIC::invalidate(IIC::BlkType *tag_ptr) -{ - if (tag_ptr) { - for (int i = 0; i < tag_ptr->numData; ++i) { - dataReferenceCount[tag_ptr->data_ptr[i]]--; - if (dataReferenceCount[tag_ptr->data_ptr[i]] == 0) { - freeDataBlock(tag_ptr->data_ptr[i]); - } - } - repl->removeEntry(tag_ptr->re); - freeTag(tag_ptr); - } -} - -void -IIC::clearLocks() -{ - for (int i = 0; i < numTags; i++){ - tagStore[i].clearLoadLocks(); - } -} - -void -IIC::cleanupRefs() -{ - for (unsigned i = 0; i < numTags; ++i) { - if (tagStore[i].isValid()) { - totalRefs += tagStore[i].refCount; - ++sampledRefs; - } - } -} |