Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hash table and O(1)

Author: Robert Hyatt

Date: 10:11:55 02/07/06

Go up one level in this thread


On February 07, 2006 at 11:46:47, h.g.muller wrote:

>On February 07, 2006 at 10:51:24, Robert Hyatt wrote:
>
>>Also hardware dependent.  On the Crays, we used 8.  But on a vector machine it
>>takes no longer to access a chain of length 8 than it does to access a single
>>entry, effectively.  For example, on a 2ns T90, it took about 50 clocks to read
>>the first entry, 1 more clock to read the next, etc.  So 57 vs 50 to read 8 vs
>>1.  On the PC this is not going to happen of course.
>
>Actually, on the PC this is very similar. Except that the 1-clock accesses are
>not going to last long, only upto the end of the cache line.

Right.  But on the Cray, this can work for 128 accesses, and the neat thing is,
the 128 addresses do _not_ need to be consecutive in memory.  They can have a
constant stride, or they can be 128 random addresses although some potential
bank conflicts might cause an occasional 6 cycle delay here and there if
multiple addresses go to the same bank.


> Usual SDRAM access
>pattern is as 6-1-1-1 bus clocks (and 2 64-bit words per such clock with DDR),
>so to read the cache line takes 9 bus clocks. With a 133MHz front-side bus
>(advertized as 266MHz because of DDR) on a 1.3 GHz CPU each bus clock equals 10
>CPU clocks. So the cache-line read takes 90 CPU clocks, although the first item
>might already be returned after 60 clocks.

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...



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.