In article <7e**********************************@k37g2000hsf. googlegroups.com>,
gianluca <ge*******@gmail.comwrote:
>I have to build a function for pairwise comparation of matrix
elements. The most logical approach is with several for(;;) but my
matrix is very large (5000 x 5000) elements (is a raster geographical
map) and required a huge machine resource. Is there a more efficient
algorithm for my pourpuse.
Is your matrix sparse or dense? Are all elements to be compared to
all other elements?
If all elements are to be compared to all other elements, then
you can probably achieve significant speed-ups by processing
the data in "blocks", paying attention to the amount of data that
will fit into your processor's cache, and paying attention to
cache line conflicts. Unfortunately there is no portable C method of
determining processor cache or cache-line information (cache is
a hardware detail that doesn't affect the semantics of C), so
you will have to make your routine somewhat system dependant, at
least to the point of determining those parameters (but then
you could have a block-processing routine that did its best within
the supplied parameters.)
Note: when you have a choice in the matter, ensure that your output
matrix does not have cache line conflicts with your input matrix.
Some compilers, given the appropriate system-specific options, will
automatically put in padding to promote good cache performance.
Block and cache aware routines will usually be more complex, and will
usually not *obviously* be more efficient. If you have to do 25 million
comparisons then you have to do 25 million comparisons, and efficiency
gains are made by working with the hardware efficiency limitations and
with working with processor instruction pipelines and other
system and hardware specific techniques.
--
"And that's the way it is." -- Walter Cronkite
