access_map_pattern_matching.cc revision 13554:f16adb9b35cc 
1/**
2 * Copyright (c) 2018 Metempsy Technology Consulting
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 *
28 * Authors: Javier Bueno
29 */
30
31#include "mem/cache/prefetch/access_map_pattern_matching.hh"
32
33#include "debug/HWPrefetch.hh"
34#include "mem/cache/prefetch/associative_set_impl.hh"
35#include "params/AccessMapPatternMatchingPrefetcher.hh"
36
37AccessMapPatternMatchingPrefetcher::AccessMapPatternMatchingPrefetcher(
38    const AccessMapPatternMatchingPrefetcherParams *p)
39    : QueuedPrefetcher(p),
40      startDegree(p->start_degree), hotZoneSize(p->hot_zone_size),
41      highCoverageThreshold(p->high_coverage_threshold),
42      lowCoverageThreshold(p->low_coverage_threshold),
43      highAccuracyThreshold(p->high_accuracy_threshold),
44      lowAccuracyThreshold(p->low_accuracy_threshold),
45      highCacheHitThreshold(p->high_cache_hit_threshold),
46      lowCacheHitThreshold(p->low_cache_hit_threshold),
47      epochCycles(p->epoch_cycles),
48      offChipMemoryLatency(p->offchip_memory_latency),
49      accessMapTable(p->access_map_table_assoc, p->access_map_table_entries,
50                     p->access_map_table_indexing_policy,
51                     p->access_map_table_replacement_policy,
52                     AccessMapEntry(hotZoneSize / blkSize)),
53      numGoodPrefetches(0), numTotalPrefetches(0), numRawCacheMisses(0),
54      numRawCacheHits(0), degree(startDegree), usefulDegree(startDegree),
55      epochEvent([this]{ processEpochEvent(); }, name())
56{
57    fatal_if(!isPowerOf2(hotZoneSize),
58        "the hot zone size must be a power of 2");
59    if (!epochEvent.scheduled()) {
60        schedule(epochEvent, clockEdge(epochCycles));
61    }
62}
63
64void
65AccessMapPatternMatchingPrefetcher::processEpochEvent()
66{
67    schedule(epochEvent, clockEdge(epochCycles));
68    double prefetch_accuracy =
69        ((double) numGoodPrefetches) / ((double) numTotalPrefetches);
70    double prefetch_coverage =
71        ((double) numGoodPrefetches) / ((double) numRawCacheMisses);
72    double cache_hit_ratio = ((double) numRawCacheHits) /
73        ((double) (numRawCacheHits + numRawCacheMisses));
74    double num_requests = (double) (numRawCacheMisses - numGoodPrefetches +
75        numTotalPrefetches);
76    double memory_bandwidth = num_requests * offChipMemoryLatency /
77        clockEdge(epochCycles);
78
79    if (prefetch_coverage > highCoverageThreshold &&
80        (prefetch_accuracy > highAccuracyThreshold ||
81        cache_hit_ratio < lowCacheHitThreshold)) {
82        usefulDegree += 1;
83    } else if ((prefetch_coverage < lowCoverageThreshold &&
84               (prefetch_accuracy < lowAccuracyThreshold ||
85                cache_hit_ratio > highCacheHitThreshold)) ||
86               (prefetch_accuracy < lowAccuracyThreshold &&
87                cache_hit_ratio > highCacheHitThreshold)) {
88        usefulDegree -= 1;
89    }
90    degree = std::min((unsigned) memory_bandwidth, usefulDegree);
91    // reset epoch stats
92    numGoodPrefetches = 0.0;
93    numTotalPrefetches = 0.0;
94    numRawCacheMisses = 0.0;
95    numRawCacheHits = 0.0;
96}
97
98AccessMapPatternMatchingPrefetcher::AccessMapEntry *
99AccessMapPatternMatchingPrefetcher::getAccessMapEntry(Addr am_addr,
100                bool is_secure)
101{
102    AccessMapEntry *am_entry = accessMapTable.findEntry(am_addr, is_secure);
103    if (am_entry != nullptr) {
104        accessMapTable.accessEntry(am_entry);
105    } else {
106        am_entry = accessMapTable.findVictim(am_addr);
107        assert(am_entry != nullptr);
108
109        accessMapTable.insertEntry(am_addr, is_secure, am_entry);
110    }
111    return am_entry;
112}
113
114void
115AccessMapPatternMatchingPrefetcher::setEntryState(AccessMapEntry &entry,
116    Addr block, enum AccessMapState state)
117{
118    enum AccessMapState old = entry.states[block];
119    entry.states[block] = state;
120
121    //do not update stats when initializing
122    if (state == AM_INIT) return;
123
124    switch (old) {
125        case AM_INIT:
126            if (state == AM_PREFETCH) {
127                numTotalPrefetches += 1;
128            } else if (state == AM_ACCESS) {
129                numRawCacheMisses += 1;
130            }
131            break;
132        case AM_PREFETCH:
133            if (state == AM_ACCESS) {
134                numGoodPrefetches += 1;
135                numRawCacheMisses += 1;
136            }
137            break;
138        case AM_ACCESS:
139            if (state == AM_ACCESS) {
140                numRawCacheHits += 1;
141            }
142            break;
143        default:
144            panic("Impossible path\n");
145            break;
146    }
147}
148
149void
150AccessMapPatternMatchingPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
151    std::vector<AddrPriority> &addresses)
152{
153    assert(addresses.empty());
154    bool is_secure = pfi.isSecure();
155    Addr am_addr = pfi.getAddr() / hotZoneSize;
156    Addr current_block = (pfi.getAddr() % hotZoneSize) / blkSize;
157    uint64_t lines_per_zone = hotZoneSize / blkSize;
158
159    // Get the entries of the curent block (am_addr), the previous, and the
160    // following ones
161    AccessMapEntry *am_entry_curr = getAccessMapEntry(am_addr, is_secure);
162    AccessMapEntry *am_entry_prev = (am_addr > 0) ?
163        getAccessMapEntry(am_addr-1, is_secure) : nullptr;
164    AccessMapEntry *am_entry_next = (am_addr < (MaxAddr/hotZoneSize)) ?
165        getAccessMapEntry(am_addr+1, is_secure) : nullptr;
166    assert(am_entry_curr != am_entry_prev);
167    assert(am_entry_curr != am_entry_next);
168    assert(am_entry_prev != am_entry_next);
169    assert(am_entry_curr != nullptr);
170
171    //Mark the current access as Accessed
172    setEntryState(*am_entry_curr, current_block, AM_ACCESS);
173
174    /**
175     * Create a contiguous copy of the 3 entries states.
176     * With this, we avoid doing boundaries checking in the loop that looks
177     * for prefetch candidates, mark out of range positions with AM_INVALID
178     */
179    std::vector<AccessMapState> states(3 * lines_per_zone);
180    for (unsigned idx = 0; idx < lines_per_zone; idx += 1) {
181        states[idx] =
182            am_entry_prev != nullptr ? am_entry_prev->states[idx] : AM_INVALID;
183        states[idx + lines_per_zone] = am_entry_curr->states[idx];
184        states[idx + 2 * lines_per_zone] =
185            am_entry_next != nullptr ? am_entry_next->states[idx] : AM_INVALID;
186    }
187
188    /**
189     * am_entry_prev->states => states[               0 ..   lines_per_zone-1]
190     * am_entry_curr->states => states[  lines_per_zone .. 2*lines_per_zone-1]
191     * am_entry_next->states => states[2*lines_per_zone .. 3*lines_per_zone-1]
192     */
193
194    // index of the current_block in the new vector
195    Addr states_current_block = current_block + lines_per_zone;
196    // consider strides 1..lines_per_zone/2
197    for (int stride = 1; stride < lines_per_zone/2; stride += 1) {
198        // Test accessed positive strides
199        if (checkCandidate(states, states_current_block, stride)) {
200            // candidate found, current_block - stride
201            Addr pf_addr;
202            if (stride > current_block) {
203                // The index (current_block - stride) falls in the range of
204                // the previous zone (am_entry_prev), adjust the address
205                // accordingly
206                Addr blk = states_current_block - stride;
207                pf_addr = (am_addr - 1) * hotZoneSize + blk * blkSize;
208                setEntryState(*am_entry_prev, blk, AM_PREFETCH);
209            } else {
210                // The index (current_block - stride) falls within
211                // am_entry_curr
212                Addr blk = current_block - stride;
213                pf_addr = am_addr * hotZoneSize + blk * blkSize;
214                setEntryState(*am_entry_curr, blk, AM_PREFETCH);
215            }
216            addresses.push_back(AddrPriority(pf_addr, 0));
217            if (addresses.size() == degree) {
218                break;
219            }
220        }
221
222        // Test accessed negative strides
223        if (checkCandidate(states, states_current_block, -stride)) {
224            // candidate found, current_block + stride
225            Addr pf_addr;
226            if (current_block + stride >= lines_per_zone) {
227                // The index (current_block + stride) falls in the range of
228                // the next zone (am_entry_next), adjust the address
229                // accordingly
230                Addr blk = (states_current_block + stride) % lines_per_zone;
231                pf_addr = (am_addr + 1) * hotZoneSize + blk * blkSize;
232                setEntryState(*am_entry_next, blk, AM_PREFETCH);
233            } else {
234                // The index (current_block + stride) falls within
235                // am_entry_curr
236                Addr blk = current_block + stride;
237                pf_addr = am_addr * hotZoneSize + blk * blkSize;
238                setEntryState(*am_entry_curr, blk, AM_PREFETCH);
239            }
240            addresses.push_back(AddrPriority(pf_addr, 0));
241            if (addresses.size() == degree) {
242                break;
243            }
244        }
245    }
246}
247
248AccessMapPatternMatchingPrefetcher*
249AccessMapPatternMatchingPrefetcherParams::create()
250{
251    return new AccessMapPatternMatchingPrefetcher(this);
252}
253