distributed/distributed.h

   1 #ifndef ZZGO_DISTRIBUTED_DISTRIBUTED_H
   2 #define ZZGO_DISTRIBUTED_DISTRIBUTED_H
   3
   4 #include <limits.h>
   5
   6 #include "engine.h"
   7 #include "stats.h"
   8
   9 /* A coord path encodes coordinates from root child to a given node:
  10  * A1->B2->C3 is encoded as coord(A1)<<18 + coord(B2)<<9 + coord(C3)
  11  * for 19x19. In this version the table is not a transposition table
  12  * so A1->B2->C3 and C3->B2->A1 are different.
  13  * The depth is limited to 7 for 19x19 (9 for 9x9) to fit in 64 bits.
  14  * path_t is signed to include pass and resign. */
  15 typedef int64_t path_t;
  16 #define PRIpath PRIx64
  17 #define PATH_T_MAX INT64_MAX
  18
  19 #define hash_mask(bits) ((1<<(bits))-1)
  20
  21 /* parent_path() must never be used if path might be pass or resign. */
  22 #define parent_path(path, board) ((path) >> board_bits2(board))
  23 #define leaf_coord(path, board) ((path) & hash_mask(board_bits2(board)))
  24 #define append_child(path, c, board) (((path) << board_bits2(board)) | (c))
  25
  26
  27 /* For debugging only */
  28 struct hash_counts {
  29         long lookups;
  30         long collisions;
  31         long inserts;
  32         long occupied;
  33 };
  34
  35 /* Find a hash table entry given its coord path from root.
  36  * Set found to false if the entry is empty.
  37  * Abort if the table gets too full (should never happen).
  38  * We use double hashing and coord_path = 0 for unused entries. */
  39 #define find_hash(hash, table, hash_bits, path, found, counts)  \
  40         do { \
  41                 if (DEBUG_MODE) counts.lookups++; \
  42                 int mask = hash_mask(hash_bits); \
  43                 int delta = (int)((path) >> (hash_bits)) | 1; \
  44                 hash = ((int)(path) ^ delta ^ (delta >> (hash_bits))) & mask; \
  45                 path_t cp = (table)[hash].coord_path; \
  46                 found = (cp == path); \
  47                 if (found | !cp) break; \
  48                 int tries = 1 << ((hash_bits)-2); \
  49                 do { \
  50                         if (DEBUG_MODE) counts.collisions++; \
  51                         hash = (hash + delta) & mask; \
  52                         cp = (table)[hash].coord_path; \
  53                         found = (cp == path); \
  54                         if (found | !cp) break; \
  55                 } while (--tries); \
  56                 assert(tries); \
  57         } while (0)
  58
  59
  60 /* Stats exchanged between master and slave. They are always
  61  * incremental values to be added to what was last sent. */
  62 struct incr_stats {
  63         path_t coord_path;
  64         struct move_stats incr;
  65 };
  66
  67 /* A slave machine updates at most 7 (19x19) or 9 (9x9) nodes for each
  68  * update of the root node. If we have at most 20 threads at 1500
  69  * games/s each, a slave machine can do at most 30K games/s. */
  70
  71 /* At 30K games/s a slave can output 270K nodes/s or 4.2 MB/s. The master
  72  * with a 100 MB/s network can thus support at most 24 slaves. */
  73 #define DEFAULT_MAX_SLAVES 24
  74
  75 /* In a 30s move at 270K nodes/s a slave can send and receive at most
  76  * 8.1M nodes so at worst 23 bits are needed for the hash table in the
  77  * slave and for the per-slave hash table in the master. However the
  78  * same nodes are often sent so in practice 21 bits are sufficient.
  79  * Larger hash tables are not desirable because it would take too much
  80  * time to clear them at each move in the master. */
  81 #define DEFAULT_STATS_HBITS 21
  82
  83 /* If we select a cycle of at most 40ms, a slave machine can update at
  84  * most 10K different nodes per cycle. In practice the updates
  85  * are biased so we update fewer nodes. As shorter cyle is preferable
  86  * because the stats are more fresh. The cycle time does not affect
  87  * the number of slaves and the hash table size. */
  88 #define DEFAULT_SHARED_NODES (10*1024)
  89
  90
  91 #define DIST_GAMELEN 1000
  92
  93 #define force_reply(id)    ((id) + DIST_GAMELEN)
  94 #define prevent_reply(id)  ((id) % DIST_GAMELEN)
  95 #define move_number(id)    ((id) % DIST_GAMELEN)
  96 #define reply_disabled(id) ((id) < DIST_GAMELEN)
  97
  98 struct move_stats2 {
  99         struct move_stats u;
 100         struct move_stats amaf;
 101 };
 102
 103 char *path2sstr(path_t path, struct board *b);
 104 struct engine *engine_distributed_init(char *arg, struct board *b);
 105
 106 #endif