Module Support Library¶

Fixed-width saturating counter¶

template<typename val_type, val_type MAXVAL, val_type MINVAL> class base_fwcounter¶

A fixed-width saturating counter. All arithmetic operations on this value are clamped between the maximum and minimum values.

Template Parameters:

val_type – The underlying representation of the value.
MAXVAL – The maximum to saturate at.
MINVAL – The minimum to saturate at.

Public Functions

base_fwcounter<val_type, MAXVAL, MINVAL> &operator++()¶: Increment the value, saturating at the maximum value.

base_fwcounter<val_type, MAXVAL, MINVAL> &operator--()¶: Decrement the value, saturating at the minimum value.

base_fwcounter<val_type, MAXVAL, MINVAL> &operator+=(base_fwcounter<val_type, MAXVAL, MINVAL>)¶: Add the other operand to the wrapped value, saturating at the minimum and maximum.

base_fwcounter<val_type, MAXVAL, MINVAL> &operator-=(base_fwcounter<val_type, MAXVAL, MINVAL>)¶: Subtract the other operand from the wrapped value, saturating at the minimum and maximum.

base_fwcounter<val_type, MAXVAL, MINVAL> &operator*=(base_fwcounter<val_type, MAXVAL, MINVAL>)¶: Multiply the wrapped value by the other operand, saturating at the minimum and maximum.

base_fwcounter<val_type, MAXVAL, MINVAL> &operator/=(base_fwcounter<val_type, MAXVAL, MINVAL>)¶: Divide the wrapped value by the other operand, saturating at the minimum and maximum.

inline bool is_max() const¶: Detect whether the counter is saturated at its maximum.

inline bool is_min() const¶: Detect whether the counter is saturated at its minimum.

inline val_type value() const¶: Unpack the wrapped value.

template<std::size_t WIDTH> using champsim::msl::fwcounter = base_fwcounter<signed long long int, (1 << WIDTH) - 1, 0>¶

template<std::size_t WIDTH> using champsim::msl::sfwcounter = base_fwcounter<signed long long int, (1 << (WIDTH - 1)) - 1, -(1 << (WIDTH - 1))>¶

Functions for bit operations¶

template<typename T> auto champsim::msl::lg2(T n)¶: Compute the base-2 logarithm of an integer.

template<typename T> T champsim::msl::next_pow2(T n)¶: Compute the smallest power of 2 not less than the given integer.

template<typename T> bool champsim::msl::is_power_of_2(T n)¶: A backport of std::has_single_bit().

long long champsim::msl::ipow(long long base, unsigned exp)¶: Compute an integer power. This function may overflow very easily. Use only for small bases or very small exponents.

uint64_t champsim::msl::bitmask(champsim::data::bits begin, champsim::data::bits end)¶

Produce a mask that can be used in a bitwise-and operation to select particular bits of a number.

0xffff & bitmask(8_b,4_b) == 0xf0;

If end is not specified, it is defaulted to 0, that is, the least-significant bit.

Note

This should not be used as a mask generator for address types. Use champsim::address_slice instead.

Parameters:

begin – The most-significant bit of the mask, not inclusive.
end – The least-significant bit of the mask, inclusive.

uint64_t champsim::msl::bitmask(champsim::data::bits begin)¶: This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

uint64_t champsim::msl::bitmask(std::size_t begin, std::size_t end = 0)¶

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Deprecated:: Users should prefer the overload with champsim::data::bits parameters.

template<typename T> auto champsim::msl::splice_bits(T upper, T lower, champsim::data::bits bits_upper, champsim::data::bits bits_lower)¶

Join two values, selecting some bits from one value and some bits from another.

splice_bits(0xaaaa, 0xbbbb, 8_b, 4_b) == 0xaaba;

If end is not specified, it is defaulted to 0, that is, the least-significant bit.

Note

This is an implementation detail of champsim::splice(), which should be preferred for address types. This function is provided for general use.

Parameters:

upper – The operand from which to take the not-selected bits.
lower – The operand from which to take the selected bits.
bits_upper – The most-significant bit of the mask, not inclusive.
bits_lower – The least-significant bit of the mask, inclusive.

template<typename T> auto champsim::msl::splice_bits(T upper, T lower, champsim::data::bits bits)¶: This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<typename T> auto champsim::msl::splice_bits(T upper, T lower, std::size_t bits_upper, std::size_t bits_lower)¶

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Deprecated:: Users should prefer the overload with champsim::data::bits parameters.

template<typename T> auto champsim::msl::splice_bits(T upper, T lower, std::size_t bits)¶

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Deprecated:: Users should prefer the overload with champsim::data::bits parameters.

LRU Table¶

template<typename T, typename SetProj = detail::table_indexer<T>, typename TagProj = detail::table_tagger<T>> class lru_table¶

A set-associative table with LRU eviction.

Elements are placed into sets using a set projection function object and matched within a set using a tag projection function object. By default, these call .index() and .tag() member functions on the element type. The number of sets must be a power of 2.

This is useful for building hardware tables such as BTB entries, stride tracker tables, and signature tables. See ip_stride and basic_btb for examples.

Template Parameters:

T – The element type stored in the table.
SetProj – A function object that projects an element to a set index. Defaults to calling T::index().
TagProj – A function object that projects an element to a tag for matching. Defaults to calling T::tag().

Public Functions

inline std::optional<value_type> check_hit(const value_type &elem)¶

Look up an element in the table by set and tag.

If a matching element is found, its LRU timestamp is updated and the element is returned. Otherwise returns std::nullopt.

Parameters:: elem – An element whose set and tag projections identify the lookup.
Returns:: The matching element, or std::nullopt on a miss.

inline void fill(const value_type &elem)¶

Insert or update an element in the table.

If an element with a matching tag already exists in the set, it is updated in place. Otherwise the LRU element in the set is evicted and replaced.

Parameters:: elem – The element to insert.

inline std::optional<value_type> invalidate(const value_type &elem)¶

Remove an element from the table.

If a matching element is found, it is removed and returned. Otherwise returns std::nullopt.

Parameters:: elem – An element whose set and tag projections identify the entry to remove.
Returns:: The removed element, or std::nullopt if not found.

inline lru_table(std::size_t sets, std::size_t ways, SetProj set_proj, TagProj tag_proj)¶

Construct an LRU table.

Parameters:

sets – The number of sets. Must be a positive power of 2.
ways – The number of ways per set.
set_proj – The function object used to compute the set index from an element.
tag_proj – The function object used to compute the tag from an element.

Set-dueling utilities¶

template<typename T, typename CatProj = category_projector<T>> class categorizer¶

Splits an input space into categories for set dueling.

Given a candidate value and a sample rate, the categorizer assigns the candidate to a category number. Category 0 and category 1 are the two “leader” categories used by set-dueling policies like DRRIP and SHiP; all other categories are “follower” sets that use the winning policy.

The sample rate must be a power of 2 and determines how many categories exist (equal to the sample rate).

Template Parameters:

T – The type of value being categorized (e.g. long for set indices).
CatProj – A function object that projects a value of type T to an integer. Defaults to identity.

Public Functions

inline std::size_t get_sample_rate() const¶: Return the sample rate used by this categorizer.

inline std::size_t get_sample_category(const T &candidate) const¶

Return the category number for a given candidate.

Category 0 and 1 are the two leader categories. All other values are follower categories.

Parameters:: candidate – The value to categorize.
Returns:: The category index (0 to sample_rate - 1).

inline categorizer(std::size_t sample_rate_)¶: Construct a categorizer with the given sample rate and default projection.

template<typename T, std::size_t COUNTER_WIDTH, typename CatProj = category_projector<T>> class dscounter¶

A dueling saturating counter for set-dueling policies.

Combines a categorizer with a fixed-width saturating counter to implement set dueling. Category 0 samples are treated as “policy A” and category 1 samples as “policy B”. The counter tracks which policy is performing better.

Use decide() to choose a policy for follower sets, update_good() when a sample performs well, and update_bad() when a sample performs poorly.

Used by replacement policies such as DRRIP and SHiP.

Template Parameters:

T – The type of value being categorized (e.g. long for set indices).
COUNTER_WIDTH – The bit width of the internal saturating counter.
CatProj – A function object that projects a value of type T to an integer. Defaults to identity.

Public Functions

inline std::size_t get_sample_rate() const¶: Return the sample rate used by the internal categorizer.

inline bool decide(const T &candidate)¶

Choose a policy for the given candidate.

Returns true for category-0 candidates (always use policy A), false for category-1 candidates (always use policy B), and for follower categories returns true if policy A is currently winning.

Parameters:: candidate – The value to decide on.
Returns:: true if policy A should be used.

inline void update_good(const T &candidate)¶

Report a good outcome for the given candidate.

Increments the counter for category-0 samples and decrements it for category-1 samples. Has no effect on follower categories.

Parameters:: candidate – The value that had a good outcome.

inline void update_bad(const T &candidate)¶

Report a bad outcome for the given candidate.

Decrements the counter for category-0 samples and increments it for category-1 samples. Has no effect on follower categories.

Parameters:: candidate – The value that had a bad outcome.

static inline std::size_t champsim::msl::get_sample_rate(long num)¶

Determine the sampling rate for set dueling based on the number of sets.

Returns a power-of-2 sample rate: 32 for 1024+ sets, 16 for 256—1023, 8 for 64—255, 4 for 8—63. Asserts if fewer than 8 sets.

Parameters:: num – The total number of sets.
Returns:: The sample rate (a power of 2).

static inline std::size_t champsim::msl::get_num_samples(long num)¶

Calculate the number of samples for set dueling.

Returns num / get_sample_rate(num). Asserts that the number of sets is evenly divisible by the sample rate.

Parameters:: num – The total number of sets.
Returns:: The number of samples per category.

Module Support Library¶

Fixed-width saturating counter¶

Functions for bit operations¶

LRU Table¶

Set-dueling utilities¶

Table of Contents

Previous topic

Next topic

This Page

This page on other branches

Branches