Russian Qt Forum
Ноябрь 01, 2024, 06:44
Добро пожаловать,
Гость
. Пожалуйста,
войдите
или
зарегистрируйтесь
.
Вам не пришло
письмо с кодом активации?
1 час
1 день
1 неделя
1 месяц
Навсегда
Войти
Начало
Форум
WIKI (Вики)
FAQ
Помощь
Поиск
Войти
Регистрация
Russian Qt Forum
>
Forum
>
Qt
>
Общие вопросы
>
Параллельные вычисления (проблемы)
Страниц: [
1
]
2
3
Вниз
« предыдущая тема
следующая тема »
Печать
Автор
Тема: Параллельные вычисления (проблемы) (Прочитано 22224 раз)
Igors
Джедай : наставник для всех
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
Гость
Re: Параллельные вычисления (проблемы)
«
Ответ #1 :
Декабрь 08, 2009, 23:20 »
Цитата: 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 и.т.п. Но эффект остается.
Идеи, опыт, эрудиция?
Спасибо
Какая там общая память (shared memory) в задаче и для семафор? Один промах в cache (memory-miss) стоит очень много вычислений! Эрудиция моя такая: на семафорах он ждёт страницу из общей или дальней памяти, а все вычисления происходят в презагруженных регистрах или презагруженной cache.
То есть, критическая роль в данном случае - это скорость памяти а не процессора.
Записан
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: Параллельные вычисления (проблемы)
«
Ответ #2 :
Декабрь 08, 2009, 23:45 »
Цитата: npkitsul от Декабрь 08, 2009, 23:20
Какая там общая память (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
Гость
Re: Параллельные вычисления (проблемы)
«
Ответ #3 :
Декабрь 09, 2009, 00:45 »
Мои мысли по данному вопросу складываются из двух твоих тем: про GetPixel и потокобезопастностm простых операций.... Может я и ошибаюсь....
Мне кажется, что такое поведение складывается из-за того, что сами задачи, которые выполняют нити ничтожны по сравнению с оверхедом от использования методов синхронизации. Т.е. если нить, грубо говоря, делает пару умножений и пару сложений и при этом использует операции синхронизации (тот же mutex), то ты больше времени тратишь на переключения контекста и ожидание, чем на сами вычисления. Думаю по этому и однопоточная версия выполняется быстрее.
Наверное лучше нагружать нити посильнее, например обрабатывать не по одному пикселю, а массивами пикселей. Играясь с размерами массивов, можно будет подбирать оптимальную нагрузку на ядра. Кстати, я уже предлагал такое решение в теме про GetPixel.
Записан
niXman
Гость
Re: Параллельные вычисления (проблемы)
«
Ответ #4 :
Декабрь 09, 2009, 03:51 »
Сделать программу многопоточной, не значит сделать ее распределенной!
Покажи диаграмму ниток, взаимодействия. Расскажи как используются общие ресурсы(если они есть).
Записан
kuzulis
Джедай : наставник для всех
Offline
Сообщений: 2812
Re: Параллельные вычисления (проблемы)
«
Ответ #5 :
Декабрь 09, 2009, 08:23 »
[crasy mode]
Тут наверное нужно переползать на CPU Е2К и подобные.
Этот проц, исходя из пиара, может реально параллельно считать
[/crasy mode]
Записан
ArchLinux x86_64 / Win10 64 bit
west
Гость
Re: Параллельные вычисления (проблемы)
«
Ответ #6 :
Декабрь 09, 2009, 09:40 »
Согласен с BRE, и исходя из собственного опыта, при планировании параллельных вычислений (распределённых тем более) необходимо учитывать накладные расходы на синхронизацию. Сравни свои тесты и реальную математику на предмет нахождения в вычислительном процессе без вызова методов синхронизации, может какие выводы получатся сами собой. Иногда может быть выгоднее подготовить исходные данные для каждой нити/процесса в собственном сегменте памяти, и потом провести вычисления, чем обеспечивать синхронизацию по доступу.
Записан
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: Параллельные вычисления (проблемы)
«
Ответ #7 :
Декабрь 09, 2009, 14:41 »
Цитата: BRE от Декабрь 09, 2009, 00:45
Мои мысли по данному вопросу складываются из двух твоих тем: про 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
Гость
Re: Параллельные вычисления (проблемы)
«
Ответ #8 :
Декабрь 09, 2009, 15:26 »
А сколько потоков создает ваша программа?
Записан
BRE
Гость
Re: Параллельные вычисления (проблемы)
«
Ответ #9 :
Декабрь 09, 2009, 15:35 »
Igors, а ты не смотрел в сторону OpenMP? Конечно, если есть такая возможность.
Записан
niXman
Гость
Re: Параллельные вычисления (проблемы)
«
Ответ #10 :
Декабрь 09, 2009, 15:44 »
2
BRE
На его картинке, показанно 223 потока
Надеюсь что его потоков много меньше
Если же его потоков большенство, то тут в серьез стОит задуматься над другим алгоритмом.
Записан
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: Параллельные вычисления (проблемы)
«
Ответ #11 :
Декабрь 09, 2009, 16:05 »
Цитата: niXman от Декабрь 09, 2009, 15:44
2
BRE
На его картинке, показанно 223 потока
Надеюсь что его потоков много меньше
Если же его потоков большенство, то тут в серьез стОит задуматься над другим алгоритмом.
Это просто Activity Monitor показывает все threads в системе. Я предлагаю пользователю ввести число ниток, по умолчанию = числу процессоров. То есть в данном случае - всего 4. (+главная)
Цитата: BRE от Декабрь 09, 2009, 15:35
Igors, а ты не смотрел в сторону OpenMP? Конечно, если есть такая возможность.
Возможность есть, у XCode это даже 1 из опций компилятора (правда не знаю про Вындоуз). Почему не смотрю - не понимаю как он может здесь помочь, я вижу какие места не могут быть распараллелены. Базовый механизм один для всех (может я неправ)
Записан
Авварон
Джедай : наставник для всех
Offline
Сообщений: 3260
Re: Параллельные вычисления (проблемы)
«
Ответ #12 :
Декабрь 09, 2009, 17:02 »
openMP есть в студии... насчет мингв не знаю.
Записан
BRE
Гость
Re: Параллельные вычисления (проблемы)
«
Ответ #13 :
Декабрь 10, 2009, 10:56 »
Цитата: Igors от Декабрь 09, 2009, 16:05
Почему не смотрю - не понимаю как он может здесь помочь, я вижу какие места не могут быть распараллелены.
IMHO, помочь он может на этапе исследования и проектирования алгоритма. Можно оптимизировать алгоритм для лучшего распараллеливания и быстро проверять результат, не задумываясь о многих низкоуровневых вещах. А когда алгоритм будет устраивать, при наличии времени и желания, можно его переписать с использованием низкоуровневых штучек.
Записан
Igors
Джедай : наставник для всех
Offline
Сообщений: 11445
Re: Параллельные вычисления (проблемы)
«
Ответ #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
Вверх
Печать
« предыдущая тема
следующая тема »
Перейти в:
Пожалуйста, выберите назначение:
-----------------------------
Qt
-----------------------------
=> Вопросы новичков
=> Уроки и статьи
=> Установка, сборка, отладка, тестирование
=> Общие вопросы
=> Пользовательский интерфейс (GUI)
=> Qt Quick
=> Model-View (MV)
=> Базы данных
=> Работа с сетью
=> Многопоточное программирование, процессы
=> Мультимедиа
=> 2D и 3D графика
=> OpenGL
=> Печать
=> Интернационализация, локализация
=> QSS
=> XML
=> Qt Script, QtWebKit
=> ActiveX
=> Qt Embedded
=> Дополнительные компоненты
=> Кладовая готовых решений
=> Вклад сообщества в Qt
=> Qt-инструментарий
-----------------------------
Программирование
-----------------------------
=> Общий
=> С/C++
=> Python
=> Алгоритмы
=> Базы данных
=> Разработка игр
-----------------------------
Компиляторы и платформы
-----------------------------
=> Linux
=> Windows
=> Mac OS X
=> Компиляторы
===> Visual C++
-----------------------------
Разное
-----------------------------
=> Новости
===> Новости Qt сообщества
===> Новости IT сферы
=> Говорилка
=> Юмор
=> Объявления
Загружается...