Распараллеливание циклов в C

#c #многопоточность

Подскажите, пожалуйста, как можно распараллелить выполнение подобного цикла на C.
for(int i = 0; i < X; i++)  
{
    for(int j = 0; j < Y; j++)
    {
        for(int k = 0; k < Z; k++) 
        {
            for(int i2 = 0; i2 < 27; i2++)  
            {
                if (count < 27) 
                {
                    count++;
                    x_vect.push_back(x_mas[i2]);
                    y_vect.push_back(y_mas[i2]);
                    z_vect.push_back(z_mas[i2]);
                }
                else
                {
                    x_vect.push_back(i*a + 2*a1 + x_mas[i2]);
                    y_vect.push_back(j*b + 2*b1 + y_mas[i2]);
                    z_vect.push_back(k*c + 2*c1 + z_mas[i2]);
                    count++;
                }
            }
        }
    }
}

Проводится множество итераций и хотелось бы, как можно проще сгенерировать код для
загрузки обоих ядер. Используется MS Visual Studio 2010 и Intel C++ Compiler. Процессор
- Core2Duo. После включения оптимизации, в том числе SSE3, скорость выросла почти в
12 раз. Но хотелось бы организовать многопоточность. На включение QParallel ругается.    

Ответы

Ответ 1

Алгоритм сводится к последовательному заполнению массива данными. Такая задача легко
распараллеливается на два ядра. Нужно разбить внешний цикл на два: первый от 0 до X/2
- 1, а второй от X/2 до X - 1. И запустить на выполнение в разных потоках.
Кроме того, поскольку размеры вектора известны заранее, нет смысла использовать собственно
вектор, можно взять плоский массив float и писать прямо в него по индексу (x[n++])
или по указателю (*x++).
Еще можно ускорить алгоритм, если убрать избыточную вложенность, то есть вместо трех
вложенных циклов сделать один, а уже внутри считать индексы, по которым обращаться
к массиву.


Ответ 2

В дополнение к ответу @jmem можно заметить, что в самом внутреннем цикле (по i2)
для count >= 27 в выражениях:
x_vect.push_back(i*a + 2*a1 + x_mas[i2]);
y_vect.push_back(j*b + 2*b1 + y_mas[i2]);
z_vect.push_back(k*c + 2*c1 + z_mas[i2]);

i*a + 2*a1  j*b + 2*b1 и k*c + 2*c1

можно вычислять во внешних циклах.


Ответ 3

Как уже было сказано dmitry_'eм, для таких случаев существует прекрасная библиотека
OpenMP, но для данной задачи, если я ее правильно понял, распараллеливание не нужно.
Первая часть кода выполнится первые 27 раз, вторая остальные. Тут нет параллельности,
здесь последовательное выполнение. Если вы хотите оптимизировать именно этот алгоритм,
вынесите следующий код в отельный цикл, идущий перед данным.
x_vect.push_back(x_mas[i2]);
y_vect.push_back(y_mas[i2]);
z_vect.push_back(z_mas[i2]);
++count;


Ответ 4

В данной ситуации, без иных оптимизирующих изменений в коде, можно, как уже было
написано, применить OpenMP. Перед циклом поставить следующую прагму:
#pragma omp parallel for firstprivate (a, b, c, a1, b1, c1) shared (x_mas, y_mas, z_mas)

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