Форум программистов, компьютерный форум CyberForum.ru

Распараллеливание с помощью OpenMP - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 59, средняя оценка - 4.63
qwrus
0 / 0 / 0
Регистрация: 10.03.2012
Сообщений: 24
05.05.2012, 13:11     Распараллеливание с помощью OpenMP #1
Здравствуйте, уважаемые участники форума!

Имеется цикл вида:
C++
1
2
3
4
for (i=1; i<number; i++)
{
  do something;
}
Цикл выполняется (замерил) за, к примеру, 7 секунд. Моя задача заключается в том, чтобы с помощью технологии OpenMP сделать так, чтобы 2 (или лучше 4) последовательные итерации выполнялись одновременно параллельно на двух процессорах (на обычном компьютере с процессором i5). Т.е. цель - сделать то же за в 2 (или 4) раза меньшее время. Пытался сделать с помощью директив #pragma omp parallel, не получилось, выполняется за те же 7 секунд.

Буду благодарен за помощь.

P.S. Также буду благодарен за любые другие, более профессиональные реализации данной задачи с использованием технологии OpenMP.

Добавлено через 3 часа 58 минут
В догонку еще вопрос.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>
#include <iostream>
#include <time.h>
#include "TimeCounter.h"
#include <omp.h>
 
using namespace std;
 
void mode (void)
{
    if (omp_in_parallel()) cout<<"Parallel"<<endl;
    else cout<<"Posl"<<endl;
}
 
int main (void)
{
    double start, end;
    int n;
    mode();
    start = omp_get_wtime();
    omp_set_nested(1);
#pragma omp parallel private(n)
    {
        n = omp_get_thread_num();
#pragma omp parallel 
        {
            cout<<"Part 1, thread "<<n<<' '<<omp_get_thread_num()<<endl;
            mode();
        }
    }
    omp_set_nested(0);
    #pragma omp parallel private(n)
    {
        n = omp_get_thread_num();
#pragma omp parallel 
        {
            cout<<"Part 2, thread "<<n<<' '<<omp_get_thread_num()<<endl;
        }
    }
    end = omp_get_wtime();
    cout<<end-start<<endl;;
#pragma omp parallel
    {
#pragma omp master
        {
            mode();
        }
    }
}
Функция mode() проверяет, выполняется ли последовательная или параллельная область. Запускаю - везде выводится что последовательная. Есть идеи, почему?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.05.2012, 13:11     Распараллеливание с помощью OpenMP
Посмотрите здесь:

Распараллеливание C++
Как выполнить распараллеливание с помощью OpenMP C++
Распараллеливание алгоритмов C++
Распараллеливание циклов с ипользованием OpenMP C++
распараллеливание C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
06.05.2012, 19:05     Распараллеливание с помощью OpenMP #21
Ну так цель какая сейчас выбрана? Release или Debug?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
qwrus
0 / 0 / 0
Регистрация: 10.03.2012
Сообщений: 24
06.05.2012, 19:07  [ТС]     Распараллеливание с помощью OpenMP #22
Realese.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
06.05.2012, 19:11     Распараллеливание с помощью OpenMP #23
Зачем же было говорить "без оптимизации"?
А какие результаты выводятся в том и в другом случае? r[...] = ?
На всякий случай можно ещё так попробовать написать: private(g,k,i) хотя ничего не должно измениться по идее.
qwrus
0 / 0 / 0
Регистрация: 10.03.2012
Сообщений: 24
06.05.2012, 19:14  [ТС]     Распараллеливание с помощью OpenMP #24
r[0] = 0
r[1] = 0
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
06.05.2012, 19:22     Распараллеливание с помощью OpenMP #25
Чёрт, эти нули не показательны, там переполнение возможно. Давай изменим циклы, чтобы не было переполнений. Например так:
C++
1
2
3
4
5
6
7
        for (i = 0; i<1000000; i++)
        {
            for (k = 1; k<1000; k++)
            {
                g = g*k % 7321;
            }
        }
Что получилось?
qwrus
0 / 0 / 0
Регистрация: 10.03.2012
Сообщений: 24
06.05.2012, 19:29  [ТС]     Распараллеливание с помощью OpenMP #26
Тут такая деталька. Запустил на компе с 4 процами - отработала за 3,52 с.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
06.05.2012, 19:33     Распараллеливание с помощью OpenMP #27
Цитата Сообщение от qwrus Посмотреть сообщение
с 4 процами
С 4мя ядрами? А до этого сколько было ядер? У меня 2 ядра.
И всё-таки, результат тоже важен. У меня в результате вычислений в последнем варианте получается 1217. Вроде везде такое должно получаться.
qwrus
0 / 0 / 0
Регистрация: 10.03.2012
Сообщений: 24
06.05.2012, 19:38  [ТС]     Распараллеливание с помощью OpenMP #28
Что мы сейчас имеем. На 2 ядрах, у меня, старый вариант работает за 6,5 секунд. Два параллельных работают за 8,8; на 4 ядрах работает за 3,52.

Вот r[] везде нули у меня.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
06.05.2012, 20:24     Распараллеливание с помощью OpenMP #29
Цитата Сообщение от qwrus Посмотреть сообщение
Вот r[] везде нули у меня.
Вот это в первую очередь непонятно. С кодом из #25 должно получаться 1217. Если, конечно, g = 1 в параллельной секции не потерялось и деление по модулю не убиралось.
qwrus
0 / 0 / 0
Регистрация: 10.03.2012
Сообщений: 24
07.05.2012, 03:27  [ТС]     Распараллеливание с помощью OpenMP #30
Щас еще раз проверю. Но ускорение нормальное?
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
08.05.2012, 15:10     Распараллеливание с помощью OpenMP #31
Цитата Сообщение от qwrus Посмотреть сообщение
Но ускорение нормальное?
В этой задаче практически нет использования памяти и нет необходимости синхронизации нитей, поэтому время не должно существенно изменяться пока количество нитей не превышает количество физических ядер (логические, вроде гипертрейдинга, не считаются).
8,8 секунд против 6,5 я считаю серьёзным замедлением. Четырёх ядерный, видимо, совсем другой процессор? В однопоточном варианте-то на нём сколько?
qwrus
0 / 0 / 0
Регистрация: 10.03.2012
Сообщений: 24
08.05.2012, 16:10  [ТС]     Распараллеливание с помощью OpenMP #32
Итак, еще раз.

2-ядерный процессор:

1-поточный вариант: около 8,8 секунд
Наш вариант: около 5 секунд

4-ядерный процессор:

1-поточный вариант: около 6,5 секунд
Наш вариант: около 3,3 секунд
qwrus
0 / 0 / 0
Регистрация: 10.03.2012
Сообщений: 24
10.05.2012, 19:56  [ТС]     Распараллеливание с помощью OpenMP #33
Доброго времени суток, снова вопрос.

Есть код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main (int argc, char* argv[])
{
    int i, k;
    omp_set_num_threads(4);
#pragma omp parallel private(i)
    {
#pragma omp for schedule (static, 2)
        
            for (i = 0; i<10; i++)
            {
                k = omp_get_thread_num();
                cout<<k<<endl;
            }
    }
 
 
    return 0;
}
По идее, опция schuedule static 2 заставляет работать так: 0-ая нить выполняет 2 итерации цикла, потом 1-ая две итерации, потом 2, потом 3, а потом распараллеливание должно начаться опять с 0 нити. В итоге должен быть выдан результат:

0
0
1
1
2
2
3
3
0
0

Вот. А у меня он выдает полную околесицу. Откомпилируйте пожалуйста. Каковы Ваши результаты? В чем может быть проблема?
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
10.05.2012, 20:50     Распараллеливание с помощью OpenMP #34
Разное выдаёт. Например
01
30
1
2
2

3

0
0
Но это правильный результат: четыре нуля и по 2 остальных, в десяти строчках. Просто, во-первых, неизвестно в каком порядке будут выполняться нити, а во-вторых, когда 2 нити одновременно выводят что-то на экран, то тут тоже неизвестно сколько символов какая нить успеет вывести перед другой. Поэтому всё перемешивается. Убедиться в этом можно если вынести вывод за параллельную секцию, например так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <omp.h>
 
int main (int argc, char* argv[])
{
    int i, k;
    const int N = 10;
    int a[N];
    omp_set_num_threads(4);
#pragma omp parallel private(i)
    {
#pragma omp for schedule (static, 2)
 
        for (i = 0; i<N; i++)
        {
            a[i] = omp_get_thread_num();
        }
    }
 
    for (i = 0; i < N; i++)
        std::cout<<a[i]<<std::endl;
 
 
    return 0;
}
Но этот пример имеет одну неприятность, которую надо учитывать в реальных программах. Неприятность эта называется false sharing. Разные нити пишут, казалось бы, в разные ячейки памяти и не должны мешать друг другу. Но проблема в том, что эти ячейки расположены рядом друг с другом и, скорее всего, попадут в одну линию кэша. И когда меняется одно значение в кэше вся линия объявляется устаревшей, что вызывает необходимость синхронизации между кэшами разных ядер и приводит к серьёзному уменьшению производительности.
qwrus
0 / 0 / 0
Регистрация: 10.03.2012
Сообщений: 24
11.05.2012, 04:09  [ТС]     Распараллеливание с помощью OpenMP #35
И опять я возвращаюсь к вопросу помочь мне реализовать мою изначальную задачу. Может быть, я не описал ее достаточно конкретно, поэтому напишу еще раз.

Имеется цикл следующего вида:

for (i = 0; i<100; i++)
{
fout<<i+1<<endl; //печать номера итерации в файл

first_population(A,n,k); // инициализация начальной популяции (для генетического алгоритма); функция не зависит от того, на какой итерации она выполняется

best_num=best_population_individ(A,B,m,n,k,func);// вычисление индекса лучшего индивида (для ГА); функция не зависит от того, на какой итерации она выполняется

сохранение лучшего индивида в массив; функция не зависит от того, на какой итерации цикла она выполняется

функции работы с поколениями; ВАЖНО: в этой части объявляются две переменные, сохраняющие надежность и скорость алгоритма; изменяются они так;

speed = speed + {какое-то число, получающееся в результате работы функций ГА}
rel = rel + {какое-то число, получающееся в результате работы функций ГА}

fout<<speed<<rel<<endl;
}

Т.е. пока не выполнились предыдущие итерации, следующие выполнятся не могут из-за:

1. В файл должна выводится аккуратная информация о запусках программы (т.е. типа ИТЕРАЦИЯ 1: поколения такие-то, время такое-то, надежность такая-то, скорость такая-то).

2. Переменные speed и rel высчитываются по результатам работы прошлых итераций.

Собственно, вопросы:

1. Целесообразно ли это вообще распараллеливать (по идее надо, поскольку функции, занимающие основное время, это функции работы с ГА, а там не зависит в какой итерации она делаются).

2. К примеру, с помощью #pragma omp for schedule (static, 25) я могу разбить цикл на 25 итераций в каждом куске на 4 ядра. Надо, чтобы программа сначала выполнила так: сначала все нити напечатали номер своей последовательно; потом 4 первых итерации могут параллельно выполнять функции с ГА; затем опять сначала первая ветвь для своей итерации считает переменные speed, rel; и затем каждая из 3 других параллельных нитей считает эти значения по результатам работы предшествующей нити; и все повторяется.

Вот. Благодарю за помощь.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
11.05.2012, 20:17     Распараллеливание с помощью OpenMP #36
Мне кажется, что с помощью omp for желаемого поведения не удастся. Наверное можно создать секцию omp parallel, в которой организовать уже обычные циклы (у одного 0, 4, 8, ..., у второго 1, 5, 9, ..., и так далее), а в нужном месте вставить барьер и секцию мастер, которая будет выполняться в один поток и объединять результаты четырёх потоков, выводить в правильном порядке и так далее.
Но я бы сначала попытался распараллелить не итерации целиком (так как это не очень естественно), а отдельные фунции. Ведь там обычно однотипная работа с множеством независимых индивидов или их пар. Правда в приведённом алгоритме я не слишком-то узнал привычный мне ГА
qwrus
0 / 0 / 0
Регистрация: 10.03.2012
Сообщений: 24
16.05.2012, 03:56  [ТС]     Распараллеливание с помощью OpenMP #37
Вроде распараллелил, теперь неизвестная ошибка.


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#pragma omp parallel private(func, select, cross, k, m, n, t, l, i, j, sp, test, tn, A, S, best, best_num, d, a, b, s, rel, speed, B), shared (A1, A2, A3, A4, A5, A6, A7)
    {
        for (test = 0; test<100; test++)
        {
            tn = omp_get_thread_num();
            test = test + 1;
            A1[tn][test-1] = test;
            first_population(A,n,k);
            A2[tn][test-1] = average_objective_function(A,B,m,n,k,func);
            best_num=best_population_individ(A,B,m,n,k,func);
            for (i=0;i<k;i++)
            {
                best[0][i]=A[best_num][i];
            }
            for (j=0;j<t;j++)
            {
                switch(select)
                {
                case 1:
                    {
                        rank_selection(A,B,S,m,n,k,func);
                        break;
                    }
                case 2:
                    {
                        tournament_selection(A,B,S,m,n,k,func);
                        break;
                    }
                default:
                    {
                        return 0;
                    }
                }
            
                switch(cross)
                {
                case 1:
                    {
                        one_point_crossingover(A,S,n,k);
                        break;
                    }
                case 2:
                    {
                        two_point_crossingover(A,S,n,k);
                        break;
                    }
                case 3:
                    {
                        equable_crossingover(A,S,n,k);
                        break;
                    }
                default:
                    {
                        return 0;
                    }
                }
 
                for (i=0;i<k;i++)
                {
                    A[0][i]=best[0][i];
                }
 
                moderate_mutation(A,n,k);
                s=s+decode(best,B,m,k,d,func);
 
                if (sp==0)
                {
                    sp = decode(best,B,m,k,d,func);
                    if (sp==1)
                    {
                        sp=j;
                    }
                }
 
                best_num=best_population_individ(A,B,m,n,k,func);
 
                if (objective_function(A,B,m,k,best_num,func)<=objective_function(best,B,m,k,0,func))
                {
                    for (i=0;i<k;i++)
                    {
                        best[0][i]=A[best_num][i];
                    }
                }
            }
 
            A3[tn][test-1] = average_objective_function(A,B,m,n,k,func);
            A4[tn][test-1] = s/t;
            s=0;
            A5[tn][test-1] = sp;
 
            if (sp==0)
            {
                sp=t;
                // массив A6 хранит новое ебанейшее значение sp
                A6[tn][test-1] = sp;
            }
            else
            {
                A6[tn][test-1] = sp;
            }
            sp = 0;
            A7[tn][test-1] = objective_function(best,B,m,k,0,func);
        }
    }
 
// потом еще код
return 1;
}
error C3010: return: не допускается переход из структурированного блока OpenMP

где у меня вообще может быть выход из блока OpenMP!?
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
16.05.2012, 04:05     Распараллеливание с помощью OpenMP #38
Такой код трудно читать. Используй, пожалуйста, специальные тэги для оформления кода (кнопка C++ на панели инструментов в форме ответа). Может успеешь ещё это отформатировать...

Добавлено через 5 минут
Но вообще, я смотрю там несколько раз встречается return 0; и в конце ещё return 1; Это всё внутри parallel блока? Да, ретурны не разрешаются. Выход из блока может произойти только одним способом: когда он закончится естественным образом, то есть закрывающей скобкой.
qwrus
0 / 0 / 0
Регистрация: 10.03.2012
Сообщений: 24
16.05.2012, 14:55  [ТС]     Распараллеливание с помощью OpenMP #39
Собственно вот какой вопрос. Имеется натуральное число n (число процессоров). Имеются функции (Гриванка, Розендрока, Растригина и т.д.). Нужно их протестировать. Существует ли алгоритм или метод (возможно, вероятностный), позволяющий определить, сколько тестовых запусков нужно провести, чтобы правильно ли работают алгоритмы. Ну в том смысле, что вот если есть алгоритм. Есть данные о том, как он должен работать правильно. Образно, к примеру, результатом работы должен быть целочисленный массив, все элементы которого больше 50. Очевидно, что проверка на 5 запусках ничего не даст, потому что все 5 раз может выпасть к примеру 60. Но и на 100000 запусков проверять бессмысленна, если будет доказано, что проверка на 50 запусках дает ответ о корректности работы.

Вот есть ли такая схема или метод для ГА.

Добавлено через 33 секунды
Собственно вот какой вопрос. Имеется натуральное число n (число процессоров). Имеются функции (Гриванка, Розендрока, Растригина и т.д.). Нужно их протестировать. Существует ли алгоритм или метод (возможно, вероятностный), позволяющий определить, сколько тестовых запусков нужно провести, чтобы правильно ли работают алгоритмы. Ну в том смысле, что вот если есть алгоритм. Есть данные о том, как он должен работать правильно. Образно, к примеру, результатом работы должен быть целочисленный массив, все элементы которого больше 50. Очевидно, что проверка на 5 запусках ничего не даст, потому что все 5 раз может выпасть к примеру 60. Но и на 100000 запусков проверять бессмысленна, если будет доказано, что проверка на 50 запусках дает ответ о корректности работы.

Вот есть ли такая схема или метод для ГА.

Добавлено через 9 минут
И еще. В моей программе очень важна возможность при невыполнении некоторых условий (их много) не начинать работу, но они в распараллелином куске кода. Как без return остановить выполнение программы?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.05.2012, 19:10     Распараллеливание с помощью OpenMP
Еще ссылки по теме:

Распараллеливание циклов C++
Работа с OpenMP. Распараллеливание цикла for C++
C++ Для распараллеливание процессов лучше пользоваться OpenMP или Win32?

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
qwrus
0 / 0 / 0
Регистрация: 10.03.2012
Сообщений: 24
17.05.2012, 19:10  [ТС]     Распараллеливание с помощью OpenMP #40
И еще раз задаю тот же вопрос. Как выйти из блока OpenMP без return?
Yandex
Объявления
17.05.2012, 19:10     Распараллеливание с помощью OpenMP
Ответ Создать тему
Опции темы

Текущее время: 18:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru