В
алгоритме необходимо выделить части, обладающие наибольшей вычислительной
нагрузкой и подходящие для распараллеливания. Для этого следует обратить
внимание на операции, никак не зависящие от данных и результатов друг друга. Из алгоритма
видно, что результат слияния одной пары упорядоченных частей никак не зависит от
результата упорядочивания другой на данной итерации. Именно эту часть мы и будем
распараллеливать. Однако распараллеливание внутреннего цикла распределения
частей слияния тоже не даст особого результата, так как потоки будут часто
получать малые по размеру задачи, в результате чего накладные расходы на
открытие и закрытие потоков будут велики. Распараллеливать саму функцию слияния
не имеет смысла, так как в случае разбиения сливаемых массивов на несколько
частей мы лишь сымитируем действия предыдущей итерации алгоритма. Таким образом,
мы разделим весь массив на число потоков, и для каждой части выполним
последовательную сортировку на отдельном потоке.
inline
void Merge (Element *M, int l1, int l2,
int k1, int
k2, Element *Buff, int N)
{
int i1, i2, i;
i1 = l1;
i2 = k1;
i = l1;
while ( i <= k2) {
if (M[i1] > M[i2]) {
Buff[i] =
M[i2];
i2++;
i++;
}
else {
Buff[i] =
M[i1];
i1++;
i++;
}
if ((i1 > l2)&&(i2 <= k2))
{
while (i2 <= k2) {
Buff[i] = M[i2];
i2++;
i++;
}
}
if ((i1 <= l2)&&(i2 > k2))
{
while (i1 <= l2) {
Buff[i] = M[i1];
i1++;
i++;
}
}
}
for (i = l1, i1 = l1; i < k2+1; i++, i1++ )
{
M[i] =
Buff[i1];
}
}
void
Sort (Element *M, int N1, int N2, Element *Buff) {
int
i, Nk, step, K, K2, temp;
int
N = N2 - N1 +1;
Nk = ((int)(N/2))*2;
for (i = N1; i < N1+Nk; i+=2)
{
if (M[i] > M[i+1])
{
M[i] = M[i] + M[i+1];
M[i+1] = M[i] -
M[i+1];
M[i] = M[i] -
M[i+1];
}
}
for (step = 2; step < N ; step = step*2)
{
K = (int)(N/step);
K2 = ((int)(K/2))*2;
for (i = N1; i < N1+K2*step;
i+=step*2) {
Merge (M, i, i+step - 1, i+step ,
i+step*2 -1, Buff, N);
}
if (((N - K*step) > 0)&&((K -
K2) > 0)) {
Merge (M, K2*step+N1, (K2+1)*step - 1
+N1, (K2+1)*step +N1, N2, Buff, N);
}
}
}
void
SortParallel (Element *M, int N, int NUM_THREADS) {
Element *Buff = new Element[N];
int k = (int)((N-1)/2);
#pragma omp parallel sections
{
#pragma
omp section
Sort(M, 0, k, Buff);
#pragma
omp section
Sort (M, k+1, N-1, Buff);
}
Merge (M, 0, k,
k+1, N-1, Buff, N);
delete
[]Buff;
}
Последовательная
функция Merge
использует буфер, выделяемый один
раз в функции SortParallel,
размером в заданный массив. Последовательная функция сортировки
Sort
используется два раза в функции SortParallel,
рассчитанной на два потока. Большее количество потоков приведёт к тому, что
после работы всех потоков над своими частями, придётся эти части сливать либо в
основном потоке, любо снова распределять между потоками, что приведёт к
существенным накладным расходам.
