home *** CD-ROM | disk | FTP | other *** search
/ Dream 57 / Amiga_Dream_57.iso / Amiga / Jeux / Reflexion / Crafty-15.19.lha / crafty-15.19 / src / thread.c < prev    next >
C/C++ Source or Header  |  1998-09-13  |  13KB  |  306 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include "chess.h"
  5. #include "data.h"
  6. #include "epdglue.h"
  7.  
  8. /* modified 04/28/98 */
  9. /*
  10. ********************************************************************************
  11. *                                                                              *
  12. *   Thread() is the driver for the threaded parallel search in Crafty.  the    *
  13. *   basic idea is that whenever we notice that one (or more) threads are       *
  14. *   in their idle loop, we drop into thread, from Search(), and begin a new    *
  15. *   parallel search from this node.  this is simply a problem of copying the   *
  16. *   search state space for each thread working at this node, then sending      *
  17. *   everyone off to SearchSMP() to search this node in parallel.               *
  18. *                                                                              *
  19. ********************************************************************************
  20. */
  21. #if defined(SMP)
  22. int Thread(TREE *tree) {
  23.   TREE *block;
  24.   int proc;
  25.   int nblocks=0;
  26. /*
  27.  ----------------------------------------------------------
  28. |                                                          |
  29. |   first, we make sure that there are idle threads. it    |
  30. |   is possible that we get here after they have all been  |
  31. |   claimed by another thread.  in that case we return.    |
  32. |                                                          |
  33.  ----------------------------------------------------------
  34. */
  35.   Lock(lock_smp);
  36.   for (proc=0;proc<max_threads && thread[proc];proc++);
  37.   if (proc == max_threads || tree->stop) {
  38.     UnLock(lock_smp);
  39.     return(0);
  40.   }
  41. # if defined(DEBUGSMP)
  42.   Lock(lock_io);
  43.   Print(128,"thread %d  block %d  ply %d  parallel split\n",
  44.         tree->thread_id,FindBlockID(tree),tree->ply);
  45.   Print(128,"thread %d  threads(s) idle:",tree->thread_id);
  46.   for (proc=0;proc<max_threads;proc++) 
  47.     if (!thread[proc]) Print(128," %d",proc);
  48.   Print(128,"\n");
  49.   UnLock(lock_io);
  50. #endif
  51. /*
  52.  ----------------------------------------------------------
  53. |                                                          |
  54. |   now we start copying the current "state" from this     |
  55. |   thread into new thread blocks so that the threads can  |
  56. |   search this position without interfering with each     |
  57. |   other.  as we copy, we link those blocks as siblings   |
  58. |   of the parent node, and point each sibling back to the |
  59. |   parent so we can unwind this confusion as the threads  |
  60. |   complete their work.                                   |
  61. |                                                          |
  62.  ----------------------------------------------------------
  63. */
  64.   thread[tree->thread_id]=0;
  65.   tree->nprocs=0;
  66.   tree->done=0;
  67.   for (proc=0;proc<max_threads;proc++) {
  68.     tree->siblings[proc]=0;
  69.     if (thread[proc] == 0) {
  70.       block=CopyToSMP(tree);
  71.       if (!block) continue;
  72.       nblocks++;
  73.       tree->siblings[proc]=block;
  74.       block->thread_id=proc;
  75.       block->parent=tree;
  76.       tree->nprocs++;
  77. #if defined(DEBUGSMP)
  78.       Print(128,"thread %d  block %d  allocated at ply=%d\n",
  79.             proc,FindBlockID(block),tree->ply);
  80. #endif
  81.     }
  82.     else tree->siblings[proc]=0;
  83.   }
  84.   tree->search_value=tree->value;
  85.   if (!nblocks) {
  86.     UnLock(lock_smp);
  87.     thread[tree->thread_id]=tree;
  88.     return(0);
  89.   }
  90. /*
  91.  ----------------------------------------------------------
  92. |                                                          |
  93. |   everything is set.  now we can stuff the address of    |
  94. |   the thread blocks into thread[i] so that those idle    |
  95. |   threads can begin the parallel search.                 |
  96. |                                                          |
  97.  ----------------------------------------------------------
  98. */
  99.   for (proc=0;proc<max_threads;proc++)
  100.     if (tree->siblings[proc])
  101.       thread[proc]=tree->siblings[proc];
  102. /*
  103.  ----------------------------------------------------------
  104. |                                                          |
  105. |   after the threads are kicked off to start the parallel |
  106. |   search using the idle threads, this thread has to be   |
  107. |   inserted as well.  however, since it is possible that  |
  108. |   this thread may finish before any or all of the other  |
  109. |   parallel threads, this thread is sent to ThreadWait()  |
  110. |   which will immediately send it to SearchSMP() just     |
  111. |   like the other threads.  going to ThreadWait() allows  |
  112. |   this thread to join others if it runs out of work to   |
  113. |   do.  we do pass ThreadWait() the address of the parent |
  114. |   thread block, so that if this thread becomes idle, and |
  115. |   this thread block shows no threads are still busy,     |
  116. |   then this thread can return to here and then back up   |
  117. |   into the previous ply as it should.  note that no      |
  118. |   other thread can back up to the previous ply since     |
  119. |   their recursive call stacks are not set for that.      |
  120. |                                                          |
  121.  ----------------------------------------------------------
  122. */
  123.   UnLock(lock_smp);
  124.   ThreadWait(tree->thread_id, tree);
  125. # if defined(DEBUGSMP)
  126.   Print(128,"thread %d  block %d  ply %d  parallel join\n",
  127.         tree->thread_id,FindBlockID(tree), tree->ply);
  128. #endif
  129.   return(1);
  130. }
  131.  
  132. /* modified 04/09/98 */
  133. /*
  134. ********************************************************************************
  135. *                                                                              *
  136. *   ThreadInit() is called from the pthread_create() function.  it then calls  *
  137. *   ThreadWait() with the appropriate arguments to park the new threads until  *
  138. *   work is available.                                                         *
  139. *                                                                              *
  140. ********************************************************************************
  141. */
  142. void *ThreadInit(void *tid) {
  143.   ThreadWait((int) tid, (TREE*) 0);
  144.   return(0);
  145. }
  146.  
  147. /* modified 04/26/98 */
  148. /*
  149. ********************************************************************************
  150. *                                                                              *
  151. *   ThreadStop() is called from SearchSMP() when it detects a beta cutoff (or  *
  152. *   fail high) at a node that is being searched in parallel.  we need to stop  *
  153. *   all threads here, and since this threading algorithm is "recursive" it may *
  154. *   be necessary to stop other threads that are helping search this branch     *
  155. *   further down into the tree.  this function simply sets tree->stop to 1,    *
  156. *   which will stop that particular thread instantly and return it to the idle *
  157. *   loop in ThreadWait().                                                      *
  158. *                                                                              *
  159. ********************************************************************************
  160. */
  161. void ThreadStop(TREE *tree) {
  162.   int proc;
  163.   Lock(tree->lock);
  164.   tree->stop=1;
  165.   for (proc=0;proc<max_threads;proc++)
  166.     if (tree->siblings[proc]) ThreadStop(tree->siblings[proc]);
  167.   UnLock(tree->lock);
  168. #if defined(DEBUGSMP)
  169.   Lock(lock_io);
  170.   Print(128,"thread %d (block %d) being stopped by beta cutoff.\n",
  171.         tree->thread_id,FindBlockID(tree));
  172.   UnLock(lock_io);
  173. #endif
  174. }
  175.  
  176. /* modified 04/09/98 */
  177. /*
  178. ********************************************************************************
  179. *                                                                              *
  180. *   ThreadWait() is the idle loop for the N threads that are created at the    *
  181. *   beginning when Crafty searches.  threads are "parked" here waiting on a    *
  182. *   pointer to something they should search (a parameter block built in the    *
  183. *   function Thread() in this case.  when this pointer becomes non-zero, each  *
  184. *   thread "parked" here will immediately call SearchSMP() and begin the       *
  185. *   parallel search as directed.                                               *
  186. *                                                                              *
  187. ********************************************************************************
  188. */
  189. int ThreadWait(int tid, TREE *waiting) {
  190. /*
  191.  ----------------------------------------------------------
  192. |                                                          |
  193. |   the N initial threads enter here and are kept penned   |
  194. |   here forever.  however, once a thread leaves here it   |
  195. |   may well re-enter ThreadWait() from the top while it   |
  196. |   waits for a parallel search to complete.  while it     |
  197. |   waits here it can also join in to help other busy      |
  198. |   threads search their subtrees as well.                 |
  199. |                                                          |
  200.  ----------------------------------------------------------
  201. */
  202.   while (1) {
  203.     Lock(lock_smp);
  204.     cpu_time_used+=ReadClock(cpu)-thread_start_time[tid];
  205.     smp_idle++;
  206.     UnLock(lock_smp);
  207. #if defined(DEBUGSMP)
  208.     Lock(lock_io);
  209.     Print(128,"thread %d now idle (%d procs, %d idle).\n",
  210.           tid,max_threads,smp_idle);
  211.     if (FindBlockID(waiting) >= 0)
  212.       Print(128,"thread %d  waiting on block %d, still %d threads busy there\n",
  213.             tid,FindBlockID(waiting), waiting->nprocs);
  214.     UnLock(lock_io);
  215. #endif
  216. /*
  217.  ----------------------------------------------------------
  218. |                                                          |
  219. |   we can exit if our thread[i] is non-zero, or if we are |
  220. |   waiting on others to finish a block that *we* have to  |
  221. |   return through.  when the busy count on such a block   |
  222. |   hits zero, we return immediately which unwinds the     |
  223. |   search as it should be.                                |
  224. |                                                          |
  225.  ----------------------------------------------------------
  226. */
  227.     while (!thread[tid] && (!waiting || waiting->nprocs));
  228.     Lock(lock_smp);
  229.     if (!thread[tid]) thread[tid]=waiting;
  230. /*
  231.  ----------------------------------------------------------
  232. |                                                          |
  233. |   we either have work to do, or threads we were waiting  |
  234. |   on have finished their work.                           |
  235. |                                                          |
  236.  ----------------------------------------------------------
  237. */
  238. #if defined(DEBUGSMP)
  239.     Lock(lock_io);
  240.     Print(128,"thread %d now has work at block %d.\n",
  241.           tid,FindBlockID(thread[tid]));
  242.     UnLock(lock_io);
  243. #endif
  244.     smp_idle--;
  245. /*
  246.  ----------------------------------------------------------
  247. |                                                          |
  248. |   if we are waiting on a block and the busy count is now |
  249. |   zero, we simply return to finish up the bookkeeping at |
  250. |   that point.                                            |
  251. |                                                          |
  252.  ----------------------------------------------------------
  253. */
  254.     thread_start_time[tid]=ReadClock(cpu);
  255.     UnLock(lock_smp);
  256.     if (thread[tid] == waiting) return(0);
  257.     if (thread[tid] == (TREE*) -1) {
  258.       Lock(lock_io);
  259.       Print(128,"thread %d exiting\n",tid);
  260.       UnLock(lock_io);
  261.       return(0);
  262.     }
  263. /*
  264.  ----------------------------------------------------------
  265. |                                                          |
  266. |   else our thread[i] pointer is non-zero, meaning we     |
  267. |   have been assigned something to search.  off we go,    |
  268. |   into the wild, blue yonder, up and away...  :)         |
  269. |                                                          |
  270.  ----------------------------------------------------------
  271. */
  272.     SearchSMP(thread[tid], thread[tid]->alpha, thread[tid]->beta,
  273.               thread[tid]->value, thread[tid]->wtm, thread[tid]->depth,
  274.               thread[tid]->ply, thread[tid]->threat);
  275.     Lock(lock_smp);
  276.     Lock(thread[tid]->parent->lock);
  277. #if defined(DEBUGSMP)
  278.     Lock(lock_io);
  279.     Print(128,"thread %d  block %d marked free at ply %d\n",
  280.           tid,FindBlockID(thread[tid]),thread[tid]->ply);
  281.     UnLock(lock_io);
  282. #endif
  283.     CopyFromSMP((TREE*)thread[tid]->parent,thread[tid]);
  284.     thread[tid]->parent->nprocs--;
  285. #if defined(DEBUGSMP)
  286.     Lock(lock_io);
  287.     Print(128, "thread %d decremented block %d  nprocs=%d\n",
  288.           tid, FindBlockID(thread[tid]->parent),thread[tid]->parent->nprocs);
  289.     UnLock(lock_io);
  290. #endif
  291.     thread[tid]->parent->siblings[tid]=0;
  292.     UnLock(thread[tid]->parent->lock);
  293. #if defined(DEBUGSMP)
  294.     Lock(lock_io);
  295.     Print(128,"thread %d  block %d  parent %d  nprocs %d exit at ply %d\n",
  296.           tid,FindBlockID(thread[tid]),
  297.           FindBlockID(thread[tid]->parent),
  298.           thread[tid]->parent->nprocs,thread[tid]->ply);
  299.     UnLock(lock_io);
  300. #endif
  301.     thread[tid]=0;
  302.     UnLock(lock_smp);
  303.   }
  304. }
  305. #endif
  306.