25,161
edits
Changes
no edit summary
also known as '''Multithreaded Search''' or [[SMP]] Search, is a way to increase [[Search|search]] speed by using additional [https://en.wikipedia.org/wiki/Central_Processing_Unit processors]. This topic that has been gaining popularity recently with [https://en.wikipedia.org/wiki/Multiprocessing multiprocessor] computers becoming widely available. Utilizing these additional processors is an interesting domain of research, as traversing a search tree is inherently serial. Several approaches have been devised, with the most popular today being [[Young Brothers Wait Concept]] and [[Shared Hash Table]] aka [[Lazy SMP]].
This page gives a brief summary of the different types. SMP algorithms are classified by their [https://en.wikipedia.org/wiki/Scalability scalability] (trend in search speed as the number of processors becomes large) and their [https://en.wikipedia.org/wiki/Speedup speedup] (change in time to complete a search). Typically, programmers use '''scaling''' to mean change in [[Nodes per secondSecond|nodes per second]] (NPS) rates, and speedup to mean change in time to [[Depth|depth]]. Scaling and scalability are thus two different concepts.
=Distributed Search=
