diff options
| -rw-r--r-- | bench/bench_window.cpp | 4 | ||||
| -rw-r--r-- | include/lib94/lib94.hpp | 25 | ||||
| -rw-r--r-- | lib94/core.cpp | 56 | ||||
| -rw-r--r-- | makefile | 2 | ||||
| -rw-r--r-- | readme.txt | 6 | ||||
| -rw-r--r-- | tabulator-mpi/constants.hpp | 3 | ||||
| -rw-r--r-- | tabulator-mpi/head.cpp | 112 | ||||
| -rw-r--r-- | tabulator-mpi/main.cpp | 60 | ||||
| -rw-r--r-- | tabulator-mpi/mpi.txt | 15 | ||||
| -rw-r--r-- | tabulator-mpi/source.cpp | 214 | ||||
| -rw-r--r-- | tabulator-mpi/worker.cpp | 51 |
11 files changed, 283 insertions, 265 deletions
diff --git a/bench/bench_window.cpp b/bench/bench_window.cpp index 99d7926..08f2236 100644 --- a/bench/bench_window.cpp +++ b/bench/bench_window.cpp @@ -194,7 +194,7 @@ void bench_window::on_click_new_round() { .bnumber = 0 }); - if (!lib94::init_round(warriors.data(), warriors.size())) { + if (!lib94::init_round(warriors.data(), warriors.size(), 0, true)) { Gtk::MessageDialog *md = new Gtk::MessageDialog("warriors do not fit in core; removing last warrior"); md->set_transient_for(*this); md->set_modal(); @@ -208,7 +208,7 @@ void bench_window::on_click_new_round() { update_ui(); return; } - assert(lib94::init_round(warriors.data(), warriors.size())); + assert(lib94::init_round(warriors.data(), warriors.size(), 0, true)); } core.mut.lock(); diff --git a/include/lib94/lib94.hpp b/include/lib94/lib94.hpp index 4924732..40c9631 100644 --- a/include/lib94/lib94.hpp +++ b/include/lib94/lib94.hpp @@ -91,15 +91,22 @@ namespace lib94 { //does not effect the address sets. void clear_core_random(); - //clears the address sets, places the supplied warriors into the core, and starts one process for - //each supplied warrior at its org. the count parameter specifies the number of warriors in the - //array. each of the warriors in the array must not be deleted for the duration of the round, but - //the array itself may be deleted after this function returns. on success, this function returns - //true. on failure (i.e. when the warriors do not all fit into the core), this function returns - //false. note that this function does not clear the core before placing the warriors, so you may - //want to call clear_core or clear_core_random before calling this. note also that you probably - //want to call seed_prng, for example with the current time, before the first time you call this. - bool init_round(const warrior *const *warriors, size_t count); + //clears the address sets, places the supplied warriors into the core, and starts one + //process for each supplied warrior at its org. the count parameter specifies the number + //of warriors in the array. each of the warriors in the array must not be deleted for + //the duration of the round, but the array itself may be deleted after this function + //returns. if the offsets parameter is not null, it specifies where in the core the first + //instruction of each warrior is put. if it is null, the warriors are placed at random + //non-overlapping locations, respecting the order that they appear in the array. if + //shuffle is true, the warriors' turn order is decided randomly. if shuffle is false, + //the turn order is the order that they appear in the warriors array. on success, this + //function returns true. on failure (i.e. when offsets is null and the warriors do not + //all fit into the core), this function returns false. note that this function does not + //clear the core before placing the warriors, so you may want to call clear_core or + //clear_core_random before calling this. note also that if you are passing null for + //offsets or setting shuffle to true, you probably want to call seed_prng, for example + //with the current time, before the first time you call this. + bool init_round(const warrior *const *warriors, size_t count, const number_t *offsets, bool shuffle); //returns the number of warriors who have at least one process size_t alive_warrior_count(); diff --git a/lib94/core.cpp b/lib94/core.cpp index 5a2654d..cf563d8 100644 --- a/lib94/core.cpp +++ b/lib94/core.cpp @@ -55,51 +55,59 @@ namespace lib94 { static std::vector<warrior_info> warrior_infos; std::deque<warrior_info *> alive_warriors; - bool init_round(const warrior *const *warriors, size_t count) { + bool init_round(const warrior *const *warriors, size_t count, const number_t *offsets, bool shuffle) { clear_address_sets(); warrior_infos.clear(); alive_warriors = std::deque<warrior_info *>(); - std::vector<number_t> gap_sizes; - gap_sizes.resize(count); + std::vector<number_t> offsets_vector; - std::uniform_real_distribution phi_dist(0.0, 1.0); - number_t gap_remaining = LIB94_CORE_SIZE; + if (!offsets) { - for (size_t i = 0; i < count; ++i) { - number_t wlength = warriors[i]->instructions.size(); - if (wlength > gap_remaining) - return false; - gap_remaining -= wlength; - } + offsets_vector.resize(count); + offsets_vector[0] = 0; - for (size_t i = 0; i < count; ++i) { - number_t gap_size = std::floor(gap_remaining * (1.0 - std::pow(phi_dist(prng), 1.0 / (count - i)))); - gap_sizes[i] = gap_size; - gap_remaining -= gap_size; - } + std::uniform_real_distribution phi_dist(0.0, 1.0); + number_t gap_remaining = LIB94_CORE_SIZE; - size_t place_at = 0; + for (size_t i = 0; i < count; ++i) { + number_t wlength = warriors[i]->instructions.size(); + if (wlength > gap_remaining) + return false; + gap_remaining -= wlength; + } + + for (size_t i = 1; i < count; ++i) { + number_t gap_size = std::floor(gap_remaining * (1.0 - std::pow(phi_dist(prng), 1.0 / (count - i)))); + offsets_vector[i] = offsets_vector[i - 1] + warriors[i - 1]->instructions.size() + gap_size; + gap_remaining -= gap_size; + } + + offsets = offsets_vector.data(); + + } for (size_t i = 0; i < count; ++i) { + const warrior *w = warriors[i]; + const number_t offset = offsets[i]; for (number_t i = 0; i < (number_t)w->instructions.size(); ++i) { - assert(place_at + i < LIB94_CORE_SIZE); - core[place_at + i] = w->instructions[i]; - add_written_instruction(core + place_at + i); + assert(offset + i < LIB94_CORE_SIZE); + core[offset + i] = w->instructions[i]; + add_written_instruction(core + offset + i); } warrior_infos.push_back({}); warrior_info *wi = &warrior_infos.back(); wi->the_warrior = w; - assert(place_at + w->org < LIB94_CORE_SIZE); - wi->processes.push_back(place_at + w->org); + assert(offset + w->org < LIB94_CORE_SIZE); + wi->processes.push_back(offsets[i] + w->org); - place_at += w->instructions.size() + gap_sizes[i]; } - std::shuffle(warrior_infos.begin(), warrior_infos.end(), prng); + if (shuffle) + std::shuffle(warrior_infos.begin(), warrior_infos.end(), prng); for (warrior_info &wi : warrior_infos) alive_warriors.push_back(&wi); @@ -16,7 +16,7 @@ bin/bench: obj/bench/main.o obj/bench/bench_window.o obj/bench/core_widget.o obj @mkdir -p $(dir $@) g++ ${CPP_ARGS} $^ ${GTKMM_LD_ARGS} -o $@ -bin/tabulator-mpi: obj/tabulator-mpi/main.o obj/tabulator-mpi/head.o obj/tabulator-mpi/worker.o obj/lib94.o +bin/tabulator-mpi: obj/tabulator-mpi/source.o obj/lib94.o @mkdir -p $(dir $@) g++ ${CPP_ARGS} $^ ${MPI_LD_ARGS} -o $@ @@ -28,9 +28,9 @@ To open bench, just run bin/bench after building as above. === tabulator === -The "tabulator" program runs every possible pairing of warriors from a selection against each other a number of times, and then shows -the number of wins of each warrior against each other warrior in a table format. This program uses MPI to run batches of these rounds -in different processes, and communicate the results back to a head process. +The "tabulator" program runs every possible pairing of warriors from a selection against each other with ever possible separation, +and then shows the number of wins of each warrior against each other warrior in a table format. This program uses MPI to run batches +of these rounds in different processes, and communicate the results back to a head process. To run all of the included warriors against each other, run mpirun bin/tabulator-mpi warriors/*.red diff --git a/tabulator-mpi/constants.hpp b/tabulator-mpi/constants.hpp deleted file mode 100644 index de4dd27..0000000 --- a/tabulator-mpi/constants.hpp +++ /dev/null @@ -1,3 +0,0 @@ -#define STEPS_TO_TIE 1000000 -#define ROUNDS_PER_CHUNK 200 -#define CHUNKS_PER_PAIR 5 diff --git a/tabulator-mpi/head.cpp b/tabulator-mpi/head.cpp deleted file mode 100644 index 38fcde6..0000000 --- a/tabulator-mpi/head.cpp +++ /dev/null @@ -1,112 +0,0 @@ -#include <lib94/lib94.hpp> -#include <cstdio> -#include <mpi.h> - -#include "constants.hpp" - -static int **wins; - -static int get_result() { - int result[4]; - MPI_Status status; - MPI_Recv(result, 4, MPI_INT, MPI_ANY_SOURCE, 1, MPI_COMM_WORLD, &status); - - if (result[0] != -1) { - wins[result[0]][result[1]] += result[2]; - wins[result[1]][result[0]] += result[3]; - } - - return status.MPI_SOURCE; -} - -void head_main(int comm_size, int warrior_count, const lib94::warrior *const *warriors) { - wins = new int *[warrior_count]; - for (int i = 0; i < warrior_count; ++i) { - wins[i] = new int[warrior_count]; - for (int j = 0; j < warrior_count; ++j) - wins[i][j] = 0; - } - - int chunks = warrior_count * (warrior_count - 1) / 2 * CHUNKS_PER_PAIR; - int on_chunk = 0; - - int right_name_width = 0; - for (int i = 0; i < warrior_count; ++i) - if ((int)warriors[i]->name.size() > right_name_width) - right_name_width = warriors[i]->name.size(); - - int rank_width = std::max(std::string("rank").size(), std::to_string(comm_size - 1).size()); - int right_round_width = std::to_string(CHUNKS_PER_PAIR * ROUNDS_PER_CHUNK).size(); - int right_chunk_width = std::to_string(chunks).size(); - - int left_name_width = std::max(right_name_width, (int)std::string("match").size() - right_name_width - 4); - int left_round_width = std::max((int)std::to_string((CHUNKS_PER_PAIR - 1) * ROUNDS_PER_CHUNK + 1).size(), (int)std::string("rounds").size() - right_round_width - 3); - int left_chunk_width = std::max(right_chunk_width, (int)std::string("chunk").size() - right_chunk_width - 3); - - fprintf(stderr, "\x1b""7\x1b[?47h\x1b[?25l\x1b[2J\x1b[0H"); - fprintf(stderr, "%*s | %*s | %*s | %*s", rank_width, "rank", - left_name_width + 4 + right_name_width, "match", - left_round_width + 3 + right_round_width, "rounds", - left_chunk_width + 3 + right_chunk_width, "chunk"); - - for (int i = 0; i < warrior_count; ++i) - for (int j = i + 1; j < warrior_count; ++j) - for (int x = 0; x < CHUNKS_PER_PAIR; ++x) { - ++on_chunk; - int rank = get_result(); - int message[4] = {i, j, x * ROUNDS_PER_CHUNK}; - MPI_Send(message, 4, MPI_INT, rank, 0, MPI_COMM_WORLD); - fprintf(stderr, "\x1b[%d;0H%*d | %*s vs %*s | %*d - %*d | %*d / %*d\x1b[0K", rank + 1, rank_width, rank, - left_name_width, warriors[i]->name.c_str(), right_name_width, warriors[j]->name.c_str(), - left_round_width, x * ROUNDS_PER_CHUNK + 1, right_round_width, x * ROUNDS_PER_CHUNK + ROUNDS_PER_CHUNK, - left_chunk_width, on_chunk, right_chunk_width, chunks); - } - - for (int i = 0; i < comm_size - 1; ++i) { - int rank = get_result(); - int message[4] = {-1}; - MPI_Send(message, 4, MPI_INT, rank, 0, MPI_COMM_WORLD); - fprintf(stderr, "\x1b[%d;0H%*d | %*s | %*s | %*s\x1b[0K", - rank + 1, rank_width, rank, - left_name_width + 4 + right_name_width, "", - left_round_width + 3 + right_round_width, "", - left_chunk_width + 3 + right_chunk_width, "done"); - } - - fprintf(stderr, "\x1b[?25h\x1b[?47l\x1b""8"); - - int *tab_widths = new int[warrior_count + 1]; - tab_widths[0] = 0; - - for (int i = 0; i < warrior_count; ++i) { - int len = warriors[i]->name.size(); - if (len > tab_widths[0]) - tab_widths[0] = len; - tab_widths[i + 1] = len > 5 ? len : 5; - } - - printf(" %*s", tab_widths[0], ""); - for (int j = 0; j < warrior_count; ++j) - printf(" | %*s", tab_widths[j + 1], warriors[j]->name.c_str()); - putchar('\n'); - - putchar('-'); - for (int x = 0; x < tab_widths[0]; ++x) - putchar('-'); - for (int j = 0; j < warrior_count; ++j) { - printf("-+-"); - for (int x = 0; x < tab_widths[j + 1]; ++x) - putchar('-'); - } - printf("-\n"); - - for (int i = 0; i < warrior_count; ++i) { - printf(" %*s", tab_widths[0], warriors[i]->name.c_str()); - for (int j = 0; j < warrior_count; ++j) - if (i == j) - printf(" | %*s", tab_widths[j + 1], "x"); - else - printf(" | %*d", tab_widths[j + 1], wins[i][j]); - putchar('\n'); - } -} diff --git a/tabulator-mpi/main.cpp b/tabulator-mpi/main.cpp deleted file mode 100644 index cd17044..0000000 --- a/tabulator-mpi/main.cpp +++ /dev/null @@ -1,60 +0,0 @@ -#include <lib94/lib94.hpp> -#include <fstream> -#include <cstdio> -#include <mpi.h> - -void head_main(int comm_size, int warrior_count, const lib94::warrior *const *warriors); - -void worker_main(const lib94::warrior *const *warriors); - -const lib94::warrior *load_warrior(const char *file) { - std::ifstream stream(file); - if (!stream) { - fprintf(stderr, "could not open %s\n", file); - exit(1); - } - - std::string source(std::istreambuf_iterator<char>(stream), {}); - - try { - return lib94::compile_warrior(source); - } - - catch (const lib94::compiler_exception &ex) { - fprintf(stderr, "error in %s on line %u: %s\n", file, ex.source_line_number, ex.message.c_str()); - exit(1); - } -} - -int main(int argc, char **argv) { - MPI_Init(&argc, &argv); - - int comm_rank, comm_size; - MPI_Comm_rank(MPI_COMM_WORLD, &comm_rank); - MPI_Comm_size(MPI_COMM_WORLD, &comm_size); - - if (comm_size < 2) { - fprintf(stderr, "at least two processes are required\n"); - return 1; - } - - const lib94::warrior **warriors = new const lib94::warrior *[argc - 1]; - for (int i = 0; i < argc - 1; ++i) - warriors[i] = load_warrior(argv[i + 1]); - - for (int i = 0; i < argc - 1; ++i) - for (int j = i + 1; j < argc - 1; ++j) { - const lib94::warrior *wbuf[2] = {warriors[i], warriors[j]}; - if (!lib94::init_round(wbuf, 2)) { - fprintf(stderr, "warriors do not fit in core\n"); - return 1; - } - } - - if (comm_rank == 0) - head_main(comm_size, argc - 1, warriors); - else - worker_main(warriors); - - MPI_Finalize(); -} diff --git a/tabulator-mpi/mpi.txt b/tabulator-mpi/mpi.txt new file mode 100644 index 0000000..9ee7ff4 --- /dev/null +++ b/tabulator-mpi/mpi.txt @@ -0,0 +1,15 @@ +message tag 0: + head -> worker + four ints: + warrior 1 index + warrior 2 index + start round + end round (exclusive, 0 for exit) + +message tag 1: + worker -> head + four ints: + warrior 1 index + warrior 2 index + w1 wins against w2 + w2 wins against w1 diff --git a/tabulator-mpi/source.cpp b/tabulator-mpi/source.cpp new file mode 100644 index 0000000..ed9c239 --- /dev/null +++ b/tabulator-mpi/source.cpp @@ -0,0 +1,214 @@ +#include <lib94/lib94.hpp> +#include <iostream> +#include <fstream> +#include <sstream> +#include <cstdio> +#include <vector> +#include <mpi.h> + +const int default_rounds_per_chunk = 250; +const int steps_to_tie = 1000000; + +int error(std::string msg, int rank) { + if (rank == 0) { + std::cerr << msg << std::endl; + return 1; + } + return 0; +} + +int main(int argc, char **argv) { + + MPI_Init(&argc, &argv); + + int rank; + int size; + + MPI_Comm_rank(MPI_COMM_WORLD, &rank); + MPI_Comm_size(MPI_COMM_WORLD, &size); + + if (size < 2) + error("this must be run under mpi with at least two processes.", rank); + + std::vector<std::string> filenames = {}; + int rounds_per_chunk = default_rounds_per_chunk; + + for (int i = 1; i < argc; ++i) { + if (atoi(argv[i]) > 0) + rounds_per_chunk = atoi(argv[i]); + else + filenames.push_back(argv[i]); + } + + if (filenames.size() == 0) + return error("no files specified.", rank); + if (filenames.size() == 1) + return error("only one file specified.", rank); + + int count = filenames.size(); + lib94::warrior **warriors = new lib94::warrior *[count]; + for (int i = 0; i < count; ++i) { + std::ifstream file(filenames[i]); + if (!file) + return error("could not open " + filenames[i] + ".", rank); + std::stringstream stream; + stream << file.rdbuf(); + try { + warriors[i] = lib94::compile_warrior(stream.str()); + } + catch (const lib94::compiler_exception &ex) { + return error("could not compile " + filenames[i] + ": " + ex.message + " on line " + std::to_string(ex.source_line_number) + ".", rank); + } + } + + //w1 * count + w2 + int *placements = new int[count * count]; + for (int i = 0; i < count; ++i) + for (int j = 0; j < count; ++j) { + int p = LIB94_CORE_SIZE - warriors[i]->instructions.size() - warriors[j]->instructions.size() + 1; + if (p <= 0) + return error(filenames[i] + " and " + filenames[j] + " do not fit in core together.", rank); + placements[i * count + j] = p; + } + + if (rank == 0) { + + std::cerr << "\x1b""7\x1b[?47h\x1b[2J" << std::flush; + + //w1 * count + w2 + int *wins_array = new int[count * count]; + for (int i = 0; i < count * count; ++i) + wins_array[i] = 0; + + for (int i = 0; i < count; ++i) + for (int j = 0; j < count; ++j) { + if (i == j) + continue; + int rounds = placements[i * count + j]; + for (int r = 0; r < rounds; r += rounds_per_chunk) { + int e = std::min(r + rounds_per_chunk, rounds); + + MPI_Status status; + int buffer[4]; + MPI_Recv(buffer, 4, MPI_INT, MPI_ANY_SOURCE, 1, MPI_COMM_WORLD, &status); + int source = status.MPI_SOURCE; + + wins_array[buffer[0] * count + buffer[1]] += buffer[2]; + wins_array[buffer[1] * count + buffer[0]] += buffer[3]; + + buffer[0] = i; + buffer[1] = j; + buffer[2] = r; + buffer[3] = e; + MPI_Send(buffer, 4, MPI_INT, source, 0, MPI_COMM_WORLD); + + std::cerr << "\x1b[" << source << ";1Hworker " << source << ": " << warriors[i]->name << " vs " << warriors[j]->name << " rounds " << r + 1 << " to " << e << " of " << rounds << ".\x1b[0K" << std::flush; + } + } + + for (int i = 1; i < size; ++i) { + MPI_Status status; + int buffer[4]; + MPI_Recv(buffer, 4, MPI_INT, MPI_ANY_SOURCE, 1, MPI_COMM_WORLD, &status); + int source = status.MPI_SOURCE; + + wins_array[buffer[0] * count + buffer[1]] += buffer[2]; + wins_array[buffer[1] * count + buffer[0]] += buffer[3]; + + buffer[3] = 0; + MPI_Send(buffer, 4, MPI_INT, source, 0, MPI_COMM_WORLD); + std::cerr << "\x1b[" << source << ";1Hworker " << source << ": complete.\x1b[0K" << std::flush; + } + + std::cerr << "\x1b[?47l\x1b""8"; + + int col_width = 13; + for (int i = 0; i < count; ++i) + if ((int)warriors[i]->name.size() > col_width) + col_width = (int)warriors[i]->name.size(); + + printf(" %*s", col_width, ""); + for (int i = 0; i < count; ++i) + printf(" | %*s", col_width, warriors[i]->name.c_str()); + putchar('\n'); + for (int k = 0; k < col_width + 2; ++k) + putchar('-'); + for (int i = 0; i < count; ++i) { + putchar('+'); + for (int k = 0; k < col_width + 2; ++k) + putchar('-'); + } + putchar('\n'); + for (int j = 0; j < count; ++j) { + printf(" %*s", col_width, warriors[j]->name.c_str()); + for (int i = 0; i < count; ++i) + if (i == j) + printf(" | %*s", col_width, ""); + else + printf(" | %5d / %5d%*s", wins_array[i * count + j], placements[i * count + j] * 2, col_width - 13, ""); + putchar('\n'); + } + + } + + else { + + lib94::instruction core_background = { + .op = lib94::DAT, + .mod = lib94::F, + .amode = lib94::DIRECT, + .bmode = lib94::DIRECT, + .anumber = 0, + .bnumber = 0 + }; + + int buffer[4] = { 0, 0, 0, 0 }; + MPI_Send(buffer, 4, MPI_INT, 0, 1, MPI_COMM_WORLD); + + while (true) { + + MPI_Recv(buffer, 4, MPI_INT, 0, 0, MPI_COMM_WORLD, 0); + if (buffer[3] == 0) + break; + + auto w1 = warriors[buffer[0]]; + auto w2 = warriors[buffer[1]]; + int start_offset = w1->instructions.size(); + int w1_wins = 0; + int w2_wins = 0; + + const lib94::warrior *const wlist[2] = { w1, w2 }; + int offsets[2] = {}; + + for (int round = buffer[2]; round < buffer[3]; ++round) { + + offsets[1] = start_offset + round; + lib94::clear_core(core_background); + lib94::init_round(wlist, 2, offsets, false); + + for (int step = 0; step < steps_to_tie; ++step) { + auto lost = lib94::single_step<false>(); + if (lost == w1) { + ++w2_wins; + break; + } + if (lost == w2) { + ++w1_wins; + break; + } + } + + } + + buffer[2] = w1_wins; + buffer[3] = w2_wins; + MPI_Send(buffer, 4, MPI_INT, 0, 1, MPI_COMM_WORLD); + + } + + } + + MPI_Finalize(); + return 0; + +} diff --git a/tabulator-mpi/worker.cpp b/tabulator-mpi/worker.cpp deleted file mode 100644 index 486d107..0000000 --- a/tabulator-mpi/worker.cpp +++ /dev/null @@ -1,51 +0,0 @@ -#include <lib94/lib94.hpp> -#include <cassert> -#include <ctime> -#include <mpi.h> - -#include "constants.hpp" - -static void do_round(const lib94::warrior *w1, const lib94::warrior *w2, int &w1_wins, int& w2_wins) { - const lib94::warrior *ws[2] = {w1, w2}; - - lib94::instruction background = { - .op = lib94::DAT, .mod = lib94::F, - .amode = lib94::DIRECT, .bmode = lib94::DIRECT, - .anumber = 0, .bnumber = 0 - }; - - lib94::clear_core(background); - - assert(lib94::init_round(ws, 2)); - - for (int i = 0; i < STEPS_TO_TIE; ++i) { - const lib94::warrior *result = lib94::single_step<false>(); - if (result == w1) { - ++w2_wins; - return; - } - if (result == w2) { - ++w1_wins; - return; - } - } -} - -void worker_main(const lib94::warrior *const *warriors) { - lib94::seed_prng(time(0)); - int buffer[4] = {-1}; - - while (1) { - MPI_Send(buffer, 4, MPI_INT, 0, 1, MPI_COMM_WORLD); - MPI_Recv(buffer, 4, MPI_INT, 0, 0, MPI_COMM_WORLD, 0); - - if (buffer[0] == -1) - return; - - buffer[2] = 0; - buffer[3] = 0; - - for (int i = 0; i < ROUNDS_PER_CHUNK; ++i) - do_round(warriors[buffer[0]], warriors[buffer[1]], buffer[2], buffer[3]); - } -} |