Сокращение по массиву в OpenMP
Я пытаюсь распараллелить следующую программу, но не знаю, как уменьшить массив. Я знаю, что это невозможно, но есть ли альтернатива? Благодарю. (Я добавил сокращение на m, что неправильно, но хотел бы получить совет о том, как это сделать.)
#include <iostream>
#include <stdio.h>
#include <time.h>
#include <omp.h>
using namespace std;
int main ()
{
int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13};
int S [10];
time_t start_time = time(NULL);
#pragma omp parallel for private(m) reduction(+:m)
for (int n=0 ; n<10 ; ++n ){
for (int m=0; m<=n; ++m){
S[n] += A[m];
}
}
time_t end_time = time(NULL);
cout << end_time-start_time;
return 0;
}
Решение
Да, можно сделать сокращение массива с помощью OpenMP. В Фортране даже есть конструкция для этого. В C / C ++ вы должны сделать это самостоятельно. Вот два способа сделать это.
Первый метод делает приватную версию S для каждой нити заполните их параллельно, а затем объедините в S в критическом разделе (см. код ниже). Второй метод создает массив с размерами 10 * nthreads. Заполняет этот массив параллельно, а затем объединяет его в S без использования критического раздела. Второй метод намного сложнее и может иметь проблемы с кэшем, особенно в системах с несколькими сокетами, если вы не будете осторожны. Для более подробной информации см. Это Заполняйте гистограммы (сокращение массива) параллельно с OpenMP без использования критической секции
Первый способ
int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13};
int S [10] = {0};
#pragma omp parallel
{
int S_private[10] = {0};
#pragma omp for
for (int n=0 ; n<10 ; ++n ) {
for (int m=0; m<=n; ++m){
S_private[n] += A[m];
}
}
#pragma omp critical
{
for(int n=0; n<10; ++n) {
S[n] += S_private[n];
}
}
}
Второй метод
int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13};
int S [10] = {0};
int *S_private;
#pragma omp parallel
{
const int nthreads = omp_get_num_threads();
const int ithread = omp_get_thread_num();
#pragma omp single
{
S_private = new int[10*nthreads];
for(int i=0; i<(10*nthreads); i++) S_private[i] = 0;
}
#pragma omp for
for (int n=0 ; n<10 ; ++n )
{
for (int m=0; m<=n; ++m){
S_private[ithread*10+n] += A[m];
}
}
#pragma omp for
for(int i=0; i<10; i++) {
for(int t=0; t<nthreads; t++) {
S[i] += S_private[10*t + i];
}
}
}
delete[] S_private;
Другие решения
У меня есть два замечания относительно ответа Збозона:
1. Метод 1, безусловно, правильный, но цикл сокращения фактически запускается последовательно из-за #pragma omp критический что, конечно, необходимо, поскольку частичные матрицы являются локальными для каждого потока, и соответствующее сокращение должно быть выполнено потоком из-за матрицы.
2. Способ 2: цикл инициализации может быть перемещен за пределы одного раздела и, следовательно, становится распараллеливаемым.
Следующая программа инвентарь уменьшение массива используя openMP v4.0 пользовательскую функцию сокращения:
/* Compile with:
gcc -Wall -fopenmp -o ar ar.c
Run with:
OMP_DISPLAY_ENV=TRUE OMP_NUM_THREADS=10 OMP_NESTED=TRUE ./ar
*/
#include <stdio.h>
#include <omp.h>
struct m10x1 {int v[10];};
int A [] = {84, 30, 95, 94, 36, 73, 52, 23, 2, 13};
struct m10x1 S = {{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
int n,m=0;
void print_m10x1(struct m10x1 x){
int i;
for(i=0;i<10;i++) printf("%d ",x.v[i]);
printf("\n");
}
struct m10x1 add_m10x1(struct m10x1 x,struct m10x1 y){
struct m10x1 r ={{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
int i;
for (i=0;i<10;i++) r.v[i]=x.v[i]+y.v[i];
return r;
}
#pragma omp declare reduction(m10x1Add: struct m10x1: \
omp_out=add_m10x1(omp_out, omp_in)) initializer( \
omp_priv={{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}} )
int main ()
{
#pragma omp parallel for reduction(m10x1Add: S)
for ( n=0 ; n<10 ; ++n )
{
for (m=0; m<=n; ++m){
S.v[n] += A[m];
}
}
print_m10x1(S);
}
Это следует дословно пример сокращения комплексного числа на странице 97 Особенности OpenMP 4.0.
Хотя параллельная версия работает правильно, вероятно, есть проблемы с производительностью, которые я не исследовал:
- Входные и выходные данные add_m10x1 передаются по значению.
- Цикл в add_m10x1 запускается последовательно.
Упомянутые «проблемы с производительностью» — мои собственные решения, и совершенно просто не вводить их:
- Параметры к add_m10x1 должны быть переданы по ссылке (через указатели в C, ссылки в C ++)
- Вычисление в add_m10x1 должно быть сделано на месте.
- add_m10x1 должен быть объявлен недействительным, а оператор возврата удален. Результат возвращается через первый параметр.
- Прагма объявлений сокращения должна быть соответственно изменена, объединитель должен быть просто вызовом функции, а не присваиванием (v4.0 specs p181 Строки 9,10).
- Цикл для в add_m10x1 может быть распараллелен через omp параллель для прагмы
- Параллельное вложение должно быть включено (например, через OMP_NESTED = TRUE)
Модифицированная часть кода тогда:
void add_m10x1(struct m10x1 * x,struct m10x1 * y){
int i;
#pragma omp parallel for
for (i=0;i<10;i++) x->v[i] += y->v[i];
}
#pragma omp declare reduction(m10x1Add: struct m10x1: \
add_m10x1(&omp_out, &omp_in)) initializer( \
omp_priv={{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}} )
Если перевод вашего кода в Fortran, который может использовать массивы в операциях сокращения OpenMP, не подходит, вы можете использовать кучу временных переменных. Например
int S0, S1, S2, ..., S9;
...
#pragma omp parallel for private(...) shared(S0, S1, S2, ..., S9) \
reduction(+:S0, S1, S2, ..., S9)
for ...
Это оставляет вас с непривлекательной перспективой написать if или же case заявление, чтобы определить, какой из временных данных должен быть обновлен. Если ваш код является лишь примером, который вы хотите использовать для обучения, продолжайте.
Но если вы действительно хотите написать параллельную подпрограмму суммирования префиксов, то ищите. Это хорошее место для старта.