parallel parallel for overhead in OpenMP

[mjc]

I have written a function that incurs a tremendous amount of overhead in [OpenMP dispatcher] called by [OpenMP fork] called on behalf of a particular parallel region of mine, according to VTune. That fork accounts for roughly a third of all CPU time in my program. My code is as follows. My intention is to have two parfor loops running concurrently.

#pragma omp parallel
{    
    #pragma omp for
    for( int y =0; y< h; y++)
    {
        // somthing fairly time consuming
    }
    #pragma omp for
    for( int x=0 ;x<w; x++)
    {
        // something else time consuming
    }
}

I already know that the function is worth parallelizing in this way because my whole program performs much more poorly if I comment out the pragmas or insert a num_threads(1) clause. Also, I have tried changing the code to use two consecutive parallel regions each containing one parfor. That version performs significantly worse than the version shown, as well.

The two time-consuming sections of code take approximately the same amounts of time, within about +/-20%. There are other threads executing at the same time. VTune says that there is no oversubscription and in fact CPU usage is well below the target of 12 for my 6-core hyperthreaded i7. Windows Task Manager reports CPU usage around 85%.

I would appreciate any suggestions about what this fork/dispatcher overhead is and how it can be reduced.

[mjc]

I absolutely agree. I think we've done well here, though it would be nice to bring in a consultant at some point.

[lara_h_]

jimdempseyatthecove wrote:

>> It mistakenly designates time spent in my "function x" as overhead attributable to [omp fork]. I don't know why this happens

fork is calling your task, fork portion of time is fork-time less call time of your task and any subsiquent nesting or additional calls in fork that you wish not to attribute to fork.

If you have subroutine foo, that calls subroutine fee then foo's time includes the runtime of the code in foo + the runtime of fee (+ anything it calls).

>> I find that about 7% of all cpu time is tbb spin time

شركة غسيل الخزانات شركة مكافحة الحشرات في الرياض شفط بيارات الرياض نظافة خزانات بالرياض شركة مكافحة حشرات بالرياض شركة شفط بيارات الرياض شفط بيارات بالرياض شفط البيارات الرياض شفط البيارات بالرياض غسيل خزانات المياه شركات نقل العفش شركات نقل العفش بالرياض شركات نقل الأثاث في الرياض تنظيف خزانات شركات نقل أثاث بالرياض افضل شركة مكافحة حشرات افضل شركات رش الحشرات بالرياض شركات نقل اثاث في الرياض غسيل خزانات المياه بالرياض شركات تنظيف خزانات الرياض شركة تنظيف خزانات الرياض تطهير خزانات مياه الشرب تطهير خزانات المياه شركات نقل العفش في الرياض شركات نقل الاثاث بالرياض شركات نقل بالرياض شركات نقل في الرياض شركات نقل العفش الرياض شركات نقل عفش شركات نقل اثاث شركات نقل الاثاث الرياض افضل شركة ابادة حشرات شركات ابادة الحشرات فى الرياض افضل شركة مكافحة الحشرات شركات رش الحشرات شركه الحشرات شركات نقل الموبيليا شركه حشرات في الرياض افضل شركات مكافحة الحشرات في الرياض شركه رش الحشرات في الرياض شركات نقل وتغليف الاثاث شركة تسليك مجارى شركة تسليك المجارى افضل شركة لقتل الحشرات افضل شركة لمكافحة الحشرات الرياض افضل شركه مكافحة الحشرات بالرياض علاج السمنة المرضية عملية الاستئصال الطولي للمعدة بالمنظار بالون المعدة عملية تحويل المعدة بالون التخسيس ربط المعدة بالمنظار عملية تصغير المعدة زيادة عدد المعجبين لصفحة الفيس بوك شركة تنظيف بيوت بالرياض نقل عفش
شركه تغليف اثاث مع الفك والتركيب مكاتب وشركات تنظيف منازل بالرياض شركه تنظيف منازل بالرياض شركه تنظيف واجهات زجاجية شركه تنظيف فلل وقصور شركه مكافحه حشرات شركه مكافحه نمل ابيض شركه رش مبيدات حشرية شركه نظافه واجهات حجريه شركه رش مبيد للبق الفراش شركه تنظيف ستائر بالبخار شركه تنظيف مكاتب وقصور وفلل وشقق افضل شركه مكافحه حشرات افضل شركه نقل أثاث وعفش المنازل شركه تخزين أثاث مع النقل والتغليف والضمان شركه كشف تسربات المياه إلكترونيا تخزين أثاث افضل شركه نظافه بالمملكة مؤسسه نظافه ونقل أثاث بالرياض نقل اثاث
مكافحة حشرات شركة نقل اثاث نقل عفش شركة تنظيف خزانات بالرياض شركة كشف تسربات المياة بالرياض شركة تنظيف فلل بالرياض نقل اثاث تخزين اثاث بالرياض شركة مكافحة حشرات رش المبيدات شركة رش مبيدات بالرياض شركة مكافحة حشرات بالرياض عزل خزانات تنظيف خزانات شركة كشف تسربات كشف تسربات المياه بالرياض شركة تنظيف بالرياض تنظيف فلل بالرياض تنظيف شقق بالرياض شركة تنظيف منازل غسيل مجالس شركة تنظيف بالرياض شركة تنظيف بيوت غسيل خزانات شركة عزل خزانات شركة نظافة فلل بالرياض عزل خزانات بالرياض شركة عزل خزانات بالرياض نظافة منازل افضل شركة نظافة شركة تنظيف بالخرج شركة نظافة منازل نقل اثاث من الرياض تنظيف خزانات المياه افضل شركة تنظيف خزانات شركة غسيل خزانات افضل شركة تنظيف خزانات بالرياض شركة نظافة خزانات شركة نظافة خزانات بالرياض شركة تنظيف خزانات بجدة تنظيف خزانات بجده شركة تنظيف خزانات المياه شركات تنظيف خزانات المياه تنظيف خزانات المياه بالرياض عزل خزانات المياه شركات عزل خزانات بالرياض عزل الخزانات الارضية عزل الخزانات شركه عزل بالرياض شركه عوازل شركات عزل مائي أفضل شركة تنظيف خزانات المياة كشف تسربات الرياض كشف تسربات افضل شركات نقل العفش بالرياض أفضل شركة تنظيف خزانات مياه عزل اسطح كشف تسربات المياه الرياض شركه عزل مائي بالرياض شركة نظافة الخزانات افضل شركات نقل اثاث بالرياض شركات نقل الأثاث غسيل خزانات الرياض افضل شركات نقل اثاث خزانات الفيبر جدة خزانات الفيبر جلاس غسيل خزانات بالرياض كشف تسربات المياه فى الرياض خزانات مياه استانلس خزانات مياه بولى إيثيلين شركة تسليك المجارى بالرياض شركة غسيل خزانات بالرياض شركة لرش الحشرات كشف تسربات المياه بالرياض شركة مبيدات الحشرات في الرياض خزانات مياه فيبر جلاس كشف تسربات المياة شركة تسليك مجارى بالرياض شركة شفط بيارات سليك مجارى بالرياض تسليك مجاري الدمام تسليك مجاري شركة مكافحة الحشرات بالرياض شفط بيارات شركات مكافحة الحشرات بالرياض
افضل شركات التنظيف بالرياض افضل شركات التنظيف في الرياض شركات تنظيف بالرياض شركات تنظيف في الرياض شركة تنظيف بالرياض شركة تنظيف الرياض شركة تنظيف في الرياض افضل شركه تنظيف شركة تنظيف الموكيت شركة تنظيف موكيت بالرياض شركة تنظيف بجدة شركة تنظيف الموكيت بالرياض شركة تنظيف بالدمام شركة تنظيف السجاد شركة تنظيف سجاد شركة تنظيف الاثاث شركة تنظيف اثاث بالرياض شركة تنظيف الاثاث بالرياض شركة نظافة بالرياض شركة تنظيف بيوت شركة تنظيف شقق تنظيف شقق بالرياض شركات مكافحة الحشرات في الرياض شركة تنظيف جدة افضل شركة تنظيف في الرياض نظافة فلل بالرياض شركات نظافة بالرياض شركه نظافه في الرياض شركات نظافة في الرياض شركة نظافة فلل شركة تنظيف فلل تنظيف فلل بالرياض شركة تنظيف منازل شركة تنظيف المنازل شركات تنظيف المنازل شركات تنظيف منازل تنظيف منازل الرياض افضل شركة تنظيف بالرياض شركة تنظيف منازل بالرياض شركة تنظيف المنازل بالرياض شركة تنظيف منازل شركه تنظيف المنزل تنظيف خزانات الرياض شركه تنظيف خزانات بالرياض تنظيف الخزانات الرياض شركات تنظيف خزانات بالرياض شركة تنظيف خزانات تنظيف خزانات بالرياض مؤسسة تنظيف خزانات شركة تنظيف خزانات بالرياض شركة تنظيف بيوت بالرياض شركة تنظيف بيوت شركة تنظيف البيوت شركات تنظيف البيوت ابواب وشبابيك شركات سياحة نقل عفش على مودك شركة نقل اثاث بالرياض نقل الاثاث شركة نقل عفش نقل اثاث بالرياض تخزين اثاث مكافحة حشرات مكافحة حشرات بالرياض رش مبيدات بالرياض عزل خزانات بالرياض تنظيف خزانات بالرياض تنظيف خزانات كشف تسربات كشف تسربات بالرياض شركة التنظيف غسيل السجاد تسليك مجارى تنظيف شقق تنظيف شقق بالرياض تنظيف بيوت تنظيف فلل تنظيف منازل

    }

You are assuming this is overhead, instead this is wait time. The tbb threads cannot do work because the other sections of (serial) code has passed out of the tbb parallel region and has not yet looped back to the tbb parallel region. When your serial code passes through the tbb parallel region (e.g. parallel_for or parallel_invoke, ...) some tbb threads complete before others. These threads then have nothing to do but wait for the remaining tbb threads to complete their slice of for or task before exiting the parallel region, once you exit the parallel region the serial portion of the app can produce more data for the parallel region to work on. More threads waiting == more apparent "overhead" when this is not overhead at all (other than from power consumption viewpoint). What is important to your application is the latency between the start of the parallel region and the completion of (all threads in) the parallel region.

Note now that because you have only one running tbb parallel region at a time, that the threads performing that region have nothing to do after completing their portion of the parallel region and thus enter a spin wait. Had you had two tbb parallel regions running at a time, then the threads finishing up in one of these regions are avalable to complete unassigned tasks of the second parallel region no spinwait time for that/those threads at least until the consume all the tasks of the second (last concurrent) parallel region..

What is your fps for

Serial (1fps)
1 TBB thread (should be less than 1fps)
2 TBB threads
...
HW # TBB threads

Look at the effects on fps, not a false metric of spin-wait time.

Now then, spin-wait time is important. You can use it as an indicator of "free time", and not as an indication of "lost time" or "overhead". Your job then is to craft a way to use this free time. This generally means increasing the tasking, as was done with the parallel_invoke(parallel_for, parallel_for).

Now lets further inspect the 7% "overhead" in spin-wait. Is this a true picture of unutilized CPU time? No, you also should look at the system idel time (or aggrigate time not spent computing by all threads in your app). This is an indicator of available processing resources you can apply to your problem.

>>so I need to overlap processing of one frame with others

This is typically performed using double-buffering or n-buffering (n=1,2,3,4...), or ring buffering. You should also look at using parallel_pipeline.

With either n-buffering or parallel_pipeline you can select the number of buffers (1, 2, 3, ...). Now you can tune for latency or throughput.

Latency reduction techniques can be imployed such as a ring buffer. Such that as a buffer is filled on one end it is concurrently processed and emptied at the other end. When setup as a ring buffer, the buffer becomes a stream device between the producer(s) on one end and the consumer(s) on the other end. If necessary, multiple ring buffers can be employed.

Jim Dempsey

At this point, my situation is a little different from what I first described. Jim is correct that my pragma omp parallel is within a loop. On the other hand, I am absolutely sure that the body of the parallelized iteration is very time consuming. Performance goes way down if I serialize it; and VTune confirms that a ton of time is in code that it calls. I am now looking at code like the following.

for ( int k=0; k< 3; k++)
{
    #pragma omp parallel sections // num_threads(2)
    {
        #pragma omp section
        {
            tbb::parallel_for( myBigSlowFunctor )
        }

        #pragma  omp section
        {
            tbb::parallel_for( myBigSlowFunctor )
        }
}

But I haven't told you enough yet. If you don't mind reading, here is an overview of what's going on.

We have multiple levels of parallelization in this video-processing application. At the top level, there is a custom-made pool of 4 threads, each of which processes one frame at a time. This gives a lot of speedup compared to single-threaded runs, because each frame requires a lot of processing and very little synchronization between one frame and another. I have experimented with different numbers of frame-level threads. Performance increases with larger numbers of threads up to 4 or more. Task manager CPU utilization is around 90% but VTune’s cpu usage histogram makes it look like usage is much less than that, despite thread concurrency being very high.

Within each frame-processing thread there are about 5 openmp parallel regions. Each of them specifies just two tasks (loop iterations or sections). In addition, this function calls some functions that in turn invoke some parallelism. Admittedly, this sounds like it could be too much but I figure it’s OK to start by exposing “too much” parallelism and then tune to a realistic range.

The most interesting part of the call-graph is where the frame-processing thread calls a computing function which has the two omp sections outined above. The functor ultimately calls the set_image_p function that takes so much time according to VTune. It is also the main use of tbb in this application, so it is presumably responsible for a large amount of the reported spin time. If I use serial code in place of the tbb parfor, throughput is much lower. If I remove the omp parallel sectioning around it, throughput goes down significantly but not dramatically. I do have a critical section around the computing function. This helps by preventing the pairs of big tbb parfors from competing with each other. They do compete with other work for other frames, though.

Vtune summary output is attached. Obviously, the cpu (a 6-core i7-970) looks to be oversubsubscribed. I have tried different settings for omp_set_num_threads and tbb::task_scheduler_init. Kmp_set_blocktime(0) helped. I feel like I’m missing a methodology for improving throughput by reducing overhead.