Two algorithms that give me different timing results on two different machines
3 次查看(过去 30 天)
显示 更早的评论
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 个评论
Walter Roberson
2013-3-11
Different numbers of cores? Different amounts of available memory? Different MATLAB versions? Different operating systems? 32 bit versus 64 bit?
Jan
2013-3-11
Using the profiler to find the commands, which cause the differences, would be a useful strategy. Then post the relevant lines.
回答(2 个)
Matt J
2013-3-11
编辑:Matt J
2013-3-11
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 个评论
Walter Roberson
2013-3-11
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
2013-3-11
编辑:Matt J
2013-3-11
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
2013-3-11
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 个评论
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Logical 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!