summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorRekai Gonzalez Alberquilla <Rekai.GonzalezAlberquilla@arm.com>2016-04-07 11:32:38 -0500
committerRekai Gonzalez Alberquilla <Rekai.GonzalezAlberquilla@arm.com>2016-04-07 11:32:38 -0500
commitaf27586fbc75480725fbef0564775fe5aa8cc8d8 (patch)
tree172bc90811714896da278d16d97edbbb1f3fe4e2 /src
parentdad7d9277b571305ee248cd761a7dbb9400b3681 (diff)
downloadgem5-af27586fbc75480725fbef0564775fe5aa8cc8d8.tar.xz
mem: Add priority to QueuedPrefetcher
Queued prefetcher entries now count with a priority field. The idea is to add packets ordered by priority and then by age. For the existing algorithms in which priority doesn't make sense, it is set to 0 for all deferred packets in the queue.
Diffstat (limited to 'src')
-rw-r--r--src/mem/cache/prefetch/queued.cc189
-rw-r--r--src/mem/cache/prefetch/queued.hh29
-rw-r--r--src/mem/cache/prefetch/stride.cc4
-rw-r--r--src/mem/cache/prefetch/stride.hh3
-rw-r--r--src/mem/cache/prefetch/tagged.cc4
-rw-r--r--src/mem/cache/prefetch/tagged.hh3
6 files changed, 162 insertions, 70 deletions
diff --git a/src/mem/cache/prefetch/queued.cc b/src/mem/cache/prefetch/queued.cc
index 4bc75acd6..015609bab 100644
--- a/src/mem/cache/prefetch/queued.cc
+++ b/src/mem/cache/prefetch/queued.cc
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2014 ARM Limited
+ * Copyright (c) 2014-2015 ARM Limited
* All rights reserved
*
* The license below extends only to copyright in the software and shall
@@ -63,7 +63,7 @@ QueuedPrefetcher::notify(const PacketPtr &pkt)
{
// Verify this access type is observed by prefetcher
if (observeAccess(pkt)) {
- Addr blk_addr = pkt->getAddr() & ~(Addr)(blkSize - 1);
+ Addr blk_addr = pkt->getBlockAddr(blkSize);
bool is_secure = pkt->isSecure();
// Squash queued prefetches if demand miss to same line
@@ -82,70 +82,28 @@ QueuedPrefetcher::notify(const PacketPtr &pkt)
}
// Calculate prefetches given this access
- std::vector<Addr> addresses;
+ std::vector<AddrPriority> addresses;
calculatePrefetch(pkt, addresses);
// Queue up generated prefetches
- for (Addr pf_addr : addresses) {
+ for (AddrPriority& pf_info : addresses) {
// Block align prefetch address
- pf_addr = pf_addr & ~(Addr)(blkSize - 1);
+ pf_info.first &= ~(Addr)(blkSize - 1);
pfIdentified++;
DPRINTF(HWPrefetch, "Found a pf candidate addr: %#x, "
- "inserting into prefetch queue.\n", pf_addr);
+ "inserting into prefetch queue.\n", pf_info.first);
- if (queueFilter && inPrefetch(pf_addr, is_secure)) {
- pfBufferHit++;
- DPRINTF(HWPrefetch, "Prefetch addr already in "
- "prefetch queue\n");
- continue;
- }
-
- if (cacheSnoop && (inCache(pf_addr, is_secure) ||
- inMissQueue(pf_addr, is_secure))) {
- pfInCache++;
- DPRINTF(HWPrefetch, "Dropping redundant in "
- "cache/MSHR prefetch addr:%#x\n", pf_addr);
- continue;
- }
-
- // Create a prefetch memory request
- Request *pf_req =
- new Request(pf_addr, blkSize, 0, masterId);
-
- if (is_secure) {
- pf_req->setFlags(Request::SECURE);
- }
- pf_req->taskId(ContextSwitchTaskId::Prefetcher);
- PacketPtr pf_pkt = new Packet(pf_req, MemCmd::HardPFReq);
- pf_pkt->allocate();
-
- if (pkt->req->hasContextId()) {
- pf_req->setContext(pkt->req->contextId());
- }
-
- if (tagPrefetch && pkt->req->hasPC()) {
- // Tag prefetch packet with accessing pc
- pf_pkt->req->setPC(pkt->req->getPC());
- }
+ // Create and insert the request
+ PacketPtr pf_pkt = insert(pf_info, is_secure);
- // Verify prefetch buffer space for request
- if (pfq.size() == queueSize) {
- pfRemovedFull++;
- PacketPtr old_pkt = pfq.begin()->pkt;
- DPRINTF(HWPrefetch, "Prefetch queue full, removing "
- "oldest packet addr: %#x", old_pkt->getAddr());
- delete old_pkt->req;
- delete old_pkt;
- pfq.pop_front();
+ if (pf_pkt != nullptr) {
+ if (tagPrefetch && pkt->req->hasPC()) {
+ // Tag prefetch packet with accessing pc
+ pf_pkt->req->setPC(pkt->req->getPC());
+ }
}
-
- Tick pf_time = curTick() + clockPeriod() * latency;
- DPRINTF(HWPrefetch, "Prefetch queued. "
- "addr:%#x tick:%lld.\n", pf_addr, pf_time);
-
- pfq.emplace_back(pf_time, pf_pkt);
}
}
@@ -171,15 +129,26 @@ QueuedPrefetcher::getPacket()
return pkt;
}
-bool
+std::list<QueuedPrefetcher::DeferredPacket>::const_iterator
QueuedPrefetcher::inPrefetch(Addr address, bool is_secure) const
{
- for (const DeferredPacket &dp : pfq) {
- if (dp.pkt->getAddr() == address &&
- dp.pkt->isSecure() == is_secure) return true;
+ for (const_iterator dp = pfq.begin(); dp != pfq.end(); dp++) {
+ if ((*dp).pkt->getAddr() == address &&
+ (*dp).pkt->isSecure() == is_secure) return dp;
+ }
+
+ return pfq.end();
+}
+
+QueuedPrefetcher::iterator
+QueuedPrefetcher::inPrefetch(Addr address, bool is_secure)
+{
+ for (iterator dp = pfq.begin(); dp != pfq.end(); dp++) {
+ if (dp->pkt->getAddr() == address &&
+ dp->pkt->isSecure() == is_secure) return dp;
}
- return false;
+ return pfq.end();
}
void
@@ -207,3 +176,103 @@ QueuedPrefetcher::regStats()
.name(name() + ".pfSpanPage")
.desc("number of prefetches not generated due to page crossing");
}
+
+PacketPtr
+QueuedPrefetcher::insert(AddrPriority &pf_info, bool is_secure)
+{
+ if (queueFilter) {
+ iterator it = inPrefetch(pf_info.first, is_secure);
+ /* If the address is already in the queue, update priority and leave */
+ if (it != pfq.end()) {
+ pfBufferHit++;
+ if (it->priority < pf_info.second) {
+ /* Update priority value and position in the queue */
+ it->priority = pf_info.second;
+ iterator prev = it;
+ bool cont = true;
+ while (cont && prev != pfq.begin()) {
+ prev--;
+ /* If the packet has higher priority, swap */
+ if (*it > *prev) {
+ std::swap(*it, *prev);
+ it = prev;
+ }
+ }
+ DPRINTF(HWPrefetch, "Prefetch addr already in "
+ "prefetch queue, priority updated\n");
+ } else {
+ DPRINTF(HWPrefetch, "Prefetch addr already in "
+ "prefetch queue\n");
+ }
+ return nullptr;
+ }
+ }
+
+ if (cacheSnoop && (inCache(pf_info.first, is_secure) ||
+ inMissQueue(pf_info.first, is_secure))) {
+ pfInCache++;
+ DPRINTF(HWPrefetch, "Dropping redundant in "
+ "cache/MSHR prefetch addr:%#x\n", pf_info.first);
+ return nullptr;
+ }
+
+ /* Create a prefetch memory request */
+ Request *pf_req =
+ new Request(pf_info.first, blkSize, 0, masterId);
+
+ if (is_secure) {
+ pf_req->setFlags(Request::SECURE);
+ }
+ pf_req->taskId(ContextSwitchTaskId::Prefetcher);
+ PacketPtr pf_pkt = new Packet(pf_req, MemCmd::HardPFReq);
+ pf_pkt->allocate();
+
+ /* Verify prefetch buffer space for request */
+ if (pfq.size() == queueSize) {
+ pfRemovedFull++;
+ /* Lowest priority packet */
+ iterator it = pfq.end();
+ panic_if (it == pfq.begin(), "Prefetch queue is both full and empty!");
+ --it;
+ /* Look for oldest in that level of priority */
+ panic_if (it == pfq.begin(), "Prefetch queue is full with 1 element!");
+ iterator prev = it;
+ bool cont = true;
+ /* While not at the head of the queue */
+ while (cont && prev != pfq.begin()) {
+ prev--;
+ /* While at the same level of priority */
+ cont = (*prev).priority == (*it).priority;
+ if (cont)
+ /* update pointer */
+ it = prev;
+ }
+ DPRINTF(HWPrefetch, "Prefetch queue full, removing lowest priority "
+ "oldest packet, addr: %#x", it->pkt->getAddr());
+ delete it->pkt->req;
+ delete it->pkt;
+ pfq.erase(it);
+ }
+
+ Tick pf_time = curTick() + clockPeriod() * latency;
+ DPRINTF(HWPrefetch, "Prefetch queued. "
+ "addr:%#x priority: %3d tick:%lld.\n",
+ pf_info.first, pf_info.second, pf_time);
+
+ /* Create the packet and find the spot to insert it */
+ DeferredPacket dpp(pf_time, pf_pkt, pf_info.second);
+ if (pfq.size() == 0) {
+ pfq.emplace_back(dpp);
+ } else {
+ iterator it = pfq.end();
+ while (it != pfq.begin() && dpp > *it)
+ --it;
+ /* If we reach the head, we have to see if the new element is new head
+ * or not */
+ if (it == pfq.begin() && dpp <= *it)
+ it++;
+ pfq.insert(it, dpp);
+ }
+
+ return pf_pkt;
+}
diff --git a/src/mem/cache/prefetch/queued.hh b/src/mem/cache/prefetch/queued.hh
index 7ce9e7b93..108891fcc 100644
--- a/src/mem/cache/prefetch/queued.hh
+++ b/src/mem/cache/prefetch/queued.hh
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2014 ARM Limited
+ * Copyright (c) 2014-2015 ARM Limited
* All rights reserved
*
* The license below extends only to copyright in the software and shall
@@ -51,8 +51,23 @@ class QueuedPrefetcher : public BasePrefetcher
struct DeferredPacket {
Tick tick;
PacketPtr pkt;
- DeferredPacket(Tick t, PacketPtr p) : tick(t), pkt(p) {}
+ int32_t priority;
+ DeferredPacket(Tick t, PacketPtr p, int32_t pr) : tick(t), pkt(p),
+ priority(pr) {}
+ bool operator>(const DeferredPacket& that) const
+ {
+ return priority > that.priority;
+ }
+ bool operator<(const DeferredPacket& that) const
+ {
+ return priority < that.priority;
+ }
+ bool operator<=(const DeferredPacket& that) const
+ {
+ return !(*this > that);
+ }
};
+ using AddrPriority = std::pair<Addr, int32_t>;
std::list<DeferredPacket> pfq;
@@ -76,7 +91,12 @@ class QueuedPrefetcher : public BasePrefetcher
/** Tag prefetch with PC of generating access? */
const bool tagPrefetch;
- bool inPrefetch(Addr address, bool is_secure) const;
+ using const_iterator = std::list<DeferredPacket>::const_iterator;
+ std::list<DeferredPacket>::const_iterator inPrefetch(Addr address,
+ bool is_secure) const;
+ using iterator = std::list<DeferredPacket>::iterator;
+ std::list<DeferredPacket>::iterator inPrefetch(Addr address,
+ bool is_secure);
// STATS
Stats::Scalar pfIdentified;
@@ -90,10 +110,11 @@ class QueuedPrefetcher : public BasePrefetcher
virtual ~QueuedPrefetcher();
Tick notify(const PacketPtr &pkt);
+ PacketPtr insert(AddrPriority& info, bool is_secure);
// Note: This should really be pure virtual, but doesnt go well with params
virtual void calculatePrefetch(const PacketPtr &pkt,
- std::vector<Addr> &addresses) = 0;
+ std::vector<AddrPriority> &addresses) = 0;
PacketPtr getPacket();
Tick nextPrefetchReadyTime() const
diff --git a/src/mem/cache/prefetch/stride.cc b/src/mem/cache/prefetch/stride.cc
index 4456cf237..6b8fee828 100644
--- a/src/mem/cache/prefetch/stride.cc
+++ b/src/mem/cache/prefetch/stride.cc
@@ -98,7 +98,7 @@ StridePrefetcher::PCTable::~PCTable() {
void
StridePrefetcher::calculatePrefetch(const PacketPtr &pkt,
- std::vector<Addr> &addresses)
+ std::vector<AddrPriority> &addresses)
{
if (!pkt->req->hasPC()) {
DPRINTF(HWPrefetch, "Ignoring request with no PC.\n");
@@ -153,7 +153,7 @@ StridePrefetcher::calculatePrefetch(const PacketPtr &pkt,
Addr new_addr = pkt_addr + d * prefetch_stride;
if (samePage(pkt_addr, new_addr)) {
DPRINTF(HWPrefetch, "Queuing prefetch to %#x.\n", new_addr);
- addresses.push_back(new_addr);
+ addresses.push_back(AddrPriority(new_addr, 0));
} else {
// Record the number of page crossing prefetches generated
pfSpanPage += degree - d + 1;
diff --git a/src/mem/cache/prefetch/stride.hh b/src/mem/cache/prefetch/stride.hh
index af17252d8..be6e41d0a 100644
--- a/src/mem/cache/prefetch/stride.hh
+++ b/src/mem/cache/prefetch/stride.hh
@@ -114,7 +114,8 @@ class StridePrefetcher : public QueuedPrefetcher
StridePrefetcher(const StridePrefetcherParams *p);
- void calculatePrefetch(const PacketPtr &pkt, std::vector<Addr> &addresses);
+ void calculatePrefetch(const PacketPtr &pkt,
+ std::vector<AddrPriority> &addresses);
};
#endif // __MEM_CACHE_PREFETCH_STRIDE_HH__
diff --git a/src/mem/cache/prefetch/tagged.cc b/src/mem/cache/prefetch/tagged.cc
index 59c489a28..32a5b47f8 100644
--- a/src/mem/cache/prefetch/tagged.cc
+++ b/src/mem/cache/prefetch/tagged.cc
@@ -43,7 +43,7 @@ TaggedPrefetcher::TaggedPrefetcher(const TaggedPrefetcherParams *p)
void
TaggedPrefetcher::calculatePrefetch(const PacketPtr &pkt,
- std::vector<Addr> &addresses)
+ std::vector<AddrPriority> &addresses)
{
Addr blkAddr = pkt->getAddr() & ~(Addr)(blkSize-1);
@@ -54,7 +54,7 @@ TaggedPrefetcher::calculatePrefetch(const PacketPtr &pkt,
pfSpanPage += degree - d + 1;
return;
} else {
- addresses.push_back(newAddr);
+ addresses.push_back(AddrPriority(newAddr,0));
}
}
}
diff --git a/src/mem/cache/prefetch/tagged.hh b/src/mem/cache/prefetch/tagged.hh
index 1aa96f5fa..02debe91a 100644
--- a/src/mem/cache/prefetch/tagged.hh
+++ b/src/mem/cache/prefetch/tagged.hh
@@ -50,7 +50,8 @@ class TaggedPrefetcher : public QueuedPrefetcher
~TaggedPrefetcher() {}
- void calculatePrefetch(const PacketPtr &pkt, std::vector<Addr> &addresses);
+ void calculatePrefetch(const PacketPtr &pkt,
+ std::vector<AddrPriority> &addresses);
};
#endif // __MEM_CACHE_PREFETCH_TAGGED_HH__