Ah which one of&nbsp;Moshibroda&#39;s papers is that?<div><br></div><div>Joe<br><br><div class="gmail_quote">On Sat, Dec 20, 2008 at 3:57 AM, Giuseppe Ghibò <span dir="ltr">&lt;<a href="mailto:ghibo@mandriva.com">ghibo@mandriva.com</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="Ih2E3d">Timothy Baldridge wrote:<br>
&gt;&gt; I&#39;m not sure how you&#39;d avoid cache misses though. . .we simply have to deal<br>
&gt;&gt; with too much data. &nbsp;About the only thing I can think of is sorting<br>
&gt;&gt; faces/strands (I actually do this in my DSM branch) per tile and using a<br>
&gt;&gt; more optimal render order then simply going over the scanlines. &nbsp;The ray<br>
&gt;&gt; tracing traversal could be made more efficient, but optimizing what the<br>
&gt;&gt; renderer does between could be more difficult.<br>
&gt;&gt; You know I think the CodeAnalyst profiling tool from AMD can measure cache<br>
&gt;&gt; misses, I&#39;ll have to try and figure out how it works.<br>
&gt;&gt;<br>
&gt;<br>
&gt; You cannot avoid all cache misses, but it is possible to avoid many<br>
&gt; cache misses. Modern CPUs load cache lines in 64byte segements. This<br>
&gt; means that if you read one byte from memory the CPU really loads<br>
&gt; 64bytes. Thus, if you can arrange data in such a way that it can be<br>
&gt; read and processed as sequential data, the performance will be greatly<br>
&gt; enhanced.<br>
&gt;<br>
&gt; I wish I could find it, but there is an excellent video on youtube<br>
&gt; from a Google Tech Talk. In the talk the speaker explains these<br>
&gt; caches, and goes to show that reading items from a linked list or<br>
&gt; vector can be (IIRC) up to a order of magnitude slower than reading<br>
&gt; items from an array. That is if the entire set does not lie in memory.<br>
&gt; This is due to the fact that linked lists require allot of jumping<br>
&gt; around in memory, which causes the cache to be come less useful.<br>
&gt;<br>
&gt;<br>
<br>
</div>Well, AFAIK many of such things are also reduced by the compiler.<br>
Backing to cache problems<br>
consider also that most of modern multicore CPU shares even the L2 or<br>
the L3 &nbsp;memory cache (so even if you<br>
have NUMA e.g. in a dual socket, you have two or four cores accessing at<br>
the same bank of memory and not at its own).<br>
But IMHO those problems are even more important in case of<br>
parallelization for multiple threads<br>
It&#39;s worthwhile to read the Moshibroda paper [(and also try yourself to<br>
run the rdarray.c and stream.c tests of the article). You&#39;ll find<br>
some interesting things, such as that most of the modern multicore CPU<br>
which are claimed like to be independent CPUs,<br>
are in most cases, just vector units, which performs good only if used<br>
in such a way... ;-)<br>
<br>
IMHO most of the boost the CUDA or OpenCL implementations apparently<br>
could give are not coming from the parallelization..., but<br>
from the fact that you have a much more powerful invisible &quot;CPU&quot;(GPU)<br>
for certain complex high level tasks (not *every* task, otherwise we would<br>
have to just replace our CPU by GPU and we have done) vs the standard<br>
multipurpose CPU. The important is to identify those tasks<br>
(indeed you have the parallelization also on the CUDA (such as in SLI or<br>
Tesla configuration but that&#39;s another story).<br>
<br>
Regarding the function I cited, we could for instance sort them by<br>
number of calls. In that case we could have:<br>
<br>
&nbsp;7.85 &nbsp; &nbsp; 73.40 &nbsp; &nbsp; 7.58 87591281 &nbsp; &nbsp; 0.00 &nbsp; &nbsp; 0.00 &nbsp;vlr_check_intersect<br>
&nbsp;20.03 &nbsp; &nbsp; 57.26 &nbsp; &nbsp;19.34 40151652 &nbsp; &nbsp; 0.00 &nbsp; &nbsp; 0.00 &nbsp;testnode<br>
 &nbsp;4.70 &nbsp; &nbsp; 82.72 &nbsp; &nbsp; 4.54 36850240 &nbsp; &nbsp; 0.00 &nbsp; &nbsp; 0.00 &nbsp;calc_ocval_ray<br>
 &nbsp;1.77 &nbsp; &nbsp; 90.77 &nbsp; &nbsp; 1.71 26767830 &nbsp; &nbsp; 0.00 &nbsp; &nbsp; 0.00 &nbsp;vlr_face_coords<br>
 &nbsp;4.67 &nbsp; &nbsp; 87.23 &nbsp; &nbsp; 4.51 25437217 &nbsp; &nbsp; 0.00 &nbsp; &nbsp; 0.00 &nbsp;Normalize_d<br>
 &nbsp;8.87 &nbsp; &nbsp; 65.82 &nbsp; &nbsp; 8.56 24297509 &nbsp; &nbsp; 0.00 &nbsp; &nbsp; 0.00<br>
RE_ray_face_intersection<br>
 &nbsp;0.41 &nbsp; &nbsp; 92.05 &nbsp; &nbsp; 0.40 20899588 &nbsp; &nbsp; 0.00 &nbsp; &nbsp; 0.00 &nbsp;vlr_get_transform<br>
&nbsp;39.28 &nbsp; &nbsp; 37.92 &nbsp; &nbsp;37.92 10317691 &nbsp; &nbsp; 0.00 &nbsp; &nbsp; 0.00<br>
RE_ray_tree_intersect_chec<br>
k<br>
 &nbsp;0.17 &nbsp; &nbsp; 94.39 &nbsp; &nbsp; 0.16 10077327 &nbsp; &nbsp; 0.00 &nbsp; &nbsp; 0.00 &nbsp;RE_ray_tree_intersect<br>
 &nbsp;0.28 &nbsp; &nbsp; 93.20 &nbsp; &nbsp; 0.27 &nbsp;3516407 &nbsp; &nbsp; 0.00 &nbsp; &nbsp; 0.00 &nbsp;Mat3MulVecfl<br>
 &nbsp;0.04 &nbsp; &nbsp; 96.04 &nbsp; &nbsp; 0.04 &nbsp; 703745 &nbsp; &nbsp; 0.00 &nbsp; &nbsp; 0.00 &nbsp;RE_vertren_get_rad<br>
<br>
Of course is not very important to optimize (or replace) for instance a<br>
function which is called only ONCE and whose<br>
execution time is 0.01% of the total. So for instance we have the<br>
vlr_check_intersect() is called 87million times and<br>
the testnode() 40million.That should also take already in account &nbsp;the<br>
number reciprocal (or recursive) calls.<br>
You may also do some speculation and &quot;forecasting&quot; about what happens if<br>
that function could be made<br>
10 times faster or 100 times faster. But also looking at the same<br>
functions (or the function they were called most of the<br>
time) you can see whether they can be cud-ized &nbsp;(or CL-ized) or not. Of<br>
course the extreme is to &quot;rewrite&quot; a new<br>
independent CUDA|OpenCL (realtime) engine. But that in a &quot;ideal world&quot;...<br>
<br>
Apart this render is problably not the only task where appartently<br>
CUDA|OpenCL (if) can do the boost..., maybe in the<br>
sequencer could also take a lot of advantages and could be an easier<br>
task (peter?). I remember also that<br>
actually there should be the possibility to access to the H264 codec of<br>
some nvidia card (VPDAU, see<br>
<a href="ftp://download.nvidia.com/XFree86/vdpau/mplayer-vdpau-3076399.README.txt" target="_blank">ftp://download.nvidia.com/XFree86/vdpau/mplayer-vdpau-3076399.README.txt</a>).<br>
Of course this would lead to have things<br>
dependent on the hardware (and in this case a particular brand) and not<br>
fully OSS, but on the other hand we have always the<br>
software fallback.<br>
<br>
Bye<br>
<font color="#888888">Giuseppe.<br>
</font><div><div></div><div class="Wj3C7c"><br>
_______________________________________________<br>
Bf-committers mailing list<br>
<a href="mailto:Bf-committers@blender.org">Bf-committers@blender.org</a><br>
<a href="http://lists.blender.org/mailman/listinfo/bf-committers" target="_blank">http://lists.blender.org/mailman/listinfo/bf-committers</a><br>
</div></div></blockquote></div><br></div>