113786Sjavier.bueno@metempsy.com/** 213786Sjavier.bueno@metempsy.com * Copyright (c) 2019 Metempsy Technology Consulting 313786Sjavier.bueno@metempsy.com * All rights reserved. 413786Sjavier.bueno@metempsy.com * 513786Sjavier.bueno@metempsy.com * Redistribution and use in source and binary forms, with or without 613786Sjavier.bueno@metempsy.com * modification, are permitted provided that the following conditions are 713786Sjavier.bueno@metempsy.com * met: redistributions of source code must retain the above copyright 813786Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer; 913786Sjavier.bueno@metempsy.com * redistributions in binary form must reproduce the above copyright 1013786Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer in the 1113786Sjavier.bueno@metempsy.com * documentation and/or other materials provided with the distribution; 1213786Sjavier.bueno@metempsy.com * neither the name of the copyright holders nor the names of its 1313786Sjavier.bueno@metempsy.com * contributors may be used to endorse or promote products derived from 1413786Sjavier.bueno@metempsy.com * this software without specific prior written permission. 1513786Sjavier.bueno@metempsy.com * 1613786Sjavier.bueno@metempsy.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1713786Sjavier.bueno@metempsy.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1813786Sjavier.bueno@metempsy.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1913786Sjavier.bueno@metempsy.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2013786Sjavier.bueno@metempsy.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2113786Sjavier.bueno@metempsy.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2213786Sjavier.bueno@metempsy.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2313786Sjavier.bueno@metempsy.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2413786Sjavier.bueno@metempsy.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2513786Sjavier.bueno@metempsy.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2613786Sjavier.bueno@metempsy.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2713786Sjavier.bueno@metempsy.com * 2813786Sjavier.bueno@metempsy.com * Authors: Javier Bueno 2913786Sjavier.bueno@metempsy.com */ 3013786Sjavier.bueno@metempsy.com 3113786Sjavier.bueno@metempsy.com /** 3213786Sjavier.bueno@metempsy.com * Implementation of the Spatio-Temporal Memory Streaming Prefetcher (STeMS) 3313786Sjavier.bueno@metempsy.com * Reference: 3413786Sjavier.bueno@metempsy.com * Spatio-temporal memory streaming. 3513786Sjavier.bueno@metempsy.com * Somogyi, S., Wenisch, T. F., Ailamaki, A., & Falsafi, B. (2009). 3613786Sjavier.bueno@metempsy.com * ACM SIGARCH Computer Architecture News, 37(3), 69-80. 3713786Sjavier.bueno@metempsy.com * 3813786Sjavier.bueno@metempsy.com * Notes: 3913786Sjavier.bueno@metempsy.com * - The functionality described in the paper as Streamed Value Buffer (SVB) 4013786Sjavier.bueno@metempsy.com * is not implemented here, as this is handled by the QueuedPrefetcher class 4113786Sjavier.bueno@metempsy.com */ 4213786Sjavier.bueno@metempsy.com 4313786Sjavier.bueno@metempsy.com#ifndef __MEM_CACHE_PREFETCH_SPATIO_TEMPORAL_MEMORY_STREAMING_HH__ 4413786Sjavier.bueno@metempsy.com#define __MEM_CACHE_PREFETCH_SPATIO_TEMPORAL_MEMORY_STREAMING_HH__ 4513786Sjavier.bueno@metempsy.com 4613786Sjavier.bueno@metempsy.com#include <vector> 4713786Sjavier.bueno@metempsy.com 4813963Sodanrc@yahoo.com.br#include "base/sat_counter.hh" 4913786Sjavier.bueno@metempsy.com#include "mem/cache/prefetch/associative_set.hh" 5013786Sjavier.bueno@metempsy.com#include "mem/cache/prefetch/queued.hh" 5113786Sjavier.bueno@metempsy.com 5213786Sjavier.bueno@metempsy.comstruct STeMSPrefetcherParams; 5313786Sjavier.bueno@metempsy.com 5413786Sjavier.bueno@metempsy.comclass STeMSPrefetcher : public QueuedPrefetcher 5513786Sjavier.bueno@metempsy.com{ 5613786Sjavier.bueno@metempsy.com /** Size of each spatial region */ 5713786Sjavier.bueno@metempsy.com const size_t spatialRegionSize; 5813786Sjavier.bueno@metempsy.com /** log_2 of the spatial region size */ 5913786Sjavier.bueno@metempsy.com const size_t spatialRegionSizeBits; 6013786Sjavier.bueno@metempsy.com /** Number of reconstruction entries */ 6113786Sjavier.bueno@metempsy.com const unsigned int reconstructionEntries; 6213786Sjavier.bueno@metempsy.com 6313786Sjavier.bueno@metempsy.com /** 6413786Sjavier.bueno@metempsy.com * Entry data type for the Active Generation Table (AGT) and the Pattern 6513786Sjavier.bueno@metempsy.com * Sequence Table (PST) 6613786Sjavier.bueno@metempsy.com */ 6713786Sjavier.bueno@metempsy.com struct ActiveGenerationTableEntry : public TaggedEntry { 6813786Sjavier.bueno@metempsy.com /** Physical address of the spatial region */ 6913786Sjavier.bueno@metempsy.com Addr paddress; 7013786Sjavier.bueno@metempsy.com /** PC that started this generation */ 7113786Sjavier.bueno@metempsy.com Addr pc; 7213786Sjavier.bueno@metempsy.com /** Counter to keep track of the interleaving between sequences */ 7313786Sjavier.bueno@metempsy.com unsigned int seqCounter; 7413786Sjavier.bueno@metempsy.com 7513786Sjavier.bueno@metempsy.com /** Sequence entry data type */ 7613786Sjavier.bueno@metempsy.com struct SequenceEntry { 7713786Sjavier.bueno@metempsy.com /** 2-bit confidence counter */ 7813963Sodanrc@yahoo.com.br SatCounter counter; 7913786Sjavier.bueno@metempsy.com /** Offset, in cache lines, within the spatial region */ 8013786Sjavier.bueno@metempsy.com unsigned int offset; 8113786Sjavier.bueno@metempsy.com /** Intearleaving position on the global access sequence */ 8213786Sjavier.bueno@metempsy.com unsigned int delta; 8313963Sodanrc@yahoo.com.br SequenceEntry() : counter(2), offset(0), delta(0) 8413786Sjavier.bueno@metempsy.com {} 8513786Sjavier.bueno@metempsy.com }; 8613786Sjavier.bueno@metempsy.com /** Sequence of accesses */ 8713786Sjavier.bueno@metempsy.com std::vector<SequenceEntry> sequence; 8813786Sjavier.bueno@metempsy.com 8913786Sjavier.bueno@metempsy.com ActiveGenerationTableEntry(int num_positions) : paddress(0), pc(0), 9013786Sjavier.bueno@metempsy.com seqCounter(0), sequence(num_positions) 9113786Sjavier.bueno@metempsy.com {} 9213786Sjavier.bueno@metempsy.com 9313786Sjavier.bueno@metempsy.com void reset() override 9413786Sjavier.bueno@metempsy.com { 9513786Sjavier.bueno@metempsy.com paddress = 0; 9613786Sjavier.bueno@metempsy.com pc = 0; 9713786Sjavier.bueno@metempsy.com seqCounter = 0; 9813786Sjavier.bueno@metempsy.com for (auto &seq_entry : sequence) { 9913963Sodanrc@yahoo.com.br seq_entry.counter.reset(); 10013786Sjavier.bueno@metempsy.com seq_entry.offset = 0; 10113786Sjavier.bueno@metempsy.com seq_entry.delta = 0; 10213786Sjavier.bueno@metempsy.com } 10313786Sjavier.bueno@metempsy.com } 10413786Sjavier.bueno@metempsy.com 10513786Sjavier.bueno@metempsy.com /** 10613786Sjavier.bueno@metempsy.com * Update the entry data with an entry from a generation that just 10713786Sjavier.bueno@metempsy.com * ended. This operation can not be done with the copy constructor, 10813786Sjavier.bueno@metempsy.com * becasuse the TaggedEntry component must not be copied. 10913786Sjavier.bueno@metempsy.com * @param e entry which generation has ended 11013786Sjavier.bueno@metempsy.com */ 11113786Sjavier.bueno@metempsy.com void update(ActiveGenerationTableEntry const &e) 11213786Sjavier.bueno@metempsy.com { 11313786Sjavier.bueno@metempsy.com paddress = e.paddress; 11413786Sjavier.bueno@metempsy.com pc = e.pc; 11513786Sjavier.bueno@metempsy.com seqCounter = e.seqCounter; 11613786Sjavier.bueno@metempsy.com sequence = e.sequence; 11713786Sjavier.bueno@metempsy.com } 11813786Sjavier.bueno@metempsy.com 11913786Sjavier.bueno@metempsy.com /** 12013786Sjavier.bueno@metempsy.com * Add a new access to the sequence 12113786Sjavier.bueno@metempsy.com * @param offset offset in cachelines within the spatial region 12213786Sjavier.bueno@metempsy.com */ 12313786Sjavier.bueno@metempsy.com void addOffset(unsigned int offset) { 12413786Sjavier.bueno@metempsy.com // Search for the offset in the deltas array, if it exist, update 12513786Sjavier.bueno@metempsy.com // the corresponding counter, if not, add the offset to the array 12613786Sjavier.bueno@metempsy.com for (auto &seq_entry : sequence) { 12713786Sjavier.bueno@metempsy.com if (seq_entry.counter > 0) { 12813786Sjavier.bueno@metempsy.com if (seq_entry.offset == offset) { 12913963Sodanrc@yahoo.com.br seq_entry.counter++; 13013786Sjavier.bueno@metempsy.com } 13113786Sjavier.bueno@metempsy.com } else { 13213786Sjavier.bueno@metempsy.com // If the counter is 0 it means that this position is not 13313786Sjavier.bueno@metempsy.com // being used, and we can allocate the new offset here 13413963Sodanrc@yahoo.com.br seq_entry.counter++; 13513786Sjavier.bueno@metempsy.com seq_entry.offset = offset; 13613786Sjavier.bueno@metempsy.com seq_entry.delta = seqCounter; 13713786Sjavier.bueno@metempsy.com break; 13813786Sjavier.bueno@metempsy.com } 13913786Sjavier.bueno@metempsy.com } 14013786Sjavier.bueno@metempsy.com seqCounter = 0; 14113786Sjavier.bueno@metempsy.com } 14213786Sjavier.bueno@metempsy.com }; 14313786Sjavier.bueno@metempsy.com 14413786Sjavier.bueno@metempsy.com /** Active Generation Table (AGT) */ 14513786Sjavier.bueno@metempsy.com AssociativeSet<ActiveGenerationTableEntry> activeGenerationTable; 14613786Sjavier.bueno@metempsy.com /** Pattern Sequence Table (PST) */ 14713786Sjavier.bueno@metempsy.com AssociativeSet<ActiveGenerationTableEntry> patternSequenceTable; 14813786Sjavier.bueno@metempsy.com 14913786Sjavier.bueno@metempsy.com /** Data type of the Region Miss Order Buffer entry */ 15013786Sjavier.bueno@metempsy.com struct RegionMissOrderBufferEntry { 15113786Sjavier.bueno@metempsy.com /** Address of the spatial region */ 15213786Sjavier.bueno@metempsy.com Addr srAddress; 15313786Sjavier.bueno@metempsy.com /** 15413786Sjavier.bueno@metempsy.com * Address used to index the PST table, generated using the PC and the 15513786Sjavier.bueno@metempsy.com * offset within the spatial region 15613786Sjavier.bueno@metempsy.com */ 15713786Sjavier.bueno@metempsy.com Addr pstAddress; 15813786Sjavier.bueno@metempsy.com /** Delta within the global miss order sequence */ 15913786Sjavier.bueno@metempsy.com unsigned int delta; 16013786Sjavier.bueno@metempsy.com /** Valid bit */ 16113786Sjavier.bueno@metempsy.com bool valid; 16213786Sjavier.bueno@metempsy.com }; 16313786Sjavier.bueno@metempsy.com 16413786Sjavier.bueno@metempsy.com /** Region Miss Order Buffer (RMOB) */ 16513786Sjavier.bueno@metempsy.com std::vector<RegionMissOrderBufferEntry> rmob; 16613786Sjavier.bueno@metempsy.com /** First free position (or older, if it is full) of the RMOB */ 16713786Sjavier.bueno@metempsy.com unsigned int rmobHead; 16813786Sjavier.bueno@metempsy.com 16913786Sjavier.bueno@metempsy.com /** Counter to keep the count of accesses between trigger accesses */ 17013786Sjavier.bueno@metempsy.com unsigned int lastTriggerCounter; 17113786Sjavier.bueno@metempsy.com 17213786Sjavier.bueno@metempsy.com /** Checks if the active generations have ended */ 17313786Sjavier.bueno@metempsy.com void checkForActiveGenerationsEnd(); 17413786Sjavier.bueno@metempsy.com /** 17513786Sjavier.bueno@metempsy.com * Adds an entry to the RMOB 17613786Sjavier.bueno@metempsy.com * @param sr_addr Spatial region address 17713786Sjavier.bueno@metempsy.com * @param pst_addr Corresponding PST address 17813786Sjavier.bueno@metempsy.com * @param delta Number of entries skipped in the global miss order 17913786Sjavier.bueno@metempsy.com */ 18013786Sjavier.bueno@metempsy.com void addToRMOB(Addr sr_addr, Addr pst_addr, unsigned int delta); 18113786Sjavier.bueno@metempsy.com 18213786Sjavier.bueno@metempsy.com /** 18313786Sjavier.bueno@metempsy.com * Reconstructs a sequence of accesses and generates the prefetch 18413786Sjavier.bueno@metempsy.com * addresses, adding them to the addresses vector 18513786Sjavier.bueno@metempsy.com * @param rmob_idx rmob position to start generating from 18613786Sjavier.bueno@metempsy.com * @param addresses vector to add the addresses to be prefetched 18713786Sjavier.bueno@metempsy.com */ 18813786Sjavier.bueno@metempsy.com void reconstructSequence(unsigned int rmob_idx, 18913786Sjavier.bueno@metempsy.com std::vector<AddrPriority> &addresses); 19013786Sjavier.bueno@metempsy.com public: 19113786Sjavier.bueno@metempsy.com STeMSPrefetcher(const STeMSPrefetcherParams* p); 19213786Sjavier.bueno@metempsy.com ~STeMSPrefetcher() {} 19313786Sjavier.bueno@metempsy.com void calculatePrefetch(const PrefetchInfo &pfi, 19413786Sjavier.bueno@metempsy.com std::vector<AddrPriority> &addresses) override; 19513786Sjavier.bueno@metempsy.com}; 19613786Sjavier.bueno@metempsy.com 19713786Sjavier.bueno@metempsy.com#endif//__MEM_CACHE_PREFETCH_SPATIO_TEMPORAL_MEMORY_STREAMING_HH__ 198