Russian Qt Forum

Qt => Общие вопросы => Тема начата: Igors от Декабрь 08, 2009, 21:45



Название: Параллельные вычисления (проблемы)
Отправлено: Igors от Декабрь 08, 2009, 21:45
Добрый вечер

Занимаюсь задействованием всех процессоров для долгих вычислений и столкнулся с проблемой.
Процессор Intel Xeon (2 процессора по 2 ядра).  Сделал механизм для ниток, семафоры - все необходимое. Результаты получаются такие:

1) Подставляю "тестовые расчеты" (т.е. проверяю сам механизм). Результаты разумные: на 4-х нитках время более чем в 2 раза меньше (по сравнению с начальной "безниточной" версией) . Понимаю что не все распараллелено, да что-то еще съедят семафоры, так что нормально.

2)  Подставляю "рабочие расчеты" (как они в задаче). Результат - время на 4-х нитках даже несколько БОЛЬШЕ исходного. Хотя все вычисления выполняются правильно, результаты совпадают. В чем дело? Смотрю в tools (OSX). CPU Sampler (по простому говоря профайлер) показывает - время ожидания на семафорах резко возросло. Activity Monitor показывает - значительная часть процессорного времени была съедена системой - непонятно для чего.

Но самое забавное - при использовании профайлера/tools время становится .. заметно меньше! (на 25% как минимум). Перепроверил много раз.

Понимаю что "нужно смотреть расчеты". Ну это сотни файлов и привести их здесь нет возможности. Да и что смотреть? Разумеется я все упростил как мог: отключил I/O, все вызовы OC и.т.п. Но эффект остается.

Идеи, опыт, эрудиция?

Спасибо


Название: Re: Параллельные вычисления (проблемы)
Отправлено: npkitsul от Декабрь 08, 2009, 23:20
Добрый вечер

Занимаюсь задействованием всех процессоров для долгих вычислений и столкнулся с проблемой.
Процессор Intel Xeon (2 процессора по 2 ядра).  Сделал механизм для ниток, семафоры - все необходимое. Результаты получаются такие:

1) Подставляю "тестовые расчеты" (т.е. проверяю сам механизм). Результаты разумные: на 4-х нитках время более чем в 2 раза меньше (по сравнению с начальной "безниточной" версией) . Понимаю что не все распараллелено, да что-то еще съедят семафоры, так что нормально.

2)  Подставляю "рабочие расчеты" (как они в задаче). Результат - время на 4-х нитках даже несколько БОЛЬШЕ исходного. Хотя все вычисления выполняются правильно, результаты совпадают. В чем дело? Смотрю в tools (OSX). CPU Sampler (по простому говоря профайлер) показывает - время ожидания на семафорах резко возросло. Activity Monitor показывает - значительная часть процессорного времени была съедена системой - непонятно для чего.

Но самое забавное - при использовании профайлера/tools время становится .. заметно меньше! (на 25% как минимум). Перепроверил много раз.

Понимаю что "нужно смотреть расчеты". Ну это сотни файлов и привести их здесь нет возможности. Да и что смотреть? Разумеется я все упростил как мог: отключил I/O, все вызовы OC и.т.п. Но эффект остается.

Идеи, опыт, эрудиция?

Спасибо

Какая там общая память (shared memory) в задаче и для семафор? Один промах в cache (memory-miss) стоит очень много вычислений! Эрудиция моя такая: на семафорах он ждёт страницу из общей или дальней памяти, а все вычисления происходят в презагруженных регистрах или презагруженной cache.

То есть, критическая роль в данном случае - это скорость памяти а не процессора.

 ??? 





Название: Re: Параллельные вычисления (проблемы)
Отправлено: Igors от Декабрь 08, 2009, 23:45
Какая там общая память (shared memory) в задаче и для семафор? Один промах в cache (memory-miss) стоит очень много вычислений! Эрудиция моя такая: на семафорах он ждёт страницу из общей или дальней памяти, а все вычисления происходят в презагруженных регистрах или презагруженной cache.

То есть, критическая роль в данном случае - это скорость памяти а не процессора.
 ??? 
Понял, отвечаю. Shared memory в задаче есть но для тестирования полностью отключена. Все происходит в памяти процесса. Были проверены 3 варианта семафоров (OSX)

1) sem_open (BSD named semaphore)
2) semaphore_create (POSIX семафор если не путаю)
3) QSemaphore (Qt)

1 и 2 дают тот же результат, 3 немного слабее - но общая картина та же.


Название: Re: Параллельные вычисления (проблемы)
Отправлено: BRE от Декабрь 09, 2009, 00:45
Мои мысли по данному вопросу складываются из двух твоих тем: про GetPixel и потокобезопастностm простых операций.... Может я и ошибаюсь....
Мне кажется, что такое поведение складывается из-за того, что сами задачи, которые выполняют нити ничтожны по сравнению с оверхедом от использования методов синхронизации. Т.е. если нить, грубо говоря, делает пару умножений и пару сложений и при этом использует операции синхронизации (тот же mutex), то ты больше времени тратишь на переключения контекста и ожидание, чем на сами вычисления. Думаю по этому и однопоточная версия выполняется быстрее.
Наверное лучше нагружать нити посильнее, например обрабатывать не по одному пикселю, а массивами пикселей. Играясь с размерами массивов, можно будет подбирать оптимальную нагрузку на ядра. Кстати, я уже предлагал такое решение в теме про GetPixel.


Название: Re: Параллельные вычисления (проблемы)
Отправлено: niXman от Декабрь 09, 2009, 03:51
Сделать программу многопоточной, не значит сделать ее распределенной!
Покажи диаграмму ниток, взаимодействия. Расскажи как используются общие ресурсы(если они есть).


Название: Re: Параллельные вычисления (проблемы)
Отправлено: kuzulis от Декабрь 09, 2009, 08:23
[crasy mode]
Тут наверное нужно переползать на CPU Е2К и подобные.
Этот проц, исходя из пиара, может реально параллельно считать
[/crasy mode]
:)


Название: Re: Параллельные вычисления (проблемы)
Отправлено: west от Декабрь 09, 2009, 09:40
Согласен с BRE, и исходя из собственного опыта, при планировании параллельных вычислений (распределённых тем более) необходимо учитывать накладные расходы на синхронизацию. Сравни свои тесты и реальную математику на предмет нахождения в вычислительном процессе без вызова методов синхронизации, может какие выводы получатся сами собой. Иногда может быть выгоднее подготовить исходные данные для каждой нити/процесса в собственном сегменте памяти, и потом провести вычисления, чем обеспечивать синхронизацию по доступу.


Название: Re: Параллельные вычисления (проблемы)
Отправлено: Igors от Декабрь 09, 2009, 14:41
Мои мысли по данному вопросу складываются из двух твоих тем: про GetPixel и потокобезопастностm простых операций.... Может я и ошибаюсь....
Мне кажется, что такое поведение складывается из-за того, что сами задачи, которые выполняют нити ничтожны по сравнению с оверхедом от использования методов синхронизации. Т.е. если нить, грубо говоря, делает пару умножений и пару сложений и при этом использует операции синхронизации (тот же mutex), то ты больше времени тратишь на переключения контекста и ожидание, чем на сами вычисления. Думаю по этому и однопоточная версия выполняется быстрее.
Наверное лучше нагружать нити посильнее, например обрабатывать не по одному пикселю, а массивами пикселей. Играясь с размерами массивов, можно будет подбирать оптимальную нагрузку на ядра. Кстати, я уже предлагал такое решение в теме про GetPixel.
Ну если бы можно было все разбить на N независимых кусков и дать каждой нитке по куску - я бы с удовольствием так и сделал. Как говорил классик "съесть конечно он бы съел да только кто ж ему даст?" :) Многие (самые трудоемкие) данные пикселей интерполируются, зависят друг от друга. Простой пример: есть квадрат из пикселей, напр. 4х4. Посчитали углы, посмотрели разброс значений. Достаточно мал - отлично, пошли дальше. Нет - разбиваем на 4 суб-квадрата и парим каждый. Расчет данных одного пикселя совсем не сводится к вычислению текстур (картинок) - это просто фрагмент расчета который должен быть thread-safe. Для каждого пикселя производится 200 и более расчетов (выбросов лучей). Они-то и потребляют 95% (и более) всего времени. Вот я и делаю чтобы эти 200 выполнялись в разных нитках. Понимаю что др. подходы также возможны, но каждый имеет свои минусы. Например, разбив все пиксели на какие-то "большие квадраты/полосы" я получу головную боль с их "сшивкой". Плюс эти квадраты могут требовать совершенно разных вычислений.

Разумеется, расчеты объединены в "пачки" и я могу варьировать ее размер. Трудоемкость одного пикселя: 80К пикселей рассчитываются за 32 сек (1 процессор). Общие ресурсы - для простоты скажем "отсутсвуют". Диаграмма нагрузки (4 нитки) здесь http://www.2shared.com/file/9838740/b1147927/Picture_2.html (http://www.2shared.com/file/9838740/b1147927/Picture_2.html)


Название: Re: Параллельные вычисления (проблемы)
Отправлено: niXman от Декабрь 09, 2009, 15:26
А сколько потоков создает ваша программа?


Название: Re: Параллельные вычисления (проблемы)
Отправлено: BRE от Декабрь 09, 2009, 15:35
Igors, а ты не смотрел в сторону OpenMP? Конечно, если есть такая возможность.


Название: Re: Параллельные вычисления (проблемы)
Отправлено: niXman от Декабрь 09, 2009, 15:44
2BRE
На его картинке, показанно 223 потока :o Надеюсь что его потоков много меньше ;)
Если же его потоков большенство, то тут в серьез стОит задуматься над другим алгоритмом.


Название: Re: Параллельные вычисления (проблемы)
Отправлено: Igors от Декабрь 09, 2009, 16:05
2BRE
На его картинке, показанно 223 потока :o Надеюсь что его потоков много меньше ;)
Если же его потоков большенство, то тут в серьез стОит задуматься над другим алгоритмом.
:) Это просто Activity Monitor показывает все threads в системе. Я предлагаю пользователю ввести число ниток, по умолчанию = числу процессоров. То есть в данном случае - всего 4. (+главная)

Igors, а ты не смотрел в сторону OpenMP? Конечно, если есть такая возможность.
Возможность есть, у XCode это даже 1 из опций компилятора (правда не знаю про Вындоуз). Почему не смотрю - не понимаю как он может здесь помочь, я вижу какие места не могут быть распараллелены. Базовый механизм один для всех (может я неправ)


Название: Re: Параллельные вычисления (проблемы)
Отправлено: Авварон от Декабрь 09, 2009, 17:02
openMP есть в студии... насчет мингв не знаю.


Название: Re: Параллельные вычисления (проблемы)
Отправлено: BRE от Декабрь 10, 2009, 10:56
Почему не смотрю - не понимаю как он может здесь помочь, я вижу какие места не могут быть распараллелены.
IMHO, помочь он может на этапе исследования и проектирования алгоритма. Можно оптимизировать алгоритм для лучшего распараллеливания и быстро проверять результат, не задумываясь о многих низкоуровневых вещах. А когда алгоритм будет устраивать, при наличии времени и желания, можно его переписать с использованием низкоуровневых штучек.


Название: Re: Параллельные вычисления (проблемы)
Отправлено: Igors от Декабрь 10, 2009, 13:27
Добрый день

Подсобрал статистику http://www.2shared.com/file/9869897/e1de3de1/stat.html (http://www.2shared.com/file/9869897/e1de3de1/stat.html) (к сожалению, прикрепить здесь не удается).

Запущены 4 нитки. Для каждой точки выполняется N расчетов (первая колонка таблицы). Расчеты могут быть более или менее трудоемкие (таблицы 1, 2 и 3) в зависимости от объема исходных данных. В таблицах представлены худшие (для меня) варианты. Когда 1000 вычислений на точку и/или каждый расчет трудоемок - все хорошо, наступает эффект "в разы". А вот когда вычислений маловато - проблемы.

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

Чего-то важного я здесь не понимаю. Может быть, поизучать исходники OpenMP - других идей пока нет.



Название: Re: Параллельные вычисления (проблемы)
Отправлено: vaprele07 от Декабрь 11, 2009, 05:11
Вот здесь много материалов по теме: http://software.intel.com/ru-ru/


Название: Re: Параллельные вычисления (проблемы)
Отправлено: niXman от Декабрь 11, 2009, 06:33
Табличку скачать не получается :(


Название: Re: Параллельные вычисления (проблемы)
Отправлено: niXman от Декабрь 11, 2009, 07:10
Все равно многого не понятно.

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

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

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

Выбирайте.


Название: Re: Параллельные вычисления (проблемы)
Отправлено: Igors от Декабрь 11, 2009, 07:43
У меня в чистом виде реализован вариант "2". Ну можно еще добавить что относительно небольшая часть расчетов (5-10%) не распараллелена и выполняется главной ниткой


Название: Re: Параллельные вычисления (проблемы)
Отправлено: niXman от Декабрь 11, 2009, 07:54
Если это так, и принцип делегирования реализован !правильно!, то самое время подумать над кластером.


п.с.
могу помочь.


Название: Re: Параллельные вычисления (проблемы)
Отправлено: Igors от Декабрь 11, 2009, 08:31
Если это так, и принцип делегирования реализован !правильно!, то самое время подумать над кластером.
Про делегирование ничего не слышал :) Главная нитка помещает задачи в очередь. Как только в очереди окажется N (размер кластера) задач - все рабочие нитки снимаются со своих семафоров и начинают брать задачи из очереди (также кластером из N задач). N в моих руках, управляемо. Послав все задачи, главная нитка засыпает на семафоре но перед этим досылает еще по одной "псевдо-задаче" (для каждой рабочей нитки). Получив задачу-терминатор, рабочая нитка засыпает на своем семафоре. Последняя засыпающая открывает семафор главной нитке. Это все :)


Название: Re: Параллельные вычисления (проблемы)
Отправлено: niXman от Декабрь 11, 2009, 08:39
Из описания правильно.
Допустим. У вас 4 ядра, и 4 рабочих нитки.
1. скажите, рабочие нитки загружены на 100 процентов?
2. сколько раз(за время своей жизни), в сумме, происходит блокировка разделяемого ресурса нитками?


Название: Re: Параллельные вычисления (проблемы)
Отправлено: niXman от Декабрь 11, 2009, 09:44
Цитировать
Про делегирование ничего не слышал
Из википедии:
Цитировать
# передача, уступка полномочий. Делегирование - такая организация работы, при которой руководитель распределяет между подчиненными конкретные задания. Также делегирование есть передача подчиненному задачи или действия, которое должен осуществить руководитель, вместе с необходимыми для этого полномочиями.

Цитировать
Как только в очереди окажется N (размер кластера)
Под словом кластер, я подразумевал аппаратный кластер. Во имя достижения большего кол-ва аппаратных процессоров.


Название: Re: Параллельные вычисления (проблемы)
Отправлено: niXman от Декабрь 11, 2009, 09:48
Вот здесь много материалов по теме: http://software.intel.com/ru-ru/
Вот было любопытно, посмотреть, что вы такого порекомендовали. Но, оказалось, что ваша ссылка, равносильна этой: http://www.*

Очень познавательно ;)


Название: Re: Параллельные вычисления (проблемы)
Отправлено: Igors от Декабрь 11, 2009, 14:02
Из описания правильно.
Допустим. У вас 4 ядра, и 4 рабочих нитки.
1. скажите, рабочие нитки загружены на 100 процентов?
2. сколько раз(за время своей жизни), в сумме, происходит блокировка разделяемого ресурса нитками?
1) Увы, совсем не на 100% (принимаем 100% = все 4 загружены до упора). Типичная загрузка только 65-70%, а очень хотелось бы большего. Остальное idle, а когда N неудачно -  появляется довольно мощный overhead (монитор показывает его как "system" красным).

2) Блокировки конечно есть для I/O и.т.п. Но в тестах реально работает только одна - для выборки ниткой следующей пачки задач из очереди. Реализация QSpinLockLock/QSpinLockUnlock (это OSX аналог QAtomicInt).

Тесты показывают что "львиная доля" тратится на подъем/усыпление рабочих ниток на семафорах. Не вижу возможности сделать 1 семафор для всех ниток (получается каждая должна иметь свой) да и неясно помогло бы это - ведь усыпление все равно будет.


Название: Re: Параллельные вычисления (проблемы)
Отправлено: Igors от Декабрь 18, 2009, 15:38
Добрый день

Попробовал OpenMP. Впечатление очень приятное, библиотека сделана по уму, пользоваться легко и удобно, ничего переделывать не пришлось.

К сожалению, OpenMP никак не быстрее ручной реализации. На совсем маленьких расчетах время примерно то же самое (хотя с OpenMP диаграмма загрузки выглядит гораздо стабильнее). А вот с увеличением числа расчетов OpenMP начинает проигрывать. Не так уж много но заметно, например 87 секунд против 76  :'(

Сейчас качаю Intel компилятор, хочу проверить еще с ним.


Название: Re: Параллельные вычисления (проблемы)
Отправлено: niXman от Декабрь 18, 2009, 16:39
не думаю что твое видение решения, окажется верным. тут проблема в архитектуре/реализации.


Название: Re: Параллельные вычисления (проблемы)
Отправлено: Igors от Декабрь 18, 2009, 17:15
не думаю что твое видение решения, окажется верным. тут проблема в архитектуре/реализации.
Трудно понять, мудрено выражаетесь :) Так в архитектуре или реализации? (часто это употребляется в смысле стратегия/тактика). Насчет видения - ну я пока ничего не вижу, буду благодарен за свежие идеи (пусть и экспериментальные).


Название: Re: Параллельные вычисления (проблемы)
Отправлено: niXman от Декабрь 18, 2009, 18:13
Цитировать
Трудно понять, мудрено выражаетесь
даже и не думал.

Цитировать
Так в архитектуре или реализации?
возможно и там, и там..

Цитировать
(часто это употребляется в смысле стратегия/тактика)
не понял сравнения.

Цитировать
Насчет видения - ну я пока ничего не вижу, буду благодарен за свежие идеи (пусть и экспериментальные).
я лишь хочу сказать, что многие думают: вот заюзаю MPI[CH] и все, избавлю себя от проблем с синхронизацией/распределением/реализацией в такой-то задаче. но нет, если бы все было так просто ;)

я задавал вопрос:
Цитировать
сколько раз(за время своей жизни), в сумме, происходит блокировка разделяемого ресурса нитками?
вы так и не ответили.


Название: Re: Параллельные вычисления (проблемы)
Отправлено: Igors от Декабрь 18, 2009, 18:48
сколько раз(за время своей жизни), в сумме, происходит блокировка разделяемого ресурса нитками?
Извините за возможные непонятки, мой ответ был
2) Блокировки конечно есть для I/O и.т.п. Но в тестах реально работает только одна - для выборки ниткой следующей пачки задач из очереди. Реализация QSpinLockLock/QSpinLockUnlock (это OSX аналог QAtomicInt).
То есть при использовании OpenMP блокировок нет вообще, все потери на синхронизации. Повторюсь также про трудоемкость 1 пикселя (для вычисления которого привлекаются все нитки)
32 sec / (80 * 1000) 


Название: Re: Параллельные вычисления (проблемы)
Отправлено: Igors от Декабрь 20, 2009, 14:07
Проверил с компилятором Intel
Результаты для 4 ниток, 2 процессора Intel Xeon по 2 ядра
Цитировать
                 1_100   1_200  1_400  2_100  2_200  2_400
---------------------------------------------------------
No threads      16       32       63      62      118     230
Custom impl.   19       28       46      50      79      135
GCC + OMP      18       28       48      57      87      149
Intel + OMP     10       18       35      32      57      108
В таблице время в секундах, колонка соответствует 1 тесту, напр. 2_200 значит: тест 2, выполняется 200 вычислений на точку. Сами тесты (1 и 2) отличаются трудоемкостью единичного вычисления.

Придется использовать Intel хотя забот с ним более чем достаточно и компилирует он совсем не быстро. Досадно что GCC проигрывает с таким разгромным счетом, но надо заметить что это OSX, т.е. POSIX. Судя по исходникам GCC 4.4, для POSIX используется простая реализация семафора (mutex + pthread_cond_wait). Для Linux используется гораздо более изощренная техника фьютексов (futex) так что там результат может быть совсем иным.


Название: Re: Параллельные вычисления (проблемы)
Отправлено: niXman от Декабрь 20, 2009, 14:37
что такое OMP ?
Цитировать
Досадно что GCC проигрывает с таким разгромным счетом, но надо заметить что это OSX, т.е. POSIX. Судя по исходникам GCC 4.4, для POSIX используется простая реализация семафора (mutex + pthread_cond_wait)
смею заметить, то, что если время тратиться на синхронизацию, то это говорить лишь об одном - слишком часто происходит блокировка/деблокировка. в этом случае, не стоит расчитывать на чудеса, а спроектировать иной алгоритм.

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


Название: Re: Параллельные вычисления (проблемы)
Отправлено: Igors от Декабрь 20, 2009, 15:29
что такое OMP ?
OpenMP  :)
смею заметить, то, что если время тратиться на синхронизацию, то это говорить лишь об одном - слишком часто происходит блокировка/деблокировка. в этом случае, не стоит расчитывать на чудеса, а спроектировать иной алгоритм.
В данном конкретном случае под "синхронизацией" понимается "старт и финиш" задачи для которой привлекаются все нитки. Это расчет одного пикселя который может состоять из N (100, 200, 400 в тестах) подрасчетов (распределяемых между нитками). Каждый подрасчет может быть более или менее трудоемким (зависит от многих исходных данных). Проблемы возникают из-за того что время расчета пикселя достаточно мало (меньше миллисекунды).

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

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


Название: Re: Параллельные вычисления (проблемы)
Отправлено: vaprele07 от Декабрь 20, 2009, 17:15
Код:
#include <qtest.h>

#include <omp.h>

class TestBenchmark : public QObject
{
Q_OBJECT

    void func() {}

private slots:

void simple2();
void simple2_omp();

void simple4();
void simple4_omp();
};

#define MAX_K 100000000


void TestBenchmark::simple2()
{
long i, j;

QBENCHMARK_ONCE {
for (i = 0; i < MAX_K; i++)
{
for (j = 0; j < 5; j++){
                            func();
                            func();
}
}
}
}

void TestBenchmark::simple2_omp()
{
long i, j;

QBENCHMARK_ONCE {
#pragma omp parallel for private(i, j, sum)
for (i = 0; i < MAX_K; i++)
{
for (j = 0; j < 5; j++){
                                func();
                                func();
}
}
}
}

void TestBenchmark::simple4()
{
long i, j;
QBENCHMARK_ONCE {
for (i = 0; i < MAX_K; i++)
{
for (j = 0; j < 10; j++){
                                func();
}
}
}
}


void TestBenchmark::simple4_omp()
{
long i, j;
QBENCHMARK_ONCE {
#pragma omp parallel for private(i, j, sum)
for (i = 0; i < MAX_K; i++)
{
for (j = 0; j < 10; j++){
                                func();
}
}
}
}

QTEST_MAIN(TestBenchmark)
#include "main.moc"
Заметьте разницу ;)



Название: Re: Параллельные вычисления (проблемы)
Отправлено: vaprele07 от Декабрь 20, 2009, 17:28
Код:
void TestBenchmark::simple3()
{
        long k, i, j;

        QBENCHMARK_ONCE {
                for (i = 0; i < MAX_K; i++)
                {

                        for (k = 0; k < 5; k++)

                            func();

                        for (j = 0; j < 5; j++)

                            func();
                }
        }
}

void TestBenchmark::simple3_omp()
{
        long k, i, j;

        QBENCHMARK_ONCE {
                #pragma omp parallel for private(i, j, k)
                for (i = 0; i < MAX_K; i++)
                {
                    for (k = 0; k < 5; k++)

                        func();

                    for (j = 0; j < 5; j++)

                        func();
                }
        }
}
А вот еще интереснее )
Вроде и инструкций больше а все равно быстрее))


Название: Re: Параллельные вычисления (проблемы)
Отправлено: Igors от Декабрь 20, 2009, 17:33
Заметьте разницу ;)
При таком шикарном MAX_K (100000000) пройдет все что угодно - вот только где ж мне его взять если по задаче это от 50 до 5000  :'(


Название: Re: Параллельные вычисления (проблемы)
Отправлено: niXman от Декабрь 20, 2009, 19:23
Цитировать
Понятно что заманчиво давать ниткам расчеты целых пикселей (а не "подрасчеты"). Но при этом мне надо гораздо больше распараллелить, появляется очень много массивов (где была 1 переменная), появляются конструкции указателей *** (понимаемые самим автором с трудом).
1. Данные общие?
2. Во время работы одной нитки, другая может изменить общие данные?
3. Если все же синхронизация ниток с общими данными не нужна, может каждой нитке передать копию данных? Ну и что, что памяти съест больше. Ныньче 2-4 гига на процесс не трагедия)

Цитировать
Вот например "запекание фотонной карты"
Даже спрашивать не стану, что это такое :o
оО...какой я все же темный ;D


Название: Re: Параллельные вычисления (проблемы)
Отправлено: Igors от Декабрь 20, 2009, 20:30
1. Данные общие?
2. Во время работы одной нитки, другая может изменить общие данные?
3. Если все же синхронизация ниток с общими данными не нужна, может каждой нитке передать копию данных? Ну и что, что памяти съест больше. Ныньче 2-4 гига на процесс не трагедия)
Подавляющее большинство исходных данных общие и "только чтение" (хотя они и требуют блокировок для подгрузки с диска). Проблема в том что нет четкой "мишени" - в начале расчетов неизвестно какие пиксели и как считать, это выясняется по ходу дела. Сетевой вариант задачи живет долго и вполне счастливо, он разбивает результат(изображение) на N полос (или кадров) и запускает свою копию для каждой части. При этом однако дублируются все исходные данные. Склеивание полос, передача исходных данных по сети и результатов обратно - все это в сумме не так уж дешево. Часть данных строится динамически и это будет тоже повторено N раз. Уязвимое место - относительно короткие расчеты (особенно превью), тогда запуск сетевой бандуры не окупает себя.  В общем пришли к банальной истине: задача должна иметь как сетевой вариант, так и поддержку multi-threading  :)



Название: Re: Параллельные вычисления (проблемы)
Отправлено: niXman от Декабрь 20, 2009, 20:43
Цитировать
(хотя они и требуют блокировок для подгрузки с диска)
а почему не загрузить весь файл за раз?

Цитировать
Сетевой вариант задачи живет долго и вполне счастливо
это вы про кластер?

Цитировать
Склеивание полос, передача исходных данных по сети и результатов обратно - все это в сумме не так уж дешево.
Согласен. Я так понял, это все же кластер?

Цитировать
В общем пришли к банальной истине: задача должна иметь как сетевой вариант, так и поддержку multi-threading
А этот алгоритм, правильно спроектирован? Может корень проблемы в нем? Возможно вы боретесь с последствиями неправильной разработки алгоритма?


Название: Re: Параллельные вычисления (проблемы)
Отправлено: Igors от Декабрь 20, 2009, 21:43
а почему не загрузить весь файл за раз?
Все файлы грузятся полностью и читаются всего 1 раз. Но не для всех распакованное содержимое держится в памяти, для многих оно хранится постранично. Если памяти достаточно - все будет в памяти, нет - будет подкачиваться с диска.

Согласен. Я так понял, это все же кластер?
Не имею цели подколоть, но не знаю что такое кластер (здесь), правда :) Ну например, выходной имедж имеет 1000 строк. Пользователь может задать число полос, напр 4. Значит будут запущены 4 копии. Первая получит задачу сделать первые 250 строк, вторая - вторые 250 и.т.п. Возможно какая-то копия не рассчитает ни одного пикселя - нечего считать, но результат (черный пустой имедж) все равно будет. То есть разбивается "тупо", по числу строк. Но эта задача давно решена и успешно эксплуатируется.

А этот алгоритм, правильно спроектирован? Может корень проблемы в нем? Возможно вы боретесь с последствиями неправильной разработки алгоритма?
Да кто ж его знает где этот корень?  :) Очень может быть я выбрал не лучший путь но в данном случае любой имеет трудности.

niXman, мы весьма отвлеклись от темы, давайте переключаться в личку, с удовольствием отвечу на любые Ваши вопросы.


Название: Re: Параллельные вычисления (проблемы)
Отправлено: niXman от Декабрь 20, 2009, 23:04
Цитировать
Не имею цели подколоть, но не знаю что такое кластер (здесь), правда
Вот кластер http://ru.wikipedia.org/wiki/IBM_Roadrunner (http://ru.wikipedia.org/wiki/IBM_Roadrunner)
Ничё так, комп :)

Цитировать
niXman, мы весьма отвлеклись от темы
разве? :) я то думал мы все о той же проблеме рассуждаем ;)

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


Название: Re: Параллельные вычисления (проблемы)
Отправлено: vaprele07 от Декабрь 21, 2009, 05:20
http://www.realcoding.net/articles/optimizatsiya-tsikla.html
http://parallel.ru/ куча литературы есть и по openMP
Это я не для автора а для широких масс  ::)