Повышение уровня параллелизма с помощью обхода или удаления искусственно внесенных зависимостей

Expose Parallelism by Avoiding or Removing Artificial Dependencies [Eng., PDF 186KB]

Введение

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

Описание проблемы

Хотя использование многопоточности - важный фактор повышения производительности, не менее важно убедиться в том, что каждый из потоков работает эффективно. Большинство компиляторов делают основную часть этой работы, однако часто бывает полезным, чтобы программист сам внес изменения в исходный код, для повышения производительности с помощью повторного использования данных и выбора таких инструкций, которые эффективно работают на данной машине. К сожалению, методы, которые повышают производительность последовательного кода, могут непредумышленно вносить зависимости данных, которые затрудняют получение дополнительной производительности через многопоточность.

Одним из примеров этого является повторное использование промежуточных результатов для того, чтобы избежать повторных вычислений. Например, смягчение изображения с помощью размытия достигается через замену каждого пикселя изображения средним взвешенным соседних пикселей, включая текущий. Приведенный псевдокод описывает размывающий шаблон 3х3:

for each pixel in (imageIn)
  sum = value of pixel
  // compute the average of 9 pixels from imageIn
  for each neighbor of (pixel)
    sum += value of neighbor
  // store the resulting value in imageOut
  pixelOut = sum / 9
Тот факт, что значение каждого пикселя участвует во множестве вычислений, позволяет повторно использовать данные. В следующем псевдокоде промежуточные результаты рассчитываются и используются трижды, что приводит к лучшей последовательной производительности:

subroutine BlurLine (lineIn, lineOut)
  for each pixel j in (lineIn)
    // compute the average of 3 pixels from line
    // and store the resulting value in lineout
    pixelOut = (pixel j-1 + pixel j + pixel j+1) / 3

declare lineCache[3]
lineCache[0] = 0
BlurLine (line 1 of imageIn, lineCache[1])
for each line i in (imageIn)
  BlurLine (line i+1 of imageIn, lineCache[i mod 3])
  lineSums = lineCache[0] + lineCache[1] + lineCache[2]
  lineOut = lineSums / 3
Такая оптимизация вносит зависимость между вычислениями соседних строк итогового изображения. Если попытаться выполнять итерации данного цикла параллельно, то эти зависимости приведут к неправильному результату.

Еще один пример – указатели внутри цикла:

ptr = &someArray[0]
for (i = 0; i < N; i++)
{
  Compute (ptr);  
  ptr++;
}
Увеличивая ptr, код потенциально использует быструю операцию регистрового инкремента и избегает расходов по вычислению someArray[i]в каждой итерации. Хотя каждый вызов данного расчета может выполняться независимо от остальных, данный указатель вносит явную зависимость: его значение в каждой итерации зависит от значения в прошлой итерации.

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

В данной статье описаны методики для эффективного применения параллелизма в таких трудных ситуациях.

Рекомендации

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

Чтобы эффективно распараллелить операцию размытия, рассмотрим деление изображения на части - блоки фиксированной величины. Алгоритм размытия позволяет независимо обрабатывать блоки данных. Следующий псевдокод иллюстрирует использование разбиения изображения:

// One time operation:
// Decompose the image into non-overlapping blocks.
blockList = Decompose (image, xRes, yRes)

foreach (block in blockList)
{
BlurBlock (block, imageIn, imageOut)
}
Существующий код размытия целого изображения можно использовать в реализации BlurBlock. Использование OpenMP или явных потоков для параллельной работы с множественными блоками дает все преимущества многопоточности и сохраняет изначальное оптимизированное ядро.

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

ptr = &someArray[0]
for (i = 0; i < N; i++)
{
  Compute (ptr[i]);
}
Отметим, что оригинальная оптимизация, хотя и небольшая, при этом не теряется. Компиляторы часто агрессивно оптимизируют расчеты с индексами, используя инкрементные или другие быстрые операции, повышая как последовательную, так и параллельную производительность.

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

Описанная выше блоковая технология является частью более общей методики, называемой «доменная декомпозиция». После такой декомпозиции каждый поток независимо работает на одном или более доменов. В некоторых ситуациях природа алгоритмов и данных указывает, что объем работы в каждом домене будет практически постоянным. В других случаях количество работы может зависеть от конкретного домена. В этом случае, если количество доменов равно количеству потоков, то параллельная производительность может ограничиваться разбалансированностью нагрузки. В общем случае будет лучше, если количество доменов сравнительно велико по сравнению с количеством потоков. Это позволит применить такие методы, как динамическое планирование, для баланса нагрузки между потоками.

Указания по применению

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

Применение блоковых алгоритмов иногда может нарушить возможности компилятора отличать данные с альтернативными декларациями (aliased) от обычных. Если после применения разбиения на блоки компилятор больше не может определить, какие из данных имеют только одну декларацию, то производительность может пострадать. Для явного запрещения алиасинга можно использовать оператор restrict. Применение интерпроцедурных оптимизаций также помогает компилятору обнаруживать неалиасные данные.

For more complete information about compiler optimizations, see our Optimization Notice.