blob: 7848b142fdece50356417442728dbf69888b2484 [file] [log] [blame]
/*
* Copyright (c) 2020 Inria
* Copyright (c) 2020 ARM Limited
* All rights reserved
*
* The license below extends only to copyright in the software and shall
* not be construed as granting a license to any other intellectual
* property including but not limited to intellectual property relating
* to a hardware implementation of the functionality of the software
* licensed hereunder. You may use the software subject to the license
* terms below provided that you ensure that this notice is replicated
* unmodified and in its entirety in all distributions of the software,
* modified or unmodified, in source code or in binary form.
*
* Copyright (c) 1999-2012 Mark D. Hill and David A. Wood
* 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.
*/
#include "mem/ruby/structures/RubyPrefetcher.hh"
#include <cassert>
#include "base/bitfield.hh"
#include "debug/RubyPrefetcher.hh"
#include "mem/ruby/slicc_interface/RubySlicc_ComponentMapping.hh"
#include "mem/ruby/system/RubySystem.hh"
RubyPrefetcher::RubyPrefetcher(const Params &p)
: SimObject(p), m_num_streams(p.num_streams),
m_array(p.num_streams), m_train_misses(p.train_misses),
m_num_startup_pfs(p.num_startup_pfs),
unitFilter(p.unit_filter),
negativeFilter(p.unit_filter),
nonUnitFilter(p.nonunit_filter),
m_prefetch_cross_pages(p.cross_page),
m_page_shift(p.sys->getPageShift()),
rubyPrefetcherStats(this)
{
assert(m_num_streams > 0);
assert(m_num_startup_pfs <= MAX_PF_INFLIGHT);
}
RubyPrefetcher::
RubyPrefetcherStats::RubyPrefetcherStats(Stats::Group *parent)
: Stats::Group(parent, "RubyPrefetcher"),
ADD_STAT(numMissObserved, "Number of misses observed"),
ADD_STAT(numAllocatedStreams, "Number of streams allocated for "
"prefetching"),
ADD_STAT(numPrefetchRequested, "Number of prefetch requests made"),
ADD_STAT(numHits, "Number of prefetched blocks accessed "
"(for the first time)"),
ADD_STAT(numPartialHits, "Number of misses observed for a block being "
"prefetched"),
ADD_STAT(numPagesCrossed, "Number of prefetches across pages"),
ADD_STAT(numMissedPrefetchedBlocks, "Number of misses for blocks that "
"were prefetched, yet missed")
{
}
void
RubyPrefetcher::observeMiss(Addr address, const RubyRequestType& type)
{
DPRINTF(RubyPrefetcher, "Observed miss for %#x\n", address);
Addr line_addr = makeLineAddress(address);
rubyPrefetcherStats.numMissObserved++;
// check to see if we have already issued a prefetch for this block
uint32_t index = 0;
PrefetchEntry *pfEntry = getPrefetchEntry(line_addr, index);
if (pfEntry != NULL) {
if (pfEntry->requestIssued[index]) {
if (pfEntry->requestCompleted[index]) {
// We prefetched too early and now the prefetch block no
// longer exists in the cache
rubyPrefetcherStats.numMissedPrefetchedBlocks++;
return;
} else {
// The controller has issued the prefetch request,
// but the request for the block arrived earlier.
rubyPrefetcherStats.numPartialHits++;
observePfMiss(line_addr);
return;
}
} else {
// The request is still in the prefetch queue of the controller.
// Or was evicted because of other requests.
return;
}
}
// Check if address is in any of the stride filters
if (accessUnitFilter(&unitFilter, line_addr, 1, type)) {
DPRINTF(RubyPrefetcher, " *** hit in unit stride buffer\n");
return;
}
if (accessUnitFilter(&negativeFilter, line_addr, -1, type)) {
DPRINTF(RubyPrefetcher, " *** hit in unit negative unit buffer\n");
return;
}
if (accessNonunitFilter(line_addr, type)) {
DPRINTF(RubyPrefetcher, " *** hit in non-unit stride buffer\n");
return;
}
}
void
RubyPrefetcher::observePfMiss(Addr address)
{
rubyPrefetcherStats.numPartialHits++;
DPRINTF(RubyPrefetcher, "Observed partial hit for %#x\n", address);
issueNextPrefetch(address, NULL);
}
void
RubyPrefetcher::observePfHit(Addr address)
{
rubyPrefetcherStats.numHits++;
DPRINTF(RubyPrefetcher, "Observed hit for %#x\n", address);
issueNextPrefetch(address, NULL);
}
void
RubyPrefetcher::issueNextPrefetch(Addr address, PrefetchEntry *stream)
{
// get our corresponding stream fetcher
if (stream == NULL) {
uint32_t index = 0;
stream = getPrefetchEntry(address, index);
}
// if (for some reason), this stream is unallocated, return.
if (stream == NULL) {
DPRINTF(RubyPrefetcher, "Unallocated stream, returning\n");
return;
}
// extend this prefetching stream by 1 (or more)
Addr page_addr = pageAddress(stream->m_address);
Addr line_addr = makeNextStrideAddress(stream->m_address,
stream->m_stride);
// possibly stop prefetching at page boundaries
if (page_addr != pageAddress(line_addr)) {
if (!m_prefetch_cross_pages) {
// Deallocate the stream since we are not prefetching
// across page boundries
stream->m_is_valid = false;
return;
}
rubyPrefetcherStats.numPagesCrossed++;
}
// launch next prefetch
rubyPrefetcherStats.numPrefetchRequested++;
stream->m_address = line_addr;
stream->m_use_time = m_controller->curCycle();
DPRINTF(RubyPrefetcher, "Requesting prefetch for %#x\n", line_addr);
m_controller->enqueuePrefetch(line_addr, stream->m_type);
}
uint32_t
RubyPrefetcher::getLRUindex(void)
{
uint32_t lru_index = 0;
Cycles lru_access = m_array[lru_index].m_use_time;
for (uint32_t i = 0; i < m_num_streams; i++) {
if (!m_array[i].m_is_valid) {
return i;
}
if (m_array[i].m_use_time < lru_access) {
lru_access = m_array[i].m_use_time;
lru_index = i;
}
}
return lru_index;
}
void
RubyPrefetcher::initializeStream(Addr address, int stride,
uint32_t index, const RubyRequestType& type)
{
rubyPrefetcherStats.numAllocatedStreams++;
// initialize the stream prefetcher
PrefetchEntry *mystream = &(m_array[index]);
mystream->m_address = makeLineAddress(address);
mystream->m_stride = stride;
mystream->m_use_time = m_controller->curCycle();
mystream->m_is_valid = true;
mystream->m_type = type;
// create a number of initial prefetches for this stream
Addr page_addr = pageAddress(mystream->m_address);
Addr line_addr = makeLineAddress(mystream->m_address);
// insert a number of prefetches into the prefetch table
for (int k = 0; k < m_num_startup_pfs; k++) {
line_addr = makeNextStrideAddress(line_addr, stride);
// possibly stop prefetching at page boundaries
if (page_addr != pageAddress(line_addr)) {
if (!m_prefetch_cross_pages) {
// deallocate this stream prefetcher
mystream->m_is_valid = false;
return;
}
rubyPrefetcherStats.numPagesCrossed++;
}
// launch prefetch
rubyPrefetcherStats.numPrefetchRequested++;
DPRINTF(RubyPrefetcher, "Requesting prefetch for %#x\n", line_addr);
m_controller->enqueuePrefetch(line_addr, m_array[index].m_type);
}
// update the address to be the last address prefetched
mystream->m_address = line_addr;
}
PrefetchEntry *
RubyPrefetcher::getPrefetchEntry(Addr address, uint32_t &index)
{
// search all streams for a match
for (int i = 0; i < m_num_streams; i++) {
// search all the outstanding prefetches for this stream
if (m_array[i].m_is_valid) {
for (int j = 0; j < m_num_startup_pfs; j++) {
if (makeNextStrideAddress(m_array[i].m_address,
-(m_array[i].m_stride*j)) == address) {
return &(m_array[i]);
}
}
}
}
return NULL;
}
bool
RubyPrefetcher::accessUnitFilter(CircularQueue<UnitFilterEntry>* const filter,
Addr line_addr, int stride, const RubyRequestType& type)
{
for (auto& entry : *filter) {
if (entry.addr == line_addr) {
entry.addr = makeNextStrideAddress(entry.addr, stride);
entry.hits++;
if (entry.hits >= m_train_misses) {
// Allocate a new prefetch stream
initializeStream(line_addr, stride, getLRUindex(), type);
}
return true;
}
}
// Enter this address in the filter
filter->push_back(UnitFilterEntry(
makeNextStrideAddress(line_addr, stride)));
return false;
}
bool
RubyPrefetcher::accessNonunitFilter(Addr line_addr,
const RubyRequestType& type)
{
/// look for non-unit strides based on a (user-defined) page size
Addr page_addr = pageAddress(line_addr);
for (auto& entry : nonUnitFilter) {
if (pageAddress(entry.addr) == page_addr) {
// hit in the non-unit filter
// compute the actual stride (for this reference)
int delta = line_addr - entry.addr;
if (delta != 0) {
// no zero stride prefetches
// check that the stride matches (for the last N times)
if (delta == entry.stride) {
// -> stride hit
// increment count (if > 2) allocate stream
entry.hits++;
if (entry.hits > m_train_misses) {
// This stride HAS to be the multiplicative constant of
// dataBlockBytes (bc makeNextStrideAddress is
// calculated based on this multiplicative constant!)
const int stride = entry.stride /
RubySystem::getBlockSizeBytes();
// clear this filter entry
entry.clear();
initializeStream(line_addr, stride, getLRUindex(),
type);
}
} else {
// If delta didn't match reset entry's hit count
entry.hits = 0;
}
// update the last address seen & the stride
entry.addr = line_addr;
entry.stride = delta;
return true;
} else {
return false;
}
}
}
// not found: enter this address in the table
nonUnitFilter.push_back(NonUnitFilterEntry(line_addr));
return false;
}
void
RubyPrefetcher::print(std::ostream& out) const
{
out << name() << " Prefetcher State\n";
// print out unit filter
out << "unit table:\n";
for (const auto& entry : unitFilter) {
out << entry.addr << std::endl;
}
out << "negative table:\n";
for (const auto& entry : negativeFilter) {
out << entry.addr << std::endl;
}
// print out non-unit stride filter
out << "non-unit table:\n";
for (const auto& entry : nonUnitFilter) {
out << entry.addr << " "
<< entry.stride << " "
<< entry.hits << std::endl;
}
// print out allocated stream buffers
out << "streams:\n";
for (int i = 0; i < m_num_streams; i++) {
out << m_array[i].m_address << " "
<< m_array[i].m_stride << " "
<< m_array[i].m_is_valid << " "
<< m_array[i].m_use_time << std::endl;
}
}
Addr
RubyPrefetcher::pageAddress(Addr addr) const
{
return mbits<Addr>(addr, 63, m_page_shift);
}