улучшить местность и уменьшить загрязнение кэша при реализации реконструкции медицинского образа

Question

Я провожу исследование для моего университета, связанное с алгоритмом реконструкции изображения для медицинского использования.

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

for (lor=lor0[mypid]; lor <= lor1[mypid]; lor++)
{
  LOR_X = P.symmLOR[lor].x;
  LOR_Y = P.symmLOR[lor].y;
  LOR_XY = P.symmLOR[lor].xy;
  lor_z = P.symmLOR[lor].z;
  LOR_Z_X = P.symmLOR[lor_z].x;
  LOR_Z_Y = P.symmLOR[lor_z].y;
  LOR_Z_XY = P.symmLOR[lor_z].xy;  

  s0 = P.a2r[lor];
  s1 = P.a2r[lor+1];

  for (s=s0; s < s1; s++)
  {
    pixel     = P.a2b[s];
    v         = P.a2p[s]; 

    b[lor]    += v * x[pixel];

    p          = P.symm_Xpixel[pixel];
    b[LOR_X]  += v * x[p];

    p          = P.symm_Ypixel[pixel];
    b[LOR_Y]  += v * x[p];

    p          = P.symm_XYpixel[pixel];
    b[LOR_XY] += v * x[p];


    // do Z symmetry.
    pixel_z    = P.symm_Zpixel[pixel];
    b[lor_z]  += v * x[pixel_z];


    p          = P.symm_Xpixel[pixel_z];
    b[LOR_Z_X]  += v * x[p];


    p          = P.symm_Ypixel[pixel_z];
    b[LOR_Z_Y]  += v * x[p];

    p          = P.symm_XYpixel[pixel_z];
    b[LOR_Z_XY] += v * x[p];

   }

}

для тех, кто хочет знать, в коде реализована функция пересылки MLEM , и все переменные FLOAT .

После нескольких тестов я заметил, что большая задержка была в этой части кода. (Вы знаете, правило 90 - 10).

Позже я использовал Papi (http://cl.cs.utk.edu/papi/) для измерения пропусков L1D-кэша. Как я и думал, Papi подтверждает, что производительность снижается из-за большого количества пропусков, особенно для произвольного доступа к вектору b (огромного размера).

Чтение информации в Интернете. Мне известны только два варианта повышения производительности: улучшение локальности данных или уменьшение загрязнения данных.

Чтобы сделать первое улучшение, я попытаюсь изменить код для поддержки кэширования, как это было предложено Ульрихом Дреппером на Что должен знать каждый программист о памяти (www.akkadia.org /drepper/cpumemory.pdf) A.1 Умножение матриц.

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

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

Есть ли способ загрузить значение из вектора b с помощью SIMD-инструкции без использования кэша?

Также можно использовать функцию типа void _mm_stream_ps (float * p, __m128 a) для хранения ОДНОГО значения с плавающей запятой в векторе b без загрязнения кэша?

Я не могу использовать _mm_stream_ps, потому что всегда храню 4 числа с плавающей запятой, но доступ к вектору b явно случайный.

Я бы хотел быть ясным в моей дилемме.

Дополнительная информация: v - это значение столбца хранилища Sparse Matrix в формате CRS. Я понимаю, что можно было бы провести другую оптимизацию, если бы я попытался изменить формат CRS на другой, однако, как я уже говорил, я провел несколько тестов в течение нескольких месяцев, и я знаю, что снижение производительности связано со случайным доступом к вектору b. из 400.000.000 L1D Пропуски Я могу перейти к 100 ~ Пропуски, когда не сохраняю в векторе b.

Спасибо.

Answer 1

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

• Объявить границы для внешнего цикла как const перед циклом.
• Объявите все переменные, которые вы можете (все LOR_..) как локальные переменные, что-то вроде: float LOR_X = P.symmLOR[lor].x; или size_t s0 = P.a2r[lor];
• Это также, в частности, для цикла переменные, если у вас есть современный, совместимый с C99, компилятор: for (size_t s=s0; s < s1; s++)
• Отдельная загрузка и хранение для вашего b вектор. Расположение предметов что вы получаете доступ, там, не зависит на s. Так что создайте локальную переменную для держать фактическое значение для всех отдельные случаи, которые вы обрабатываете перед внутренним циклом, обновите эти локальные переменные внутри внутреннего цикл и сохранить результаты после внутренний цикл.
• Возможно, отделить свой внутренний цикл в несколько. Индексные вычисления сравнительно дешево, а затем ваш Система может лучше распознать потоковый доступ к некоторым из ваших векторы.
• Посмотрите на ассемблере, что ваш Компилятор производит и идентифицирует код для внутреннего цикла. Эксперимент А немного сдвинуть как можно больше "дальних" нагрузок и хранит из этого цикла.

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

Answer 2

Я даже не буду притворяться, что знаю, что делает код :) Но одной возможной причиной некоторого дополнительного доступа к памяти является алиасинг: если компилятор не может быть уверен, что b, x, иразличные массивы P.symm не перекрываются, тогда запись в b будет влиять на то, как считывания из x и P.symm могут быть запланированы.Если компилятор особенно пессимистичен, он может даже заставить поля P быть повторно извлеченными из памяти.Все это будет способствовать отсутствию кеша, которое вы видите.Два простых способа улучшить это:

1. Использовать __restrict на b.Это гарантирует, что b не перекрывает другие массивы, поэтому запись в него не повлияет на чтение (или запись) из других массивов.

2. Переупорядочьте все так, чтобы все чтениясначала P.symm, затем чтение x, затем, наконец, все записи в b.Это должно сломать некоторые зависимости в чтениях и компилятор запланирует чтение из P.symm параллельно, затем чтения из x параллельно, и, надеюсь, делать записи в b разумно.

Еще одна стилистическая вещь (которая поможет с пунктом №2) - не так многократно использовать переменные p.Нет причин, по которым вы не можете, например, p_x, p_y, p_xy и т. Д., И это упростит переупорядочение кода.

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

Надеюсь, это поможет.

Answer 3

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

Вместо загрузки всех значений, необходимых из вектора B, во временные переменные, выполните всю внутреннюю переменную.цикл for при обновлении этих временных переменных затем записывает временные переменные обратно в вектор B.

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

Answer 4

Это хорошие ответы, и я бы спросил, почему так много индексации?по значениям индекса, которые не сильно меняются локально?

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