Добро пожаловать, гость | Вход | Зарегистрироваться

Почему компиляторы не любят параллельный код?

Alexey Kukanov (Intel) (1 пост(а)) 03.03.2008 09:55

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

За последнее время мне довелось наблюдать несколько таких попыток, в которых параллельный код был написан при помощи библиотеки Threading Building Blocks (TBB). К удивлению экспериментаторов, их простые параллельные программы порой не только не показывают ускорения по сравнению с обычной, последовательной версией, но даже и проигрывают в скорости! И далеко не всегда автор может (или хочет) разобраться, что к чему.

Разбираться приходилось мне, как одному из разработчиков TBB. А поскольку мне уже не раз предлагали вести сетевой журнал-блог на Intel Software Network, я в конце концов решил попытаться, и начать с анализа таких вот примеров. Они, с одной стороны, просты и понятны: не каждый готов начать параллельные эксперименты со сколь-нибудь сложной программы, а написать цикл, суммирующий элементы вектора – дело недолгое. С другой стороны, они весьма познавательны, причём порой именно в силу простоты.

Начну как раз с суммы элементов вектора. Вопрос о том, почему столь простая программа медленнее в параллельной TBB версии, чем в не-параллельной, возник на форуме TBB (см. тему “performance of parallel_for”). Я приведу здесь лишь часть кода:

#define REAL double
#define MAX 10000000
class SumFoo {
    REAL *a;
    REAL sum;
    ...
    void operator()(const blocked_range<size_t>& r) {
        REAL *arr = a;
        for(size_t i=r.begin(); i!=r.end(); i++) sum+=arr[i];
    }
};
void ParallelSumFoo(REAL a[], size_t n, size_t gs) {
    SumFoo sf(a,n);
    parallel_reduce(blocked_range<size_t>(0,n,gs), sf);
    ...
}
class SerialApplyFoo {
    REAL *a;
    size_t len;
    double sum;
public :
    SerialApplyFoo(REAL *array, size_t length) : a(array), len(length){
        sum = 0.0;
        for(size_t i=0; i<len; i++)
            sum += a[i];
    }
    …
};
int main() {
    task_scheduler_init init;
    REAL *array = new REAL[MAX];
    ...
    SerialApplyFoo sf(array, MAX);
    ParallelSumFoo(array, MAX, GRAINSIZE);
    ...
}

На двухъядерном процессоре Intel® Core® 2 Duo, вместо ожидаемого двукратного ускорения, параллельный код работал почти вдвое медленнее, чем последовательный; на моём ноутбуке, к примеру, 0.08 сек против 0.044. В чём дело?

Прежде всего, давайте посмотрим, а что произойдёт, если параллельный код запустить последовательно, в одном потоке. С TBB это можно сделать двумя способами: либо явно указав количество потоков (в нашем случае, один) конструктору объекта инициализации библиотеки task_scheduler_init, либо установив параллельному алгоритму так называемый «размер зерна» (grain size) равным количеству итераций цикла. Я воспользуюсь первым способом:

    task_scheduler_init init(1);

Результат может показаться неожиданным: 0.21 сек, почти впятеро медленнее, чем исходный последовательный код! Такое замедление явно не из-за использования TBB. Неудивительно, что и на двух ядрах нет выигрыша.

Всё дело в оптимизации, проводимой компилятором. Цикл суммирования в последовательной версии очень прост для оптимизации; компилятор знает о нём всё, начиная от константной длины (передача через аргумент для компилятора не помеха), заканчивая тем, что результат sum должен быть виден только по выходу из конструктора. Поэтому он может сгенерировать очень эффективный машинный код, к примеру, вот такой (я использовал Visual Studio* 2005):

            fldz
            lea      eax, DWORD PTR [edi+010h]
            mov      ecx, 0x2625A0h
main+0x105: fadd     QWORD PTR [eax-16]
            add      eax, 0x20h
            sub      ecx, 0x1h
            fadd     QWORD PTR [eax-40]
            fadd     QWORD PTR [eax-32]
            fadd     QWORD PTR [eax-24]
            jnz      main+0x105

0x2625A0 – это 2500000, четверть длины массива. Компилятор развернул четыре итерации цикла в одну, снизив расходы на обслуживание цикла. Промежуточные результаты вычислений накапливаются в регистре процессора, и только конечный результат будет записан в память. На каждую итерацию исходного цикла ровно одна операция чтения данных из памяти.

В случае использования TBB для компилятора всё не так просто. Начало и конец цикла определяются полями объекта, переданного по ссылке, длина цикла во время компиляции неизвестна, результат накапливается в поле данных “живого” объекта. Компилятор вынужденно более консервативен, и результат не замедлил сказаться:

execute+0x57: fld      QWORD PTR [edi]
              add      ecx, 0x1h
              fadd     QWORD PTR [edx+08h]
              add      edi, 0x8h
              fstp     QWORD PTR [edx+08h]
              cmp      ecx, DWORD PTR [esi+08h]
              jnz      execute+0x57

Здесь одна итерация цикла обрабатывает один элемент, но при этом задействует 3 операции чтения (!) и одну – записи. Помимо элемента данных, каждый раз подгружаются из памяти значение конца цикла для сравнения и промежуточная сумма, которая затем сохраняется и на следующей итерации подгружается снова.

Изложив всё это в форуме, я добавил, что тест «отдаёт предпочтение» последовательному коду, и этим, боюсь, направил автора не в ту сторону. В попытке улучшить тест, автор ввёл чтение размера массива с клавиатуры и заменил в не-параллельном коде объект на функцию:

REAL SerialSum(REAL *a_, unsigned long int start, unsigned long int end) {
    REAL sum = 0.0;
    for(unsigned long int i=start; i<end; i++)
        sum += a_[i];
    return sum;
}

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

    void operator()(blocked_range<size_t> &r) {
        REAL local_sum = 0;
        const size_t end = r.end();
        for(size_t i=r.begin(); i!=end; i++)
            local_sum+=a[i];
        sum += local_sum;
    }

И вот какой получен машинный код:

              fldz
execute+0x58: fadd        qword ptr [edx]
              add         edx,8
              sub         ecx,1
              jne         execute+58h
              fadd        qword ptr [edi+8]
              fstp        qword ptr [edi+8]

Последние две инструкции – добавление локального результата к полю sum. Как и в последовательном коде, мы получили одно обращение к памяти на итерацию, и это сразу сказалось на скорости: теперь параллельный код выполняется 0.033 сек на двухъядерном процессоре. Ускорение достигнуто, но с коэффициентом 1.33, а не 2. Почему? В этом попробуем разобраться в следующий раз.

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

Категории: Многоядерность, Разработка софта

Комментарии (9)

По Intel® Software Network Blogs » Why a simple test can get parallel slowdown в Март 4th, 2008 в 09:58

[...] Those who read Russian may follow this link. [...]

По mt2 в Март 14th, 2008 в 04:08

Здравствуйте, Алексей!
Материал впечатляет. Но, как я уже говорил, проблема может быть не только в TBB, но и в том, что он завязан на С++ -- один из наиболее сложных языков как для программистов, так и для компиляторов. Кстати, мы с Вами договаривались обсудить возможность переноса TBB в Delphi, Вы еще не раздумали?

-- Михаил (mt2).

По Alexey Kukanov (Intel) в Март 14th, 2008 в 04:47

"А была бы шерсть, были бы блохи"
Извините, Михаил, не удержался.
Кстати, Вы не видели на TopCoder-е новый параллельный контест, на сей раз от AMD? Так вот, там ограничение ещё более жёсткое - кроме C++, никакой другой язык использовать нельзя. Это к сведению, выводов из этого никаких не делаю.
Про то обсуждение я помню и не раздумал; да вот времени всё никак не найду. Тем не менее, в списке задач этот пункт есть.

По mt2 в Март 19th, 2008 в 00:51

Может, я предубежден против AMD, но я даже процессоры их не использую (только от Intel)... так что Вы подкрепили мое предубеждение

-- Михаил.

По В.Любченко в Апрель 15th, 2008 в 19:38

Здравствуйте, Алексей!
Cайт PARALLEL.RU в рамках созданного совместного Центра МГУ-Intel анонсировал перспективные технологии параллельного программирования фирмы Intel (см. http://parallel.ru/russia/MSU-Intel/technology.html).
Почему-то среди перечисленных средств разработки параллельных программ и поддержки многопоточного программирования не была упомянута библиотека TBB. Это досадная оплошность или ... за этим скрывается что-то иное?
Скорее всего, для программирования кластерных систем TBB не рассчитана (а, с другой стороны, почему бы и нет?). Думаю, что в рамках отдельного "многоядерного узла" скорее всего предпочтительнее использовать TBB, чем упомянутые на сайте библиотеки реализации того же MPI или даже OpenMP.
--
С уважением,
Вячеслав

По Dmitry Oganezov (Intel) в Апрель 16th, 2008 в 13:51

Хороший вопрос, Вячеслав! Насколько я знаю, Алексей сейчас в командировке, и мне тоже интересно его мнение... Я со своей стороны попробую связаться с автором и высянить этот вопрос "с другой стороны".

Вопрос к вам - почему вы считаете, что TBB предпочтительнее OpenMP для кластеров?

По В.Любченко в Апрель 16th, 2008 в 22:32

Почему TBB, а не Open MP?
Речь не идет о подмене одной библиотеки другой. Именно для кластеров, думаю, последняя будет лучше. Просто потому, что пока еще последняя рассчитана именно на кластеры. А TBB предпочтительнее для программирования на отдельном узле кластера (многоядерном конечно). Хотя ничто, думаю, не мешает расширить применение TBB для кластеров, а OpenMP оптимизировать под многоядерность. Но все же лучше, когда каждому свое: TBB - узел кластера, OpenMP - уровень кластера.
Я не противопоставляю одно другому. Просто несколько "задело" то, что в силу каких-то причин кто-то, планируя "будущее" параллелизма, "выплеснул" за пределы параллельных вычислений TBB. Библиотеку, которая представляет собой уже достаточно сформировавшееся решение. Библиотеку, которая не менее параллельна, чем упомянутые в анонсе библиотеки и в которую, судя по ее возможностям, было вложено, думаю, немало сил и средств.
Можно и нужно, безусловно, осуждать и достоинства, и недостатки TBB, но никак не делать вид, что ее нет. Хотя бы потому, что это равносильно отрицанию определенных отличий в параллельном программировании уровня кластера и уровня узла кластера. В случае многоядерных систем последний сам становится неким «мини-кластером», но со своей спецификой параллельного программирования. И здесь нужны решения подобные TBB.

По Dmitry Oganezov (Intel) в Апрель 17th, 2008 в 16:04

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

И большое спасибо за развернутый ответ - полагаю, Алексей сейчас гордится собой

По vlubch в Апрель 28th, 2008 в 20:47

У него есть чем гордиться безусловно, но... Посмотрите на мой эксперимент по проверке параллельных свойств ТВВ (http://deeplab.ru/forum/topic.php?forum=6&topic=1&postid=1209194327#1209194327).
TBB не прошла тест на параллелизм. Но, справедливости ради, нужно уточнить, что не сама TBB, а та основа, на котороя она базируется - многопоточное програмирование. Хотя... как отделить одно от другого (TBB и многопоточность)?

Почему компиляторы не любят параллельный код?

Alexey Kukanov (Intel) (1 пост(а)) 03.03.2008 09:55

Категории: Многоядерность, Разработка софта

Комментарии (9)

А что думаете вы?