Уменьшение скорости OpenMP

Question

Существует две версии кодов openmp с уменьшением и без.

// с уменьшением

#pragma omp parallel for reduction(+:sum) 
    for (i=1;i<= num_steps; i++){ 
     x = (i-0.5)*step; 
     sum = sum + 4.0/(1.0+x*x); 
    } 

// без уменьшения

#pragma omp parallel private(i) 
{ 
    int id = omp_get_thread_num(); 
    int numthreads = omp_get_num_threads(); 
    double x; 

    double partial_sum = 0; 

    for (i=id;i< num_steps; i+=numthreads){ 
     x = (i+0.5)*step; 
     partial_sum += + 4.0/(1.0+x*x); 
    } 
#pragma omp critical 
     sum += partial_sum; 
} 

Я бег коды с использованием 8 ядер, общее время двойного для версии восстановления. В чем причина? Благодарю.

Answer 1

Если вы хотите вручную распараллелить цикл, а также сокращения вы можете сделать это следующим образом:

#pragma omp parallel private(i) 
{ 
    int id = omp_get_thread_num(); 
    int numthreads = omp_get_num_threads(); 
    int start = id*num_steps/numthreads; 
    int finish = (id+1)*num_steps/numthreads; 
    double x; 
    double partial_sum = 0; 

    for (i=start; i<finish ; i++){ 
     x = (i+0.5)*step; 
     partial_sum += + 4.0/(1.0+x*x); 
    } 
    #pragma omp atomic 
    sum += partial_sum; 
} 

Однако я не рекомендую это. Сокращения не должны выполняться с помощью атома, и вы должны просто позволить OpenMP распараллелить цикл. Первый случай - лучшее решение (но убедитесь, что вы объявляете x частным).

Редактировать: Согласно Христу, когда вы делаете x private, эти два метода почти одинаковы по скорости. Я хочу объяснить, почему использование критического в вашем втором методе вместо атомарного или разрешение OpenMP делать сокращение вряд ли повлияет на производительность в этом случае.

Есть два способа я могу думать делать сокращение:

• Суммы частичные суммы линейно с использованием атомной или критический
• Суммы частичных сумм с использованием дерева. То есть если у вас есть 8 ядер, это дает вам восемь частичных сумм, вы уменьшаете это до 4 частичных сумм, затем 2 частичные суммы, затем 1.

Первый литой имеет линейную конвергенцию в количестве сердечников. Второй случай относится к журналу количества ядер. Поэтому один из меня может подумать, что второй случай всегда лучше. Однако, только для восьми ядер, восстановление полностью доминирует за счет частичных сумм. Добавление восьми чисел с атомарным/критическим против сокращения дерева в 3 этапа будет небрежным.

Что делать, если у вас есть, например, 1024 ядра? Тогда дерево может быть уменьшено всего за 10 шагов, а линейная сумма - 1024 шага. Но постоянный член может быть намного больше для второго случая и делать частичную сумму большого массива, например. с 1 миллионом элементов, вероятно, все еще доминирует над сокращением.

Таким образом, я подозреваю, что использование атомного или даже критического для сокращения оказывает незначительное влияние на время сокращения вообще.

Answer 2

Скалярное сокращение в OpenMP обычно довольно быстрое. Наблюдаемое поведение в вашем случае происходит из-за двух вещей, сделанных неправильно двумя разными способами.

В вашем первом коде вы не сделали x частным. Поэтому он разделяется между потоками и, помимо получения неправильных результатов, выполнение страдает от совместного использования данных. Всякий раз, когда один поток записывает в x, ядро, которое он выполняет, отправляет сообщение всем другим ядрам и делает их недействительными для своих копий этой строки кэша. Когда какая-либо из них записывается в x позже, вся строка кэша должна быть перезагружена, а затем строки кэша во всех остальных ядрах становятся недействительными. И так далее. Это значительно замедляет процесс.

В вашем втором коде вы использовали конструкцию OpenMP critical. Это относительно тяжелый вес по сравнению с атомными добавками, обычно используемыми для реализации сокращения в конце. Атомные добавления на x86 выполняются с использованием префикса команд LOCK и все реализуется в аппаратном обеспечении. С другой стороны, критические разделы реализуются с использованием мьютексов и требуют нескольких инструкций и часто занятых циклов ожидания. Это намного менее эффективно, чем атомные добавления.

В конце концов, ваш первый код замедляется из-за плохого условия совместного использования данных. Второй код замедляется из-за использования некорректного примитива синхронизации. Просто случается, что на вашей конкретной системе последний эффект менее суровый, чем первый, и, следовательно, ваш второй пример работает быстрее.