sbooe.hh revision 13735
113735Sivan.pizarro@metempsy.com/** 213735Sivan.pizarro@metempsy.com * Copyright (c) 2018 Metempsy Technology Consulting 313735Sivan.pizarro@metempsy.com * All rights reserved. 413735Sivan.pizarro@metempsy.com * 513735Sivan.pizarro@metempsy.com * Redistribution and use in source and binary forms, with or without 613735Sivan.pizarro@metempsy.com * modification, are permitted provided that the following conditions are 713735Sivan.pizarro@metempsy.com * met: redistributions of source code must retain the above copyright 813735Sivan.pizarro@metempsy.com * notice, this list of conditions and the following disclaimer; 913735Sivan.pizarro@metempsy.com * redistributions in binary form must reproduce the above copyright 1013735Sivan.pizarro@metempsy.com * notice, this list of conditions and the following disclaimer in the 1113735Sivan.pizarro@metempsy.com * documentation and/or other materials provided with the distribution; 1213735Sivan.pizarro@metempsy.com * neither the name of the copyright holders nor the names of its 1313735Sivan.pizarro@metempsy.com * contributors may be used to endorse or promote products derived from 1413735Sivan.pizarro@metempsy.com * this software without specific prior written permission. 1513735Sivan.pizarro@metempsy.com * 1613735Sivan.pizarro@metempsy.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1713735Sivan.pizarro@metempsy.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1813735Sivan.pizarro@metempsy.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1913735Sivan.pizarro@metempsy.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2013735Sivan.pizarro@metempsy.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2113735Sivan.pizarro@metempsy.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2213735Sivan.pizarro@metempsy.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2313735Sivan.pizarro@metempsy.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2413735Sivan.pizarro@metempsy.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2513735Sivan.pizarro@metempsy.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2613735Sivan.pizarro@metempsy.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2713735Sivan.pizarro@metempsy.com * 2813735Sivan.pizarro@metempsy.com * Authors: Ivan Pizarro 2913735Sivan.pizarro@metempsy.com */ 3013735Sivan.pizarro@metempsy.com 3113735Sivan.pizarro@metempsy.com/** 3213735Sivan.pizarro@metempsy.com * Implementation of the 'Sandbox Based Optimal Offset Estimation' 3313735Sivan.pizarro@metempsy.com * Reference: 3413735Sivan.pizarro@metempsy.com * Brown, N. T., & Sendag, R. Sandbox Based Optimal Offset Estimation. 3513735Sivan.pizarro@metempsy.com*/ 3613735Sivan.pizarro@metempsy.com 3713735Sivan.pizarro@metempsy.com#ifndef __MEM_CACHE_PREFETCH_SBOOE_HH__ 3813735Sivan.pizarro@metempsy.com#define __MEM_CACHE_PREFETCH_SBOOE_HH__ 3913735Sivan.pizarro@metempsy.com 4013735Sivan.pizarro@metempsy.com#include <deque> 4113735Sivan.pizarro@metempsy.com#include <unordered_map> 4213735Sivan.pizarro@metempsy.com#include <vector> 4313735Sivan.pizarro@metempsy.com 4413735Sivan.pizarro@metempsy.com#include "mem/cache/prefetch/queued.hh" 4513735Sivan.pizarro@metempsy.com#include "mem/packet.hh" 4613735Sivan.pizarro@metempsy.com 4713735Sivan.pizarro@metempsy.comstruct SBOOEPrefetcherParams; 4813735Sivan.pizarro@metempsy.com 4913735Sivan.pizarro@metempsy.comclass SBOOEPrefetcher : public QueuedPrefetcher 5013735Sivan.pizarro@metempsy.com{ 5113735Sivan.pizarro@metempsy.com private: 5213735Sivan.pizarro@metempsy.com 5313735Sivan.pizarro@metempsy.com /** Prefetcher parameters */ 5413735Sivan.pizarro@metempsy.com const int latencyBufferSize; 5513735Sivan.pizarro@metempsy.com const int sequentialPrefetchers; 5613735Sivan.pizarro@metempsy.com 5713735Sivan.pizarro@metempsy.com /** Threshold used to issue prefetchers */ 5813735Sivan.pizarro@metempsy.com const unsigned int scoreThreshold; 5913735Sivan.pizarro@metempsy.com 6013735Sivan.pizarro@metempsy.com /** 6113735Sivan.pizarro@metempsy.com * Holds the current demand addresses and tick. This is later used to 6213735Sivan.pizarro@metempsy.com * calculate the average latency buffer when the address is filled in 6313735Sivan.pizarro@metempsy.com * the cache. 6413735Sivan.pizarro@metempsy.com */ 6513735Sivan.pizarro@metempsy.com std::unordered_map<Addr, Tick> demandAddresses; 6613735Sivan.pizarro@metempsy.com 6713735Sivan.pizarro@metempsy.com /** 6813735Sivan.pizarro@metempsy.com * The latency buffer holds the elapsed ticks between the demand and 6913735Sivan.pizarro@metempsy.com * the fill in the cache for the latest N accesses which are used to 7013735Sivan.pizarro@metempsy.com * calculate the average access latency which is later used to 7113735Sivan.pizarro@metempsy.com * predict if a prefetcher would be filled on time if issued. 7213735Sivan.pizarro@metempsy.com */ 7313735Sivan.pizarro@metempsy.com std::deque<Tick> latencyBuffer; 7413735Sivan.pizarro@metempsy.com 7513735Sivan.pizarro@metempsy.com /** Holds the current average access latency */ 7613735Sivan.pizarro@metempsy.com Tick averageAccessLatency; 7713735Sivan.pizarro@metempsy.com 7813735Sivan.pizarro@metempsy.com /** Holds the current sum of the latency buffer latency */ 7913735Sivan.pizarro@metempsy.com Tick latencyBufferSum; 8013735Sivan.pizarro@metempsy.com 8113735Sivan.pizarro@metempsy.com struct SandboxEntry { 8213735Sivan.pizarro@metempsy.com /** Cache line predicted by the candidate prefetcher */ 8313735Sivan.pizarro@metempsy.com Addr line; 8413735Sivan.pizarro@metempsy.com /** Tick when the simulated prefetch is expected to be filled */ 8513735Sivan.pizarro@metempsy.com Tick expectedArrivalTick; 8613735Sivan.pizarro@metempsy.com /** To indicate if it was initialized */ 8713735Sivan.pizarro@metempsy.com bool valid; 8813735Sivan.pizarro@metempsy.com 8913735Sivan.pizarro@metempsy.com SandboxEntry() 9013735Sivan.pizarro@metempsy.com : valid(false) 9113735Sivan.pizarro@metempsy.com {} 9213735Sivan.pizarro@metempsy.com }; 9313735Sivan.pizarro@metempsy.com 9413735Sivan.pizarro@metempsy.com struct Sandbox { 9513735Sivan.pizarro@metempsy.com /** FIFO queue. Max entries is 'sandboxEntries' */ 9613735Sivan.pizarro@metempsy.com std::vector<SandboxEntry> entries; 9713735Sivan.pizarro@metempsy.com /** 9813735Sivan.pizarro@metempsy.com * Accesses during the eval period that were present 9913735Sivan.pizarro@metempsy.com * in the sandbox 10013735Sivan.pizarro@metempsy.com */ 10113735Sivan.pizarro@metempsy.com unsigned int sandboxScore; 10213735Sivan.pizarro@metempsy.com /** Hits in the sandbox that wouldn't have been filled on time */ 10313735Sivan.pizarro@metempsy.com unsigned int lateScore; 10413735Sivan.pizarro@metempsy.com /** Index of the oldest entry in the FIFO */ 10513735Sivan.pizarro@metempsy.com unsigned int index; 10613735Sivan.pizarro@metempsy.com /** Sequential stride for this prefetcher */ 10713735Sivan.pizarro@metempsy.com const int stride; 10813735Sivan.pizarro@metempsy.com 10913735Sivan.pizarro@metempsy.com Sandbox(unsigned int max_entries, int _stride) 11013735Sivan.pizarro@metempsy.com : sandboxScore(0), lateScore(0), index(0), stride(_stride) 11113735Sivan.pizarro@metempsy.com { 11213735Sivan.pizarro@metempsy.com entries.resize(max_entries); 11313735Sivan.pizarro@metempsy.com } 11413735Sivan.pizarro@metempsy.com 11513735Sivan.pizarro@metempsy.com /** 11613735Sivan.pizarro@metempsy.com * Insert the line address being accessed to the cache into the 11713735Sivan.pizarro@metempsy.com * FIFO queue of the sandbox. 11813735Sivan.pizarro@metempsy.com * @param line Line address being accessed 11913735Sivan.pizarro@metempsy.com * @param tick Tick in which the access is expected to be filled 12013735Sivan.pizarro@metempsy.com */ 12113735Sivan.pizarro@metempsy.com void insert(Addr line, Tick tick); 12213735Sivan.pizarro@metempsy.com 12313735Sivan.pizarro@metempsy.com /** Calculate the useful score 12413735Sivan.pizarro@metempsy.com * @return Useful score of the sandbox. Sandbox score adjusted by 12513735Sivan.pizarro@metempsy.com * by the late score 12613735Sivan.pizarro@metempsy.com */ 12713735Sivan.pizarro@metempsy.com unsigned int score() const { 12813735Sivan.pizarro@metempsy.com return (sandboxScore - lateScore); 12913735Sivan.pizarro@metempsy.com } 13013735Sivan.pizarro@metempsy.com }; 13113735Sivan.pizarro@metempsy.com 13213735Sivan.pizarro@metempsy.com std::vector<Sandbox> sandboxes; 13313735Sivan.pizarro@metempsy.com 13413735Sivan.pizarro@metempsy.com /** Current best sandbox */ 13513735Sivan.pizarro@metempsy.com Sandbox * bestSandbox; 13613735Sivan.pizarro@metempsy.com 13713735Sivan.pizarro@metempsy.com /** Number of accesses notified to the prefetcher */ 13813735Sivan.pizarro@metempsy.com unsigned int accesses; 13913735Sivan.pizarro@metempsy.com 14013735Sivan.pizarro@metempsy.com /** 14113735Sivan.pizarro@metempsy.com * Process an access to the specified line address and update the 14213735Sivan.pizarro@metempsy.com * sandbox counters counters. 14313735Sivan.pizarro@metempsy.com * @param line Address of the line being accessed 14413735Sivan.pizarro@metempsy.com * @return TRUE if the evaluation finished, FALSE otherwise 14513735Sivan.pizarro@metempsy.com */ 14613735Sivan.pizarro@metempsy.com bool access(Addr line); 14713735Sivan.pizarro@metempsy.com 14813735Sivan.pizarro@metempsy.com /** Update the latency buffer after a prefetch fill */ 14913735Sivan.pizarro@metempsy.com void notifyFill(const PacketPtr& pkt) override; 15013735Sivan.pizarro@metempsy.com 15113735Sivan.pizarro@metempsy.com public: 15213735Sivan.pizarro@metempsy.com SBOOEPrefetcher(const SBOOEPrefetcherParams *p); 15313735Sivan.pizarro@metempsy.com 15413735Sivan.pizarro@metempsy.com void calculatePrefetch(const PrefetchInfo &pfi, 15513735Sivan.pizarro@metempsy.com std::vector<AddrPriority> &addresses) override; 15613735Sivan.pizarro@metempsy.com}; 15713735Sivan.pizarro@metempsy.com 15813735Sivan.pizarro@metempsy.com#endif // __MEM_CACHE_PREFETCH_SBOOE_HH__ 159