indirect_memory.hh revision 13772:31b71dadc472
110779SCurtis.Dunham@arm.com/** 210779SCurtis.Dunham@arm.com * Copyright (c) 2018 Metempsy Technology Consulting 310779SCurtis.Dunham@arm.com * All rights reserved. 410779SCurtis.Dunham@arm.com * 510779SCurtis.Dunham@arm.com * Redistribution and use in source and binary forms, with or without 610779SCurtis.Dunham@arm.com * modification, are permitted provided that the following conditions are 710779SCurtis.Dunham@arm.com * met: redistributions of source code must retain the above copyright 810779SCurtis.Dunham@arm.com * notice, this list of conditions and the following disclaimer; 910779SCurtis.Dunham@arm.com * redistributions in binary form must reproduce the above copyright 1010779SCurtis.Dunham@arm.com * notice, this list of conditions and the following disclaimer in the 1110779SCurtis.Dunham@arm.com * documentation and/or other materials provided with the distribution; 1210779SCurtis.Dunham@arm.com * neither the name of the copyright holders nor the names of its 1310779SCurtis.Dunham@arm.com * contributors may be used to endorse or promote products derived from 1410779SCurtis.Dunham@arm.com * this software without specific prior written permission. 1510779SCurtis.Dunham@arm.com * 1610779SCurtis.Dunham@arm.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1710779SCurtis.Dunham@arm.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1810779SCurtis.Dunham@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1910779SCurtis.Dunham@arm.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2010779SCurtis.Dunham@arm.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2110779SCurtis.Dunham@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2210779SCurtis.Dunham@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2310779SCurtis.Dunham@arm.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2410779SCurtis.Dunham@arm.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2510779SCurtis.Dunham@arm.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2610779SCurtis.Dunham@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2710779SCurtis.Dunham@arm.com * 2810779SCurtis.Dunham@arm.com * Authors: Javier Bueno 2910779SCurtis.Dunham@arm.com */ 3010779SCurtis.Dunham@arm.com 3110779SCurtis.Dunham@arm.com/** 3210779SCurtis.Dunham@arm.com * Implementation of the Indirect Memory Prefetcher 3310779SCurtis.Dunham@arm.com * 3410779SCurtis.Dunham@arm.com * References: 3510779SCurtis.Dunham@arm.com * IMP: Indirect memory prefetcher. 3610779SCurtis.Dunham@arm.com * Yu, X., Hughes, C. J., Satish, N., & Devadas, S. (2015, December). 3710779SCurtis.Dunham@arm.com * In Proceedings of the 48th International Symposium on Microarchitecture 3810779SCurtis.Dunham@arm.com * (pp. 178-190). ACM. 3910779SCurtis.Dunham@arm.com */ 4010779SCurtis.Dunham@arm.com 4110779SCurtis.Dunham@arm.com#ifndef __MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__ 4210779SCurtis.Dunham@arm.com#define __MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__ 4310779SCurtis.Dunham@arm.com 4410779SCurtis.Dunham@arm.com#include <vector> 4510779SCurtis.Dunham@arm.com 4610779SCurtis.Dunham@arm.com#include "mem/cache/prefetch/associative_set.hh" 4710779SCurtis.Dunham@arm.com#include "mem/cache/prefetch/queued.hh" 4810779SCurtis.Dunham@arm.com 4910779SCurtis.Dunham@arm.comstruct IndirectMemoryPrefetcherParams; 5010779SCurtis.Dunham@arm.com 5110779SCurtis.Dunham@arm.comclass IndirectMemoryPrefetcher : public QueuedPrefetcher 5210779SCurtis.Dunham@arm.com{ 5310779SCurtis.Dunham@arm.com /** Maximum number of prefetches generated per event */ 5410779SCurtis.Dunham@arm.com const unsigned int maxPrefetchDistance; 5510779SCurtis.Dunham@arm.com /** Shift values considered */ 5610779SCurtis.Dunham@arm.com const std::vector<int> shiftValues; 5710779SCurtis.Dunham@arm.com /** Counter threshold to start prefetching */ 5810779SCurtis.Dunham@arm.com const unsigned int prefetchThreshold; 5910779SCurtis.Dunham@arm.com /** Maximum value of the confidence indirectCounter */ 6010779SCurtis.Dunham@arm.com const unsigned int maxIndirectCounterValue; 6110779SCurtis.Dunham@arm.com /** streamCounter value to trigger the streaming prefetcher */ 6210779SCurtis.Dunham@arm.com const int streamCounterThreshold; 6310779SCurtis.Dunham@arm.com /** Number of prefetches generated when using the streaming prefetcher */ 6410779SCurtis.Dunham@arm.com const int streamingDistance; 6510779SCurtis.Dunham@arm.com 6610779SCurtis.Dunham@arm.com /** Prefetch Table Entry */ 6710779SCurtis.Dunham@arm.com struct PrefetchTableEntry : public TaggedEntry 6810779SCurtis.Dunham@arm.com { 6910779SCurtis.Dunham@arm.com /* Stream table fields */ 7010779SCurtis.Dunham@arm.com 7110779SCurtis.Dunham@arm.com /** Accessed address */ 7210779SCurtis.Dunham@arm.com Addr address; 7310779SCurtis.Dunham@arm.com /** Whether this address is in the secure region */ 7410779SCurtis.Dunham@arm.com bool secure; 7510779SCurtis.Dunham@arm.com /** Confidence counter of the stream */ 7610779SCurtis.Dunham@arm.com unsigned int streamCounter; 7710779SCurtis.Dunham@arm.com 7810779SCurtis.Dunham@arm.com /* Indirect table fields */ 7910779SCurtis.Dunham@arm.com 8010779SCurtis.Dunham@arm.com /** Enable bit of the indirect fields */ 8110779SCurtis.Dunham@arm.com bool enabled; 8210779SCurtis.Dunham@arm.com /** Current index value */ 8310779SCurtis.Dunham@arm.com int64_t index; 8410779SCurtis.Dunham@arm.com /** BaseAddr detected */ 8510779SCurtis.Dunham@arm.com Addr baseAddr; 8610779SCurtis.Dunham@arm.com /** Shift detected */ 8710779SCurtis.Dunham@arm.com int shift; 8810779SCurtis.Dunham@arm.com /** Confidence counter of the indirect fields */ 8910779SCurtis.Dunham@arm.com int indirectCounter; 9010779SCurtis.Dunham@arm.com /** 9110779SCurtis.Dunham@arm.com * This variable is set to indicate that there has been at least one 9210779SCurtis.Dunham@arm.com * match with the current index value. This information is later used 9310779SCurtis.Dunham@arm.com * when a new index is updated. If there were no increases in the 9410779SCurtis.Dunham@arm.com * indirectCounter, the counter is decremented. 9510779SCurtis.Dunham@arm.com */ 9610779SCurtis.Dunham@arm.com bool increasedIndirectCounter; 9710779SCurtis.Dunham@arm.com 9810779SCurtis.Dunham@arm.com PrefetchTableEntry() : TaggedEntry(), address(0), secure(false), 9910779SCurtis.Dunham@arm.com streamCounter(0), enabled(false), index(0), baseAddr(0), shift(0), 10010779SCurtis.Dunham@arm.com indirectCounter(0), increasedIndirectCounter(false) 10110779SCurtis.Dunham@arm.com {} 10210779SCurtis.Dunham@arm.com 10310779SCurtis.Dunham@arm.com void reset() override { 10410779SCurtis.Dunham@arm.com address = 0; 10510779SCurtis.Dunham@arm.com secure = false; 10610779SCurtis.Dunham@arm.com streamCounter = 0; 10710779SCurtis.Dunham@arm.com enabled = false; 10810779SCurtis.Dunham@arm.com index = 0; 10910779SCurtis.Dunham@arm.com baseAddr = 0; 11010779SCurtis.Dunham@arm.com shift = 0; 11110779SCurtis.Dunham@arm.com indirectCounter = 0; 11210779SCurtis.Dunham@arm.com increasedIndirectCounter = false; 11310779SCurtis.Dunham@arm.com } 11410779SCurtis.Dunham@arm.com }; 11510779SCurtis.Dunham@arm.com /** Prefetch table */ 11610779SCurtis.Dunham@arm.com AssociativeSet<PrefetchTableEntry> prefetchTable; 11710779SCurtis.Dunham@arm.com 11810779SCurtis.Dunham@arm.com /** Indirect Pattern Detector entrt */ 11910779SCurtis.Dunham@arm.com struct IndirectPatternDetectorEntry : public TaggedEntry 12010779SCurtis.Dunham@arm.com { 12110779SCurtis.Dunham@arm.com /** First index */ 12210779SCurtis.Dunham@arm.com int64_t idx1; 12310779SCurtis.Dunham@arm.com /** Second index */ 12410779SCurtis.Dunham@arm.com int64_t idx2; 12510779SCurtis.Dunham@arm.com /** Valid bit for the second index */ 12610779SCurtis.Dunham@arm.com bool secondIndexSet; 12710779SCurtis.Dunham@arm.com /** Number of misses currently recorded */ 12810779SCurtis.Dunham@arm.com int numMisses; 12911158SCurtis.Dunham@arm.com /** 13010779SCurtis.Dunham@arm.com * Potential BaseAddr candidates for each recorded miss. 13110779SCurtis.Dunham@arm.com * The number of candidates per miss is determined by the number of 13210779SCurtis.Dunham@arm.com * elements in the shiftValues array. 13310779SCurtis.Dunham@arm.com */ 13410779SCurtis.Dunham@arm.com std::vector<std::vector<Addr>> baseAddr; 13510779SCurtis.Dunham@arm.com 13610779SCurtis.Dunham@arm.com IndirectPatternDetectorEntry(unsigned int num_addresses, 13710779SCurtis.Dunham@arm.com unsigned int num_shifts) 13810779SCurtis.Dunham@arm.com : idx1(0), idx2(0), secondIndexSet(false), numMisses(0), 13910779SCurtis.Dunham@arm.com baseAddr(num_addresses, std::vector<Addr>(num_shifts)) 14010779SCurtis.Dunham@arm.com {} 14110779SCurtis.Dunham@arm.com 14210779SCurtis.Dunham@arm.com void reset() override { 14310779SCurtis.Dunham@arm.com idx1 = 0; 14410779SCurtis.Dunham@arm.com idx2 = 0; 14510779SCurtis.Dunham@arm.com secondIndexSet = false; 14610779SCurtis.Dunham@arm.com numMisses = 0; 14710779SCurtis.Dunham@arm.com setInvalid(); 14810779SCurtis.Dunham@arm.com } 14910779SCurtis.Dunham@arm.com }; 15010779SCurtis.Dunham@arm.com /** Indirect Pattern Detector (IPD) table */ 15110779SCurtis.Dunham@arm.com AssociativeSet<IndirectPatternDetectorEntry> ipd; 15210779SCurtis.Dunham@arm.com 15310779SCurtis.Dunham@arm.com /** Entry currently tracking misses */ 15410779SCurtis.Dunham@arm.com IndirectPatternDetectorEntry *ipdEntryTrackingMisses; 15510779SCurtis.Dunham@arm.com 15610779SCurtis.Dunham@arm.com /** Byte order used to access the cache */ 15710779SCurtis.Dunham@arm.com const ByteOrder byteOrder; 15810779SCurtis.Dunham@arm.com 15910779SCurtis.Dunham@arm.com /** 16010779SCurtis.Dunham@arm.com * Allocate or update an entry in the IPD 16110779SCurtis.Dunham@arm.com * @param pt_entry Pointer to the associated page table entry 16210779SCurtis.Dunham@arm.com * @param index Detected first index value 16310779SCurtis.Dunham@arm.com */ 16410779SCurtis.Dunham@arm.com void allocateOrUpdateIPDEntry(const PrefetchTableEntry *pt_entry, 16510779SCurtis.Dunham@arm.com int64_t index); 16610779SCurtis.Dunham@arm.com /** 16710779SCurtis.Dunham@arm.com * Update an IPD entry with a detected miss address, when the first index 16810779SCurtis.Dunham@arm.com * is being tracked 16910779SCurtis.Dunham@arm.com * @param miss_addr The address that caused the miss 17010779SCurtis.Dunham@arm.com */ 17110779SCurtis.Dunham@arm.com void trackMissIndex1(Addr miss_addr); 17210779SCurtis.Dunham@arm.com 17310779SCurtis.Dunham@arm.com /** 17410779SCurtis.Dunham@arm.com * Update an IPD entry with a detected miss address, when the second index 17510779SCurtis.Dunham@arm.com * is being tracked 17610779SCurtis.Dunham@arm.com * @param miss_addr The address that caused the miss 17710779SCurtis.Dunham@arm.com */ 17810779SCurtis.Dunham@arm.com void trackMissIndex2(Addr miss_addr); 17910779SCurtis.Dunham@arm.com 18010779SCurtis.Dunham@arm.com /** 18110779SCurtis.Dunham@arm.com * Checks if an access to the cache matches any active PT entry, if so, 18210779SCurtis.Dunham@arm.com * the indirect confidence counter is incremented 18310779SCurtis.Dunham@arm.com * @param addr address of the access 18410779SCurtis.Dunham@arm.com */ 18510779SCurtis.Dunham@arm.com void checkAccessMatchOnActiveEntries(Addr addr); 18610779SCurtis.Dunham@arm.com 18711158SCurtis.Dunham@arm.com public: 18810779SCurtis.Dunham@arm.com IndirectMemoryPrefetcher(const IndirectMemoryPrefetcherParams *p); 18910779SCurtis.Dunham@arm.com ~IndirectMemoryPrefetcher() {} 19010779SCurtis.Dunham@arm.com 19110779SCurtis.Dunham@arm.com void calculatePrefetch(const PrefetchInfo &pfi, 19210779SCurtis.Dunham@arm.com std::vector<AddrPriority> &addresses) override; 19310779SCurtis.Dunham@arm.com}; 19410779SCurtis.Dunham@arm.com#endif//__MEM_CACHE_PREFETCH_INDIRECT_MEMORY_HH__ 19510779SCurtis.Dunham@arm.com