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

Я хочу реализовать алгоритм суммирования параллельных префиксов с использованием С++. Моя программа должна принимать входной массив 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 в качестве вывода, моя программа также должна отображать операции каждого шага. Я также ссылаюсь на эту цепочку вычислить сумму префикса, но может получить от нее большую помощь.

Ответ 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 [], подав их из файла или так.

Ответ 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. Фаза Up-Sweep (Уменьшение) алгоритма сканирования суммарного объема (после 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. Фаза Down-Sweep эффективного алгоритма сканирования параллельной суммы (после 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 - степень parallelism (количество ЦП). Это модель вычисления разделяемой памяти, если в ней используется распределенная память, вам нужно будет добавить шаги связи к этому коду, как это было в приведенном примере Github.

Ответ 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 работает лучше всего для моего GPU.

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