analyze-blocking-sizes.cpp File Reference

#include <iostream>
#include <cstdint>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <fstream>
#include <string>
#include <cmath>
#include <cassert>
#include <cstring>
#include <memory>
#include <Eigen/Core>

Classes
struct	size_triple_t
struct	inputfile_entry_t
struct	inputfile_t
struct	preprocessed_inputfile_entry_t
struct	preprocessed_inputfile_t
struct	action_t
struct	partition_action_t
struct	evaluate_defaults_action_t
struct	evaluate_defaults_action_t::results_entry_t

Functions
uint8_t	log2_pot (size_t x)
uint16_t	compact_size_triple (size_t k, size_t m, size_t n)
ostream &	operator<< (ostream &s, const size_triple_t &t)
bool	lower_efficiency (const preprocessed_inputfile_entry_t &e1, const preprocessed_inputfile_entry_t &e2)
void	check_all_files_in_same_exact_order (const vector< preprocessed_inputfile_t > &preprocessed_inputfiles)
float	efficiency_of_subset (const vector< preprocessed_inputfile_t > &preprocessed_inputfiles, const vector< size_t > &subset)
void	dump_table_for_subset (const vector< preprocessed_inputfile_t > &preprocessed_inputfiles, const vector< size_t > &subset)
float	efficiency_of_partition (const vector< preprocessed_inputfile_t > &preprocessed_inputfiles, const vector< vector< size_t >> &partition)
void	make_first_subset (size_t subset_size, vector< size_t > &out_subset, size_t set_size)
bool	is_last_subset (const vector< size_t > &subset, size_t set_size)
void	next_subset (vector< size_t > &inout_subset, size_t set_size)
bool	is_number_of_subsets_feasible (size_t n, size_t p)
size_t	max_feasible_subset_size (size_t n)
void	find_subset_with_efficiency_higher_than (const vector< preprocessed_inputfile_t > &preprocessed_inputfiles, float required_efficiency_to_beat, vector< size_t > &inout_remainder, vector< size_t > &out_subset)
void	find_partition_with_efficiency_higher_than (const vector< preprocessed_inputfile_t > &preprocessed_inputfiles, float required_efficiency_to_beat, vector< vector< size_t >> &out_partition)
void	print_partition (const vector< preprocessed_inputfile_t > &preprocessed_inputfiles, const vector< vector< size_t >> &partition)
void	show_usage_and_exit (int argc, char *argv[], const vector< unique_ptr< action_t >> &available_actions)
int	main (int argc, char *argv[])

Variables
const int	default_precision = 4
bool	only_cubic_sizes = false
bool	dump_tables = false
const size_t	number_of_subsets_limit = 100
const size_t	always_search_subsets_of_size_at_least = 2

Function Documentation

check_all_files_in_same_exact_order()

void check_all_files_in_same_exact_order

(

const vector< preprocessed_inputfile_t > &

preprocessed_inputfiles

)

                                                                                                          {
  if (preprocessed_inputfiles.empty()) {
    return;
  }
 
  const preprocessed_inputfile_t& first_file = preprocessed_inputfiles[0];
  const size_t num_entries = first_file.entries.size();
 
  for (size_t i = 0; i < preprocessed_inputfiles.size(); i++) {
    if (preprocessed_inputfiles[i].entries.size() != num_entries) {
      cerr << "these files have different number of entries: " << preprocessed_inputfiles[i].filename << " and "
           << first_file.filename << endl;
      exit(1);
    }
  }
 
  for (size_t entry_index = 0; entry_index < num_entries; entry_index++) {
    const uint16_t entry_product_size = first_file.entries[entry_index].product_size;
    const uint16_t entry_block_size = first_file.entries[entry_index].block_size;
    for (size_t file_index = 0; file_index < preprocessed_inputfiles.size(); file_index++) {
      const preprocessed_inputfile_t& cur_file = preprocessed_inputfiles[file_index];
      if (cur_file.entries[entry_index].product_size != entry_product_size ||
          cur_file.entries[entry_index].block_size != entry_block_size) {
        cerr << "entries not in same order between these files: " << first_file.filename << " and " << cur_file.filename
             << endl;
        exit(1);
      }
    }
  }
}

References preprocessed_inputfile_t::entries, preprocessed_inputfile_t::filename, and i.

Referenced by partition_action_t::run().

compact_size_triple()

uint16_t compact_size_triple	(	size_t	k,
		size_t	m,
		size_t	n
	)

                                                           {
  return (log2_pot(k) << 8) | (log2_pot(m) << 4) | log2_pot(n);
}

References k, log2_pot(), m, and n.

dump_table_for_subset()

void dump_table_for_subset	(	const vector< preprocessed_inputfile_t > &	preprocessed_inputfiles,
		const vector< size_t > &	subset
	)

                                                         {
  const preprocessed_inputfile_t& first_file = preprocessed_inputfiles[subset[0]];
  const size_t num_entries = first_file.entries.size();
  size_t entry_index = 0;
  size_t first_entry_index_with_this_product_size = 0;
  uint16_t product_size = first_file.entries[0].product_size;
  size_t i = 0;
  size_triple_t min_product_size(first_file.entries.front().product_size);
  size_triple_t max_product_size(first_file.entries.back().product_size);
  if (!min_product_size.is_cubic() || !max_product_size.is_cubic()) {
    abort();
  }
  if (only_cubic_sizes) {
    cerr << "Can't generate tables with --only-cubic-sizes." << endl;
    abort();
  }
  cout << "struct LookupTable {" << endl;
  cout << "  static const size_t BaseSize = " << min_product_size.k << ";" << endl;
  const size_t NumSizes = log2_pot(max_product_size.k / min_product_size.k) + 1;
  const size_t TableSize = NumSizes * NumSizes * NumSizes;
  cout << "  static const size_t NumSizes = " << NumSizes << ";" << endl;
  cout << "  static const unsigned short* Data() {" << endl;
  cout << "    static const unsigned short data[" << TableSize << "] = {";
  while (entry_index < num_entries) {
    ++entry_index;
    if (entry_index == num_entries || first_file.entries[entry_index].product_size != product_size) {
      float best_efficiency_this_product_size = 0.0f;
      uint16_t best_block_size_this_product_size = 0;
      for (size_t e = first_entry_index_with_this_product_size; e < entry_index; e++) {
        float efficiency_this_entry = 1.0f;
        for (auto i = subset.begin(); i != subset.end(); ++i) {
          efficiency_this_entry = min(efficiency_this_entry, preprocessed_inputfiles[*i].entries[e].efficiency);
        }
        if (efficiency_this_entry > best_efficiency_this_product_size) {
          best_efficiency_this_product_size = efficiency_this_entry;
          best_block_size_this_product_size = first_file.entries[e].block_size;
        }
      }
      if ((i++) % NumSizes) {
        cout << " ";
      } else {
        cout << endl << "      ";
      }
      cout << "0x" << hex << best_block_size_this_product_size << dec;
      if (entry_index < num_entries) {
        cout << ",";
        first_entry_index_with_this_product_size = entry_index;
        product_size = first_file.entries[entry_index].product_size;
      }
    }
  }
  if (i != TableSize) {
    cerr << endl << "Wrote " << i << " table entries, expected " << TableSize << endl;
    abort();
  }
  cout << endl << "    };" << endl;
  cout << "    return data;" << endl;
  cout << "  }" << endl;
  cout << "};" << endl;
}

References e(), preprocessed_inputfile_t::entries, i, size_triple_t::is_cubic(), size_triple_t::k, log2_pot(), min, and only_cubic_sizes.

Referenced by print_partition().

efficiency_of_partition()

float efficiency_of_partition	(	const vector< preprocessed_inputfile_t > &	preprocessed_inputfiles,
		const vector< vector< size_t >> &	partition
	)

                                                                       {
  float efficiency = 1.0f;
  for (auto s = partition.begin(); s != partition.end(); ++s) {
    efficiency = min(efficiency, efficiency_of_subset(preprocessed_inputfiles, *s));
  }
  return efficiency;
}

References efficiency_of_subset(), min, and s.

Referenced by print_partition(), and partition_action_t::run().

efficiency_of_subset()

float efficiency_of_subset	(	const vector< preprocessed_inputfile_t > &	preprocessed_inputfiles,
		const vector< size_t > &	subset
	)

                                                         {
  if (subset.size() <= 1) {
    return 1.0f;
  }
  const preprocessed_inputfile_t& first_file = preprocessed_inputfiles[subset[0]];
  const size_t num_entries = first_file.entries.size();
  float efficiency = 1.0f;
  size_t entry_index = 0;
  size_t first_entry_index_with_this_product_size = 0;
  uint16_t product_size = first_file.entries[0].product_size;
  while (entry_index < num_entries) {
    ++entry_index;
    if (entry_index == num_entries || first_file.entries[entry_index].product_size != product_size) {
      float efficiency_this_product_size = 0.0f;
      for (size_t e = first_entry_index_with_this_product_size; e < entry_index; e++) {
        float efficiency_this_entry = 1.0f;
        for (auto i = subset.begin(); i != subset.end(); ++i) {
          efficiency_this_entry = min(efficiency_this_entry, preprocessed_inputfiles[*i].entries[e].efficiency);
        }
        efficiency_this_product_size = max(efficiency_this_product_size, efficiency_this_entry);
      }
      efficiency = min(efficiency, efficiency_this_product_size);
      if (entry_index < num_entries) {
        first_entry_index_with_this_product_size = entry_index;
        product_size = first_file.entries[entry_index].product_size;
      }
    }
  }
 
  return efficiency;
}

References e(), preprocessed_inputfile_t::entries, i, max, and min.

Referenced by efficiency_of_partition(), find_subset_with_efficiency_higher_than(), and print_partition().

find_partition_with_efficiency_higher_than()

void find_partition_with_efficiency_higher_than	(	const vector< preprocessed_inputfile_t > &	preprocessed_inputfiles,
		float	required_efficiency_to_beat,
		vector< vector< size_t >> &	out_partition
	)

                                                                                       {
  out_partition.resize(0);
 
  vector<size_t> remainder;
  for (size_t i = 0; i < preprocessed_inputfiles.size(); i++) {
    remainder.push_back(i);
  }
 
  while (!remainder.empty()) {
    vector<size_t> new_subset;
    find_subset_with_efficiency_higher_than(preprocessed_inputfiles, required_efficiency_to_beat, remainder,
                                            new_subset);
    out_partition.push_back(new_subset);
  }
}

References find_subset_with_efficiency_higher_than(), and i.

Referenced by partition_action_t::run().

find_subset_with_efficiency_higher_than()

void find_subset_with_efficiency_higher_than	(	const vector< preprocessed_inputfile_t > &	preprocessed_inputfiles,
		float	required_efficiency_to_beat,
		vector< size_t > &	inout_remainder,
		vector< size_t > &	out_subset
	)

                                                                         {
  out_subset.resize(0);
 
  if (required_efficiency_to_beat >= 1.0f) {
    cerr << "can't beat efficiency 1." << endl;
    abort();
  }
 
  while (!inout_remainder.empty()) {
    vector<size_t> candidate_indices(inout_remainder.size());
    for (size_t i = 0; i < candidate_indices.size(); i++) {
      candidate_indices[i] = i;
    }
 
    size_t candidate_indices_subset_size = max_feasible_subset_size(candidate_indices.size());
    while (candidate_indices_subset_size >= 1) {
      vector<size_t> candidate_indices_subset;
      make_first_subset(candidate_indices_subset_size, candidate_indices_subset, candidate_indices.size());
 
      vector<size_t> best_candidate_indices_subset;
      float best_efficiency = 0.0f;
      vector<size_t> trial_subset = out_subset;
      trial_subset.resize(out_subset.size() + candidate_indices_subset_size);
      while (true) {
        for (size_t i = 0; i < candidate_indices_subset_size; i++) {
          trial_subset[out_subset.size() + i] = inout_remainder[candidate_indices_subset[i]];
        }
 
        float trial_efficiency = efficiency_of_subset(preprocessed_inputfiles, trial_subset);
        if (trial_efficiency > best_efficiency) {
          best_efficiency = trial_efficiency;
          best_candidate_indices_subset = candidate_indices_subset;
        }
        if (is_last_subset(candidate_indices_subset, candidate_indices.size())) {
          break;
        }
        next_subset(candidate_indices_subset, candidate_indices.size());
      }
 
      if (best_efficiency > required_efficiency_to_beat) {
        for (size_t i = 0; i < best_candidate_indices_subset.size(); i++) {
          candidate_indices[i] = candidate_indices[best_candidate_indices_subset[i]];
        }
        candidate_indices.resize(best_candidate_indices_subset.size());
      }
      candidate_indices_subset_size--;
    }
 
    size_t candidate_index = candidate_indices[0];
    auto candidate_iterator = inout_remainder.begin() + candidate_index;
    vector<size_t> trial_subset = out_subset;
 
    trial_subset.push_back(*candidate_iterator);
    float trial_efficiency = efficiency_of_subset(preprocessed_inputfiles, trial_subset);
    if (trial_efficiency > required_efficiency_to_beat) {
      out_subset.push_back(*candidate_iterator);
      inout_remainder.erase(candidate_iterator);
    } else {
      break;
    }
  }
}

References efficiency_of_subset(), i, is_last_subset(), make_first_subset(), max_feasible_subset_size(), and next_subset().

Referenced by find_partition_with_efficiency_higher_than().

is_last_subset()

bool is_last_subset	(	const vector< size_t > &	subset,
		size_t	set_size
	)

{ return subset[0] == set_size - subset.size(); }

Referenced by find_subset_with_efficiency_higher_than(), and next_subset().

is_number_of_subsets_feasible()

bool is_number_of_subsets_feasible	(	size_t	n,
		size_t	p
	)

                                                       {
  assert(n > 0 && p > 0 && p <= n);
  uint64_t numerator = 1, denominator = 1;
  for (size_t i = 0; i < p; i++) {
    numerator *= n - i;
    denominator *= i + 1;
    if (numerator > denominator * number_of_subsets_limit) {
      return false;
    }
  }
  return true;
}

References assert, i, n, number_of_subsets_limit, and p.

Referenced by max_feasible_subset_size().

log2_pot()

uint8_t log2_pot

(

size_t

x

)

                           {
  size_t l = 0;
  while (x >>= 1) l++;
  return l;
}

References plotDoE::x.

Referenced by compact_size_triple(), and dump_table_for_subset().

lower_efficiency()

bool lower_efficiency	(	const preprocessed_inputfile_entry_t &	e1,
		const preprocessed_inputfile_entry_t &	e2
	)

                                                                                                          {
  return e1.efficiency < e2.efficiency;
}

References preprocessed_inputfile_entry_t::efficiency.

Referenced by evaluate_defaults_action_t::run().

main()

int main	(	int argc	,
		char *	argv[]
	)

                                 {
  cout.precision(default_precision);
  cerr.precision(default_precision);
 
  vector<unique_ptr<action_t>> available_actions;
  available_actions.emplace_back(new partition_action_t);
  available_actions.emplace_back(new evaluate_defaults_action_t);
 
  vector<string> input_filenames;
 
  action_t* action = nullptr;
 
  if (argc < 2) {
    show_usage_and_exit(argc, argv, available_actions);
  }
  for (int i = 1; i < argc; i++) {
    bool arg_handled = false;
    // Step 1. Try to match action invocation names.
    for (auto it = available_actions.begin(); it != available_actions.end(); ++it) {
      if (!strcmp(argv[i], (*it)->invokation_name())) {
        if (!action) {
          action = it->get();
          arg_handled = true;
          break;
        } else {
          cerr << "can't specify more than one action!" << endl;
          show_usage_and_exit(argc, argv, available_actions);
        }
      }
    }
    if (arg_handled) {
      continue;
    }
    // Step 2. Try to match option names.
    if (argv[i][0] == '-') {
      if (!strcmp(argv[i], "--only-cubic-sizes")) {
        only_cubic_sizes = true;
        arg_handled = true;
      }
      if (!strcmp(argv[i], "--dump-tables")) {
        dump_tables = true;
        arg_handled = true;
      }
      if (!arg_handled) {
        cerr << "Unrecognized option: " << argv[i] << endl;
        show_usage_and_exit(argc, argv, available_actions);
      }
    }
    if (arg_handled) {
      continue;
    }
    // Step 3. Default to interpreting args as input filenames.
    input_filenames.emplace_back(argv[i]);
  }
 
  if (dump_tables && only_cubic_sizes) {
    cerr << "Incompatible options: --only-cubic-sizes and --dump-tables." << endl;
    show_usage_and_exit(argc, argv, available_actions);
  }
 
  if (!action) {
    show_usage_and_exit(argc, argv, available_actions);
  }
 
  action->run(input_filenames);
}

References calibrate::action, default_precision, dump_tables, i, only_cubic_sizes, and show_usage_and_exit().

make_first_subset()

void make_first_subset	(	size_t	subset_size,
		vector< size_t > &	out_subset,
		size_t	set_size
	)

                                                                                        {
  assert(subset_size >= 1 && subset_size <= set_size);
  out_subset.resize(subset_size);
  for (size_t i = 0; i < subset_size; i++) {
    out_subset[i] = i;
  }
}

References assert, and i.

Referenced by find_subset_with_efficiency_higher_than().

max_feasible_subset_size()

size_t max_feasible_subset_size

(

size_t

n

)

                                          {
  assert(n > 0);
  const size_t minresult = min<size_t>(n - 1, always_search_subsets_of_size_at_least);
  for (size_t p = 1; p <= n - 1; p++) {
    if (!is_number_of_subsets_feasible(n, p + 1)) {
      return max(p, minresult);
    }
  }
  return n - 1;
}

References always_search_subsets_of_size_at_least, assert, is_number_of_subsets_feasible(), max, n, and p.

Referenced by find_subset_with_efficiency_higher_than().

next_subset()

void next_subset	(	vector< size_t > &	inout_subset,
		size_t	set_size
	)

                                                                {
  if (is_last_subset(inout_subset, set_size)) {
    cerr << "iterating past the last subset" << endl;
    abort();
  }
  size_t i = 1;
  while (inout_subset[inout_subset.size() - i] == set_size - i) {
    i++;
    assert(i <= inout_subset.size());
  }
  size_t first_index_to_change = inout_subset.size() - i;
  inout_subset[first_index_to_change]++;
  size_t p = inout_subset[first_index_to_change];
  for (size_t j = first_index_to_change + 1; j < inout_subset.size(); j++) {
    inout_subset[j] = ++p;
  }
}

References assert, i, is_last_subset(), j, and p.

Referenced by find_subset_with_efficiency_higher_than().

operator<<()

ostream& operator<<	(	ostream &	s,
		const size_triple_t &	t
	)

{ return s << "(" << t.k << ", " << t.m << ", " << t.n << ")"; }

References s, and plotPSD::t.

print_partition()

void print_partition	(	const vector< preprocessed_inputfile_t > &	preprocessed_inputfiles,
		const vector< vector< size_t >> &	partition
	)

                                                              {
  float efficiency = efficiency_of_partition(preprocessed_inputfiles, partition);
  cout << "Partition into " << partition.size() << " subsets for " << efficiency * 100.0f << "% efficiency" << endl;
  for (auto subset = partition.begin(); subset != partition.end(); ++subset) {
    cout << "  Subset " << (subset - partition.begin()) << ", efficiency "
         << efficiency_of_subset(preprocessed_inputfiles, *subset) * 100.0f << "%:" << endl;
    for (auto file = subset->begin(); file != subset->end(); ++file) {
      cout << "    " << preprocessed_inputfiles[*file].filename << endl;
    }
    if (dump_tables) {
      cout << "  Table:" << endl;
      dump_table_for_subset(preprocessed_inputfiles, *subset);
    }
  }
  cout << endl;
}

References dump_table_for_subset(), dump_tables, efficiency_of_partition(), and efficiency_of_subset().

Referenced by partition_action_t::run().

show_usage_and_exit()

void show_usage_and_exit	(	int	argc,
		char *	argv[],
		const vector< unique_ptr< action_t >> &	available_actions
	)

                                                                                                        {
  cerr << "usage: " << argv[0] << " <action> [options...] <input files...>" << endl;
  cerr << "available actions:" << endl;
  for (auto it = available_actions.begin(); it != available_actions.end(); ++it) {
    cerr << "  " << (*it)->invokation_name() << endl;
  }
  cerr << "the input files should each contain an output of benchmark-blocking-sizes" << endl;
  exit(1);
}

Referenced by main(), and evaluate_defaults_action_t::run().

Variable Documentation

always_search_subsets_of_size_at_least

const size_t always_search_subsets_of_size_at_least = 2

Referenced by max_feasible_subset_size().

default_precision

const int default_precision = 4

Referenced by main(), and evaluate_defaults_action_t::run().

dump_tables

bool dump_tables = false

Referenced by main(), and print_partition().

number_of_subsets_limit

const size_t number_of_subsets_limit = 100

Referenced by is_number_of_subsets_feasible().

only_cubic_sizes

bool only_cubic_sizes = false

Referenced by dump_table_for_subset(), inputfile_t::inputfile_t(), and main().