Как вы перебираете одновременно два массива, которые не одинаково разнесены оптимизированным способом? - PullRequest
Новая
       51

Как вы перебираете одновременно два массива, которые не одинаково разнесены оптимизированным способом?

0 голосов
/ 26 октября 2018

Допустим, я умножил два массива, таких как A[MAX_BUFFER] и B[MAX_BUFFER] (с MAX_BUFFER = 256).

По какой-то причине каждое значение B[MAX_BUFFER] рассчитывается с фиксированной контрольной скоростью (например, 8), поскольку каждое значение будет подвергаться интенсивной обработке.

Позже мне нужно умножить друг друга на C[MAX_BUFFER], учитывая (введенный) разный интервал. Так что с A на 256 значениях я получу B с переменным размером (32 в нашем примере, так как контрольная скорость равна 8).

Вот пример кода : 

#include <iostream>
#include <math.h>

#define MAX_BUFFER 256

double HeavyFunction(double value) {
    if (value == 0) return 0.0;

    return pow(10.0, value); // heavy operations on value...
}

int main()
{    
    int blockSize = 256;
    int controlRate = 8;

    double A[MAX_BUFFER];
    double B[MAX_BUFFER];
    double C[MAX_BUFFER];

    // fill A
    for (int sampleIndex = 0; sampleIndex < blockSize; sampleIndex++) {
        A[sampleIndex] = sampleIndex;
    }

    // fill B (control rated)
    int index = 0;
    for (int sampleIndex = 0; sampleIndex < blockSize; sampleIndex += controlRate, index++) {
        B[index] = HeavyFunction(index);
    }

    // calculate C
    for (int sampleIndex = 0; sampleIndex < blockSize; sampleIndex++) {     
        C[sampleIndex] = A[sampleIndex] + B[sampleIndex / 8];

        std::cout << C[sampleIndex] << std::endl;
    }
}

Мне нужна производительность, так как я буду обрабатывать множество этих операций параллельно, посылая множество данных за 1 секунду (что-то вроде 44100 выборок, разбитых на blockSize <= <code>MAX_BUFFER).

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

В предыдущем примере это введет sampleIndex / 8 * N «бесполезную» N-операцию; вещи, если я назову эту процедуру для миллионов образцов ...

Как бы вы перестроили этот код причудливым и легким способом для процессора?

Ответы [ 2 ]

0 голосов
/ 26 октября 2018

Как выполнить итерацию одновременно двух массивов, которые не одинаково разнесены оптимизированным способом?

Краткий ответ: Сосредоточьтесь на HeavyFunction, избегайте разделения ненужных вещей между потоками.

К сожалению, ваш пример не подходит под вопрос. Массивы 

double A[MAX_BUFFER];
double B[MAX_BUFFER];
double C[MAX_BUFFER];

выделяются в стеке простым перемещением указателя стека, так что вы можете сказать, что они очень похожи на один непрерывный массив.

Даже если бы они не были современными, кеши настолько сложны, что, пытаясь микрооптимизировать, вы можете снизить производительность.

Если у вас есть 

BUFFER_SIZE = 1024 * 1024 * 1024;
std::vector<double> A(MAX_BUFFER);
std::vector<double> B(MAX_BUFFER);

Хорошее улучшение - 

std::vector<double> C{A};
for (int i = 0; i < blockSize/controlRate; i++) { 
     const double b = B[i];
     int indexStart = i*controlRate;
     for(int j = 0 ; j < controlRate; ++j){
        Cprime[indexStart+j] += b;
     }

}

Вы читаете A один раз (в блоках), B один раз (по одному двойному за раз) и получаете доступ к C такое же количество времени.

0 голосов
/ 26 октября 2018

Я думаю, что оптимизатор может выполнить эту работу в одиночку, но вы можете развернуть цикл, чтобы избежать разделения: 

// calculate C
const max = blockSize / 8;
int j = 0;
for (int i = 0; i != max; ++i) {
    const auto b = B[i];
    C[j] = A[j] + b; std::cout << C[j] << std::endl; ++j;
    C[j] = A[j] + b; std::cout << C[j] << std::endl; ++j;
    C[j] = A[j] + b; std::cout << C[j] << std::endl; ++j;
    C[j] = A[j] + b; std::cout << C[j] << std::endl; ++j;
    C[j] = A[j] + b; std::cout << C[j] << std::endl; ++j;
    C[j] = A[j] + b; std::cout << C[j] << std::endl; ++j;
    C[j] = A[j] + b; std::cout << C[j] << std::endl; ++j;
    C[j] = A[j] + b; std::cout << C[j] << std::endl; ++j;
}
...