Я пытаюсь распараллелить этот код, используя OpenMP. OpenCV (построенный с использованием IPP для лучшей эффективности) используется в качестве внешней библиотеки.

У меня проблемы с несбалансированным использованием ЦП в parallel fors, но кажется, что дисбаланса нагрузки нет. Как вы увидите, это может быть из-за KMP_BLOCKTIME=0, но это может быть необходимо из-за внешних библиотек (IPP, TBB, OpenMP, OpenCV). В остальных вопросах вы найдете более подробную информацию и данные, которые вы можете скачать.

Это ссылки Google Диска на мои результаты VTune:

c755823 базовый KMP_BLOCKTIME=0 30 запусков: базовая точка доступа с переменной среды KMP_BLOCKTIME, установленной на 0 на 30 прогонах одного и того же ввода

c755823 базовые 30 запусков: то же, что и выше, но по умолчанию KMP_BLOCKTIME=200.

c755823 расширенный KMP_BLOCKTIME=0 30 запусков: то же, что и первый, но расширенная точка доступа

Для тех, кто заинтересован, я могу отправить вам исходный код как-нибудь.

На моем Intel i7-4700MQ фактическое время приложения на настенных часах в среднем при 10 запусках составляет около 0,73 секунды. Я компилирую код с icpc 2017 update 3 со следующими флагами компилятора:

INTEL_OPT=-O3 -ipo -simd -xCORE-AVX2 -parallel -qopenmp -fargument-noalias -ansi-alias -no-prec-div -fp-model fast=2 -fma -align -finline-functions    
INTEL_PROFILE=-g -qopt-report=5 -Bdynamic -shared-intel -debug inline-debug-info -qopenmp-link dynamic -parallel-source-info=2 -ldl

Кроме того, я установил KMP_BLOCKTIME=0, потому что значение по умолчанию (200) создавало огромные накладные расходы.

Мы можем разделить код на 3 параллельных области (завернутые только в один #pragma parallel для эффективности) и предыдущий последовательный, который составляет около 25% алгоритма (и его нельзя распараллелить).

Я попытаюсь описать их (или вы можете сразу перейти к структуре кода):

1. Мы создаем регион parallel, чтобы избежать накладных расходов на создание нового параллельного региона. Конечным результатом является заполнение строк матричного объекта cv::Mat descriptor. У нас есть 3 общих объекта std::vector: (a) blurs, который представляет собой цепочку размытий (не распараллеливаемых) с использованием GuassianBlur от OpenCV (который использует реализацию гуассового размытия IPP) (b) hessResps (известный размер, скажем, 32) (c) findAffineShapeArgs (неизвестный размер, но в порядке тысяч элементов, скажем, 2,3 тыс.) (d) cv::Mat descriptors (неизвестный размер, окончательный результат). В последовательной части мы заполняем `blurs, который является вектором только для чтения.
2. В первом параллельном регионе hessResps заполняется с использованием blurs без какого-либо механизма синхронизации.
3. Во второй параллельной области findLevelKeypoints заполняется с использованием hessResps только для чтения. Поскольку размер findAffineShapeArgs неизвестен, нам нужен локальный вектор localfindAffineShapeArgs, который будет добавлен к findAffineShapeArgs на следующем шаге.
4. Так как findAffineShapeArgs является общим и его размер неизвестен, нам нужен раздел critical, к которому добавляются все localfindAffineShapeArgs.
5. В третьей параллельной области каждый findAffineShapeArgs используется для генерации строк финального cv::Mat descriptor. Опять же, поскольку descriptors является общим, нам нужна локальная версия cv::Mat localDescriptors.
6. Заключительный critical раздел push_back каждый с localDescriptors по descriptors. Обратите внимание, что это очень быстро, так как cv::Mat является «своего рода» интеллектуальным указателем, поэтому мы используем push_back указатели.

Это структура кода:

cv::Mat descriptors;
std::vector<Mat> blurs(blursSize);
std::vector<Mat> hessResps(32);
std::vector<FindAffineShapeArgs> findAffineShapeArgs;//we don't know its tsize in advance

#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++)
    {
       hessResps[/**/] = hessianResponse(/*...*/);
    }

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++){
    findLevelKeypoints(localfindAffineShapeArgs, hessResps[/*...*], /*...*/); //populate localfindAffineShapeArgs with push_back
}

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

#pragma omp barrier
#pragma omp for schedule(dynamic) nowait
for(int i=0; i<findAffineShapeArgs.size(); i++){
{
  findAffineShape(findAffineShapeArgs[i]);
}

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

В конце вопроса вы можете найти FindAffineShapeArgs.

Я использую Intel Amplifier для просмотра горячих точек и оценки своего приложения.

Анализ потенциального прироста OpenMP говорит, что потенциальный прирост при идеальной балансировке нагрузки составил бы 5,8%, поэтому мы можем сказать, что рабочая нагрузка сбалансирована между разными процессорами.

Это гистограмма использования ЦП для региона OpenMP (помните, что это результат 10 последовательных запусков):

Итак, как вы можете видеть, среднее использование ЦП составляет 7 ядер, что хорошо.

Эта гистограмма длительности области OpenMP показывает, что в этих 10 запусках параллельная область всегда выполняется с одним и тем же временем (с разбросом около 4 миллисекунд):

Это вкладка Caller/Calee:

Для вас знания:

• interpolate вызывается в последнем параллельном регионе
• l9_ownFilter* функций вызываются в последнем параллельном регионе
• samplePatch вызывается в последнем параллельном регионе.
• hessianResponse вызывается во втором параллельном регионе

Теперь мой первый вопрос: как мне интерпретировать приведенные выше данные? Как вы можете видеть, во многих функциях в половине случаев «Эффективное время использования» «в порядке», которое, вероятно, станет «плохим» с большим количеством ядер (например, на машине KNL, где я буду тестировать приложение далее).

Наконец, это результат анализа ожидания и блокировки:

Теперь первая странность: строка 276Join Barrier (соответствует самому дорогому объекту ожидания) is#pragma omp parallel`, то есть началу параллельной области. Значит, похоже, что кто-то раньше порождал потоки. Я ошибаюсь? В Кроме того, время ожидания больше, чем сама программа (0,827 с против 1,253 с барьера присоединения, о котором я говорю)! невозможно, так как она длиннее самой программы).

Затем явный барьер в строке 312 представляет собой #pragma omp barrier кода выше, и его продолжительность составляет 0,183 с.

Глядя на вкладку Caller/Callee:

Как видите, большая часть времени ожидания невелика, поэтому относится к одному потоку. Но я уверен, что понимаю это. Мой второй вопрос: можем ли мы интерпретировать это как "все потоки ждут только одного потока, который остался позади?".

FindAffineShapeArgs определение:

struct FindAffineShapeArgs
{
    FindAffineShapeArgs(float x, float y, float s, float pixelDistance, float type, float response, const Wrapper &wrapper) :
        x(x), y(y), s(s), pixelDistance(pixelDistance), type(type), response(response), wrapper(std::cref(wrapper)) {}

    float x, y, s;
    float pixelDistance, type, response;
    std::reference_wrapper<Wrapper const> wrapper;
};

Топ-5 параллельных регионов по потенциальному выигрышу в сводном представлении показывает только один регион (единственный)

Посмотрите на группу "/OpenMP Region/OpenMP Barrier-to-Barrier", это порядок самых дорогих циклов:

• 3-я петля:

  pragma omp для расписания (динамического) nowait

  for(int i=0; i

  is the most expensive one (as I already knew) and here's a screenshot of the expended view:

Как видите, многие функции взяты из OpenCV, который использует IPP и (должен быть) уже оптимизирован. Расширение двух других функций (interpolate и samplePatch) показывает [Нет информации о стеке вызовов]. То же самое и со всеми остальными функциями (в том числе и в других регионах).

2-й самый дорогой регион - это вторая параллель для:

#pragma omp for collapse(2) schedule(dynamic) nowait
for(int i=0; i<levels; i++)
    for (int j = 2; j < scaleCycles; j++){
    findLevelKeypoints(localfindAffineShapeArgs, hessResps[/*...*], /*...*/); //populate localfindAffineShapeArgs with push_back
}

Вот расширенный вид:

И, наконец, 3-й самый дорогой — это первый цикл:

#pragma omp for collapse(2) schedule(dynamic)
for(int i=0; i<levels; i++)
    for (int j = 1; j <= scaleCycles; j++)
    {
       hessResps[/**/] = hessianResponse(/*...*/);
    }

Вот расширенный вид:

Если вы хотите узнать больше, воспользуйтесь моими прикрепленными файлами VTune или просто спросите!