From 93e283abb348b81d086225f7861d94901c9b0888 Mon Sep 17 00:00:00 2001 From: Nilay Vaish Date: Tue, 11 Dec 2012 10:05:54 -0600 Subject: ruby: add a prefetcher This patch adds a prefetcher for the ruby memory system. The prefetcher is based on a prefetcher implemented by others (well, I don't know who wrote the original). The prefetcher does stride-based prefetching, both unit and non-unit. It obseves the misses in the cache and trains on these. After the training period is over, the prefetcher starts issuing prefetch requests to the controller. --- src/mem/ruby/structures/Prefetcher.hh | 210 ++++++++++++++++++++++++++++++++++ 1 file changed, 210 insertions(+) create mode 100644 src/mem/ruby/structures/Prefetcher.hh (limited to 'src/mem/ruby/structures/Prefetcher.hh') diff --git a/src/mem/ruby/structures/Prefetcher.hh b/src/mem/ruby/structures/Prefetcher.hh new file mode 100644 index 000000000..f64d39f8a --- /dev/null +++ b/src/mem/ruby/structures/Prefetcher.hh @@ -0,0 +1,210 @@ +/* + * 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. + */ + +#ifndef PREFETCHER_H +#define PREFETCHER_H + +// Implements Power 4 like prefetching + +#include + +#include "base/statistics.hh" +#include "mem/ruby/buffers/MessageBuffer.hh" +#include "mem/ruby/common/Address.hh" +#include "mem/ruby/common/Global.hh" +#include "mem/ruby/slicc_interface/AbstractController.hh" +#include "mem/ruby/slicc_interface/RubyRequest.hh" +#include "params/Prefetcher.hh" +#include "sim/sim_object.hh" + +#define MAX_PF_INFLIGHT 8 + +class PrefetchEntry +{ + public: + /// constructor + PrefetchEntry() + { + // default: 1 cache-line stride + m_stride = (1 << RubySystem::getBlockSizeBits()); + m_use_time = Cycles(0); + m_is_valid = false; + } + + //! The base address for the stream prefetch + Address m_address; + + //! stride distance to get next address from + int m_stride; + + //! the last time that any prefetched request was used + Cycles m_use_time; + + //! valid bit for each stream + bool m_is_valid; + + //! L1D prefetches loads and stores + RubyRequestType m_type; + + //! Bitset for tracking prefetches for which addresses have been + //! issued, which ones have completed. + std::bitset requestIssued; + std::bitset requestCompleted; +}; + +class Prefetcher : public SimObject +{ + public: + typedef PrefetcherParams Params; + Prefetcher(const Params *p); + ~Prefetcher(); + + void issueNextPrefetch(const Address &address, PrefetchEntry *stream); + /** + * Implement the prefetch hit(miss) callback interface. + * These functions are called by the cache when it hits(misses) + * on a line with the line's prefetch bit set. If this address + * hits in m_array we will continue prefetching the stream. + */ + void observePfHit(const Address& address); + void observePfMiss(const Address& address); + + /** + * Observe a memory miss from the cache. + * + * @param address The physical address that missed out of the cache. + */ + void observeMiss(const Address& address, const RubyRequestType& type); + + /** + * Print out some statistics + */ + void print(std::ostream& out) const; + void setController(AbstractController *_ctrl) + { m_controller = _ctrl; } + + void regStats(); + + private: + /** + * Returns an unused stream buffer (or if all are used, returns the + * least recently used (accessed) stream buffer). + * @return The index of the least recently used stream buffer. + */ + uint32_t getLRUindex(void); + + //! clear a non-unit stride prefetcher entry + void clearNonunitEntry(uint32_t index); + + //! allocate a new stream buffer at a specific index + void initializeStream(const Address& address, int stride, + uint32_t index, const RubyRequestType& type); + + //! get pointer to the matching stream entry, returns NULL if not found + //! index holds the multiple of the stride this address is. + PrefetchEntry* getPrefetchEntry(const Address &address, + uint32_t &index); + + /// access a unit stride filter to determine if there is a hit + bool accessUnitFilter(std::vector
& filter_table, + uint32_t *hit_table, uint32_t &index, const Address &address, + int stride, bool &alloc); + + /// access a unit stride filter to determine if there is a hit + bool accessNonunitFilter(const Address& address, int *stride, + bool &alloc); + + //! number of prefetch streams available + uint32_t m_num_streams; + //! an array of the active prefetch streams + std::vector m_array; + + //! number of misses I must see before allocating a stream + uint32_t m_train_misses; + //! number of initial prefetches to startup a stream + uint32_t m_num_startup_pfs; + //! number of stride filters + uint32_t m_num_unit_filters; + //! number of non-stride filters + uint32_t m_num_nonunit_filters; + + /// a unit stride filter array: helps reduce BW requirement of + /// prefetching + std::vector
m_unit_filter; + /// a round robin pointer into the unit filter group + uint32_t m_unit_filter_index; + //! An array used to count the of times particular filter entries + //! have been hit + uint32_t *m_unit_filter_hit; + + //! a negative nit stride filter array: helps reduce BW requirement + //! of prefetching + std::vector
m_negative_filter; + /// a round robin pointer into the negative filter group + uint32_t m_negative_filter_index; + /// An array used to count the of times particular filter entries + /// have been hit + uint32_t *m_negative_filter_hit; + + /// a non-unit stride filter array: helps reduce BW requirement of + /// prefetching + std::vector
m_nonunit_filter; + /// An array of strides (in # of cache lines) for the filter entries + int *m_nonunit_stride; + /// An array used to count the of times particular filter entries + /// have been hit + uint32_t *m_nonunit_hit; + /// a round robin pointer into the unit filter group + uint32_t m_nonunit_index; + + /// Used for allowing prefetches across pages. + bool m_prefetch_cross_pages; + + AbstractController *m_controller; + + //! Count of accesses to the prefetcher + Stats::Scalar numMissObserved; + //! Count of prefetch streams allocated + Stats::Scalar numAllocatedStreams; + //! Count of prefetch requests made + Stats::Scalar numPrefetchRequested; + //! Count of prefetch requests accepted + Stats::Scalar numPrefetchAccepted; + //! Count of prefetches dropped + Stats::Scalar numDroppedPrefetches; + //! Count of successful prefetches + Stats::Scalar numHits; + //! Count of partial successful prefetches + Stats::Scalar numPartialHits; + //! Count of pages crossed + Stats::Scalar numPagesCrossed; + //! Count of misses incurred for blocks that were prefetched + Stats::Scalar numMissedPrefetchedBlocks; +}; + +#endif // PREFETCHER_H -- cgit v1.2.3