Two algorithms that give me different timing results on two different machines
3 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
What could possibly be going on?
I ran algorithm 1 and 2 in Matlab on one machine a few thousand times. Algorithm 1 always dominates algorithm 2 in terms of speed.
I then run it again on another machine a few thousand times but only 40-50% of the times do Algorithm 1 dominates algorithm 2's speed.
I can't seem to explain it. The results are different. How do I really know which algorithm's speed is better?
2 comentarios
Walter Roberson
el 11 de Mzo. de 2013
Different numbers of cores? Different amounts of available memory? Different MATLAB versions? Different operating systems? 32 bit versus 64 bit?
Jan
el 11 de Mzo. de 2013
Using the profiler to find the commands, which cause the differences, would be a useful strategy. Then post the relevant lines.
Respuestas (2)
Matt J
el 11 de Mzo. de 2013
Editada: Matt J
el 11 de Mzo. de 2013
For example ... if Algorithm 2 uses more/larger basic linear algebra operations than Algorithm 1, then Algorithm 2 might start to overtake Algorithm 1 on a machine with more cores. MATLAB tries to multi-thread matrix manipulation as optimally as it can, and the resulting acceleration of those operations is greater when more parallel computing resources are available.
How do I really know which algorithm's speed is better?
This is always a hardware-dependent question.
3 comentarios
Walter Roberson
el 11 de Mzo. de 2013
There are algorithms for doing parallel sorts that are better complexity than the best non-parallel sort can do. But if you try to use that parallel sort algorithm on a system that does not have multiple processors, the result is going to be worse than the non-parallel sort.
Matt J
el 11 de Mzo. de 2013
Editada: Matt J
el 11 de Mzo. de 2013
Now if I asked which algorithm has better complexity, that shouldn't be a hardware dependent question
If by complexity, you mean, number of operations in relation to the data size O(N), O(N^2), etc... then it's true that that is not a hardware dependent question. However, the number of operations does not always correlate with speed, especially when parallel computing is in play.
Even without parallel computing, memory access patterns can influence speed as much or more than number of operations performed. If memory is accessed in a highly sequential matter, for example, it will be faster than an algorithm that jumps randomly to different locations. Differences in caching can also affect memory access effort. The latter, I think, is the more likely thing to vary machine-to-machine.
Jan
el 11 de Mzo. de 2013
When doubles are processed by the floating point unit of a Intel CPU, NaNs cause a significantly slower execution time. This does not happen for the SSE unit or the floating point unit of AMD processors. So depending on the hardware storing the information of bad values by NaNs or a dedicated logical mask can be more efficient.
Multi-threading can have strange effects for simple operations like the SUM already: For more than 89900 elements, multi-threading is applied. Then the limited precision will cause different results depending on the number of cores. And because summing is not numerically stable, the effects can be large. Now imagine, an iterative method depends on the result of a dot-product. Now rounding errors depend on the hardware and can influence the convergence systematically. To control such effects, a very exhaustive debugging is required.
0 comentarios
Ver también
Categorías
Más información sobre Logical en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!