What is an example of a parallel acceleration anomaly? ie. A task that when run over p processors, results in a speedup greater than p.
A:
see http://publishing.eur.nl/ir/repub/asset/1438/eur-few-cs-95-05.pdf, page 11, "5 Anomalies in the real world"
VolkerK
2009-06-25 08:08:12
+2
A:
Consider a matrix algorithm that for the purposes of parallelization is modified in such a way that every computing node is assigned a region of the matrix and only operates on this region.
If with one node the region doesn't fit into cache (because it's the whole matrix) and with multiple nodes it starts fitting into cache (the more nodes the smaller is the region) accessing data becomes much faster and this might (but not always will) result in abnormal acceleration.
sharptooth
2009-06-25 08:09:51
This is often called "superlinear speedup". You expect a speedup of 4 when running on a four processor system but actually you get 5.
Ade Miller
2009-07-09 05:53:11
+2
A:
One area where superlinear speedup occurs is for search problems.
If the solution is found on one of the additional processors then the computation finishes early, and part of the original workload is never executed.
Of course, one could simulate the n processors by parallel threads on one processor and get the same effect, but this is not usually done.
starblue
2009-06-25 09:20:44