Параллельное ускорение с OpenMP

Question

У меня есть два сценария измерения метрик, таких как время вычислений и параллельное ускорение (sequential_time / parallel_time).

Сценарий 1:

Последовательное измерение времени:

startTime=omp_get_wtime();  
for loop computation  
endTime=omp_get_wtime();  
seq_time = endTime-startTime;

Параллельное измерение времени:

startTime = omp_get_wtime();  
for loop computation (#pragma omp parallel for reduction (+:pi) private (i)  
for (blah blah) {   
    computation;   
}  
endTime=omp_get_wtime();  
paralleltime = endTime-startTime; 

speedup = seq_time/paralleltime;

Сценарий 2:

Последовательное измерение времени:

for loop{  
startTime=omp_get_wtime();  
   computation;  
endTime=omp_get_wtime();  
seq_time += endTime-startTime;  
}

Параллельное измерение времени:

for loop computation (#pragma omp parallel for reduction (+:pi, paralleltime) private (i,startTime,endTime)  
for (blah blah) {  
    startTime=omp_get_wtime();  
    computation;  
    endTime=omp_get_wtime();  
    paralleltime = endTime-startTime;  
}  

speedup = seq_time/paralleltime;

Я знаю, что Сценарий 2 НЕ лучший код производства,но я думаю, что он измеряет фактическую теоретическую производительность, ПЕРЕСМОТРЯ на издержки, связанные с порождением openmp и управлением (переключением контекста потока) нескольких потоков.Так что это даст нам линейное ускорение.Но сценарий 1 учитывает накладные расходы, связанные с порождением и управлением потоками.

Я сомневаюсь в следующем: со сценарием 1 я получаю ускорение, которое начинается линейно, но сужается, когда мы переходим к большему числу итераций.Со Сценарием 2 я получаю полное линейное ускорение независимо от количества итераций.Мне сказали, что в действительности сценарий 1 даст мне линейное ускорение независимо от количества итераций.Но я думаю, что это не из-за высокой перегрузки из-за управления потоками.Может кто-нибудь объяснить мне, почему я не прав?

Спасибо!И извините за довольно длинный пост.

Answer 1

Прежде всего, по определению ускорения, вы должны использовать сценарий 1, который включает параллельные издержки.

---

В сценарии 2 у вас неправильный код при измерении paralleltime. Чтобы достичь своей цели в сценарии 2, вам нужно иметь для каждого потока paralleltime, выделяя int paralleltime[NUM_THREADS] и получая к ним доступ omp_get_thread_num() (обратите внимание, что этот код будет иметь ложное совместное использование, поэтому лучше выделить 64 -байтовая структура с отступом). Затем измерьте время вычисления для каждого потока и, наконец, возьмите самый длинный , чтобы вычислить другой тип ускорения (я бы сказал, что-то вроде параллелизма).

---

Нет, вы можете увидеть сублинейное ускорение даже для Сценария 2, или даже суперлинейное ускорение может быть получено. Потенциальные причины (т. Е. Исключая параллельные издержки):

1. Неуравновешенность нагрузки: длина рабочей нагрузки в compuation отличается на итерации. Это было бы самой распространенной причиной низкого ускорения (но вы говорите, что дисбаланс нагрузки не тот случай).
2. Стоимость синхронизации: если есть какие-либо виды синхронизации (например, мьютекс, событие, барьер), у вас может быть время ожидания / блокировки.
3. Кэши и стоимость памяти: когда computation требует большой пропускной способности и большого рабочего набора, параллельный код может страдать от ограничения пропускной способности (хотя в действительности это редко встречается) и конфликтов кеша. Кроме того, ложная передача была бы важной причиной, но этого легко избежать. Суперлинейный эффект также может наблюдаться, потому что использование многоядерности может иметь больше кэшей (то есть частных кэшей L1 / L2).

В сценарии 1 он будет включать издержки параллельных библиотек:

1. Форкирование / присоединение потоков: хотя большинство реализаций параллельных библиотек не будут создавать / завершать физические потоки для каждой параллельной конструкции.
2. Диспетчеризация / объединение логических задач: даже если физические потоки уже созданы, вам необходимо отправить логическую задачу в каждый поток (в общем случае из задачи M в N поток), а также выполнить своего рода операцию объединения в конце (например, скрытый барьер).
3. Затраты на планирование: для статического планирования (как показано в вашем коде, который использует статическое планирование OpenMP), накладные расходы минимальны. Вы можете безопасно игнорировать накладные расходы, когда рабочей нагрузки достаточно (скажем, 0,1 секунды). Тем не менее, динамическое планирование (например, похищение работы в TBB) имеет некоторые накладные расходы, но это не существенно, когда ваша рабочая нагрузка достаточна.

Я не думаю, что ваш код (1-уровневый статический параллельный цикл) имеет большие параллельные издержки из-за управления потоками, если только этот код не вызывается миллион раз в секунду. Итак, могут быть и другие причины, о которых я упоминал выше.

Имейте в виду, что есть много факторов, которые будут определять ускорение; от присущего ей параллелизма (= дисбаланс нагрузки и синхронизации) до издержек параллельной библиотеки (например, накладных расходов на планирование).

Answer 2

Есть много ситуаций, когда сценарий 2 также не даст вам линейного ускорения - ложное разделение между потоками (или, в этом отношении, истинное разделение разделяемых переменных, которые модифицируются), конфликт пропускной способности памяти и т. Д. Сублинейныйускорение, как правило, реальное, а не артефакт измерения.

В целом, как только вы достигнете точки, в которую вы помещаете таймеры внутри для циклов, вы рассматриваете более детальную синхронизациюинформацию, которую на самом деле уместно измерить, используя такие таймеры.Возможно, вы захотите иметь возможность отделить накладные расходы на управление потоками от фактической работы, выполняемой по разным причинам, но здесь вы пытаетесь это сделать, вставив N дополнительных вызовов функций в omp_get_wtime(), а также арифметикуи операция сокращения, каждая из которых будет иметь свои собственные незначительные накладные расходы.

Если вы действительно хотите точную синхронизацию того, сколько времени тратится в строке computation;, вы действительно хотите использовать что-токак выборка, а не ручное приборостроение (мы немного поговорим о различии здесь ).Использование gprof или scalasca или openspeedshop (все бесплатное программное обеспечение) или Intel VTune или чего-то еще (коммерческий пакет) даст вам информацию о том, сколько времени тратитсяв этой строке - часто даже по ниткам - с гораздо меньшими накладными расходами.

Answer 3

Что вы хотите точно измерить? Издержки из-за параллелизма являются частью реального времени выполнения, поэтому сценарий 1 ИМХО лучше.

Кроме того, согласно вашим директивам OpenMP, вы делаете сокращение для некоторого массива. В сценарии 1 вы принимаете это во внимание. В сценарии 2 вы не. В общем, вы измеряете меньше вещей, чем в сценарии 1. Это, вероятно, также влияет на ваши измерения.

В противном случае, ответ Джонатана Дурси будет превосходным.

Answer 4

В OpenMP есть несколько опций для распределения работы между потоками.Это может повлиять на линейность вашего метода измерения 1. Ваш метод измерения 2 не кажется полезным.Что вы пытались получить с этим?Если вы хотите узнать производительность одного потока, запустите один поток.Если вы хотите параллельную производительность, то вам нужно включить накладные расходы.