From ccb512ecc1b4224ef68f5cb76f59c3fd36a59c63 Mon Sep 17 00:00:00 2001 From: Andreas Hansson Date: Tue, 3 Feb 2015 14:25:54 -0500 Subject: base: Add XOR-based hashed address interleaving This patch extends the current address interleaving with basic hashing support. Instead of directly comparing a number of address bits with a matching value, it is now possible to use two independent set of address bits XOR'ed together. This avoids issues where strided address patterns are heavily biased to a subset of the interleaved ranges. --- src/base/addr_range.hh | 116 +++++++++++++++++++++++++++++++++++++++--------- src/python/m5/params.py | 9 ++-- 2 files changed, 100 insertions(+), 25 deletions(-) diff --git a/src/base/addr_range.hh b/src/base/addr_range.hh index 4cb1ebd5a..57db8db71 100644 --- a/src/base/addr_range.hh +++ b/src/base/addr_range.hh @@ -1,5 +1,5 @@ /* - * Copyright (c) 2012 ARM Limited + * Copyright (c) 2012, 2014 ARM Limited * All rights reserved * * The license below extends only to copyright in the software and shall @@ -53,6 +53,22 @@ #include "base/misc.hh" #include "base/types.hh" +/** + * The AddrRange class encapsulates an address range, and supports a + * number of tests to check if two ranges intersect, if a range + * contains a specific address etc. Besides a basic range, the + * AddrRange also support interleaved ranges, to stripe across cache + * banks, or memory controllers. The interleaving is implemented by + * allowing a number of bits of the address, at an arbitrary bit + * position, to be used as interleaving bits with an associated + * matching value. In addition, to prevent uniformly strided address + * patterns from a very biased interleaving, we also allow basic + * XOR-based hashing by specifying an additional set of bits to XOR + * with before matching. + * + * The AddrRange is also able to coalesce a number of interleaved + * ranges to a contiguous range. + */ class AddrRange { @@ -66,6 +82,10 @@ class AddrRange /// The high bit of the slice that is used for interleaving uint8_t intlvHighBit; + /// The high bit of the slice used to XOR hash the value we match + /// against, set to 0 to disable. + uint8_t xorHighBit; + /// The number of bits used for interleaving, set to 0 to disable uint8_t intlvBits; @@ -76,18 +96,42 @@ class AddrRange public: AddrRange() - : _start(1), _end(0), intlvHighBit(0), intlvBits(0), intlvMatch(0) + : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(0), + intlvMatch(0) {} AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit, - uint8_t _intlv_bits, uint8_t _intlv_match) + uint8_t _xor_high_bit, uint8_t _intlv_bits, + uint8_t _intlv_match) : _start(_start), _end(_end), intlvHighBit(_intlv_high_bit), - intlvBits(_intlv_bits), intlvMatch(_intlv_match) - {} + xorHighBit(_xor_high_bit), intlvBits(_intlv_bits), + intlvMatch(_intlv_match) + { + // sanity checks + fatal_if(intlvBits && intlvMatch >= ULL(1) << intlvBits, + "Match value %d does not fit in %d interleaving bits\n", + intlvMatch, intlvBits); + + // ignore the XOR bits if not interleaving + if (intlvBits && xorHighBit) { + if (xorHighBit == intlvHighBit) { + fatal("XOR and interleave high bit must be different\n"); + } else if (xorHighBit > intlvHighBit) { + if ((xorHighBit - intlvHighBit) < intlvBits) + fatal("XOR and interleave high bit must be at least " + "%d bits apart\n", intlvBits); + } else { + if ((intlvHighBit - xorHighBit) < intlvBits) { + fatal("Interleave and XOR high bit must be at least " + "%d bits apart\n", intlvBits); + } + } + } + } AddrRange(Addr _start, Addr _end) - : _start(_start), _end(_end), intlvHighBit(0), intlvBits(0), - intlvMatch(0) + : _start(_start), _end(_end), intlvHighBit(0), xorHighBit(0), + intlvBits(0), intlvMatch(0) {} /** @@ -97,13 +141,15 @@ class AddrRange * @param ranges Interleaved ranges to be merged */ AddrRange(const std::vector& ranges) - : _start(1), _end(0), intlvHighBit(0), intlvBits(0), intlvMatch(0) + : _start(1), _end(0), intlvHighBit(0), xorHighBit(0), intlvBits(0), + intlvMatch(0) { if (!ranges.empty()) { // get the values from the first one and check the others _start = ranges.front()._start; _end = ranges.front()._end; intlvHighBit = ranges.front().intlvHighBit; + xorHighBit = ranges.front().xorHighBit; intlvBits = ranges.front().intlvBits; if (ranges.size() != (ULL(1) << intlvBits)) @@ -111,21 +157,21 @@ class AddrRange ranges.size(), intlvBits); uint8_t match = 0; - for (std::vector::const_iterator r = ranges.begin(); - r != ranges.end(); ++r) { - if (!mergesWith(*r)) + for (const auto& r : ranges) { + if (!mergesWith(r)) fatal("Can only merge ranges with the same start, end " "and interleaving bits\n"); - if (r->intlvMatch != match) + if (r.intlvMatch != match) fatal("Expected interleave match %d but got %d when " - "merging\n", match, r->intlvMatch); + "merging\n", match, r.intlvMatch); ++match; } // our range is complete and we can turn this into a // non-interleaved range intlvHighBit = 0; + xorHighBit = 0; intlvBits = 0; } } @@ -137,6 +183,11 @@ class AddrRange */ bool interleaved() const { return intlvBits != 0; } + /** + * Determine if the range interleaving is hashed or not. + */ + bool hashed() const { return interleaved() && xorHighBit != 0; } + /** * Determing the interleaving granularity of the range. * @@ -182,12 +233,22 @@ class AddrRange */ std::string to_string() const { - if (interleaved()) - return csprintf("[%#llx : %#llx], [%d : %d] = %d", _start, _end, - intlvHighBit, intlvHighBit - intlvBits + 1, - intlvMatch); - else + if (interleaved()) { + if (hashed()) { + return csprintf("[%#llx : %#llx], [%d : %d] XOR [%d : %d] = %d", + _start, _end, + intlvHighBit, intlvHighBit - intlvBits + 1, + xorHighBit, xorHighBit - intlvBits + 1, + intlvMatch); + } else { + return csprintf("[%#llx : %#llx], [%d : %d] = %d", + _start, _end, + intlvHighBit, intlvHighBit - intlvBits + 1, + intlvMatch); + } + } else { return csprintf("[%#llx : %#llx]", _start, _end); + } } /** @@ -202,6 +263,7 @@ class AddrRange { return r._start == _start && r._end == _end && r.intlvHighBit == intlvHighBit && + r.xorHighBit == xorHighBit && r.intlvBits == intlvBits; } @@ -263,10 +325,20 @@ class AddrRange // check if the address is in the range and if there is either // no interleaving, or with interleaving also if the selected // bits from the address match the interleaving value - return a >= _start && a <= _end && - (!interleaved() || - (bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) == - intlvMatch)); + bool in_range = a >= _start && a <= _end; + if (!interleaved()) { + return in_range; + } else if (in_range) { + if (!hashed()) { + return bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) == + intlvMatch; + } else { + return (bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) ^ + bits(a, xorHighBit, xorHighBit - intlvBits + 1)) == + intlvMatch; + } + } + return false; } /** diff --git a/src/python/m5/params.py b/src/python/m5/params.py index 7dc443b2d..846c5416e 100644 --- a/src/python/m5/params.py +++ b/src/python/m5/params.py @@ -726,8 +726,9 @@ class AddrRange(ParamValue): cxx_type = 'AddrRange' def __init__(self, *args, **kwargs): - # Disable interleaving by default + # Disable interleaving and hashing by default self.intlvHighBit = 0 + self.xorHighBit = 0 self.intlvBits = 0 self.intlvMatch = 0 @@ -745,6 +746,8 @@ class AddrRange(ParamValue): # Now on to the optional bit if 'intlvHighBit' in kwargs: self.intlvHighBit = int(kwargs.pop('intlvHighBit')) + if 'xorHighBit' in kwargs: + self.xorHighBit = int(kwargs.pop('xorHighBit')) if 'intlvBits' in kwargs: self.intlvBits = int(kwargs.pop('intlvBits')) if 'intlvMatch' in kwargs: @@ -814,8 +817,8 @@ class AddrRange(ParamValue): from m5.internal.range import AddrRange return AddrRange(long(self.start), long(self.end), - int(self.intlvHighBit), int(self.intlvBits), - int(self.intlvMatch)) + int(self.intlvHighBit), int(self.xorHighBit), + int(self.intlvBits), int(self.intlvMatch)) # Boolean parameter type. Python doesn't let you subclass bool, since # it doesn't want to let you create multiple instances of True and -- cgit v1.2.3