thread.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 #if defined(_WIN32)
   5 #  include <process.h>
   6 #else
   7 #  include <sched.h>
   8 #endif
   9 #include "shogi.h"
  10
  11 #if defined(TLP)
  12
  13 #  if defined(_WIN32)
  14 static unsigned int __stdcall start_address( void *arg );
  15 #  else
  16 static void *start_address( void *arg );
  17 #  endif
  18
  19 static tree_t *find_child( void );
  20 static void init_state( const tree_t * restrict parent,
  21                         tree_t * restrict child );
  22 static void copy_state( tree_t * restrict parent,
  23                         const tree_t * restrict child, int value );
  24 static void wait_work( int tid, tree_t *parent );
  25
  26 int
  27 tlp_start( void )
  28 {
  29   int work[ TLP_MAX_THREADS ];
  30   int num;
  31
  32   if ( tlp_num ) { return 1; }
  33
  34   for ( num = 1; num < tlp_max; num++ )
  35     {
  36       work[num] = num;
  37
  38 #  if defined(_WIN32)
  39       if ( ! _beginthreadex( 0, 0, start_address, work+num, 0, 0 ) )
  40         {
  41           str_error = "_beginthreadex() failed.";
  42           return -2;
  43         }
  44 #  else
  45       {
  46         pthread_t pt;
  47         if ( pthread_create( &pt, &pthread_attr, start_address, work+num ) )
  48           {
  49             str_error = "pthread_create() failed.";
  50             return -2;
  51           }
  52       }
  53 #  endif
  54     }
  55   while ( tlp_num +1 < tlp_max ) { tlp_yield(); }
  56
  57   return 1;
  58 }
  59
  60
  61 void
  62 tlp_end( void )
  63 {
  64   tlp_abort = 1;
  65   while ( tlp_num ) { tlp_yield(); }
  66   tlp_abort = 0;
  67 }
  68
  69
  70 int
  71 tlp_split( tree_t * restrict ptree )
  72 {
  73   tree_t *child;
  74   int num, nchild, i;
  75
  76   lock( &tlp_lock );
  77
  78   if ( ! tlp_idle || ptree->tlp_abort )
  79     {
  80       unlock( &tlp_lock );
  81       return 0;
  82     }
  83
  84   tlp_ptrees[ ptree->tlp_id ] = NULL;
  85   ptree->tlp_nsibling         = 0;
  86   nchild                      = 0;
  87   for ( num = 0; num < tlp_max; num++ )
  88     {
  89       if ( tlp_ptrees[num] ) { ptree->tlp_ptrees_sibling[num] = 0; }
  90       else {
  91         child = find_child();
  92         if ( ! child ) { continue; }
  93
  94         nchild += 1;
  95
  96         for ( i=0; i<tlp_max; i++ ) { child->tlp_ptrees_sibling[i] = NULL; }
  97         child->tlp_ptree_parent        = ptree;
  98         child->tlp_id                  = (unsigned char)num;
  99         child->tlp_used                = 1;
 100         child->tlp_abort               = 0;
 101         ptree->tlp_ptrees_sibling[num] = child;
 102         ptree->tlp_nsibling           += 1;
 103         init_state( ptree, child );
 104
 105         tlp_ptrees[num] = child;
 106       }
 107     }
 108
 109   if ( ! nchild )
 110     {
 111       tlp_ptrees[ ptree->tlp_id ] = ptree;
 112       unlock( &tlp_lock );
 113       return 0;
 114     }
 115
 116   tlp_nsplit += 1;
 117   tlp_idle   += 1;
 118
 119   unlock( &tlp_lock );
 120
 121   wait_work( ptree->tlp_id, ptree );
 122
 123   return 1;
 124 }
 125
 126
 127 void
 128 tlp_set_abort( tree_t * restrict ptree )
 129 {
 130   int num;
 131
 132   ptree->tlp_abort = 1;
 133   for ( num = 0; num < tlp_max; num++ )
 134     if ( ptree->tlp_ptrees_sibling[num] )
 135       {
 136         tlp_set_abort( ptree->tlp_ptrees_sibling[num] );
 137       }
 138 }
 139
 140
 141 #if defined(MNJ_LAN)
 142 uint64_t
 143 tlp_count_node( tree_t * restrict ptree )
 144 {
 145   uint64_t uret = ptree->node_searched;
 146   int num;
 147
 148   for ( num = 0; num < tlp_max; num++ )
 149     if ( ptree->tlp_ptrees_sibling[num] )
 150       {
 151         uret += tlp_count_node( ptree->tlp_ptrees_sibling[num] );
 152       }
 153
 154   return uret;
 155 }
 156 #endif
 157
 158
 159 int
 160 tlp_is_descendant( const tree_t * restrict ptree, int slot_ancestor )
 161 {
 162   int slot = (int)ptree->tlp_slot;
 163
 164   for ( ;; ) {
 165     if ( slot == slot_ancestor ) { return 1; }
 166     else if ( ! slot )           { return 0; }
 167     else { slot = tlp_atree_work[slot].tlp_ptree_parent->tlp_slot; }
 168   }
 169 }
 170
 171
 172 int
 173 lock_init( lock_t *plock )
 174 {
 175 #  if defined(_MSC_VER)
 176   *plock = 0;
 177 #  elif defined(__GNUC__) && ( defined(__i386__) || defined(__x86_64__) )
 178   *plock = 0;
 179 #  else
 180   if ( pthread_mutex_init( plock, 0 ) )
 181     {
 182       str_error = "pthread_mutex_init() failed.";
 183       return -1;
 184     }
 185 #  endif
 186   return 1;
 187 }
 188
 189
 190 int
 191 lock_free( lock_t *plock )
 192 {
 193 #  if defined(_MSC_VER)
 194   *plock = 0;
 195 #  elif defined(__GNUC__) && ( defined(__i386__) || defined(__x86_64__) )
 196   *plock = 0;
 197 #  else
 198   if ( pthread_mutex_destroy( plock ) )
 199     {
 200       str_error = "pthread_mutex_destroy() failed.";
 201       return -1;
 202     }
 203 #  endif
 204   return 1;
 205 }
 206
 207
 208 void
 209 unlock( lock_t *plock )
 210 {
 211 #  if defined(_MSC_VER)
 212   *plock = 0;
 213 #  elif defined(__GNUC__) && ( defined(__i386__) || defined(__x86_64__) )
 214   *plock = 0;
 215 #  else
 216   pthread_mutex_unlock( plock );
 217 #  endif
 218 }
 219
 220
 221 void
 222 lock( lock_t *plock )
 223 {
 224 #  if defined(_MSC_VER)
 225   long l;
 226
 227   for ( ;; )
 228     {
 229       l = _InterlockedExchange( (void *)plock, 1 );
 230       if ( ! l ) { return; }
 231       while ( *plock );
 232     }
 233 #  elif defined(__GNUC__) && ( defined(__i386__) || defined(__x86_64__) )
 234   int itemp;
 235
 236   for ( ;; )
 237     {
 238       asm ( "1:   movl     $1,  %1 \n\t"
 239             "     xchgl   (%0), %1 \n\t"
 240             : "=g" (plock), "=r" (itemp) : "0" (plock) );
 241       if ( ! itemp ) { return; }
 242       while ( *plock );
 243     }
 244 #  else
 245   pthread_mutex_lock( plock );
 246 #  endif
 247 }
 248
 249
 250 void
 251 tlp_yield( void )
 252 {
 253 #if defined(_WIN32)
 254   Sleep( 0 );
 255 #else
 256   sched_yield();
 257 #endif
 258 }
 259
 260
 261 #  if defined(_MSC_VER)
 262 static unsigned int __stdcall start_address( void *arg )
 263 #  else
 264 static void *start_address( void *arg )
 265 #endif
 266 {
 267   int tid = *(int *)arg;
 268
 269   tlp_ptrees[tid] = NULL;
 270
 271   lock( &tlp_lock );
 272   Out( "Hi from thread no.%d\n", tid );
 273   tlp_num  += 1;
 274   tlp_idle += 1;
 275   unlock( &tlp_lock );
 276
 277   wait_work( tid, NULL );
 278
 279   lock( &tlp_lock );
 280   Out( "Bye from thread no.%d\n", tid );
 281   tlp_num  -= 1;
 282   tlp_idle -= 1;
 283   unlock( &tlp_lock );
 284
 285   return 0;
 286 }
 287
 288
 289 static void
 290 wait_work( int tid, tree_t *parent )
 291 {
 292   tree_t *slot;
 293   int value;
 294
 295   for ( ;; ) {
 296
 297     for ( ;; ) {
 298       if ( tlp_ptrees[tid] )                  { break; }
 299       if ( parent && ! parent->tlp_nsibling ) { break; }
 300       if ( tlp_abort )                        { return; }
 301
 302       tlp_yield();
 303     }
 304
 305     lock( &tlp_lock );
 306     if ( ! tlp_ptrees[tid] ) { tlp_ptrees[tid] = parent; }
 307     tlp_idle -= 1;
 308     unlock( &tlp_lock );
 309
 310     slot = tlp_ptrees[tid];
 311     if ( slot == parent ) { return; }
 312
 313     value = tlp_search( slot,
 314                         slot->tlp_ptree_parent->tlp_best,
 315                         slot->tlp_ptree_parent->tlp_beta,
 316                         slot->tlp_ptree_parent->tlp_turn,
 317                         slot->tlp_ptree_parent->tlp_depth,
 318                         slot->tlp_ptree_parent->tlp_ply,
 319                         slot->tlp_ptree_parent->tlp_state_node );
 320
 321     lock( &tlp_lock );
 322     copy_state( slot->tlp_ptree_parent, slot, value );
 323     slot->tlp_ptree_parent->tlp_nsibling            -= 1;
 324     slot->tlp_ptree_parent->tlp_ptrees_sibling[tid]  = NULL;
 325     slot->tlp_used   = 0;
 326     tlp_ptrees[tid]  = NULL;
 327     tlp_idle        += 1;
 328     unlock( &tlp_lock);
 329   }
 330 }
 331
 332
 333 static tree_t *
 334 find_child( void )
 335 {
 336   int i;
 337
 338   for ( i = 1; i < TLP_NUM_WORK && tlp_atree_work[i].tlp_used; i++ );
 339   if ( i == TLP_NUM_WORK ) { return NULL; }
 340   if ( i > tlp_nslot ) { tlp_nslot = i; }
 341
 342   return tlp_atree_work + i;
 343 }
 344
 345
 346 static void
 347 init_state( const tree_t * restrict parent, tree_t * restrict child )
 348 {
 349   int i, ply;
 350
 351   child->posi                  = parent->posi;
 352   child->node_searched         = 0;
 353   child->null_pruning_done     = 0;
 354   child->null_pruning_tried    = 0;
 355   child->check_extension_done  = 0;
 356   child->recap_extension_done  = 0;
 357   child->onerp_extension_done  = 0;
 358   child->neval_called          = 0;
 359   child->nquies_called         = 0;
 360   child->nfour_fold_rep        = 0;
 361   child->nperpetual_check      = 0;
 362   child->nsuperior_rep         = 0;
 363   child->nrep_tried            = 0;
 364   child->nreject_tried         = 0;
 365   child->nreject_done          = 0;
 366   child->ntrans_always_hit     = 0;
 367   child->ntrans_prefer_hit     = 0;
 368   child->ntrans_probe          = 0;
 369   child->ntrans_exact          = 0;
 370   child->ntrans_lower          = 0;
 371   child->ntrans_upper          = 0;
 372   child->ntrans_superior_hit   = 0;
 373   child->ntrans_inferior_hit   = 0;
 374   child->fail_high             = 0;
 375   child->fail_high_first       = 0;
 376   ply = parent->tlp_ply;
 377
 378   child->anext_move[ply].value_cap1 = parent->anext_move[ply].value_cap1;
 379   child->anext_move[ply].value_cap2 = parent->anext_move[ply].value_cap2;
 380   child->anext_move[ply].move_cap1  = parent->anext_move[ply].move_cap1;
 381   child->anext_move[ply].move_cap2  = parent->anext_move[ply].move_cap2;
 382
 383   child->move_last[ply]        = child->amove;
 384   child->stand_pat[ply]        = parent->stand_pat[ply];
 385   child->current_move[ply-1]   = parent->current_move[ply-1];
 386   child->nsuc_check[ply-1]     = parent->nsuc_check[ply-1];
 387   child->nsuc_check[ply]       = parent->nsuc_check[ply];
 388
 389   memcpy( child->hist_good,  parent->hist_good,  sizeof(parent->hist_good) );
 390   memcpy( child->hist_tried, parent->hist_tried, sizeof(parent->hist_tried) );
 391
 392   for ( i = 0; i < root_nrep + ply - 1; i++ )
 393     {
 394       child->rep_board_list[i] = parent->rep_board_list[i];
 395       child->rep_hand_list[i]  = parent->rep_hand_list[i];
 396     }
 397   for ( i = ply; i < PLY_MAX; i++ )
 398     {
 399       child->amove_killer[i] = parent->amove_killer[i];
 400       child->killers[i]      = parent->killers[i];
 401     }
 402
 403 }
 404
 405
 406 static void
 407 copy_state( tree_t * restrict parent, const tree_t * restrict child,
 408             int value )
 409 {
 410   int i, ply;
 411
 412   parent->check_extension_done += child->check_extension_done;
 413   parent->recap_extension_done += child->recap_extension_done;
 414
 415   if ( ! child->node_searched ) { return; }
 416
 417   parent->node_searched        += child->node_searched;
 418   parent->null_pruning_done    += child->null_pruning_done;
 419   parent->null_pruning_tried   += child->null_pruning_tried;
 420   parent->onerp_extension_done += child->onerp_extension_done;
 421   parent->neval_called         += child->neval_called;
 422   parent->nquies_called        += child->nquies_called;
 423   parent->nrep_tried           += child->nrep_tried;
 424   parent->nfour_fold_rep       += child->nfour_fold_rep;
 425   parent->nperpetual_check     += child->nperpetual_check;
 426   parent->nsuperior_rep        += child->nsuperior_rep;
 427   parent->nreject_tried        += child->nreject_tried;
 428   parent->nreject_done         += child->nreject_done;
 429   parent->ntrans_always_hit    += child->ntrans_always_hit;
 430   parent->ntrans_prefer_hit    += child->ntrans_prefer_hit;
 431   parent->ntrans_probe         += child->ntrans_probe;
 432   parent->ntrans_exact         += child->ntrans_exact;
 433   parent->ntrans_lower         += child->ntrans_lower;
 434   parent->ntrans_upper         += child->ntrans_upper;
 435   parent->ntrans_superior_hit  += child->ntrans_superior_hit;
 436   parent->ntrans_inferior_hit  += child->ntrans_inferior_hit;
 437   parent->fail_high_first      += child->fail_high_first;
 438   parent->fail_high            += child->fail_high;
 439
 440   if ( child->tlp_abort || value <= parent->tlp_best ) { return; }
 441
 442   ply                       = parent->tlp_ply;
 443   parent->tlp_best          = (short)value;
 444   parent->pv[ply]           = child->pv[ply];
 445   parent->current_move[ply] = child->current_move[ply];
 446
 447   memcpy( parent->hist_tried, child->hist_tried, sizeof(child->hist_tried) );
 448   memcpy( parent->hist_good,  child->hist_good,  sizeof(child->hist_good) );
 449
 450   for ( i = ply; i < PLY_MAX; i++ )
 451     {
 452       parent->amove_killer[i] = child->amove_killer[i];
 453       parent->killers[i]      = child->killers[i];
 454     }
 455 }
 456
 457
 458 #endif /* TLP */