Editing Speedup (section)

==Super-linear speedup==
Sometimes a speedup of more than ''A'' when using ''A'' processors is observed in [[parallel computing]], which is called ''super-linear speedup''. Super-linear speedup rarely happens and often confuses beginners, who believe the theoretical maximum speedup should be ''A'' when ''A'' processors are used.

One possible reason for super-linear speedup in low-level computations is the [[CPU cache|cache effect]] resulting from the different [[Memory hierarchy|memory hierarchies]] of a modern computer: in parallel computing, not only do the numbers of processors change, but so does the size of accumulated caches from different processors. With the larger accumulated cache size, more or even all of the [[working set]] can fit into caches and the memory access time reduces dramatically, which causes the extra speedup in addition to that from the actual computation.<ref>{{cite conference
| last1 = Benzi
| first1 = John
| last2 = Damodaran 
| first2 = M.
| title = Parallel Three Dimensional Direct Simulation Monte Carlo for Simulating Micro Flows
| conference = Parallel Computational Fluid Dynamics
| book-title = Parallel Computational Fluid Dynamics 2007: Implementations and Experiences on Large Scale and Grid Computing
| publisher = Springer
| url = https://books.google.com/books?id=MOiZ2NJ8pywC
| year = 2007
| page = 95
| access-date = 2013-03-21
}}</ref>

An analogous situation occurs when searching large datasets, such as the genomic data searched by [[BLAST (biotechnology)|BLAST]] implementations. There the accumulated RAM from each of the nodes in a cluster enables the dataset to move from disk into RAM thereby drastically reducing the time required by e.g. mpiBLAST to search it.<ref>{{Cite web| title=Green Destiny + mpiBLAST = Bioinfomagic | url=http://people.cs.vt.edu/~feng/presentations/030903-ParCo.pdf | archive-url=https://web.archive.org/web/20080221173824/http://people.cs.vt.edu/~feng/presentations/030903-ParCo.pdf | archive-date=2008-02-21}}</ref>

Super-linear speedups can also occur when performing [[backtracking]] in parallel: an exception in one thread can cause several other threads to backtrack early, before they reach the exception themselves.<ref>{{Cite book|last=Speckenmeyer|first=Ewald|title=Supercomputing |chapter=Superlinear speedup for parallel backtracking |series=Lecture Notes in Computer Science |date=1988 |volume=297|pages=985–993|doi=10.1007/3-540-18991-2_58|isbn=978-3-540-18991-6}}</ref>

Super-linear speedups can also occur in parallel implementations of branch-and-bound for optimization:<ref>{{cite web|url=http://mat.tepper.cmu.edu/blog/?p=534#comment-3029|title=Gurobi versus CPLEX benchmarks|date=29 January 2009|website=cmu.edu|access-date=23 April 2018}}</ref> the processing of one node by one processor may affect the work other processors need to do for the other nodes.