From eab56a7f006f5a73c2b7eb984b2aae72bc898212 Mon Sep 17 00:00:00 2001 From: Benji Dial Date: Sat, 25 Nov 2023 18:15:30 -0500 Subject: allow more control over init_round, rewrite tabulator and make it run every possible separation and turn order exactly once --- tabulator-mpi/constants.hpp | 3 - tabulator-mpi/head.cpp | 112 ----------------------- tabulator-mpi/main.cpp | 60 ------------- tabulator-mpi/mpi.txt | 15 ++++ tabulator-mpi/source.cpp | 214 ++++++++++++++++++++++++++++++++++++++++++++ tabulator-mpi/worker.cpp | 51 ----------- 6 files changed, 229 insertions(+), 226 deletions(-) delete mode 100644 tabulator-mpi/constants.hpp delete mode 100644 tabulator-mpi/head.cpp delete mode 100644 tabulator-mpi/main.cpp create mode 100644 tabulator-mpi/mpi.txt create mode 100644 tabulator-mpi/source.cpp delete mode 100644 tabulator-mpi/worker.cpp (limited to 'tabulator-mpi') 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 -#include -#include - -#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 -#include -#include -#include - -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(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 +#include +#include +#include +#include +#include +#include + +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 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(); + 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 -#include -#include -#include - -#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(); - 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]); - } -} -- cgit v1.2.3