Параллельные вычисления (проблемы)

[Igors]

Добрый вечер

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

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

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

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

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

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

Спасибо

[npkitsul]

Добрый вечер

Занимаюсь задействованием всех процессоров для долгих вычислений и столкнулся с проблемой.
Процессор 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]

Какая там общая память (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]

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

[niXman]

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

[kuzulis]

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

[west]

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

[Igors]

Мои мысли по данному вопросу складываются из двух твоих тем: про 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]

А сколько потоков создает ваша программа?

[BRE]

Igors, а ты не смотрел в сторону OpenMP? Конечно, если есть такая возможность.

[niXman]

2BRE
На его картинке, показанно 223 потока Надеюсь что его потоков много меньше
Если же его потоков большенство, то тут в серьез стОит задуматься над другим алгоритмом.

[Igors]

2BRE
На его картинке, показанно 223 потока Надеюсь что его потоков много меньше
Если же его потоков большенство, то тут в серьез стОит задуматься над другим алгоритмом.

Это просто Activity Monitor показывает все threads в системе. Я предлагаю пользователю ввести число ниток, по умолчанию = числу процессоров. То есть в данном случае - всего 4. (+главная)

Igors, а ты не смотрел в сторону OpenMP? Конечно, если есть такая возможность.

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

[Авварон]

openMP есть в студии... насчет мингв не знаю.

[BRE]

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

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

[Igors]

Добрый день

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

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

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

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