From af27586fbc75480725fbef0564775fe5aa8cc8d8 Mon Sep 17 00:00:00 2001 From: Rekai Gonzalez Alberquilla Date: Thu, 7 Apr 2016 11:32:38 -0500 Subject: 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. --- src/mem/cache/prefetch/queued.cc | 189 ++++++++++++++++++++++++++------------- src/mem/cache/prefetch/queued.hh | 29 +++++- src/mem/cache/prefetch/stride.cc | 4 +- src/mem/cache/prefetch/stride.hh | 3 +- src/mem/cache/prefetch/tagged.cc | 4 +- src/mem/cache/prefetch/tagged.hh | 3 +- 6 files changed, 162 insertions(+), 70 deletions(-) (limited to 'src/mem/cache') 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 addresses; + std::vector 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::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; std::list 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::const_iterator; + std::list::const_iterator inPrefetch(Addr address, + bool is_secure) const; + using iterator = std::list::iterator; + std::list::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 &addresses) = 0; + std::vector &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 &addresses) + std::vector &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 &addresses); + void calculatePrefetch(const PacketPtr &pkt, + std::vector &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 &addresses) + std::vector &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 &addresses); + void calculatePrefetch(const PacketPtr &pkt, + std::vector &addresses); }; #endif // __MEM_CACHE_PREFETCH_TAGGED_HH__ -- cgit v1.2.3