Распараллеливание черного ящика.(ч.1)

Kirill Mavrodiev (Intel) (22 пост(а)) 26.10.2009 15:16

Существует точка зрения, что при распараллеливании неправильно рассматривать последовательно реализованную программу как черный ящик. Другими словами, необходимо знать алгоритмы, которые реализованы в данном пакете. С одной стороны, это правильно, ведь порой эффективнее заменить, существующий алгоритм на другой. На алгоритм, который хорошо ложиться на ту или иную архитектуру.
Я хочу рассказать о результате летнего школьника Интел-ННГУ 2009, т.е. о проекте, которым занимался студент, у которого я был руководителем. Задача стояла следующая: взять уже существующий проект и распараллелить его с помощью Intel(R) Parallel Studio, рассматривая его как черный ящик. А потом сравнить с параллельным вариантом разработчиков сэмпла. Главное условие было взять только последовательный вариант проекта и не смотреть параллельный вариант. Выбор остановился на сэмпле для Intel(R) TBB - Tachyon, у которого существует два параллельных варианта с использованием технологии Intel(R) TBB. (если установлен пакет "Intel(R) Parallel Studio", то солющен(Solution) можно найти тут: C:\Program Files\Intel\Parallel Studio\Composer\tbb\examples\parallel_for\tachyon). Это трассировщик лучей, один из результатов которого фрактал с тремя источниками освещения.

Стоит заметить, что 3 ноября будет проведен Онлайн Семинар "Intel(R) Parallel Studio Workflow" на базе Tachyon. Количество участников ограничено.
Первый Шаг в расспараллеливание - это найти наиболее часто используемый участок программы. Для этого использовался Intel(R) Parallel Amplifier. И для сравнения удобства и простоты работы Intel(R) VTune(TM) Performance Analyzer. Как Amplifier так и VTune указали на функции:
grid_intersect и sphere_intersect.

Анализ данных функций показывает, что они не совсем пригодны к распараллеливанию или тюнингу. Соответственно нужно найти либо родительские либо дочерние функции, которые содержат циклы.
Для VTune пришлось собрать профиль Call Graph, на что ушло порядка 13 минут накладных расходов (время работы последовательного варианта Tachyon 30 сек). И 1 час на анализ профиля. У Ampilfier-а использовался уже созданный профиль, что оказалось очень удобным:

В результате мы остановились на кандидате parallel_thread:

static void parallel_thread (void)
{

    unsigned int serial = 1;
	unsigned int mboxsize = sizeof(unsigned int)*(max_objectid() + 20);
    unsigned int * local_mbox = (unsigned int *) alloca(mboxsize);
	memset(local_mbox,0,mboxsize);

    for (int y = starty; y < stopy; y++) { {
        drawing_area drawing(startx, totaly-y, stopx-startx, 1);
        for (int x = startx; x next_frame()) return;
     }

}

И пока я дописываю следующий Блог, предлагаю Вам самим попытаться распараллелить.

Категории: Intel Software Network, Академическое сообщество, Графика, Конкурсы и мероприятия, Параллельное программирование, Разработка софта
Метки:

Пожалуйста, обратитесь к странице Уведомление об оптимизации для более подробной информации относительно производительности и оптимизации в программных продуктах компании Intel.

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

26.10.2009 06:32

yuryserdyuk
yuryserdyukВсего баллов:
5,200
коричневый пояс
 Кто хоть чуть-чуть представляет себе, что такое трассировка лучей,
сразу поймет что функции grid_intersect и sphere_intersect здесь не причем,
а надо искать место, где происходит цикл по изображению (пикселам).

С другой стороны, параллелизация здесь простейшая,
поскольку отдельные потоки никак не взаимодействуют друг с другом,
поэтому было бы интереснее и полезнее взять пример
со взаимодействием отдельных частей.
Показательный здесь пример - задача "Game Of Life" с Intel Threading Challenge 2007-2008,
где давался последовательный код на С++,
который нужно было распараллелить.
26.10.2009 06:45

Kirill Mavrodiev (Intel)
Kirill Mavrodiev (Intel)Всего баллов:
2,704
Зарегистрированный пользователь
 Возможно Вы правы. Но как я так и студент знали о трассирование лучей ровно столько, сколько написано на вики.
04.11.2009 23:55

Andrey Karpov
Andrey KarpovВсего баллов:
18,920
черный пояс
 To Kirill: А где можно скачать исходники этого проекта и промежуточные ошибочные варианты с распараллеливанием (которые были показаны на вебинаре)? Я хочу попробовать на них PVS-Studio.
05.11.2009 09:59

Kirill Mavrodiev (Intel)
Kirill Mavrodiev (Intel)Всего баллов:
2,704
Зарегистрированный пользователь
 2 Андрей: Я как раз заканчиваю блог, в котором и будет ссылка. Сегодня-завтра опубликую его.
09.11.2009 10:35

eustas
eustasВсего баллов:
1,965
Зарегистрированный пользователь
 Кстати, да! По дереву исполнения/потребления видно, что первое "проедание" времени идёт как-раз таки на render_one_pixel->trace ;-)

Обратная ссылка (6)


Оставить комментарий  

Для получения технической помощи посетите сайт службы поддержки.
Имя (обязательно)*

Электронная почта (обязательно; не будет отображено на этой странице)*

Ваш URL-адрес (необязательно)


Комментарий*