access_map_pattern_matching.cc revision 13700:56fa28e6fab4 
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/AMPMPrefetcher.hh"
36#include "params/AccessMapPatternMatching.hh"
37
38AccessMapPatternMatching::AccessMapPatternMatching(
39    const AccessMapPatternMatchingParams *p)
40    : ClockedObject(p), blkSize(p->block_size), limitStride(p->limit_stride),
41      startDegree(p->start_degree), hotZoneSize(p->hot_zone_size),
42      highCoverageThreshold(p->high_coverage_threshold),
43      lowCoverageThreshold(p->low_coverage_threshold),
44      highAccuracyThreshold(p->high_accuracy_threshold),
45      lowAccuracyThreshold(p->low_accuracy_threshold),
46      highCacheHitThreshold(p->high_cache_hit_threshold),
47      lowCacheHitThreshold(p->low_cache_hit_threshold),
48      epochCycles(p->epoch_cycles),
49      offChipMemoryLatency(p->offchip_memory_latency),
50      accessMapTable(p->access_map_table_assoc, p->access_map_table_entries,
51                     p->access_map_table_indexing_policy,
52                     p->access_map_table_replacement_policy,
53                     AccessMapEntry(hotZoneSize / blkSize)),
54      numGoodPrefetches(0), numTotalPrefetches(0), numRawCacheMisses(0),
55      numRawCacheHits(0), degree(startDegree), usefulDegree(startDegree),
56      epochEvent([this]{ processEpochEvent(); }, name())
57{
58    fatal_if(!isPowerOf2(hotZoneSize),
59        "the hot zone size must be a power of 2");
60    if (!epochEvent.scheduled()) {
61        schedule(epochEvent, clockEdge(epochCycles));
62    }
63}
64
65void
66AccessMapPatternMatching::processEpochEvent()
67{
68    schedule(epochEvent, clockEdge(epochCycles));
69    double prefetch_accuracy =
70        ((double) numGoodPrefetches) / ((double) numTotalPrefetches);
71    double prefetch_coverage =
72        ((double) numGoodPrefetches) / ((double) numRawCacheMisses);
73    double cache_hit_ratio = ((double) numRawCacheHits) /
74        ((double) (numRawCacheHits + numRawCacheMisses));
75    double num_requests = (double) (numRawCacheMisses - numGoodPrefetches +
76        numTotalPrefetches);
77    double memory_bandwidth = num_requests * offChipMemoryLatency /
78        clockEdge(epochCycles);
79
80    if (prefetch_coverage > highCoverageThreshold &&
81        (prefetch_accuracy > highAccuracyThreshold ||
82        cache_hit_ratio < lowCacheHitThreshold)) {
83        usefulDegree += 1;
84    } else if ((prefetch_coverage < lowCoverageThreshold &&
85               (prefetch_accuracy < lowAccuracyThreshold ||
86                cache_hit_ratio > highCacheHitThreshold)) ||
87               (prefetch_accuracy < lowAccuracyThreshold &&
88                cache_hit_ratio > highCacheHitThreshold)) {
89        usefulDegree -= 1;
90    }
91    degree = std::min((unsigned) memory_bandwidth, usefulDegree);
92    // reset epoch stats
93    numGoodPrefetches = 0.0;
94    numTotalPrefetches = 0.0;
95    numRawCacheMisses = 0.0;
96    numRawCacheHits = 0.0;
97}
98
99AccessMapPatternMatching::AccessMapEntry *
100AccessMapPatternMatching::getAccessMapEntry(Addr am_addr,
101                bool is_secure)
102{
103    AccessMapEntry *am_entry = accessMapTable.findEntry(am_addr, is_secure);
104    if (am_entry != nullptr) {
105        accessMapTable.accessEntry(am_entry);
106    } else {
107        am_entry = accessMapTable.findVictim(am_addr);
108        assert(am_entry != nullptr);
109
110        accessMapTable.insertEntry(am_addr, is_secure, am_entry);
111    }
112    return am_entry;
113}
114
115void
116AccessMapPatternMatching::setEntryState(AccessMapEntry &entry,
117    Addr block, enum AccessMapState state)
118{
119    enum AccessMapState old = entry.states[block];
120    entry.states[block] = state;
121
122    //do not update stats when initializing
123    if (state == AM_INIT) return;
124
125    switch (old) {
126        case AM_INIT:
127            if (state == AM_PREFETCH) {
128                numTotalPrefetches += 1;
129            } else if (state == AM_ACCESS) {
130                numRawCacheMisses += 1;
131            }
132            break;
133        case AM_PREFETCH:
134            if (state == AM_ACCESS) {
135                numGoodPrefetches += 1;
136                numRawCacheMisses += 1;
137            }
138            break;
139        case AM_ACCESS:
140            if (state == AM_ACCESS) {
141                numRawCacheHits += 1;
142            }
143            break;
144        default:
145            panic("Impossible path\n");
146            break;
147    }
148}
149
150void
151AccessMapPatternMatching::calculatePrefetch(
152    const BasePrefetcher::PrefetchInfo &pfi,
153    std::vector<QueuedPrefetcher::AddrPriority> &addresses)
154{
155    assert(addresses.empty());
156    bool is_secure = pfi.isSecure();
157    Addr am_addr = pfi.getAddr() / hotZoneSize;
158    Addr current_block = (pfi.getAddr() % hotZoneSize) / blkSize;
159    uint64_t lines_per_zone = hotZoneSize / blkSize;
160
161    // Get the entries of the curent block (am_addr), the previous, and the
162    // following ones
163    AccessMapEntry *am_entry_curr = getAccessMapEntry(am_addr, is_secure);
164    AccessMapEntry *am_entry_prev = (am_addr > 0) ?
165        getAccessMapEntry(am_addr-1, is_secure) : nullptr;
166    AccessMapEntry *am_entry_next = (am_addr < (MaxAddr/hotZoneSize)) ?
167        getAccessMapEntry(am_addr+1, is_secure) : nullptr;
168    assert(am_entry_curr != am_entry_prev);
169    assert(am_entry_curr != am_entry_next);
170    assert(am_entry_prev != am_entry_next);
171    assert(am_entry_curr != nullptr);
172
173    //Mark the current access as Accessed
174    setEntryState(*am_entry_curr, current_block, AM_ACCESS);
175
176    /**
177     * Create a contiguous copy of the 3 entries states.
178     * With this, we avoid doing boundaries checking in the loop that looks
179     * for prefetch candidates, mark out of range positions with AM_INVALID
180     */
181    std::vector<AccessMapState> states(3 * lines_per_zone);
182    for (unsigned idx = 0; idx < lines_per_zone; idx += 1) {
183        states[idx] =
184            am_entry_prev != nullptr ? am_entry_prev->states[idx] : AM_INVALID;
185        states[idx + lines_per_zone] = am_entry_curr->states[idx];
186        states[idx + 2 * lines_per_zone] =
187            am_entry_next != nullptr ? am_entry_next->states[idx] : AM_INVALID;
188    }
189
190    /**
191     * am_entry_prev->states => states[               0 ..   lines_per_zone-1]
192     * am_entry_curr->states => states[  lines_per_zone .. 2*lines_per_zone-1]
193     * am_entry_next->states => states[2*lines_per_zone .. 3*lines_per_zone-1]
194     */
195
196    // index of the current_block in the new vector
197    Addr states_current_block = current_block + lines_per_zone;
198    // consider strides 1..lines_per_zone/2
199    int max_stride = limitStride == 0 ? lines_per_zone / 2 : limitStride + 1;
200    for (int stride = 1; stride < max_stride; stride += 1) {
201        // Test accessed positive strides
202        if (checkCandidate(states, states_current_block, stride)) {
203            // candidate found, current_block - stride
204            Addr pf_addr;
205            if (stride > current_block) {
206                // The index (current_block - stride) falls in the range of
207                // the previous zone (am_entry_prev), adjust the address
208                // accordingly
209                Addr blk = states_current_block - stride;
210                pf_addr = (am_addr - 1) * hotZoneSize + blk * blkSize;
211                setEntryState(*am_entry_prev, blk, AM_PREFETCH);
212            } else {
213                // The index (current_block - stride) falls within
214                // am_entry_curr
215                Addr blk = current_block - stride;
216                pf_addr = am_addr * hotZoneSize + blk * blkSize;
217                setEntryState(*am_entry_curr, blk, AM_PREFETCH);
218            }
219            addresses.push_back(QueuedPrefetcher::AddrPriority(pf_addr, 0));
220            if (addresses.size() == degree) {
221                break;
222            }
223        }
224
225        // Test accessed negative strides
226        if (checkCandidate(states, states_current_block, -stride)) {
227            // candidate found, current_block + stride
228            Addr pf_addr;
229            if (current_block + stride >= lines_per_zone) {
230                // The index (current_block + stride) falls in the range of
231                // the next zone (am_entry_next), adjust the address
232                // accordingly
233                Addr blk = (states_current_block + stride) % lines_per_zone;
234                pf_addr = (am_addr + 1) * hotZoneSize + blk * blkSize;
235                setEntryState(*am_entry_next, blk, AM_PREFETCH);
236            } else {
237                // The index (current_block + stride) falls within
238                // am_entry_curr
239                Addr blk = current_block + stride;
240                pf_addr = am_addr * hotZoneSize + blk * blkSize;
241                setEntryState(*am_entry_curr, blk, AM_PREFETCH);
242            }
243            addresses.push_back(QueuedPrefetcher::AddrPriority(pf_addr, 0));
244            if (addresses.size() == degree) {
245                break;
246            }
247        }
248    }
249}
250
251AccessMapPatternMatching*
252AccessMapPatternMatchingParams::create()
253{
254    return new AccessMapPatternMatching(this);
255}
256
257AMPMPrefetcher::AMPMPrefetcher(const AMPMPrefetcherParams *p)
258  : QueuedPrefetcher(p), ampm(*p->ampm)
259{
260}
261
262void
263AMPMPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
264    std::vector<AddrPriority> &addresses)
265{
266    ampm.calculatePrefetch(pfi, addresses);
267}
268
269AMPMPrefetcher*
270AMPMPrefetcherParams::create()
271{
272    return new AMPMPrefetcher(this);
273}
274