PARALLEL.RU

Дискуссионный клуб по параллельным вычислениям
Текущее время: 28 сен 20 13:13

Часовой пояс: UTC + 4 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 6 ] 
Автор Сообщение
 Заголовок сообщения: OpenMP в рекурсии
СообщениеДобавлено: 11 авг 08 15:45 
Не в сети

Зарегистрирован: 11 авг 08 15:27
Сообщения: 4
Попробовал я использовать директивы OpenMP в рекурсии и сильно разочаровался :(...

Параллелил я алгоритм Штрассена (быстрый алгоритм перемножения матриц). Перепробовал всё, что возможно и невозможно (реализовывал полную независимость по данным и инструкциям для потоков, выделял память под результаты перемножений заранее, оперируя в алгоритме только ссылками, изменял и увеличивал как мог параллельные секции, ставил условия - if - на выполнение директив с учётом размерности задачи и т.д. и т.п.), а результат один - с OpenMP всегда медленнее.

Может у кого есть положительный опыт использования OpenMP в рекурсии ?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: OpenMP в рекурсии
СообщениеДобавлено: 12 авг 08 11:44 
Не в сети

Зарегистрирован: 11 дек 02 19:37
Сообщения: 872
Откуда: НИВЦ МГУ
1. Непонятно, что значит "openmp в рекурсии"? Рекурсивный вызов внутри omp-конструкций? omp-конструкция внутри рекурсивного вызова (???) или что-то ещё?
2. А Вы уверены, что замедление происходит из-за рекурсивности алгоритма, а не из-за неэффективного распараллеливания?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: OpenMP в рекурсии
СообщениеДобавлено: 12 авг 08 14:54 
Не в сети

Зарегистрирован: 11 авг 08 15:27
Сообщения: 4
Serg_Zhum писал(а):
1. Непонятно, что значит "openmp в рекурсии"? Рекурсивный вызов внутри omp-конструкций? omp-конструкция внутри рекурсивного вызова (???) или что-то ещё?


На самом деле, пробовалось и то и то, - помимо этого ещё и вложенный параллелизм. Конечный результат неизменен.

Serg_Zhum писал(а):
2. А Вы уверены, что замедление происходит из-за рекурсивности алгоритма, а не из-за неэффективного распараллеливания?

Если бы я был бы в чём-то уверен, то не отписывался бы на форумах :).
Что касается лично меня, то с технологией OpenMP знаком не первый день и уже есть достаточный опыт, чтобы можно было что-то утверждать.
Если реализуется схема, при которой достигалась независимость по данным и инструкциям для потоков, то о какой неэффективности распараллеливания может быть речь ?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: OpenMP в рекурсии
СообщениеДобавлено: 12 авг 08 20:25 
Не в сети

Зарегистрирован: 11 дек 02 19:37
Сообщения: 872
Откуда: НИВЦ МГУ
Johnny писал(а):
На самом деле, пробовалось и то и то, - помимо этого ещё и вложенный параллелизм. Конечный результат неизменен.


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

Johnny писал(а):
Если бы я был бы в чём-то уверен, то не отписывался бы на форумах :).


Эх, все бы пользователи форума так :)

Johnny писал(а):
Если реализуется схема, при которой достигалась независимость по данным и инструкциям для потоков, то о какой неэффективности распараллеливания может быть речь ?

О самой разной. Конфликты в кэше, к примеру? А может число потоков из-за рекурсии (или чего-то ещё) стало больше числа ядер? Или наличие приватной памяти привело к своппингу?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: OpenMP в рекурсии
СообщениеДобавлено: 13 авг 08 8:27 
Не в сети

Зарегистрирован: 11 авг 08 15:27
Сообщения: 4
Serg_Zhum писал(а):
А пробовались варианты без вложенного параллелизма?

Конечно же... я имел в виду, что было перепробовано буквально всё, что позволяет сделать стандарт OpenMP.

Serg_Zhum писал(а):
Кроме того, я не уверен, что OMP-конструкции внутри рекурсивных функций будут работать. Хотя могу и ошибиться.

А почему нет? Что этому мешает? Попробуйте - убедитесь сами.

Serg_Zhum писал(а):
О самой разной. Конфликты в кэше, к примеру? ... Или наличие приватной памяти привело к своппингу?


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

Serg_Zhum писал(а):
А может число потоков из-за рекурсии (или чего-то ещё) стало больше числа ядер?

А вот это я недопонял...можете пояснить как это возможно ?

Единственное, к чему я ещё не прибегал, так это использование Thread Checker для анализа...видно, всё же придётся...

P.S. Специфика алгоритма Штрассена (да и не только) заключается в том, что каждый отдельно взятый вызов рекурсивной процедуры не содержит в себе массивных вычислений - они осуществляются крайне быстро по сравнению со временем работы всей программы. Корень проблемы заключается в том, что суммарное время работы программы накапливается из-за большого числа таких маловесных вычислительных задачек.
Я даже пробовал сделать развёртку нескольких вложений рекурсии - всё напрасно.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: OpenMP в рекурсии
СообщениеДобавлено: 25 авг 08 13:22 
Не в сети

Зарегистрирован: 11 дек 02 19:37
Сообщения: 872
Откуда: НИВЦ МГУ
Johnny писал(а):
Serg_Zhum писал(а):
А может число потоков из-за рекурсии (или чего-то ещё) стало больше числа ядер?

А вот это я недопонял...можете пояснить как это возможно ?

Вы заводите 10 нитей на 4 ядрах и получаете неприятности.

Johnny писал(а):
Единственное, к чему я ещё не прибегал, так это использование Thread Checker для анализа...видно, всё же придётся...

Если он есть в доступности - то обязательно надо.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Часовой пояс: UTC + 4 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB