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

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

Я застрял в чем-то до 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. Как я и думал, Папи подтверждает, что производительность снижается из-за большего количества промахов, особенно для произвольного доступа к вектору 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 — это значение столбца хранилища разреженных матриц в формате CRS. Я понимаю, что можно было бы сделать другую оптимизацию, если бы я попытался изменить формат CRS на другой, однако, как я уже говорил ранее, я провел несколько тестов в течение нескольких месяцев и знаю, что снижение производительности связано со случайным доступом к вектору b. от 400 000 000 промахов L1D я могу перейти к 100 ~ промахам, если я не сохраняю в векторе b.

Спасибо.


c optimization caching blocking simd
person Fbarisio    schedule 18.01.2011    source источник
comment
+1 за правильно сформулированный вопрос с большим количеством справочной информации и подробностей о том, что вы пробовали до сих пор.   -  person Paul R    schedule 19.01.2011

Ответы (4)


arrow_upward
2
arrow_downward

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

  • Объявите границы внешнего цикла как 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. Поэтому создайте локальную переменную для хранения фактического значения для всех отдельных случаев, которые вы обрабатываете до внутреннего цикла, обновляйте эти локальные переменные внутри внутреннего цикла и сохраняйте результаты после внутреннего цикла.
  • Возможно, разделите свой внутренний цикл на несколько. Вычисления индекса относительно дешевы, и тогда ваша система может лучше распознать потоковый доступ к некоторым из ваших векторов.
  • Посмотрите на ассемблер, созданный вашим компилятором, и определите код внутреннего цикла. Немного поэкспериментируйте, чтобы переместить как можно больше «дальних» загрузок и хранилищ из этого цикла.

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

person Jens Gustedt    schedule 19.01.2011
comment
Эй, Дженс, предложенные вами изменения помогли мне, потому что они действительно увеличили производительность, однако количество промахов кэша не уменьшилось. Я не знаю связи между этими подсказками компилятора и производительностью. Может пора сравнить ассемблер с objdump, я прав? - person Fbarisio; 02.02.2011
comment
Да и нет, не используйте objdump. Просто скомпилируйте напрямую с помощью -S или аналогичной опции, чтобы получить ассемблер. Это будет легче читать, чем реконструкция, которую сможет выполнить objdump. - person Jens Gustedt; 02.02.2011

arrow_upward
2
arrow_downward

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

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

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

person gravitron    schedule 18.01.2011
comment
Я пробовал это, но не работает, я не знаю почему, но если я выполняю присваивание вне внутреннего цикла, я получаю почти такое же количество промахов кэша, как если бы я выполнял присваивание внутри внутреннего цикла. Спасибо! - person Fbarisio; 19.01.2011
comment
не могли бы вы указать, сколько раз каждый цикл выполняется в среднем? если внутренний цикл выполняется небольшое количество раз, то это не будет большой экономией. Т.е. каковы средние значения для s0, s1, lor0[mypid],lor1[mypid]. - person gravitron; 19.01.2011
comment
Среднее выполнение внутреннего цикла 1136 и 72191 для внешнего цикла. Я хочу поблагодарить вас за обсуждение этой проблемы, я не знал, что было 35328 внутренних циклов с s0 равным s1. Может быть, это потому, что не было большой экономии, делая то, что вы предложили. Для 72191 раз, когда выполняется внешний цикл, только 72191 - 35328 = 36863 раза код фактически выполнил внутреннюю часть. - person Fbarisio; 02.02.2011
comment
Хм. Поскольку внутренний цикл пропускается очень много раз, возможно, стоит проверить этот случай, прежде чем выполнять 7 назначений LOR_x,y,... . Таким образом, ваш код сначала будет считывать значения s0 и s1 из их массива, а затем иметь if (s0 != s1) { делать все остальное}. Однако он оптимизирован для представленных значений, поэтому, если данные изменятся, эта оптимизация может увеличить стоимость, а не уменьшить ее. - person gravitron; 03.02.2011

arrow_upward
2
arrow_downward

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

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

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

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

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

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

person celion    schedule 18.01.2011
comment
Спасибо за помощь! Я попробую ограничить изменение, а потом выложу результаты. - person Fbarisio; 19.01.2011

arrow_upward
0
arrow_downward

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

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

person Mike Dunlavey    schedule 18.01.2011