Преобразуйте последовательный цикл в параллельный в C, используя pthreads

Question

Я хотел бы применить довольно простой и простой расчет для n -by- d -мерного массива. Цель состоит в том, чтобы преобразовать последовательный расчет в параллельный, используя pthreads. Мой вопрос: Каков оптимальный способ решения проблемы ? Как можно значительно сократить время выполнения моего скрипта ? Я предоставляю пример последовательного кода на C и некоторые мысли о параллельных реализациях, которые я уже пробовал.

double * calcDistance(double * X ,int n, int d)
{
    //calculate and return an array[n-1] of all the distances
    //from the last point
    double *distances = calloc(n,sizeof(double));
    for(int i=0 ; i<n-1; i++)
    {
        //distances[i]=0;
        for (int j=0; j< d; j++)
        {

            distances[i] += pow(X[(j+1)*n-1]-X[j*n+i], 2);

        }
        distances[i] = sqrt(distances[i]);


    }
    return distances;
}

Я предоставляю функцию вызова main() для того, чтобы образец был полным и тестируемым:

#include <stdio.h>
#include <stdlib.h>

#define N 10 //00000
#define D 2        

int main()
{

    srand(time(NULL));

    //allocate the proper space for X
    double *X = malloc(D*N*(sizeof(double)));

    //fill X with numbers in space (0,1)
    for(int i = 0 ; i<N ; i++)
    {
        for(int j=0; j<D; j++)
        {
            X[i+j*N] = (double) (rand()  / (RAND_MAX + 2.0));
        }

    }
    X = calcDistances(X, N, D);

    return 0;
}

• Я уже пытался использовать pthreads асинхронно, используя global_index, который накладывается на mutex и local_index. Используя цикл while(), local_index присваивается каждому потоку на каждой итерации. Назначение local_index зависит от значения global_index в то время (оба происходят в блоке mutual exclusion). Поток выполняет вычисления для элемента distances[local_index]. К сожалению, эта реализация привела к гораздо более медленной программе с х10 или х20 большим временем выполнения по сравнению с последовательной, которая упоминалась выше.
• Другая идея состоит в том, чтобы заранее определить и разделить массив (скажем, на четыре равные части) и назначить вычисление каждого сегмента данному pthread. Я не знаю, является ли это общей эффективной процедурой.

Answer 1

Ваш внутренний цикл перепрыгивает по всему массиву X со смесью шагов, которые зависят от итерации внешнего цикла. Если n и d не достаточно малы, ^* это может привести к плохому использованию кэша - в последовательном коде тоже, но распараллеливание усилит этот эффект. По крайней мере X не написана функцией, которая улучшает внешний вид. Кроме того, по-видимому, не существует каких-либо зависимостей данных между итерациями внешнего цикла, что хорошо.

Каков оптимальный способ разделения проблемы?

Вероятно, наилучшим доступным способом было бы разделить итерации внешнего цикла между вашими потоками. Для потоков T один должен выполнить итерации 0 ... (N / T) - 1, второй - сделать (N / T) ... (2 * N / T) - 1, и т. Д. ..

Как я мог значительноуменьшить время выполнения моего скрипта?

Первое, что I должен сделать, это использовать простое умножение вместо pow для вычисления квадратов. Неясно, добьетесь ли вы чего-либо от параллелизма.

• Я уже пытался использовать pthreads асинхронно с помощью global_index, который навязывается мьютексу и local_index. [...]

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

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

Это похоже на то, что я описал. Это одна из стандартных моделей планирования, предоставляемых OMP, и одна из наиболее эффективных, доступных для решения многих задач, учитывая, что она сама по себе не требует мьютекса. Однако он несколько чувствителен к взаимосвязи между количеством потоков и количеством доступных исполнительных блоков. Например, если вы распараллеливаете пять ядер на четырехъядерном компьютере, то одному придется подождать, пока не завершится работа одного из остальных - наилучшее теоретическое ускорение 60%. Распараллеливание одного и того же вычисления только по четырем ядрам более эффективно использует вычислительные ресурсы, обеспечивая лучшее теоретическое ускорение примерно на 75%.

---

^* Если n и d довольно малы , скажем, что-нибудь удаленно близкое к значениям в примере программы драйвера, тогда накладные расходы, возникающие при распараллеливании, имеют хороший шанс преодолеть любые выгоды от параллельного выполнения.