Java: микрооптимизирующая обработка массива

Question

Я пытаюсь сделать порт Java простой нейронной сетью с прямой связью.
Это, очевидно, включает в себя множество числовых вычислений, поэтому я стараюсь максимально оптимизировать мой центральный цикл. Результаты должны быть правильными в пределах типа данных float.

Мой текущий код выглядит следующим образом (обработка ошибок и инициализация удалены):

/**
 * Simple implementation of a feedforward neural network. The network supports
 * including a bias neuron with a constant output of 1.0 and weighted synapses
 * to hidden and output layers.
 * 
 * @author Martin Wiboe
 */
public class FeedForwardNetwork {
private final int outputNeurons;    // No of neurons in output layer
private final int inputNeurons;     // No of neurons in input layer
private int largestLayerNeurons;    // No of neurons in largest layer
private final int numberLayers;     // No of layers
private final int[] neuronCounts;   // Neuron count in each layer, 0 is input
                                // layer.
private final float[][][] fWeights; // Weights between neurons.
                                    // fWeight[fromLayer][fromNeuron][toNeuron]
                                    // is the weight from fromNeuron in
                                    // fromLayer to toNeuron in layer
                                    // fromLayer+1.
private float[][] neuronOutput;     // Temporary storage of output from previous layer


public float[] compute(float[] input) {
    // Copy input values to input layer output
    for (int i = 0; i < inputNeurons; i++) {
        neuronOutput[0][i] = input[i];
    }

    // Loop through layers
    for (int layer = 1; layer < numberLayers; layer++) {

        // Loop over neurons in the layer and determine weighted input sum
        for (int neuron = 0; neuron < neuronCounts[layer]; neuron++) {
            // Bias neuron is the last neuron in the previous layer
            int biasNeuron = neuronCounts[layer - 1];

            // Get weighted input from bias neuron - output is always 1.0
            float activation = 1.0F * fWeights[layer - 1][biasNeuron][neuron];

            // Get weighted inputs from rest of neurons in previous layer
            for (int inputNeuron = 0; inputNeuron < biasNeuron; inputNeuron++) {
                activation += neuronOutput[layer-1][inputNeuron] * fWeights[layer - 1][inputNeuron][neuron];
            }

            // Store neuron output for next round of computation
            neuronOutput[layer][neuron] = sigmoid(activation);
        }
    }

    // Return output from network = output from last layer
    float[] result = new float[outputNeurons];
    for (int i = 0; i < outputNeurons; i++)
        result[i] = neuronOutput[numberLayers - 1][i];

    return result;
}

private final static float sigmoid(final float input) {
    return (float) (1.0F / (1.0F + Math.exp(-1.0F * input)));
}
}

Я использую JVM с параметром -server, и на данный момент мой код на 25–50% медленнее, чем аналогичный код на Си. Что я могу сделать, чтобы улучшить эту ситуацию?

Спасибо,

Мартин Вибо

Редактировать # 1: После просмотра огромного количества ответов, мне, вероятно, следует уточнить цифры в нашем сценарии. Во время типичного прогона метод будет вызываться около 50000 раз с разными входами. Типичная сеть будет иметь число слоев = 3 слоя с 190, 2 и 1 нейроном, соответственно. Поэтому внутренний цикл будет иметь около 2*191+3=385 итераций (при подсчете добавленного нейрона смещения в слоях 0 и 1)

Редактировать # 1: После реализации различных предложений в этой теме наша реализация практически так же быстра, как версия C (в пределах ~ 2%). Спасибо за помощь! Все предложения были полезны, но, поскольку я могу пометить только один ответ как правильный, я передам его @Durandal как за предложения по оптимизации массивов, так и за то, что он единственный, который предварительно вычислит заголовок цикла for.

Answer 1

Несколько советов.

• в вашем самом внутреннем цикле, подумайте о том, как вы обходите свой кэш ЦП, и переставьте матрицу так, чтобы вы последовательно обращались к самому внешнему массиву.Это приведет к тому, что вы получите доступ к своему кешу по порядку, а не будете перепрыгивать повсюду.Попадание в кеш может быть на два порядка быстрее, чем попадание в кеш.например, реструктурировать fWeights так, чтобы к нему обращались как

активации + = neuronOutput [layer-1] [inputNeuron] * fWeights [layer - 1] [neuron] [inputNeuron];

• не выполнять работу внутри цикла (каждый раз), которую можно выполнить вне цикла (один раз).Не выполняйте поиск [layer -1] каждый раз, когда вы можете поместить это в локальную переменную.Ваша IDE должна иметь возможность легко рефакторинг.

• многомерных массивов в Java не так эффективны, как в C. Они на самом деле являются несколькими слоями одномерных массивов.Вы можете реструктурировать код, чтобы вы использовали только одномерный массив.

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

• вместо того, чтобы обрабатывать layer-1 повсеместно, почему бы не использовать layer1 как layer-1 и использовать layer1 + 1 вместо layer.

Answer 2

Независимо от математики, индексация массива в Java сама по себе может привести к снижению производительности. Учтите, что в Java нет реальных многомерных массивов, а реализует их как массив массивов. В вашем самом внутреннем цикле вы получаете доступ к нескольким индексам, некоторые из которых фактически являются постоянными в этом цикле. Часть массива доступа может быть перемещена за пределы цикла:

final int[] neuronOutputSlice = neuronOutput[layer - 1];
final int[][] fWeightSlice = fWeights[layer - 1];
for (int inputNeuron = 0; inputNeuron < biasNeuron; inputNeuron++) {
    activation += neuronOutputSlice[inputNeuron] * fWeightsSlice[inputNeuron][neuron];
}

Возможно, что сервер JIT выполняет аналогичное перемещение, инвариантное к коду, единственный способ узнать это изменить и профилировать его. На клиентском JIT это должно улучшить производительность, несмотря ни на что. Другая вещь, которую вы можете попробовать, - это предварительно рассчитать условия выхода цикла for, как это:

for (int neuron = 0; neuron < neuronCounts[layer]; neuron++) { ... }
// transform to precalculated exit condition (move invariant array access outside loop)
for (int neuron = 0, neuronCount = neuronCounts[layer]; neuron < neuronCount; neuron++) { ... }

Опять же, JIT уже может сделать это для вас, так что, если это поможет, просим сообщить.

Есть ли смысл умножать на 1.0F, что ускользает от меня здесь?:

float activation = 1.0F * fWeights[layer - 1][biasNeuron][neuron];

Другие вещи, которые могут потенциально улучшить скорость за счет читабельности: встроенная функция sigmoid () вручную (JIT имеет очень жесткий предел для встраивания, и функция может быть больше). Может быть немного быстрее запустить цикл в обратном направлении (где это, конечно, не меняет результат), поскольку проверка индекса цикла против нуля немного дешевле, чем проверка по локальной переменной (самый внутренний цикл снова является потенциальным кандидатом, но не ожидайте, что выходные данные будут на 100% идентичны во всех случаях, поскольку добавление чисел с плавающей точкой a + b + c потенциально не совпадает с a + c + b).

Answer 3

Для начала не делайте этого:

// Copy input values to input layer output
for (int i = 0; i < inputNeurons; i++) {
    neuronOutput[0][i] = input[i];
}

Но это:

System.arraycopy( input, 0, neuronOutput[0], 0, inputNeurons );

Answer 4

Заменить дорогостоящую передаточную функцию сигмоида с плавающей запятой на целочисленную шаговую передаточную функцию.

Передаточная функция сигмоида представляет собой модель органического аналогового синаптического обучения, которая, в свою очередь, представляется моделью ступенчатой ​​функции.

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

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

Вместо того, чтобы моделировать модель, замените дорогостоящую реализацию функции передачи органической сигмоиды с плавающей запятой на прямую цифровую реализацию ступенчатой ​​функции (меньше нуля = -1, больше нуля = +1).

Мозг не может этого сделать, но backprop может!

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

Также поддерживает аргумент, что информатика по своей сути крутая.

Answer 5

Первое, на что я бы обратил внимание - это если Math.exp замедляет вас. См. этот пост в приближении Math.exp для нативной альтернативы.

Answer 6

Я предлагаю использовать систему с фиксированной запятой, а не систему с плавающей запятой. Практически на всех процессорах использование int происходит быстрее, чем float. Самый простой способ сделать это - просто сдвинуть все, что осталось, на определенную величину (4 или 5 - хорошие начальные точки) и обработать младшие 4 бита как десятичные.

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

Answer 7

Чисто основываясь на проверке кода, ваш внутренний цикл должен вычислять ссылки на трехмерный параметр, и его работа выполняется очень часто. В зависимости от размеров вашего массива могут возникнуть проблемы с кэшем из-за необходимости перепрыгивать память при каждой итерации цикла. Может быть, вы могли бы изменить размеры, чтобы внутренний цикл пытался получить доступ к элементам памяти, которые ближе друг к другу, чем сейчас?

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

Answer 8

Ключ к оптимизации заключается в том, чтобы сначала измерить, на что тратится время. Окружите различные части вашего алгоритма вызовами System.nanoTime ():

long start_time = System.nanoTime();
doStuff();
long time_taken = System.nanoTime() - start_time;

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

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