Блог

Я работаю с научной задачей оптимизации в том, что мы могли бы рассматривать как 3 1-мерное пространство, где дополнительное измерение описывается тензором, представленным в программе либо коэффициентами, либо угловой сегментацией, наряду с координатами высоты и азимута. В типичном случае мне может потребоваться эффективно работать с несколькими массивами (двойными) измерений вдоль линий 75 x 75 x 75 x 16 и потенциально промежуточными, такими большими, как 75 x 75 x 75 x 16 x 16 , при использовании обоих представлений и коэффициентов. Я должен выполнять в основном реальную и несколько сложную арифметику и тригонометрию с разумной эффективностью, чтобы выполнять такие вещи, как повышающая дискретизация, проецирование из и в два измерения и числовое дифференцирование. Возможно, в будущем я смогу создать более удобный алгоритм, но в настоящее время мой метод выглядит так.

Для выполнения этих задач я написал реализацию на C объемом около 1500 строк, где я использую комбинацию функций MKL, где это применимо, и прибегаю к вложенным циклам в противном случае. Проблема здесь в том, что циклам приходится иметь дело с большими массивами размеров, которые (как сейчас) неизвестны во время компиляции во вложенных циклах со сложной индексацией. Таким образом, то, что я получаю, когда пытаюсь проанализировать производительность с помощью отчета perf, выглядит как случайные (но на самом деле согласованные) узкие места для некоторых операций (скажем, умножение и суммирование по двум векторам вышеуказанных измерений некоторым немного сложным способом, например, некоторым расширением по самому внутреннему измерению), но нет узких мест для аналогичных. Похоже, это связано с различными ошибками, связанными с хранилищем, которые наводят меня на мысль, что скомпилированный код на самом деле не оптимизирован для таких больших массивов. Для справки, в настоящее время я выполняю вычисления на AMD Ryzen 3900 с одним физическим ядром на поток; алгоритм распараллеливается по существу на «верхнем» уровне (вся значительная арифметика и тому подобное выполняется каждым ядром индивидуально).

Итак, по сути, вопрос в том, какой должна быть моя стратегия повышения производительности? У меня есть две основные идеи: одна из них — заменить переменные измерения макросами, которые я устанавливаю и компилирую во время выполнения с помощью моего запланированного мастер-скрипта. Насколько я понимаю, это не проблема со стороны реализации. Таким образом, по крайней мере, компилятор будет иметь информацию о размерах в числовом выражении, хотя я не знаю, насколько компилятор будет использовать этот тип информации. Приветствуется любой вклад.

Второй подход, о котором я могу подумать, был бы, в основном, если у меня есть какие-либо другие способы сообщить компилятору: «эй, это большое число, поэтому этот массив будет большим, обрабатывайте соответственно», что позволяет ему учитывать это? В данный момент я использую GCC, но открыт для использования других компиляторов.

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

Примером того, как выглядит фрагмент моего кода со вставленными общими параметрами, может быть что-то вроде

 for(int j = 0;j<ALL_3D_SPACE;j  )
{
    for (int k = 0; k< DIM_4_1; k  )
    {
        for (int l = 0; l< DIM_4_2; l  )
        {
            REDUCED_SUM[j*DIM_4_1  k]  = EXPANDED_SUM[j*DIM_4_2*DIM_4_1 k*DIM_4_2 l]*COEFFS[j*DIM_4_2 l];
        }   
    }
}   
  

Различные структуры данных объявляются стандартным способом pointer-malloc, например, следуя приведенному выше макетному примеру:

 double * EXPANDED_SUM, *COEFFS, REDUCED_SUM;
EXPANDED_SUM = (double*) malloc(sizeof(double)*ALL_3D_SPACE*DIM_4_2*DIM_4_1);
COEFFS = (double*) malloc(sizeof(double)*ALL_3D_SPACE*DIM_4_2);
REDUCED_SUM = (double*) malloc(sizeof(double)*ALL_3D_SPACE*DIM_4_1);
  

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

В ожидаемом варианте использования пользователь вводит набор из ~ 100 2D-проекций примерно такого размера nX*nY*DIM_4_1 , размерных и других параметров, где ALL_3D_SPACE = nX*nY*nZ и DIM_4_1 порядка 10-20, а nX, nY и nZ — все около 50-100. Ожидаемый результат будет (3 1) общими реконструкциями размера ALL_3D_SPACE*(DIM_4_2 2) , где DIM_4_2 имеет порядок 5-10. В настоящее время ввод и вывод обрабатываются как текстовые файлы. Обратите внимание, что любые сравнения с входными данными являются очень небольшой частью кода и что подавляющее большинство из них — это арифметическое / числовое дифференцирование по приведенным выше строкам. Фактическая основная функция ошибок, которая обрабатывает почти всю обработку, принимает прогнозы и текущую оценку выходных данных в качестве входных данных и при необходимости выдает ошибку, а также градиенты для лучшей оценки выходных данных для использования оптимизирующей процедурой.

Если вы используете массивы такого размера, я предлагаю хранить их в куче или в виде глобальных переменных. Стек взорвется с такими размерами