Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hash table and O(1)

Author: Robert Hyatt

Date: 13:33:58 02/07/06

Go up one level in this thread


On February 07, 2006 at 16:11:27, h.g.muller wrote:

>On February 07, 2006 at 13:11:55, Robert Hyatt wrote:
>
>>Also on the PC this is a variable latency problem, since the first word you ask
>>for might be the last word of a cache line, in which case the next word will
>>have another large delay built in..  The cray doesn't do "cache lines" for
>>vector operations...
>
>I know, the Cray was a great machine (even though current PCs can beat the old
>Y/MP by a factor 10, if you program them carefully).
>
>But you underestimate the Pentium and its brethren: they load a cache line in
>the smart (or at least: non-dumb) order, starting with the word that is first
>needed (at the address where the original cache miss occured). Even if it is the
>last word in the cache line. For a 4-word burst due to a miss on address 12 the
>order would be 12,8,4,0. The address bits toggle in the usual binary counting
>order, but start out at a funny value (probably by xoring the requested address
>with a normal counter internally).

I understand that.  My point was that you might incur two cache miss penalties
since a single hash entry can span over two cache lines.  That's a big hit.  The
net effect is not quite the same as the Cray.

BTW, for comparison, that older T90 could do two 16 byte memory reads and one 16
byte memory write per processor per clock cycle.  That is 32 * 48 * 500000000
bytes per second (2ns system clock).  And it could sustain that for reasonable
reference patterns due to so many independent memory banks being available.

Try that on your local PC.  :)



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.