Идеально распараллеливаемый цикл

На момент публикации этого поста конкурс уже наверняка закончится, так что в плане неспортивного поведения и помощи соперникам моя совесть чиста. В любом случае, излагаемые сведения едва ли станут откровением для кого-либо из участников. :)

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

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

Этот цикл используется почти всеми участниками, так как составляет часть референсного кода заполнения матрицы, предоставленного организаторами. Он осуществляет нормализацию матрицы:


for(int i = 0; i < dstSize; ++i) {

    pDst[i] -= mean;

}



Здесь pDst является указателем на (одномерный) массив, представляющий матрицу, dstSize - его длина, а mean - среднее значение элементов, вычисленное ранее.

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

Что ж, библиотека Intel Threading Building Blocks позволяет нам явно записать это свойство и воспользоваться всеми доступными ядрами всех доступных процессоров:


class Normalizer {

    int *m_pDst;

    int m_mean;

public:

    Normalizer(int *pDst, int mean) : m_pDst(pDst), m_mean(mean) {}


    void operator()(const blocked_range &r) const;

};


void Normalizer::operator()(const blocked_range &r) const {

    const int end = r.end();

    for(int i = r.begin(); i < end; ++i) {

	m_pDst[i] -= m_mean;

    }

}



И теперь заменить исходный цикл одной строкой:


parallel_for(blocked_range(0, dstSize), Normalizer(pDst, mean));



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

Как известно, компиляторы от Интел содержат мощный модуль автоматической векторизации циклов, и главное - не мешать им заниматься своим делом. Но зачастую нужно всё-таки немного помочь. Запустив компиляцию с опцией -vec-report3 узнаём, что он не смог векторизовать наш цикл - в цикле присутствуют зависимости. В самом деле, ведь m_pDst[i] -= m_mean; означает m_pDst[i] = m_pDst[i] - m_mean;, т.е. новое значение элемента зависит от значения другого элемента. Но подождите, ведь "другой элемент" - это всего лишь предыдущее значение того же самого элемента! Мы возьмём прежнее значение элемента, положим его в регистр, вычтем среднее и вернём туда где взяли - и можем сделать так для всего массива одновременно. Компилятор просто перестраховывается, так что давайте скажем ему так не делать в данном конкретном случае:


const int end = r.end();

#pragma ivdep

for(int i = r.begin(); i < end; ++i) {

    m_pDst[i] -= m_mean;

}



Но он снова не смог векторизовать этот цикл! На сей раз жалуется на слишком сложную адресацию, хотя куда уж проще - просто берём элементы массива по номеру, один за другим. Дело в том, что m_pDst - переменная-член класса, а значит на самом деле адресуется через неявный указатель this. Просто создадим локальные синонимы:


int *const pDst = m_pDst;

const int end = r.end();

const int mean = m_mean;

#pragma ivdep

for(int i = r.begin(); i < end; ++i) {

    pDst[i] -= mean;

}



Вуаля! Цикл успешно векторизован компилятором.

Разминку закончили. :)

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