Stride Prefetcher

ggn666

May 20th, 2025

204

10 days

Add comment

Not a member of Pastebin yet? Sign Up, it unlocks many cool features!

C++ 5.23 KB | None | 0 0

raw download clone embed print report

#include <list>
#include <vector>
#include <queue>
#include <utility>
#include <unordered_map>
#include "base/types.hh"
// avoiding typedefs purposefully
class prefetchEntry
{
public:
//Addr pc;
//unsigned coreId;
std::pair<Addr, unsigned> pcAndCore;
std::queue<Addr> addrq;
prefetchEntry(Addr _pc, unsigned _coreId, Addr _addr)
{
//pc = _pc;
//coreId = _coreId;
pcAndCore = std::make_pair((Addr)_pc, (unsigned)_coreId);
addrq.push(_addr);
}
prefetchEntry(Addr _pc, unsigned _coreId)
{
//pc = _pc;
//coreId = _coreId;
pcAndCore = std::make_pair((Addr)_pc, (unsigned)_coreId);
}
bool operator==(const prefetchEntry& other) const
{
return (pcAndCore.first == other.pcAndCore.first && pcAndCore.second == other.pcAndCore.second);
}
void print()
{
std::cout << "PC: " << std::hex << pcAndCore.first << std::dec << pcAndCore.second << std::hex << ", addrq: ";
if(addrq.size() == 1)
{
std::cout << addrq.front() << std::endl;
}
else if(addrq.size() == 2)
{
std::cout << addrq.front() << ", " << addrq.back() << std::endl;
}
else
{
std::cout << "NULL" << std::endl;
}
}
};
struct prefetchEntryHash
{
template <class T1, class T2>
std::size_t operator() (const std::pair<T1, T2> &k) const
{
return std::hash<T1>()(k.first) ^ std::hash<T2>()(k.second);
}
};
class prefetchTable
{
public:
// store block addresses, LRU kept at the end, MRU kept in front
std::list<prefetchEntry> table;
std::unordered_map<std::pair<Addr, unsigned>, std::list<prefetchEntry>::iterator, prefetchEntryHash> ma;
unsigned degree;
unsigned size; //ways in a set
void printInfo()
{
std::cout << "Size: " << size << " entries" << std::endl;
std::cout << "Degree: " << degree << std::endl;
}
prefetchTable(unsigned _size, unsigned _degree)
{
size = _size;
degree = _degree;
//occupancy = 0;
}
bool find(Addr _pc, unsigned _coreId)
{
//prefetchEntry entry(_pc, _coreId);
//auto it = std::find(table.begin(), table.end(), entry);
std::pair<Addr, unsigned> _pcAndCore = std::make_pair((Addr)_pc, (unsigned)_coreId);
if(ma.find(_pcAndCore) == ma.end())
{
//std::cout << "not found.\n";
return false;
}
else
{
//std::cout << "found.";
//(*it).print();
return true;
}
}
/*
std::vector<prefetchEntry>::iterator traverse(Addr _pc)
{
for(auto it = table.begin(); it != table.end(); ++it)
{
if(it->pc == _pc)
return it;
}
return table.end();
}
*/
// updates the set, returns whether it was a hit or miss
std::vector<Addr> access(Addr _pc, unsigned _coreId, Addr _addr)
{
std::vector<Addr> memoryBlocksToPrefetch;
// find
//prefetchEntry entry(_pc, _coreId);
//auto find_it = std::find(table.begin(), table.end(), entry);
std::pair<Addr, unsigned> _pcAndCore = std::make_pair((Addr)_pc, (unsigned)_coreId);
// not present in the table
if(ma.find(_pcAndCore) == ma.end())
{
//std::cout << "miss\n";
// table is full
if(table.size() == size)
{
// delete least recently used element
auto last = table.back();
table.pop_back();
ma.erase(last.pcAndCore);
}
table.push_front(prefetchEntry(_pc, _coreId, _addr));
ma[_pcAndCore] = table.begin();
}
else
{
//std::cout << "hit\n";
// get the iterator from the hashmap
auto find_it = ma[_pcAndCore];
size_t addrqsize = find_it->addrq.size();
assert(addrqsize >= 1 && addrqsize <= 2);
// can insert the addr
if(addrqsize < 2)
{
assert(addrqsize <= 1);
find_it->addrq.push(_addr);
}
else
{
assert(addrqsize == 2);
long old_stride = find_it->addrq.back() - find_it->addrq.front();
long new_stride = _addr - find_it->addrq.back();
//std::cout << "old stride = " << std::dec << stride << "\n";
//std::cout << "new stride = " << std::dec << new_stride << "\n";
if(old_stride == new_stride)
{
/*
display();
std::cout << std::endl << std::endl;
std::cout << "Let's calculate stride: " << std::endl;
find_it->print();
std::cout << "access addr: " << _addr << std::endl;
//exit(0);
*/
// TODO: compute memory blocks to prefetch
memoryBlocksToPrefetch = blocksToPrefetch(_addr, new_stride);
}
find_it->addrq.pop();
find_it->addrq.push(_addr);
}
auto moveToFront = *find_it;
//moveToFront.print();
table.erase(find_it);
//table.insert(table.begin(), moveToFront);
table.push_front(moveToFront);
ma[_pcAndCore] = table.begin();
}
return memoryBlocksToPrefetch;
}
std::vector<Addr> blocksToPrefetch(Addr lastAddress, long stride)
{
std::vector<Addr> returnVector;
for(int i = 0; i < degree; ++i)
{
lastAddress += stride;
returnVector.push_back(lastAddress);
}
return returnVector;
}
// display contents of set
void display()
{
int idx = 0;
for (auto it = table.begin(); it != table.end(); it++)
{
std::cout << "<" << idx << ">" << "\t\t";
(*it).print();
++idx;
}
std::cout << std::endl;
}
};

Add Comment

Please, Sign In to add comment