<div class="gmail_quote">On Sun, Feb 26, 2012 at 04:07, Gerard Gorman <span dir="ltr"><<a href="mailto:g.gorman@imperial.ac.uk">g.gorman@imperial.ac.uk</a>></span> wrote: <blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="im">
<br>
</div>I agree that different data sizes might require different approaches.<br>
One might consider this as part of an autotuning framework for PETSc.<br>
<br>
The cost of spawning threads is generally minimised through the use of<br>
thread pools typically used by OpenMP - i.e. you only have a one time<br>
cost associated with forking and joining threads. However, even with a<br>
pool there are still some overheads (e.g. scheduling chunks) which will<br>
effect you for small data sizes. I have not measured this myself<br>
(appending to the todo list) but it is frequently discussed, e.g.<br>
<a href="http://software.intel.com/en-us/articles/performance-obstacles-for-threading-how-do-they-affect-openmp-code/" target="_blank">http://software.intel.com/en-us/articles/performance-obstacles-for-threading-how-do-they-affect-openmp-code/</a><br>

<a href="http://www2.fz-juelich.de/jsc/datapool/scalasca/scalasca_patterns-1.3.html" target="_blank">http://www2.fz-juelich.de/jsc/datapool/scalasca/scalasca_patterns-1.3.html</a></blockquote><div><br></div><div>Any threading model of this sort should be implemented with thread pools, but that's not what I'm concerned about. Just opening and closing a parallel region costs a significant amount. With two threads, I see it taking 1000 to 2000 cycles which is a sizeable fraction of a microsecond. Note that 1 microsecond is a typical latency of a network, so this is really a meaningful quantity. If I use OpenMP for AXPY, the crossover point seems to be around 3000 double precision elements. This would be a typical subdomain size after one coarsening of a 100k dof 3D subdomain using a smoothed aggregation multigrid. This is smack in the middle of a typical subdomain size for implicit methods, so in a very common scenario, it doesn't make sense to use OpenMP threads for any vector operations on any level except for the finest. Note that this is still without NUMA effects which tend to make threads worse, unless allocation can be done so there is no contention.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">I think you mean thread-pools, as are used for OpenMP. The same thing is<br>
done for pthreads (e.g.<br>
<a href="http://www.hlnum.org/english/projects/tools/threadpool/doc.html" target="_blank">http://www.hlnum.org/english/projects/tools/threadpool/doc.html</a>) and others.<br></blockquote><div><br></div><div>No, I mean</div>
<div><br></div><div>int main(int argc,char **argv) {</div><div>#pragma omp parallel</div><div>  {</div><div>  // your entire program is threaded, most allocations are independent</div><div>  // control-flow is computed redundantly, reductions/synchronization are explicit</div>
<div>  }</div><div>  return 0;</div><div>}</div><div><br></div><div>OpenMP isn't currently very well equipped to be used this way, but I think this a better model for fine-grained parallelism than making the program serial by default and opening a parallel region when you decide there is enough work. The current solution is more pragmatic, but I don't see it scaling nearly as well.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
</div>We are using static schedules. This means that the chunk size =<br>
array_length/nthreads. Therefore, we can have bad page/thread locality<br>
at the start (ie malloc may have returned a pointer to the middle of a<br>
page already faulted and this is not necessary on the same memory node<br>
that thread 0 is located), and where chunks boundaries don't align with<br>
page boundaries, where the successive threads id's are on different<br>
memory nodes. I've attached a figure to fill in deficiencies in my<br>
explanation - it is based on an Intel Westmere with two sockets (and two<br>
memory nodes), 6 cores per socket, an array of 10000 doubles, and page<br>
sizes of 4096 bytes.<br></blockquote><div><br></div><div>Thanks, that's all I was asking. If we could do independent allocation (as in my extreme example above) or even simple padding, we could ensure that each thread actually gets a local page.</div>
<div>  </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
You can control the page fault at the start of the array by replacing<br>
malloc with posix_memalign, where the alignment is the page size. For<br>
the pages that stride chunks that have been allocated to threads on<br>
different sockets...you'd have to use gaps in your arrays or something<br>
similar to resolve this. I would do the first of these because it's<br>
easy. I don't know an easy way to implement the second so I'd be<br>
inclined that inefficiency unless profiling indicates it cannot be ignored.<br></blockquote><div><br></div><div>You can change the default alignment (used inside PetscMallocAlign()) by configuring --with-memalign=4096 (pull petsc-dev to not error for such huge values). Note that this will also use a huge alignment for strings and structures, so it'll be quite wasteful. But it's a cheap way to experiment.</div>
<div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">It's on Barry's favourite collaborative software development site of<br>
course ;-)<br>
<br>
<a href="https://bitbucket.org/wence/petsc-dev-omp/overview" target="_blank">https://bitbucket.org/wence/petsc-dev-omp/overview</a></blockquote><div><br></div><div>Aha, thanks.</div></div>