Параллельная сумма префикса - самая быстрая реализация

Question

Я хочу реализовать алгоритм суммы параллельных префиксов с использованием C++. Моя программа должна взять входной массив x[1....N]и он должен отображать вывод в массиве y[N], (Обратите внимание, что максимальное значение N составляет 1000.)

До сих пор я просмотрел множество исследовательских работ и даже алгоритм в Википедии. Но моя программа также должна отображать вывод, шаги, а также операции / инструкции каждого шага.

Я хочу самую быструю реализацию, как я хочу минимизировать количество операций, а также шагов.

Например::

x = {1, 2, 3,  4,   5,   6,   7,  8 } - Input
y = ( 1, 3, 6, 10, 15, 21, 28, 36) - Output

Но наряду с отображением массива y в качестве вывода моя программа также должна отображать операции каждого шага. Я также рекомендую эту цепочку вычислить сумму префикса, но могу получить от этого большую помощь.

Answer 1

Следующий кусок кода сделает работу

void prfxSum()
{
    int *x=0;
    int *y=0;
    int sum=0;
    int num=0;
    int i=0;

    cout << "Enter the no. of elements in input array : ";
    cin >> num;

    x = new int[num];
    y = new int[num];

    while(i < num)
    {
        cout << "Enter element " << i+1 << " : ";
        cin >> x[i++];
    }

    cout << "Output array :- " << endl;
    i = 0;
    while(i < num)
    {
        sum += x[i];
        y[i] = sum;
        cout << y[i++] << ", ";
    }

    delete [] x;
    delete [] y;
}

Ниже приводится вывод о выполнении

Enter the no. of elements in input array : 8
Enter element 1 : 1
Enter element 2 : 2
Enter element 3 : 3
Enter element 4 : 4
Enter element 5 : 5
Enter element 6 : 6
Enter element 7 : 7
Enter element 8 : 8
Output array :- 
1, 3, 6, 10, 15, 21, 28, 36

Вы можете избежать ввода пользователем 1000 элементов массива x[], подавая его из файла или около того.

Answer 2

Ответ на этот вопрос находится здесь: http://http.developer.nvidia.com/GPUGems3/gpugems3_ch39.html и здесь http://www.cs.cmu.edu/~guyb/papers/Ble93.pdf. Статья NVidia предоставляет наилучшую возможную реализацию с использованием графических процессоров CUDA, а в PDF-документе Университета Карнеги-Меллона поясняется алгоритм. Я также реализовал сумму префикса O(n/p) с помощью MPI, которую вы можете найти здесь: в моем репозитории github

Это псевдокод универсального алгоритма (не зависит от платформы):

Пример 3. Фаза увеличения-уменьшения (уменьшения) алгоритма сканирования суммы, эффективной для работы (после Blelloch 1990)

 for d = 0 to log2(n) – 1 do 
      for all k = 0 to n – 1 by 2^(d+1) in parallel do 
           x[k +  2^(d+1) – 1] = x[k +  2^d  – 1] + x[k +  2^(d+1) – 1]

Пример 4. Фаза развертки работоспособного алгоритма параллельного сканирования суммы (после Blelloch 1990)

 x[n – 1] = 0
 for d = log2(n) – 1 down to 0 do 
       for all k = 0 to n – 1 by 2^(d+1) in parallel do 
            t = x[k +  2^d  – 1]
            x[k +  2^d  – 1] = x[k +  2^(d+1) – 1]
            x[k +  2^(d+1) – 1] = t +  x[k +  2^(d+1) – 1]

Где x - входные данные, n - размер входных данных, а d - степень параллелизма (количество процессоров). Это модель вычисления с общей памятью, если она использует распределенную память, вам нужно добавить шаги связи к этому коду, как я делал в приведенном примере Github.

Answer 3

Я реализовал только сумму всех элементов в массиве (часть сокращения Blelloch), а не полную сумму префикса, используя Aparapi ( https://code.google.com/p/aparapi/) в java/opencl. Его можно найти по адресу https://github.com/klonikar/trial-aparapi/blob/master/src/trial/aparapi/Reducer.java и он написан для общего размера блока (называемого в коде localBatchSize) вместо 2. Я нашел этот размер блока 8 лучше всего подходит для моего графического процессора.

Хотя реализация работает (вычисление суммы правильное), она работает намного хуже, чем последовательная сумма. На моем процессоре core-i7 (8-ядерном) последовательная сумма занимает около 12 мс для чисел 8388608 (8 МБ), параллельное выполнение на GPU (NVidia Quadro K2000M с 384 ядрами) занимает около 100 мс. Я даже оптимизировал перевод только окончательной суммы после вычисления, а не всего массива. Без этой оптимизации требуется еще 20 мс. Реализация, похоже, соответствует алгоритму, описанному в ответе @marcel-valdez-orozco.