Использование динамического планирования OpenMP и его влияние на производительность-как найти детали

При запуске алгоритма, который не использует планирование и использует планирование, разница в производительности очень велика - при планировании алгоритм завершается за 4 секунды, а не за 14 секунд. Я думал, что perf даст некоторое представление о том, почему это может произойти, но статистика очень похожа.

Можно ли с уверенностью предположить, что при работе с динамическим планированием я решил некоторую проблему с балансировкой нагрузки? Я надеялся найти что-нибудь в деталях perf. Ниже приводится подробно на всякий случай полезно. Также код используется для Pagerank, где используется планирование...

    # pragma omp parallel for schedule(dynamic, 64)
    for (int u = 0; u < vertex_count; u++) {
        int* in_edge = G.getAdjList(u);
        double sum = 0.0;
        for (int j = 0; j < in_edge_counts[u]; j++) {
            int v = in_edge[j];
            sum += conntrib[v];
        }
        pr_temp[u] = sum * damp + adj;
    }

С использованием планирования 

     107470.977295      task-clock (msec)         #    1.743 CPUs utilized
             1,187      context-switches          #    0.011 K/sec
                44      cpu-migrations            #    0.000 K/sec
         2,279,522      page-faults               #    0.021 M/sec
   255,920,277,205      cycles                    #    2.381 GHz                      (20.00%)
    17,116,048,117      stalled-cycles-frontend   #    6.69% frontend cycles idle     (20.02%)
   153,944,352,418      stalled-cycles-backend    #   60.15% backend cycles idle      (20.02%)
   148,412,677,859      instructions              #    0.58  insn per cycle
                                                  #    1.04  stalled cycles per insn  (30.01%)
    27,479,936,585      branches                  #  255.696 M/sec                    (40.01%)
       321,470,463      branch-misses             #    1.17% of all branches          (50.01%)
    78,562,370,506      L1-dcache-loads           #  731.010 M/sec                    (50.00%)
     2,075,635,902      L1-dcache-load-misses     #    2.64% of all L1-dcache hits    (49.99%)
     3,100,740,665      LLC-loads                 #   28.852 M/sec                    (50.00%)
       964,981,918      LLC-load-misses           #   31.12% of all LL-cache hits     (50.00%)

Без использования планирования 

      106872.881349      task-clock (msec)         #    1.421 CPUs utilized
             1,237      context-switches          #    0.012 K/sec
                69      cpu-migrations            #    0.001 K/sec
         2,262,865      page-faults               #    0.021 M/sec
   254,236,425,448      cycles                    #    2.379 GHz                      (20.01%)
    14,384,218,171      stalled-cycles-frontend   #    5.66% frontend cycles idle     (20.04%)
   163,855,226,466      stalled-cycles-backend    #   64.45% backend cycles idle      (20.03%)
   149,318,162,762      instructions              #    0.59  insn per cycle
                                                  #    1.10  stalled cycles per insn  (30.03%)
    27,627,422,078      branches                  #  258.507 M/sec                    (40.03%)
       213,805,935      branch-misses             #    0.77% of all branches          (50.03%)
    78,495,942,802      L1-dcache-loads           #  734.480 M/sec                    (50.00%)
     2,089,837,393      L1-dcache-load-misses     #    2.66% of all L1-dcache hits    (49.99%)
     3,166,900,999      LLC-loads                 #   29.632 M/sec                    (49.98%)
       929,170,535      LLC-load-misses           #   29.34% of all LL-cache hits     (49.98%)
2 2
openmp

2 ответа:

schedule(dynamic, 64) говорит OpenMP не предполагать, что каждая итерация внутреннего цикла занимает одно и то же время, IIRC.

Таким образом, статическое планирование разбивает работу на диапазоны значений u, но один из ваших потоков должен иметь больше общего объема работы, чем остальные (или по какой-то причине занимает много времени), задерживая общее время для завершения всех потоков.

Он работал на вычислительном сервере с четырех процессоров AMD процессор Opteron. В то время машина в основном простаивала. Единственная разница между два - это использование планирования. Я опустил время, потому что оно включает в себя предварительный этап обработки, который выполняется обоими, но все равно отличается на 10 секунд.

В этом случае общее использование процессоров 1.4 против 1.7 может быть объяснено гораздо большей загрузкой в течение 4/14 секунды, о которой вы говорите. Вы можете приблизить результаты для интересующей вас части, выполнив выход программы непосредственно перед параллельной частью и профилировав ее. Вычтите эти подсчеты из вашего всего отсчетов, чтобы получить очень грубое приближение.

IDK почему работа несбалансирована; это ваш код + данные; G.getAdjList(u) может занять больше времени, или, скорее всего, in_edge_counts[u] больше в среднем для некоторых потоков.

Различия в локальности для conntrib[in_edge[j]] могут иметь большое значение, вызывая промахи кэша при рассеянном чтении или попадание в кэш, когда различные элементы in_edge были близки к предыдущим значениям.

Когда у вас есть разные ядра, конкурирующие за память + последний уровень пропускная способность кэша, задержка в обслуживании запроса на кэш-строку значений in_edge будет хуже, чем задержка ответа на строку conntrib[], потому что ЦП нуждается в данных in_edge[], Прежде чем он узнает, какие строки кэша ему нужны для большего количества данных conntrib. Так что in_edge пропуски кэша уменьшают параллелизм памяти, возможно, заставляя этот поток получать меньшую долю пропускной способности памяти.

IDK, насколько эти эффекты будут сбалансированы или нет. Скорее всего, ваши данные просто не распределены равномерно.

Тоже плохая AMD не имеет эффективных сборщиков AVX2, потому что ваши данные идеально подходят для vpgatherdd ymm. Не то чтобы это помогло бы с честностью или чем-то еще, просто (на Skylake) дает вероятно-незначительное ускорение против скалярного сбора.

1

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

perf timechart может быть, стоит попробовать, но он не знает OpenMP специально. Вы получите лучшее понимание, используя инструмент анализа, который сделан специально для OpenMP. Кроме того, чтобы получить динамику, я рекомендую использовать инструмент трассировки / временной шкалы в качестве в отличие от инструмента профилирования, который показывает только сводку. Примером такого инструмента может бытьIntel VTune илиScore-P (трассировка) / Vampir (визуализация).

1