Author: Robert Hyatt
Date: 11:45:38 11/12/98
Go up one level in this thread
On November 12, 1998 at 10:58:29, Quenton Fyfe wrote: >>>When people from IBM tried to answer him >>>"We have no way to know what *exactly* happened in multi-CPU >>>environment under a real-time conditions", he answered "I don't >>>beleive you. If you'd want to do so, I'm absolutely sure you'll >>>find a way to do that". He could consult *any* specialist in a >>>concurrent programming (IMHO any CS student will be enough) before >>>doing that statement. > >Re the above (posted by Bob unless I've got my quotes in a muddle). I'm a >computer pro, (and ex CS student), and I'd like to have a better understanding >of this issue. > >I've always worked on the assumption that computers are deterministic, and will >give you the same answer time after time, unless there's a hardware fault. This >seems to hold true in practice, even on multi-processor servers and the like. > >Can you explain to me why this isn't true for a machine like Deep Blue ? >Is it a theoretical thing caused by small timing anomalies, or could it actually >choose a different move in practice ? >Approx what % of the time would it choose a different move ? >Does it affect Crafty SMP ? > >Let's be clear here: I *believe* you implicitly - I just want to *understand* > >Thanks > >Quenton Fyfe The problem is caused by the parallel search and the transposition table... If one processor searches down an interesting line and gets back to position X before another one, and has time to store his result in the transposition table, then any other processor coming this way later can use this "interesting" result to help in evaluating a particular branch. But the next time you run this, what guarantees that processor will get back to that point again before the one that used the score the last time? Because the two processors are running the same code, but they handle interrupts on a first-come-first-served basis, and the process behavior varies quite a bit... I've seen this happen *many* times, where we couldn't reproduce a move, because of the parallel search. To further understand this, try your favorite program on some endgame positions like fine#70 and vary the size of the hash table, and try to figure out why a simple change like that lets it solve the position at a shallower depth with some sizes and at a deeper depth at others. That is the second part of the parallel problem. All the cpus are storing into the transposition table... and overwriting things all the time. One time A gets back to position X first and uses that entry, then you run it again and this time B stores in that position overwriting the useful score A used the last time, producing a different score, or a different best move, or a different PV, etc... Hope that helps...
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.