113825Sivan.pizarro@metempsy.com/** 213825Sivan.pizarro@metempsy.com * Copyright (c) 2019 Metempsy Technology Consulting 313825Sivan.pizarro@metempsy.com * All rights reserved. 413825Sivan.pizarro@metempsy.com * 513825Sivan.pizarro@metempsy.com * Redistribution and use in source and binary forms, with or without 613825Sivan.pizarro@metempsy.com * modification, are permitted provided that the following conditions are 713825Sivan.pizarro@metempsy.com * met: redistributions of source code must retain the above copyright 813825Sivan.pizarro@metempsy.com * notice, this list of conditions and the following disclaimer; 913825Sivan.pizarro@metempsy.com * redistributions in binary form must reproduce the above copyright 1013825Sivan.pizarro@metempsy.com * notice, this list of conditions and the following disclaimer in the 1113825Sivan.pizarro@metempsy.com * documentation and/or other materials provided with the distribution; 1213825Sivan.pizarro@metempsy.com * neither the name of the copyright holders nor the names of its 1313825Sivan.pizarro@metempsy.com * contributors may be used to endorse or promote products derived from 1413825Sivan.pizarro@metempsy.com * this software without specific prior written permission. 1513825Sivan.pizarro@metempsy.com * 1613825Sivan.pizarro@metempsy.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1713825Sivan.pizarro@metempsy.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1813825Sivan.pizarro@metempsy.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1913825Sivan.pizarro@metempsy.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2013825Sivan.pizarro@metempsy.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2113825Sivan.pizarro@metempsy.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2213825Sivan.pizarro@metempsy.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2313825Sivan.pizarro@metempsy.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2413825Sivan.pizarro@metempsy.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2513825Sivan.pizarro@metempsy.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2613825Sivan.pizarro@metempsy.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2713825Sivan.pizarro@metempsy.com * 2813825Sivan.pizarro@metempsy.com * Authors: Ivan Pizarro 2913825Sivan.pizarro@metempsy.com */ 3013825Sivan.pizarro@metempsy.com 3113825Sivan.pizarro@metempsy.com/** Implementation of the 'Proactive Instruction Fetch' prefetcher 3213825Sivan.pizarro@metempsy.com * Reference: 3313825Sivan.pizarro@metempsy.com * Ferdman, M., Kaynak, C., & Falsafi, B. (2011, December). 3413825Sivan.pizarro@metempsy.com * Proactive instruction fetch. 3513825Sivan.pizarro@metempsy.com * In Proceedings of the 44th Annual IEEE/ACM International Symposium 3613825Sivan.pizarro@metempsy.com * on Microarchitecture (pp. 152-162). ACM. 3713825Sivan.pizarro@metempsy.com */ 3813825Sivan.pizarro@metempsy.com 3913825Sivan.pizarro@metempsy.com#ifndef __MEM_CACHE_PREFETCH_PIF_HH__ 4013825Sivan.pizarro@metempsy.com#define __MEM_CACHE_PREFETCH_PIF_HH__ 4113825Sivan.pizarro@metempsy.com 4213825Sivan.pizarro@metempsy.com#include <deque> 4313825Sivan.pizarro@metempsy.com#include <vector> 4413825Sivan.pizarro@metempsy.com 4513825Sivan.pizarro@metempsy.com#include "mem/cache/prefetch/associative_set.hh" 4613825Sivan.pizarro@metempsy.com#include "mem/cache/prefetch/queued.hh" 4713825Sivan.pizarro@metempsy.com 4813825Sivan.pizarro@metempsy.comstruct PIFPrefetcherParams; 4913825Sivan.pizarro@metempsy.com 5013825Sivan.pizarro@metempsy.comclass PIFPrefetcher : public QueuedPrefetcher 5113825Sivan.pizarro@metempsy.com{ 5213825Sivan.pizarro@metempsy.com private: 5313825Sivan.pizarro@metempsy.com /** Number of preceding and subsequent spatial addresses to compact */ 5413825Sivan.pizarro@metempsy.com const unsigned int precSize; 5513825Sivan.pizarro@metempsy.com const unsigned int succSize; 5613825Sivan.pizarro@metempsy.com /** Number of entries used for the temporal compactor */ 5713825Sivan.pizarro@metempsy.com const unsigned int maxCompactorEntries; 5813825Sivan.pizarro@metempsy.com /** Max number of entries to be used in the Stream Address Buffer */ 5913825Sivan.pizarro@metempsy.com const unsigned int maxStreamAddressBufferEntries; 6013825Sivan.pizarro@metempsy.com 6113825Sivan.pizarro@metempsy.com /** 6213825Sivan.pizarro@metempsy.com * The compactor tracks retired instructions addresses, leveraging the 6313825Sivan.pizarro@metempsy.com * spatial and temporal locality among instructions for compaction. It 6413825Sivan.pizarro@metempsy.com *comprises the spatial and temporal compaction mechanisms. 6513825Sivan.pizarro@metempsy.com * 6613825Sivan.pizarro@metempsy.com * Taking advantage of the spatial locality across instruction blocks, 6713825Sivan.pizarro@metempsy.com * the spatial compactor combines instruction-block addresses that fall 6813825Sivan.pizarro@metempsy.com * within a 'spatial region', a group of adjacent instruction blocks. 6913825Sivan.pizarro@metempsy.com * When an instruction outside the current spatial region retires, the 7013825Sivan.pizarro@metempsy.com * existing spatial region is sent to the temporal compactor. 7113825Sivan.pizarro@metempsy.com * 7213825Sivan.pizarro@metempsy.com * The temporal compactor tracks a small number of the 7313825Sivan.pizarro@metempsy.com * most-recently-observed spatial region records. 7413825Sivan.pizarro@metempsy.com */ 7513825Sivan.pizarro@metempsy.com struct CompactorEntry { 7613825Sivan.pizarro@metempsy.com Addr trigger; 7713825Sivan.pizarro@metempsy.com std::vector<bool> prec; 7813825Sivan.pizarro@metempsy.com std::vector<bool> succ; 7913825Sivan.pizarro@metempsy.com CompactorEntry() {} 8013825Sivan.pizarro@metempsy.com CompactorEntry(Addr, unsigned int, unsigned int); 8113825Sivan.pizarro@metempsy.com 8213825Sivan.pizarro@metempsy.com /** 8313825Sivan.pizarro@metempsy.com * Checks if a given address is in the same defined spatial region 8413825Sivan.pizarro@metempsy.com * as the compactor entry. 8513825Sivan.pizarro@metempsy.com * @param addr Address to check if it's inside the spatial region 8613825Sivan.pizarro@metempsy.com * @param log_blk_distance log_2(block size of the cache) 8713825Sivan.pizarro@metempsy.com * @param update if true, set the corresponding succ/prec entry 8813825Sivan.pizarro@metempsy.com * @return TRUE if they are in the same spatial region, FALSE 8913825Sivan.pizarro@metempsy.com * otherwise 9013825Sivan.pizarro@metempsy.com */ 9113825Sivan.pizarro@metempsy.com bool inSameSpatialRegion(Addr addr, unsigned int log_blk_size, 9213825Sivan.pizarro@metempsy.com bool update); 9313825Sivan.pizarro@metempsy.com /** 9413825Sivan.pizarro@metempsy.com * Checks if the provided address is contained in this spatial 9513825Sivan.pizarro@metempsy.com * region and if its corresponding bit vector entry is set 9613825Sivan.pizarro@metempsy.com * @param target address to check 9713825Sivan.pizarro@metempsy.com * @param log_blk_distance log_2(block size of the cache) 9813825Sivan.pizarro@metempsy.com * @return TRUE if target has its bit set 9913825Sivan.pizarro@metempsy.com */ 10013825Sivan.pizarro@metempsy.com bool hasAddress(Addr target, unsigned int log_blk_size) const; 10113825Sivan.pizarro@metempsy.com 10213825Sivan.pizarro@metempsy.com /** 10313825Sivan.pizarro@metempsy.com * Fills the provided vector with the predicted addresses using the 10413825Sivan.pizarro@metempsy.com * recorded bit vectors of the entry 10513825Sivan.pizarro@metempsy.com * @param log_blk_distance log_2(block size of the cache) 10613825Sivan.pizarro@metempsy.com * @param addresses reference to a vector to add the generated 10713825Sivan.pizarro@metempsy.com * addresses 10813825Sivan.pizarro@metempsy.com */ 10913825Sivan.pizarro@metempsy.com void getPredictedAddresses(unsigned int log_blk_size, 11013825Sivan.pizarro@metempsy.com std::vector<AddrPriority> &addresses) const; 11113825Sivan.pizarro@metempsy.com private: 11213825Sivan.pizarro@metempsy.com /** 11313825Sivan.pizarro@metempsy.com * Computes the distance, in cache blocks, from an address to the 11413825Sivan.pizarro@metempsy.com * trigger of the entry. 11513825Sivan.pizarro@metempsy.com * @param addr address to compute the distance from the trigger 11613825Sivan.pizarro@metempsy.com * @param log_blk_distance log_2(block size of the cache) 11713825Sivan.pizarro@metempsy.com * @result distance in cache blocks from the address to the trigger 11813825Sivan.pizarro@metempsy.com */ 11913835Sgambordr@oregonstate.edu Addr distanceFromTrigger(Addr addr, 12013835Sgambordr@oregonstate.edu unsigned int log_blk_size) const; 12113825Sivan.pizarro@metempsy.com }; 12213825Sivan.pizarro@metempsy.com 12313825Sivan.pizarro@metempsy.com CompactorEntry spatialCompactor; 12413825Sivan.pizarro@metempsy.com std::deque<CompactorEntry> temporalCompactor; 12513825Sivan.pizarro@metempsy.com 12613825Sivan.pizarro@metempsy.com /** 12713825Sivan.pizarro@metempsy.com * History buffer is a circular buffer that stores the sequence of 12813825Sivan.pizarro@metempsy.com * retired instructions in FIFO order. 12913825Sivan.pizarro@metempsy.com */ 13013825Sivan.pizarro@metempsy.com std::vector<CompactorEntry> historyBuffer; 13113825Sivan.pizarro@metempsy.com unsigned int historyBufferTail; 13213825Sivan.pizarro@metempsy.com 13313825Sivan.pizarro@metempsy.com struct IndexEntry : public TaggedEntry 13413825Sivan.pizarro@metempsy.com { 13513825Sivan.pizarro@metempsy.com unsigned int historyIndex; 13613825Sivan.pizarro@metempsy.com }; 13713825Sivan.pizarro@metempsy.com /** 13813825Sivan.pizarro@metempsy.com * The index table is a small cache-like structure that facilitates 13913825Sivan.pizarro@metempsy.com * fast search of the history buffer. 14013825Sivan.pizarro@metempsy.com */ 14113825Sivan.pizarro@metempsy.com AssociativeSet<IndexEntry> index; 14213825Sivan.pizarro@metempsy.com 14313825Sivan.pizarro@metempsy.com /** 14413825Sivan.pizarro@metempsy.com * A Stream Address Buffer (SAB) tracks a window of consecutive 14513825Sivan.pizarro@metempsy.com * spatial regions. The SAB mantains a pointer to the sequence in the 14613825Sivan.pizarro@metempsy.com * history buffer, initiallly set to the pointer taken from the index 14713825Sivan.pizarro@metempsy.com * table 14813825Sivan.pizarro@metempsy.com */ 14913825Sivan.pizarro@metempsy.com std::deque<CompactorEntry*> streamAddressBuffer; 15013825Sivan.pizarro@metempsy.com 15113825Sivan.pizarro@metempsy.com /** 15213825Sivan.pizarro@metempsy.com * Updates the prefetcher structures upon an instruction retired 15313825Sivan.pizarro@metempsy.com * @param pc PC of the instruction being retired 15413825Sivan.pizarro@metempsy.com */ 15513825Sivan.pizarro@metempsy.com void notifyRetiredInst(const Addr pc); 15613825Sivan.pizarro@metempsy.com 15713825Sivan.pizarro@metempsy.com /** 15813825Sivan.pizarro@metempsy.com * Probe Listener to handle probe events from the CPU 15913825Sivan.pizarro@metempsy.com */ 16013825Sivan.pizarro@metempsy.com class PrefetchListenerPC : public ProbeListenerArgBase<Addr> 16113825Sivan.pizarro@metempsy.com { 16213825Sivan.pizarro@metempsy.com public: 16313825Sivan.pizarro@metempsy.com PrefetchListenerPC(PIFPrefetcher &_parent, ProbeManager *pm, 16413825Sivan.pizarro@metempsy.com const std::string &name) 16513825Sivan.pizarro@metempsy.com : ProbeListenerArgBase(pm, name), 16613825Sivan.pizarro@metempsy.com parent(_parent) {} 16713825Sivan.pizarro@metempsy.com void notify(const Addr& pc) override; 16813825Sivan.pizarro@metempsy.com protected: 16913825Sivan.pizarro@metempsy.com PIFPrefetcher &parent; 17013825Sivan.pizarro@metempsy.com }; 17113825Sivan.pizarro@metempsy.com 17213825Sivan.pizarro@metempsy.com /** Array of probe listeners */ 17313825Sivan.pizarro@metempsy.com std::vector<PrefetchListenerPC *> listenersPC; 17413825Sivan.pizarro@metempsy.com 17513825Sivan.pizarro@metempsy.com 17613825Sivan.pizarro@metempsy.com public: 17713825Sivan.pizarro@metempsy.com PIFPrefetcher(const PIFPrefetcherParams *p); 17813825Sivan.pizarro@metempsy.com ~PIFPrefetcher() {} 17913825Sivan.pizarro@metempsy.com 18013825Sivan.pizarro@metempsy.com void calculatePrefetch(const PrefetchInfo &pfi, 18113825Sivan.pizarro@metempsy.com std::vector<AddrPriority> &addresses); 18213825Sivan.pizarro@metempsy.com 18313825Sivan.pizarro@metempsy.com /** 18413825Sivan.pizarro@metempsy.com * Add a SimObject and a probe name to monitor the retired instructions 18513825Sivan.pizarro@metempsy.com * @param obj The SimObject pointer to listen from 18613825Sivan.pizarro@metempsy.com * @param name The probe name 18713825Sivan.pizarro@metempsy.com */ 18813825Sivan.pizarro@metempsy.com void addEventProbeRetiredInsts(SimObject *obj, const char *name); 18913825Sivan.pizarro@metempsy.com}; 19013825Sivan.pizarro@metempsy.com 19113825Sivan.pizarro@metempsy.com#endif // __MEM_CACHE_PREFETCH_PIF_HH__ 192