Class model::PuboAdaptive

Adaptive Pubo Model.

This pubo implementation aims for adaptability to per-state memory constraints while using a cache-friendly graph representation.

  1. The numeric type used for indexing can be templated. This type needs to be chosen such that #variables < std::numeric_limits::max() - 2. (the last two values of the range are used as sentinels in the graph representation).
  2. If the graph has high-locality terms, there should (ideally) be some unused range between #variables and that upper limit; this range is used to index into the cache. The number of terms for which caching can be used is limited by the width of that empty range.
  3. The graph representation uses a contigous chunk of memory initialized with an adjacency list for each node. For each term, the first 8 bytes contain the coefficient, followed by a sentinel terminated list of variable_ids (or cache_ids) participating in the term. The sentinel type (NEXT_TERM or NEXT_VAR) denotes when the last term of a variable is reached.
  4. During configuration of the graph representaion, the maximum number of bytes for each state can be specified. If this number exceeds the required bytes to store the boolean variables, the extra bytes are used to preferentially cache the number of zeros in high-locality terms (using either 32-bit or 8-bit counters). This has the effect of both reducing the graph size and time to compute a term.
Inheritance
markov::LinearSweepModel
model::PuboAdaptive
Inherited Members

Constructors

PuboAdaptive()

Create an unconfigured PuboAdaptive model.

Declaration
model::PuboAdaptive<Index>::PuboAdaptive()

Methods

get_identifier()

Return the identifier of this model.

Declaration
std::string model::PuboAdaptive<Index>::get_identifier() const override

get_version()

Return the version of this model.

Declaration
std::string model::PuboAdaptive<Index>::get_version() const override

match_version()

Accept both version 1.0 and 1.1.

Declaration
void model::PuboAdaptive<Index>::match_version(const std::string&version) override

configure()

Configure the model from input.

Declaration
void model::PuboAdaptive<Index>::configure(const utils::Json&json) override

configure()

Declaration
void model::PuboAdaptive<Index>::configure(Configuration_T&config)

get_const_cost()

Declaration
double model::PuboAdaptive<Index>::get_const_cost() const override

is_empty()

Declaration
bool model::PuboAdaptive<Index>::is_empty() const override

configure()

Declaration
void model::PuboAdaptive<Index>::configure(model::Terms&&terms, size_t max_state_size_in_bytes)

get_random_state()

Create a random initial state.

Declaration
State_T model::PuboAdaptive<Index>::get_random_state(utils::RandomGenerator&rng) const override

state_memory_estimate()

Get memory estimation for state.

Declaration
size_t model::PuboAdaptive<Index>::state_memory_estimate() const override

state_only_memory_estimate()

Declaration
size_t model::PuboAdaptive<Index>::state_only_memory_estimate() const override

get_random_transition()

Create a random transition.

Declaration
Transition_T model::PuboAdaptive<Index>::get_random_transition(const State_T&, utils::RandomGenerator&rng) const override

apply_transition()

Applying a random transition is done by advancing the graph pointer to the offset corresponding to the variable being flipped.

Declaration
void model::PuboAdaptive<Index>::apply_transition(const Transition_T&transition, State_T&state) const override

calculate_cost()

Evaluate the whole cost function.

Note

The adjacency list representation is inefficient for this purpose, but we don't expect to evaluate this frequently.

  1. For non-cached terms, double counting is avoided by ensuring neighbor ids are larger than the variable we are processing
  2. For cached terms we use a std::vector to keep track which ones have been counted.
Declaration
double model::PuboAdaptive<Index>::calculate_cost(const State_T&state) const override

calculate_cost_difference()

The cost difference of an arbitrary transition is evaluated by setting up the state pointers and advancing the graph pointer to the offset corresponding to the variable being flipped.

Declaration
double model::PuboAdaptive<Index>::calculate_cost_difference(const State_T&state, const Transition_T&transition) const override

make_linear_sweep()

For a linear sweep, we can avoid the overhead of repeatedly setting up state pointers and jumping to specific offsets in the graph; it can simply be processed in order.

Declaration
void model::PuboAdaptive<Index>::make_linear_sweep(double&cost, State_T&state, std::function<bool(double)>accept, std::function<void(void)>check_lowest) const override

render_state()

Render the state as a structure mapping (original) names to pubo values. NOTE: the mapping is true=zero, false=1.

Declaration
utils::Structure model::PuboAdaptive<Index>::render_state(const State_T&state) const override

get_sweep_size()

One sweep consists of attempting to update each variable once.

Declaration
size_t model::PuboAdaptive<Index>::get_sweep_size() const override

flip_spin()

Flip a spin by applying xor with a shifted bit.

Declaration
void model::PuboAdaptive<Index>::flip_spin(uint64_t *spins, Index index) const

get_spin_value()

Extract a bit by masking with a shifted bit.

Declaration
bool model::PuboAdaptive<Index>::get_spin_value(const uint64_t *spins, Index index) const

get_cache()

Select the appropriate (type and index) of the cache for a given cache_id. NOTE: the cache_id=index-var_count_ is in [0..cache_count_).

Declaration
uint32_t model::PuboAdaptive<Index>::get_cache(size_t cache_id, const uint32_t *cache32, const uint8_t *cache8) const

update_cache()

Add the cache_change to the appropriate (type and index) of the cache.

Declaration
void model::PuboAdaptive<Index>::update_cache(size_t cache_id, uint32_t *cache32, uint8_t *cache8, uint8_t cache_change) const

configure_state_size()

Calculate how many terms we want to and can afford to cache. After a call to this method, state_size_ and the cache counters/offsets have been initialized to the correct values.

Declaration
void model::PuboAdaptive<Index>::configure_state_size(const model::Terms&terms, size_t max_state_size_in_bytes)

configure_graph()

Allocate and fill the adjacency list graph representation.

Declaration
void model::PuboAdaptive<Index>::configure_graph(const model::Terms&terms)

calculate_term_difference()

Declaration
double model::PuboAdaptive<Index>::calculate_term_difference(uint8_t *&p, bool spin_value, const uint64_t *spins, const uint32_t *cache32, const uint8_t *cache8) const

update_caches()

Declaration
void model::PuboAdaptive<Index>::update_caches(uint8_t *&p, bool spin, uint32_t *cache32, uint8_t *cache8) const

take_index()

Interpret the next sizeof(Index) bytes as an Index and advance the pointer.

Declaration
static Index model::PuboAdaptive<Index>::take_index(uint8_t *&p)

take_double()

Interpret the next 8 bytes as a double and advance the pointer.

Declaration
static double model::PuboAdaptive<Index>::take_double(uint8_t *&p)

put_double()

Declaration
static void model::PuboAdaptive<Index>::put_double(uint8_t *&p, double d)

put_index()

Declaration
static void model::PuboAdaptive<Index>::put_index(uint8_t *&p, Index index)