_kmp huge overhead and spin time for unkown calls in OpenMP?

Question

I'm using Intel VTune to analyze my parallel application.

As you can see, there is an huge Spin Time at the beginning of the application (represented as the orange section on the left side):

It's more than 28% of the application durations (which is roughly 0.14 seconds)!

As you can see, these functions are _clone, start_thread, _kmp_launch_thread and _kmp_fork_barrier and they look like OpenMP internals or system calls, but it's not specified where these fucntion are called from.

In addition, if we zoom at the beginning of this section, we can notice a region instantiation, represented by the selected region:

However, I never call initInterTab2d and I have no idea if it's called by some of the labraries that I'm using (especially OpenCV).

Digging deeply and running an Advanced Hotspot analysis I found a little bit more about the firsts unkown functions:

And exaplanding tthe Function/Call Stack tab:

But again, I can't really understand why these functions, why they take so long and why only the master thread works during them, while the others are in a "barrier" state.

If you're interested, this is the link to part of the code.

Notice that I have only one #pragma omp parallel region, which is the selected section of this image (on the right side):

The code structure is the following:

1. Compute some serial, non parallelizable stuff. In particular, compute a chain of blurs, which is represented by gaussianBlur (included at the end of the code). cv::GaussianBlur is an OpenCV function which exploits IPP.
2. Start the parallel region, where 3 parallel for are used
3. The first one calls hessianResponse
4. A single thread add the results to a shared vector.
5. The second parallel region localfindAffineShapeArgs generates the data used by the next parallel region. The two regions can't be merged because of load imbalance.
6. The third region generates the final result in a balanced way.
7. Note: according to the lock analysis of VTune, the critical and barrier sections are not the reason of spinning.

This is the main function of the code:

void HessianDetector::detectPyramidKeypoints(const Mat &image, cv::Mat &descriptors, const AffineShapeParams ap, const SIFTDescriptorParams sp)
{
   float curSigma = 0.5f;
   float pixelDistance = 1.0f;
   cv::Mat octaveLayer;

   // prepare first octave input image
   if (par.initialSigma > curSigma)
   {
      float sigma = sqrt(par.initialSigma * par.initialSigma - curSigma * curSigma);
      octaveLayer = gaussianBlur(image, sigma);
   }

   // while there is sufficient size of image
   int minSize = 2 * par.border + 2;
   int rowsCounter = image.rows;
   int colsCounter = image.cols;
   float sigmaStep = pow(2.0f, 1.0f / (float) par.numberOfScales);
   int levels = 0;
   while (rowsCounter > minSize && colsCounter > minSize){
       rowsCounter/=2; colsCounter/=2;
       levels++;
   }
   int scaleCycles = par.numberOfScales+2;

   //-------------------Shared Vectors-------------------
    std::vector<Mat> blurs (scaleCycles*levels+1, Mat());
    std::vector<Mat> hessResps (levels*scaleCycles+2); //+2 because high needs an extra one
    std::vector<Wrapper> localWrappers;
    std::vector<FindAffineShapeArgs> findAffineShapeArgs;
    localWrappers.reserve(levels*(scaleCycles-2));
    vector<float> pixelDistances;
    pixelDistances.reserve(levels);

    for(int i=0; i<levels; i++){
       pixelDistances.push_back(pixelDistance);
       pixelDistance*=2;
    }

   //compute blurs at all layers (not parallelizable)
   for(int i=0; i<levels; i++){
       blurs[i*scaleCycles+1] = octaveLayer.clone();
       for (int j = 1; j < scaleCycles; j++){
           float sigma = par.sigmas[j]* sqrt(sigmaStep * sigmaStep - 1.0f);
           blurs[j+1+i*scaleCycles] = gaussianBlur(blurs[j+i*scaleCycles], sigma);
           if(j == par.numberOfScales)
               octaveLayer = halfImage(blurs[j+1+i*scaleCycles]);
       }
   }

   #pragma omp parallel
   {

   //compute all the hessianResponses
    #pragma omp for collapse(2) schedule(dynamic)
    for(int i=0; i<levels; i++)
        for (int j = 1; j <= scaleCycles; j++)
        {
            int scaleCyclesLevel = scaleCycles * i;
            float curSigma = par.sigmas[j];
            hessResps[j+scaleCyclesLevel] = hessianResponse(blurs[j+scaleCyclesLevel], curSigma*curSigma);
        }

    //we need to allocate here localWrappers to keep alive the reference for FindAffineShapeArgs
    #pragma omp single
    {
        for(int i=0; i<levels; i++)
            for (int j = 2; j < scaleCycles; j++){
                int scaleCyclesLevel = scaleCycles * i;
                localWrappers.push_back(Wrapper(sp, ap, hessResps[j+scaleCyclesLevel-1], hessResps[j+scaleCyclesLevel], hessResps[j+scaleCyclesLevel+1],
                                    blurs[j+scaleCyclesLevel-1], blurs[j+scaleCyclesLevel]));
            }
    }

    std::vector<FindAffineShapeArgs> localfindAffineShapeArgs;
    #pragma omp for collapse(2) schedule(dynamic) nowait
    for(int i=0; i<levels; i++)
        for (int j = 2; j < scaleCycles; j++){
            size_t c = (scaleCycles-2) * i +j-2;
            //toDo: octaveMap is shared, need synchronization
            //if(j==1)
            //  octaveMap = Mat::zeros(blurs[scaleCyclesLevel+1].rows, blurs[scaleCyclesLevel+1].cols, CV_8UC1);
            float curSigma = par.sigmas[j];
            // find keypoints in this part of octave for curLevel
            findLevelKeypoints(curSigma, pixelDistances[i], localWrappers[c]);
            localfindAffineShapeArgs.insert(localfindAffineShapeArgs.end(), localWrappers[c].findAffineShapeArgs.begin(), localWrappers[c].findAffineShapeArgs.end());
        }

    #pragma omp critical
    {
        findAffineShapeArgs.insert(findAffineShapeArgs.end(), localfindAffineShapeArgs.begin(), localfindAffineShapeArgs.end());
    }

    #pragma omp barrier
    std::vector<Result> localRes;
    #pragma omp for schedule(dynamic) nowait
    for(int i=0; i<findAffineShapeArgs.size(); i++){
        hessianKeypointCallback->onHessianKeypointDetected(findAffineShapeArgs[i], localRes);
    }

    #pragma omp critical
    {
        for(size_t i=0; i<localRes.size(); i++)
            descriptors.push_back(localRes[i].descriptor);
    }

}

Mat gaussianBlur(const Mat input, const float sigma)
{
   Mat ret(input.rows, input.cols, input.type());
   int size = (int)(2.0 * 3.0 * sigma + 1.0); if (size % 2 == 0) size++;      
   GaussianBlur(input, ret, Size(size, size), sigma, sigma, BORDER_REPLICATE);
   return ret;
}

Answer 1

If you consider a 50 ms (a fraction of the blink of an eye) one time cost to be a huge overhead, then you should probably focus on your workflow as such. Try to use one fully initialized process (with it's threads and data structures) in a persistent way to increase the work done during each each run.

That said, it may be possible to reduce the overhead, but in any case you will be very dependent on the runtime and initialization cost of your library, thus limiting your performance portability.

Your performance analysis may also be problematic. AFAIK VTune uses sampling, your data indicates a 1 ms sampling interval. That means you may have just 50 samples during the critical initialization path of your application, too little for a confident analysis. VTune might also have some forms of OpenMP instrumentation that provides more accurate results at small time scales. In any case I would take any performance measurement over just 150 ms with a grain of salt unless I knew exactly what impact and method the measurement has.

P.S. Running a simple code like:

#include <stdio.h>
#include <omp.h>

int main() {
  double start = omp_get_wtime();
#pragma omp parallel
  {
#pragma omp barrier
#pragma omp master
    printf("%f s\n", omp_get_wtime() - start);
  }
}

Shows an initial thread creation overhead between 3 ms and 200 ms on different systems / thread counts with the Intel OpenMP runtime.