Russian Qt Forum
Ноябрь 26, 2024, 19:48 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: [1] 2 3   Вниз
  Печать  
Автор Тема: Параллельные вычисления (проблемы)  (Прочитано 22391 раз)
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« : Декабрь 08, 2009, 21:45 »

Добрый вечер

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

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

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

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

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

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

Спасибо
Записан
npkitsul
Гость
« Ответ #1 : Декабрь 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.

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

 Непонимающий 



Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #2 : Декабрь 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 немного слабее - но общая картина та же.
Записан
BRE
Гость
« Ответ #3 : Декабрь 09, 2009, 00:45 »

Мои мысли по данному вопросу складываются из двух твоих тем: про GetPixel и потокобезопастностm простых операций.... Может я и ошибаюсь....
Мне кажется, что такое поведение складывается из-за того, что сами задачи, которые выполняют нити ничтожны по сравнению с оверхедом от использования методов синхронизации. Т.е. если нить, грубо говоря, делает пару умножений и пару сложений и при этом использует операции синхронизации (тот же mutex), то ты больше времени тратишь на переключения контекста и ожидание, чем на сами вычисления. Думаю по этому и однопоточная версия выполняется быстрее.
Наверное лучше нагружать нити посильнее, например обрабатывать не по одному пикселю, а массивами пикселей. Играясь с размерами массивов, можно будет подбирать оптимальную нагрузку на ядра. Кстати, я уже предлагал такое решение в теме про GetPixel.
Записан
niXman
Гость
« Ответ #4 : Декабрь 09, 2009, 03:51 »

Сделать программу многопоточной, не значит сделать ее распределенной!
Покажи диаграмму ниток, взаимодействия. Расскажи как используются общие ресурсы(если они есть).
Записан
kuzulis
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2812


Просмотр профиля
« Ответ #5 : Декабрь 09, 2009, 08:23 »

[crasy mode]
Тут наверное нужно переползать на CPU Е2К и подобные.
Этот проц, исходя из пиара, может реально параллельно считать
[/crasy mode]
Улыбающийся
Записан

ArchLinux x86_64 / Win10 64 bit
west
Гость
« Ответ #6 : Декабрь 09, 2009, 09:40 »

Согласен с BRE, и исходя из собственного опыта, при планировании параллельных вычислений (распределённых тем более) необходимо учитывать накладные расходы на синхронизацию. Сравни свои тесты и реальную математику на предмет нахождения в вычислительном процессе без вызова методов синхронизации, может какие выводы получатся сами собой. Иногда может быть выгоднее подготовить исходные данные для каждой нити/процесса в собственном сегменте памяти, и потом провести вычисления, чем обеспечивать синхронизацию по доступу.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #7 : Декабрь 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
Записан
niXman
Гость
« Ответ #8 : Декабрь 09, 2009, 15:26 »

А сколько потоков создает ваша программа?
Записан
BRE
Гость
« Ответ #9 : Декабрь 09, 2009, 15:35 »

Igors, а ты не смотрел в сторону OpenMP? Конечно, если есть такая возможность.
Записан
niXman
Гость
« Ответ #10 : Декабрь 09, 2009, 15:44 »

2BRE
На его картинке, показанно 223 потока Шокированный Надеюсь что его потоков много меньше Подмигивающий
Если же его потоков большенство, то тут в серьез стОит задуматься над другим алгоритмом.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #11 : Декабрь 09, 2009, 16:05 »

2BRE
На его картинке, показанно 223 потока Шокированный Надеюсь что его потоков много меньше Подмигивающий
Если же его потоков большенство, то тут в серьез стОит задуматься над другим алгоритмом.
Улыбающийся Это просто Activity Monitor показывает все threads в системе. Я предлагаю пользователю ввести число ниток, по умолчанию = числу процессоров. То есть в данном случае - всего 4. (+главная)

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

Сообщений: 3260


Просмотр профиля
« Ответ #12 : Декабрь 09, 2009, 17:02 »

openMP есть в студии... насчет мингв не знаю.
Записан
BRE
Гость
« Ответ #13 : Декабрь 10, 2009, 10:56 »

Почему не смотрю - не понимаю как он может здесь помочь, я вижу какие места не могут быть распараллелены.
IMHO, помочь он может на этапе исследования и проектирования алгоритма. Можно оптимизировать алгоритм для лучшего распараллеливания и быстро проверять результат, не задумываясь о многих низкоуровневых вещах. А когда алгоритм будет устраивать, при наличии времени и желания, можно его переписать с использованием низкоуровневых штучек.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #14 : Декабрь 10, 2009, 13:27 »

Добрый день

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

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

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

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

Записан
Страниц: [1] 2 3   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.092 секунд. Запросов: 23.