📄 global hash table.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0050)http://www.npac.syr.edu/copywrite/pcw/node352.html -->
<!Converted with LaTeX2HTML 0.7a2 (Fri Dec 2 1994) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds ><HTML><HEAD><TITLE>Global Hash Table</TITLE>
<META content="text/html; charset=hz-gb-2312" http-equiv=Content-Type>
<META content="MSHTML 5.00.2614.3500" name=GENERATOR></HEAD>
<BODY>
<META name=description value=" Global Hash Table">
<META name=keywords value="BOOK">
<META name=resource-type value="document">
<META name=distribution value="global">
<P><BR>
<HR>
<A href="http://www.npac.syr.edu/copywrite/pcw/node353.html"
name=tex2html7089><IMG align=bottom alt=next
src="Global Hash Table.files/next_motif.gif"></A> <A
href="http://www.npac.syr.edu/copywrite/pcw/node350.html" name=tex2html7087><IMG
align=bottom alt=up src="Global Hash Table.files/up_motif.gif"></A> <A
href="http://www.npac.syr.edu/copywrite/pcw/node351.html" name=tex2html7083><IMG
align=bottom alt=previous src="Global Hash Table.files/previous_motif.gif"></A>
<A href="http://www.npac.syr.edu/copywrite/pcw/node1.html"
name=tex2html7091><IMG align=bottom alt=contents
src="Global Hash Table.files/contents_motif.gif"></A> <A
href="http://www.npac.syr.edu/copywrite/pcw/node484.html" name=tex2html7092><IMG
align=bottom alt=index src="Global Hash Table.files/index_motif.gif"></A>
<BR><B>Next:</B> <A href="http://www.npac.syr.edu/copywrite/pcw/node353.html"
name=tex2html7090>14.3.4 Load Balancing</A> <B>Up:</B> <A
href="http://www.npac.syr.edu/copywrite/pcw/node350.html"
name=tex2html7088>14.3.3 Parallel Alpha-Beta Pruning</A> <B>Previous:</B> <A
href="http://www.npac.syr.edu/copywrite/pcw/node351.html"
name=tex2html7084>Analysis of Alpha-Beta </A><BR>
<HR>
<P>
<H3><A name=SECTION001633200000000000000>Global Hash Table</A></H3>
<P>The central role of the hash table in providing refutations and telling the
program when to go parallel makes it clear that the hash table must be shared
among all processors. Local hash tables would not work since the complex,
dynamically changing organization of processors makes it very unlikely that a
processor will search the same region of the tree in two successive levels of
iterative deepening. A shared table is expensive on a distributed-memory
machine, but in this case it is worth it.
<P>Each processor contributes an equal amount of memory to the shared hash
table. The global hash function maps each chess position to a global slot number
consisting of a processor ID and a local slot number. Remote memory is accessed
by sending a message to the processor in which the desired memory resides. To
insure prompt service to remote memory requests, these messages must cause an
interrupt on arrival. The VERTEX system does not support this feature, so we
implemented a system called <EM>generalized signals</EM> [<A
href="http://www.npac.syr.edu/copywrite/pcw/node483.html#Felten88b">Felten:88b</A>],
which allows interrupt-time servicing of some messages without disturbing the
running program.
<P>When a processor wants to read a remote slot in the hash table, it sends a
message containing the local slot number and the 64-bit collision check to the
appropriate processor. When this message arrives the receiving processor is
interrupted; it updates the staleness flag and sends the contents of the desired
slot back to the requesting processor. The processor which made the request
waits until the answer comes back before proceeding.
<P>Remote writing is a bit more complicated due to the possibility of
collisions. As explained previously, collisions are resolved by a priority
scheme; the decision of whether to overwrite the previous entry must be made by
the processor which actually owns the relevant memory. Remote writing is
accomplished by sending a message containing the new hash table entry to the
appropriate processor. This message causes an interrupt on arrival and the
receiver examines the new data and the old contents of that hash table slot and
decides which one to keep.
<P>Since hash table data is shared among many processors, any access to the hash
table must be an atomic operation. This means we must guarantee that two
accesses to the same slot cannot happen at the same time. The generalized
signals system provides a critical-section protection feature which can be used
to queue remote read and write requests while an access is in progress.
<P>Experiments show that the overhead associated with the global hash table is
only a few percent, which is a small price to pay for accurate move ordering.
<P><BR>
<HR>
<A href="http://www.npac.syr.edu/copywrite/pcw/node353.html"
name=tex2html7089><IMG align=bottom alt=next
src="Global Hash Table.files/next_motif.gif"></A> <A
href="http://www.npac.syr.edu/copywrite/pcw/node350.html" name=tex2html7087><IMG
align=bottom alt=up src="Global Hash Table.files/up_motif.gif"></A> <A
href="http://www.npac.syr.edu/copywrite/pcw/node351.html" name=tex2html7083><IMG
align=bottom alt=previous src="Global Hash Table.files/previous_motif.gif"></A>
<A href="http://www.npac.syr.edu/copywrite/pcw/node1.html"
name=tex2html7091><IMG align=bottom alt=contents
src="Global Hash Table.files/contents_motif.gif"></A> <A
href="http://www.npac.syr.edu/copywrite/pcw/node484.html" name=tex2html7092><IMG
align=bottom alt=index src="Global Hash Table.files/index_motif.gif"></A>
<BR><B>Next:</B> <A href="http://www.npac.syr.edu/copywrite/pcw/node353.html"
name=tex2html7090>14.3.4 Load Balancing</A> <B>Up:</B> <A
href="http://www.npac.syr.edu/copywrite/pcw/node350.html"
name=tex2html7088>14.3.3 Parallel Alpha-Beta Pruning</A> <B>Previous:</B> <A
href="http://www.npac.syr.edu/copywrite/pcw/node351.html"
name=tex2html7084>Analysis of Alpha-Beta </A><BR>
<HR>
<P><BR>
<HR>
<P>
<ADDRESS><I>Guy Robinson <BR>Wed Mar 1 10:19:35 EST 1995</I>
</ADDRESS></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -