iic.cc

来自「linux下基于c++的处理器仿真平台。具有处理器流水线」· CC 代码 · 共 872 行 · 第 1/2 页

/*
 * Copyright (c) 2002, 2003, 2004, 2005
 * The Regents of The University of Michigan
 * All Rights Reserved
 *
 * This code is part of the M5 simulator, developed by Nathan Binkert,
 * Erik Hallnor, Steve Raasch, and Steve Reinhardt, with contributions
 * from Ron Dreslinski, Dave Greene, Lisa Hsu, Kevin Lim, Ali Saidi,
 * and Andrew Schultz.
 *
 * Permission is granted to use, copy, create derivative works and
 * redistribute this software and such derivative works for any
 * purpose, so long as the copyright notice above, this grant of
 * permission, and the disclaimer below appear in all copies made; and
 * so long as the name of The University of Michigan is not used in
 * any advertising or publicity pertaining to the use or distribution
 * of this software without specific, written prior authorization.
 *
 * THIS SOFTWARE IS PROVIDED AS IS, WITHOUT REPRESENTATION FROM THE
 * UNIVERSITY OF MICHIGAN AS TO ITS FITNESS FOR ANY PURPOSE, AND
 * WITHOUT WARRANTY BY THE UNIVERSITY OF MICHIGAN OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE. THE REGENTS OF THE UNIVERSITY OF MICHIGAN SHALL NOT BE
 * LIABLE FOR ANY DAMAGES, INCLUDING DIRECT, SPECIAL, INDIRECT,
 * INCIDENTAL, OR CONSEQUENTIAL DAMAGES, WITH RESPECT TO ANY CLAIM
 * ARISING OUT OF OR IN CONNECTION WITH THE USE OF THE SOFTWARE, EVEN
 * IF IT HAS BEEN OR IS HEREAFTER ADVISED OF THE POSSIBILITY OF SUCH
 * DAMAGES.
 */

/**
 * @file
 * Definitions of the Indirect Index Cache tagstore.
 */

#include <algorithm>
#include <string>
#include <vector>
#include <sstream>

#include <math.h>

#include "mem/cache/base_cache.hh"
#include "mem/cache/tags/iic.hh"
#include "base/intmath.hh"
#include "sim/root.hh" // for curTick

#include "base/trace.hh" // for DPRINTF


using namespace std;

/** Track the number of accesses to each cache set. */
#define PROFILE_IIC 1

IIC::IIC(IIC::Params &params) :
    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),
    numBlocks(params.size/subSize), 
    numTags(hashSets * assoc + params.size/blkSize -1), 
    numSecondary(params.size/blkSize),
    tagNull(numTags),
    primaryBound(hashSets * assoc)
{
    int i;

    // Check parameters
    if (blkSize < 4 || ((blkSize & (blkSize - 1)) != 0)) {
	fatal("Block size must be at least 4 and a power of 2");
    }
    if (hashSets <= 0 || ((hashSets & (hashSets - 1)) != 0)) {
	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;
  
    // 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.
    int data_index = 0;
    dataStore = new uint8_t[(numBlocks + numTags) * blkSize];
    dataBlks = new uint8_t*[numBlocks];
    for (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];
    
    int blkIndex = 0;
    // allocate and init sets
    sets = new IICSet[hashSets];
    for (i = 0; i < hashSets; ++i) {
	sets[i].assoc = assoc;
	sets[i].tags = new IICTag*[assoc];
	sets[i].chain_ptr = tagNull;
	
	for (int 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 (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;
}

/* 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->regStats(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")
	;
}

// probe cache for presence of given block.
bool
IIC::probe(int asid, Addr addr) const
{
    return (findBlock(addr,asid) != NULL);
}

IICTag*
IIC::findBlock(Addr addr, int asid, int &lat)
{
    Addr tag = extractTag(addr);
    unsigned set = hash(addr);
    int set_lat;

    unsigned long chain_ptr;

    if (PROFILE_IIC)
	setAccess.sample(set);

    IICTag *tag_ptr = sets[set].findTag(asid, tag, chain_ptr);
    set_lat = 1;
    if (tag_ptr == NULL && chain_ptr != tagNull) {
	int secondary_depth;
	tag_ptr = secondaryChain(asid, tag, chain_ptr, &secondary_depth);
	set_lat += 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(asid, tag, chain_ptr);
	    assert(tag_ptr!=NULL);
	}

    }
    set_lat = 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 && tag_ptr->whenReady - curTick > set_lat) {
	    lat = 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(MemReqPtr &req, int &lat)
{
    Addr addr = req->paddr;
    int asid = req->asid;

    Addr tag = extractTag(addr);
    unsigned set = hash(addr);
    int set_lat;

    unsigned long chain_ptr;

    if (PROFILE_IIC)
	setAccess.sample(set);

    IICTag *tag_ptr = sets[set].findTag(asid, tag, chain_ptr);
    set_lat = 1;
    if (tag_ptr == NULL && chain_ptr != tagNull) {
	int secondary_depth;
	tag_ptr = secondaryChain(asid, tag, chain_ptr, &secondary_depth);
	set_lat += 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(asid, tag, chain_ptr);
	    assert(tag_ptr!=NULL);
	}

    }
    set_lat = 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 && tag_ptr->whenReady - curTick > set_lat) {
	    lat = 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, int asid) const
{
    Addr tag = extractTag(addr);
    unsigned set = hash(addr);

    unsigned long chain_ptr;

    IICTag *tag_ptr = sets[set].findTag(asid, tag, chain_ptr);
    if (tag_ptr == NULL && chain_ptr != tagNull) {
	int secondary_depth;
	tag_ptr = secondaryChain(asid, tag, chain_ptr, &secondary_depth);
    }
    return tag_ptr;
}


IICTag*
IIC::findReplacement(MemReqPtr &req, MemReqList &writebacks,
		     BlkList &compress_blocks)
{
    DPRINTF(IIC, "Finding Replacement for %x\n", req->paddr);
    unsigned set = hash(req->paddr);
    IICTag *tag_ptr;
    unsigned long *tmp_data = new unsigned long[numSub];

    // Get a enough subblocks for a full cache line
    for (int 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 (int 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::freeReplacementBlock(MemReqList & writebacks)
{
    IICTag *tag_ptr;
    unsigned long data_ptr;
    /* consult replacement policy */
    tag_ptr = &tagStore[repl->getRepl()];
    assert(tag_ptr->isValid());

    DPRINTF(Cache, "Replacing %x in IIC: %s\n",
	    regenerateBlkAddr(tag_ptr->tag,0),
	    tag_ptr->isModified() ? "writeback" : "clean");
    /* write back replaced block data */
    if (tag_ptr && (tag_ptr->isValid())) {
	int thread_num = (tag_ptr->xc) ? tag_ptr->xc->thread_num : 0;
	replacements[thread_num]++;
	totalRefs += tag_ptr->refCount;
	++sampledRefs;
	tag_ptr->refCount = 0;

	if (tag_ptr->isModified()) {
	    MemReqPtr writeback = 
		buildWritebackReq(regenerateBlkAddr(tag_ptr->tag, 0), 
				  tag_ptr->asid, tag_ptr->xc, blkSize,
				  (cache->doData())?tag_ptr->data:0, 
				  tag_ptr->size);
	    writebacks.push_back(writeback);
	}