Как улучшить производительность без параллели для моего backprop ANN

После профилирования моего алгоритма обратного распространения я понял, что он занимает 60% моего вычислительного времени. Прежде чем я начну рассматривать параллельные альтернативы, я хотел бы узнать, могу ли я что-нибудь сделать дальше.

Функция activate(const double input[]) профилируется, чтобы занимать только ~ 5% времени. Функция gradient(const double input) реализована следующим образом:

inline double gradient(const double input) { return (1 - (input * input)); }

Обучающая функция:

void train(const vector<double>& data, const vector<double>& desired, const double learn_rate, const double momentum) {
        this->activate(data);
        this->calculate_error(desired);

        // adjust weights for layers
        const auto n_layers = this->config.size();
        const auto adjustment = (1 - momentum) * learn_rate;

        for (size_t i = 1; i < n_layers; ++i) {
            const auto& inputs = i - 1 > 0 ? this->outputs[i - 1] : data;
            const auto n_inputs = this->config[i - 1];
            const auto n_neurons = this->config[i];

            for (auto j = 0; j < n_neurons; ++j) {
                const auto adjusted_error = adjustment * this->errors[i][j];

                for (auto k = 0; k < n_inputs; ++k) {
                    const auto delta = adjusted_error * inputs[k] + (momentum * this->deltas[i][j][k]);

                    this->deltas[i][j][k] = delta;
                    this->weights[i][j][k] += delta;
                }

                const auto delta = adjusted_error * this->bias + (momentum * this->deltas[i][j][n_inputs]);

                this->deltas[i][j][n_inputs] = delta;
                this->weights[i][j][n_inputs] += delta;
            }
        }
    }
}

Этот вопрос лучше подходит для https://codereview.stackexchange.com/.

Ответы

Ответ 1

Вы не можете избежать алгоритма O (n ^ 2), если хотите тренировать/использовать NN. Но он отлично подходит для векторной арифметики. Например, при умном использовании SSE или AVX вы можете обрабатывать нейроны в кусках 4 или 8 и использовать умножить-добавить вместо двух отдельных инструкций.

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

Для gcc autovectorization активируется с использованием -O3 или -ветво-векторизации. Конечно, вам нужен вектор, способный к процессору, например, -march = core2 -mssse4.1 или аналогичный, в зависимости от целевого процессора. Если вы используете -ftree-vectorizer-verbose = 2, вы получите подробные объяснения, почему и где петли не были векторизованы. Посмотрите http://gcc.gnu.org/projects/tree-ssa/vectorization.html.

Лучше, конечно, напрямую использовать встроенные функции компилятора.

Ответ 2

Вы хотите исключить условное изнутри своего цикла здесь:

const double lower_layer_output = i > 0 ? outputs[lower_layer][k] : input[k]; // input layer semantics

Вы можете устранить это условие, вычислив нулевую итерацию (частный случай я == 0) раньше.

        deltas[i][j][k] = delta;
        weights[i][j][k] += delta;

Вы упоминаете использование std::vector, так что это вектор вектора вектора? Ваши данные не будут смежными (за исключением того, что каждый вектор является смежным). Рассмотрим использование массивов стилей C.

Насколько велики эти измерения? Могут быть некоторые соображения кэширования, если они очень большие. Например. вы не хотите, чтобы последний индекс [k] сбросил кеш L1. Иногда разрыв цикла для обработки меньшего диапазона k индексов за один раз может помочь (strip mining).

Вы также можете экспериментировать с разворачиванием своих внутренних циклов, например. попробуйте выполнить 4 или восемь операций внутри цикла. Приращение на 4/8 соответственно и обработка любого остатка в другом цикле. Компилятор уже может это сделать.

Как уже упоминалось, использование SIMD (SSE/AVX), вероятно, там, где вы можете найти наибольший выигрыш. Вы можете использовать компилятор intrinsics (ссылка на Visual Studio, но gcc имеет поддержку с тем же синтаксисом) или писать в сборке (в строчном или в другом). Как вы упомянули, масштабирование нескольких ядер - это другое направление. OpenMP может помочь вам сделать это без большой боли.

Иногда полезно создать аннотированный список ассемблера из вашего кода, чтобы попытаться увидеть, где компилятор не делает такие замечательные задания.

Это - отличный общий ресурс об оптимизации.

Ответ 3

Я не уверен, что компилятор может оптимизировать его в вашем случае, но выход inverse_momentum * (learn_rate * errors[i][j]) в переменную вне цикла "k" в нижних циклах может снизить нагрузку на CPU.

Кстати, вы профилируете двоичный файл release, а не отладочный, не так ли.

Ответ 4

Я не люблю valarray, но у меня есть догадка, что для тех, кто здесь есть, есть определенная возможность.

Blitz ++ (boost), похоже, имеет лучшую ауру в Интернете, но я этого не знаю:)

Я начал работать над PoC самостоятельно, но слишком много отсутствующих бит кода

void activate(const double input[]) { /* ??? */ }
const unsigned int n_layers_ns;
const unsigned int n_layers;
const unsigned int output_layer_s;
const unsigned int output_layer;

T/*double?*/ bias = 1/*.0f?/;

const unsigned int config[];
double outputs[][];
double errors [][];
double weights[][][];
double deltas [][][];

Теперь он логически вытекает из кода, что по крайней мере первые (ранг-0) индексы для массивов определяются четырьмя отсутствующими константами. Если эти константы могут быть известны временем компиляции, это создало бы большие параметры шаблона класса значений:

template <unsigned int n_layers_ns = 2,
          unsigned int n_layers = 3>
struct Backprop {
    void train(const double input[], const double desired[], const double learn_rate, const double momentum);

    void activate(const double input[]) { }
    enum _statically_known
    {
        output_layer = n_layers_ns - 1,
        output_layer_s = n_layers - 1, // output_layer with input layer semantics (for config use only)

        n_hidden_layers = output_layer - 1,
    };

    static const double bias = 1.0f;

    const unsigned int config[];
    double outputs[3][50];      // if these dimensions could be statically known, 
    double errors[3][50];       //        slap them in valarrays and 
    double weights[3][50][50];  //        see what the compiler does with that!
    double deltas[3][50][50];   // 
};

template <unsigned int n_layers_ns,
          unsigned int n_layers>
void Backprop<n_layers_ns, n_layers>::train(const double input[], const double desired[], const double learn_rate, const double momentum) {
    activate(input);

    // calculated constants
    const double inverse_momentum = 1.0 - momentum;
    const unsigned int n_outputs = config[output_layer_s];

    // calculate error for output layer
    const double *output_layer_input = output_layer > 0 ? outputs[output_layer] : input; // input layer semantics
    for (unsigned int j = 0; j < n_outputs; ++j) {
        //errors[output_layer][j] = f'(outputs[output_layer][j]) * (desired[j] - outputs[output_layer][j]);
        errors[output_layer][j] = gradient(output_layer_input[j]) * (desired[j] - output_layer_input[j]);
    }
    [... snip ...]

Обратите внимание, как я немного упорядочил операторы в первом цикле, чтобы сделать цикл тривиальным. Теперь я могу представить, что последние строки становятся

// calculate error for output layer
const std::valarray<double> output_layer_input = output_layer>0? outputs[output_layer] : input; // input layer semantics
errors[output_layer] = output_layer_input.apply(&gradient) * (desired - output_layer_input);

Для этого потребуются правильные (g) срезы для ввода. Я не могу понять, как они должны быть рассчитаны. Суть в том, что до тех пор, пока эти размеры среза могут быть статически определены компилятором, у вас будет потенциал для значимой экономии времени, поскольку компилятор может оптимизировать их в векторизованные операции либо на FPU или использование набора инструкций SSE4. Я предполагаю, что вы объявите свой вывод примерно так:

std::valarray<double> rawoutput(/*capacity?*/);
std::valarray<double> outputs = rawoutput[std::slice(0, n_outputs, n_layers)]; // guesswork

(Я ожидаю, что веса и дельта должны стать gslices, потому что AFAICT они трехмерны)

Разное (выравнивание, макет)

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

В этом свете важно понимать, что "оптимальный" порядок рангов в конечном счете зависит от самих шаблонов доступа (так что профиль и проверка снова).

Кроме того, возможность оптимизации может быть затруднена неудачным выравниванием памяти [1]. В этом свете вам может потребоваться переключить порядок рангов ранга (вал) и округлых размеров ранга до ближайших степеней 2 (или мор практически, скажем, кратных 32 байтам).

Если все это на самом деле оказывает большое влияние (сначала профиль/проверка сгенерированного кода!) Я бы предположил, что поддержка

что Blitz ++ или boost могут содержать помощники (распределители?) для обеспечения выравнивания
ваш компилятор будет иметь атрибуты (из align и/или ограничивать), чтобы сказать им, что они могут считать эти выравнивания для указателей ввода

Unrelated:

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

inverse_momentum * (learn_rate * ???)

вы можете взять

(inverse_momentum * learn_rate) * ???

и предварительно вычислить первое подпродукт. Однако из-за того, что он явно упорядочен таким образом, я предполагаю, что это приведет к большему шуму.

[1] отказ: я на самом деле не делал никакого анализа, я просто бросаю его туда, чтобы вы не пропустили "хотя суставы" (как это для ангрича)