Запуск развернутого связанного списка занимает около 40% времени выполнения кода - есть ли очевидные способы его оптимизации?

Я являюсь автором научного кода с открытым исходным кодом под названием vampire (http://github.com/richard-evans/vampire), а интенсивность вычислений означает любое улучшение производительности кода может значительно увеличить объем исследований, которые могут быть сделаны. Типичными временем выполнения этого кода могут быть сотни основных часов, поэтому я всегда ищу способы улучшить критические разделы кода. Тем не менее, я немного зациклился на следующем немного относительно безобидного вида кода, который составляет около 40% времени выполнения:

for (int atom = start_index; atom < end_index; atom++){
    register double Hx = 0.0;
    register double Hy = 0.0;
    register double Hz = 0.0;
    const int start = atoms::neighbour_list_start_index[atom];
    const int end = atoms::neighbour_list_end_index[atom] + 1;
    for (int nn = start; nn < end; nn++){
        const int natom = atoms::neighbour_list_array[nn];
        const double Jij = atoms::i_exchange_list[atoms::neighbour_interaction_type_array[nn]].Jij;
        Hx -= Jij * atoms::x_spin_array[natom];
        Hy -= Jij * atoms::y_spin_array[natom];
        Hz -= Jij * atoms::z_spin_array[natom];
    }
    atoms::x_total_spin_field_array[atom] += Hx;
    atoms::y_total_spin_field_array[atom] += Hy;
    atoms::z_total_spin_field_array[atom] += Hz;
}

Обзор функций и переменных этого кода на высоком уровне выглядит следующим образом: существует 1D-массив физического вектора (разбивается на три массива 1D для каждого компонента x, y, z для целей кэширования памяти, atoms::x_spin_array, и т.д.) называется "спин". Каждый из этих спинов взаимодействует с некоторыми другими спинами, и все взаимодействия хранятся в виде списка 1D-соседей (atoms::neighbour_list_array). Соответствующий список взаимодействий для каждого атома определяется начальным и конечным индексом соседа listarray в двух отдельных массивах. В конце вычисления каждый атомный спин имеет эффективное поле, которое является векторной суммой взаимодействий.

Учитывая небольшой объем кода и значительную долю времени выполнения, который он занимает, я сделал лучше всего, но я считаю, что должен быть способ оптимизировать это дальше, но, как физик, а не компьютерный ученый, возможно, я отсутствую что-то?

Ответ 1

У вас есть постоянный поток умножения, вычитания и добавления на смежных данных. Это похоже на идеальное использование SSE. Если ограничена полоса пропускания памяти, тогда вместо OpenCL/CUDA.

Попробуйте использовать эту библиотеку, если вы не знакомы со всеми инструкциями низкого уровня.

Этот внутренний цикл потенциально может быть реструктурирован, что может привести к ускорению.

Ответ 2

Если компоненты x, y, z действительно связаны списками, выполнение x[i], y[i] и z[i] приведет к переходу списков несколько раз, предоставив итерации (n^2)/2. Использование векторов сделает это O(1).

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

Используя что-то вроде:

struct vector3d {
    double x;
    double y;
    double z;
};

std::vector<vector3d> spin;
std::vector<vector3d> total_spin;

Это должно улучшить локальность кэша, поскольку значения x, y и z смежны в памяти, а спины занимают линейный блок памяти.

Ответ 3

Я чувствую, что следующие рекомендации могут помочь вам немного оптимизировать код, если не полностью:

Использовать инициализацию над присваиваниями, когда это возможно
Предпочитайте pre-increment над сообщением для лучшей скорости. (поверьте, он действительно вносит изменения)

Кроме того, я думаю, что код в порядке. Есть несколько плюсов и минусов каждого DS. Вы должны жить с ним.

Счастливое кодирование!