Можно ли это оптимизировать?

Question

У меня есть программа, которая работает медленнее, чем хотелось бы.

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

        DO K = 0, K_MAX
            WRITE(EIGENVALUES_IO, *) K * 0.001 * PI, (W_UP(J), J=1, ATOM_COUNT)
            DCMPLXW_UP(:) = DCMPLX(W_UP(:))
            DO E = 1, ENERGY_STEPS
                ENERGY = MIN_ENERGY + ENERGY_STEP * REAL(E, DP)
                ZV = DCMPLX(ENERGY, DELTA)
                ON_SITE_SINGLE = DCMPLX(0.0_DP)
                DO Q = 1, ATOM_COUNT
                    DO J = 1, ATOM_COUNT
                        ON_SITE_SINGLE(J) = ON_SITE_SINGLE(J) + (MATRIX_UP(J, Q) * MATRIX_UP_CONJG(J, Q)) / (ZV - DCMPLXW_UP(Q))
                    END DO
                END DO
                DOS_DOWN(E) = DOS_DOWN(E) - WEIGHTS(K) * SUM(IMAG(ON_SITE_SINGLE))
            END DO
        END DO

Линия

ON_SITE_SINGLE(J) = ON_SITE_SINGLE(J) + (MATRIX_UP(J, Q) * MATRIX_UP_CONJG(J, Q)) / (ZV - DCMPLXW_UP(Q))

Тот, кто наносит урон.

Я довольно новичок в этом, есть ли способ ускорить это? AFAIK, те же принципы применимы к C, так что любая помощь от вас, ребята, тоже будет полезна.

Все массивы являются СЛОЖНЫМИ

K_MAX - 1000

ENERGY_STEPS - 1000

ATOM_COUNT низкий (<50) </p>

Answer 1

Все мои программы работают медленнее, чем хотелось бы.Во всех (хорошо, не во всех, но во многих) моих научных программах есть гнездо с глубоким циклом, в котором самые внутренние утверждения занимают большую часть времени вычислений.Обычно я ожидаю, что 90% моих вычислений будут приняты этими утверждениями.Это ваше самое внутреннее утверждение выполняется 2,5x10 ^ 9 раз, поэтому вы должны ожидать, что оно займет значительную долю общего времени.

Учитывая это, я предлагаю вам:

a) Воспользуйтесь советом @ Alexandre, чтобы использовать BLAS вместо умножения собственного матричного вектора на вектор.

b) игнорировать совет @ Yuval о выводе операций из цикла - хороший компилятор Fortran сделает это за вас, еслиВы повышаете оптимизацию (ВНИМАНИЕ: это самоисполняющееся пророчество настолько, насколько компилятор этого не делает, не является хорошим).Есть много других оптимизаций, которые я ожидаю от хорошего Фортрана в эти дни, см. (D).(Я не ожидаю оптимизации доступа к памяти компилятором, я ожидаю, что от BLAS.)

c) Сформируйте реалистичное ожидание того, какую производительность вы должны получить от своей программы.Если вы получаете устойчивый показатель FLOP, превышающий 10% от номинальной производительности процессоров, вы делаете это очень хорошо и должны тратить свое время на другие задачи, а не на оптимизацию.

d) Внимательно прочитайте документацию по компилятору.Убедитесь, что вы понимаете, что на самом деле делают флаги оптимизации.Убедитесь, что вы генерируете код для используемых процессоров, а не какой-то более старый вариант.Включите быстрые векторные операции, если они доступны.Все подобные вещи.

e) Начните распараллеливание.OpenMP - хорошее место для начала, и, как указывает @Nicolas, кривая обучения поначалу довольно мягкая.

О, и совет 0, которому вы, похоже, следовали, - это измерить производительность кода и измеритьвлияние любых изменений, которые вы делаете.

Answer 2

Если при обычной оптимизации кода вы застряли, вы можете попробовать OpenMP , который представляет собой API для параллельного программирования, созданный для C и Fortran.Есть некоторые инструкции, которые вы вставляете в свой код перед циклами, в стиле «pre-compiler», и это разделит тяжелые циклы между различными процессами.

У вас есть несколько инструкций, которые вы можете попробовать.Например:

#pragma omp parallel for
/* Loop here */

Это очень полный API, и вы можете разделить все по множеству параметров, общих переменных и с различными методами параллельного разделения.Вы также можете указать количество процессов, которые вы хотите создать в OpenMP, количество ядер и т. Д.

После небольшой настройки вы в итоге найдете решение, увеличивающее скорость вычислений.

Answer 3

Пожалуйста, используйте BLAS для 'умножения vactor плюс матрица-вектор'.Вы в основном делаете это в строке

ON_SITE_SINGLE(J) = ON_SITE_SINGLE(J) + (MATRIX_UP(J, Q) * MATRIX_UP_CONJG(J, Q)) / (ZV - DCMPLXW_UP(Q)) 

С хорошо настроенными библиотеками BLAS вы можете добиться значительного улучшения.

Answer 4

Факторы, на которые вы делитесь, а именно

(ZV - DCMPLXW_UP(Q))

не зависит от J, только от Q. Следовательно, я бы переместил этот расчет в цикл Q. А еще лучше, посчитайте:

1/(ZV - DCMPLXW_UP(Q))

во внешнем цикле и умножьте его вместо деления внутри цикла (AFAIR, умножения быстрее, чем деления). Также убедитесь, что ваши матричные структуры данных соответствуют циклам (чтобы циклы проходили через непрерывные части памяти как можно больше). Как правило, если вы сможете улучшить алгоритм, это будет наибольшим улучшением во время выполнения.

Programming Pearls имеет большое описание подобных оптимизаций.