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

Работаю я в MS VS 2005, использую openmp, который как известно этой студией поддерживается…. Тестирую на двух 2-ядерных процах: AMD и Intel.
Схема распараллеливаемого кода:

For (i)
            PrepareToDraw(i)
For (j)
            Draw(j)

Первый for — занимает в среднем 30% времени при последовательном выполнении.


Пробовал я распараллеливать софт 3мя способами:


1) for (i) Draw(i). Где Draw – это куча функций, которые сводятся в итоге к вызову Polyline(hdc, points(i)), где Polyline – это GDI-ный Polyline.
Я поставил #pragma omp parallel for, на Draw поставил критическую секцию (т.к. обращение к GDI + общий dc). Выигрыша не было никакого. Поразмыслив, я решил, что этого стоило ожидать, т.к. 90% времени тратится внутри самой GDi-функции, она непараллельна – ну и результата нет.
2) Я завёл 2 секции соответственно (#pragma omp parallel sections) для двух for соответственно. Конечно, вторая секция зависит от первой, имеет место некая конвеерность. Побился над синхронизацией и… получил совершенно мизерный выигрыш (около 2%). Странно, подумал я.
3) Тогда я распараллелил 1й блок – подготовка к рисованию. Этот блок тоже представляет собой for (i), где i меняется от 1 до 10-100 тысяч. Тело цикла – весьма затратный метод с выполнением разных вычислений и заполнений некоего массива. Шаги друг от друга не зависят. Поставил parallel for – выигрыш был порядка 1-2%. Ужас.

Я пробовал разное число потоков (от 2х и более), пробовал запрещать вложение (omp_set_nested) , без результата.

Отсюда у меня возникло 2 вопроса;



a) Поразмышляв над первым результатом — я подумал, а неужели распараллеливание GDI растеризации вообще невозможно? Неужели никто никогда не пробовал это сделать?
b) Поразмышляв над последними 2 результатами я заподозрил неладное. Тем более слышал страшные рассказы, что по Windows добиться прироста от 2х ядерного проца удаётся только на 10% (против 100% на Linux). Неужели в этом есть доля правды? Может есть какие-то трюки, заставляющие реально распараллеливать алгоритм под Windows?

p.s. Честно говоря, на amd процессоре у меня средняя загрузка проца около 20% — хотя там нет операций ввода-вывода — просто рекурсивные for с заполнением индексных массивов и пересчётом координат. Непонятно во-первых, почему такая маленькая загрузка. Ну и во-вторых, означает ли это, что в силу малой загруженности проца, добавление 2го потока на 2 ядре ничего не принесёт?


Вот и всё собственно,

Заранее благодарю!

Здравствуйте, Аноним, Вы писали:

А>a) Поразмышляв над первым результатом — я подумал, а неужели распараллеливание GDI растеризации вообще невозможно? Неужели никто никогда не пробовал это сделать?

А точно нельзя тупо использовать один hdc из разных потоков? Я сейчас не помню уже.. Но и не вижу принципиальных препятствий.
В любом случае, можно разбить на квадраты, для каждого — свой контекст, тогда можно рисовать параллельно.
В крайнем случае, можно отказаться от вызовов GDI, и написать свою функцию рисования линии в матрице пикселей.

А>b) Поразмышляв над последними 2 результатами я заподозрил неладное. Тем более слышал страшные рассказы, что по Windows добиться прироста от 2х ядерного проца удаётся только на 10% (против 100% на Linux). Неужели в этом есть доля правды? Может есть какие-то трюки, заставляющие реально распараллеливать алгоритм под Windows?

Не слышал про такое.

А>p.s. Честно говоря, на amd процессоре у меня средняя загрузка проца около 20% — хотя там нет операций ввода-вывода — просто рекурсивные for с заполнением индексных массивов и пересчётом координат. Непонятно во-первых, почему такая маленькая загрузка. Ну и во-вторых, означает ли это, что в силу малой загруженности проца, добавление 2го потока на 2 ядре ничего не принесёт?

Хм, может свопинг постоянный? Странно вообще-то.

Здравствуйте, Аноним, Вы писали:

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

Здравствуйте, SergH, Вы писали:

SH>В крайнем случае, можно отказаться от вызовов GDI, и написать свою функцию рисования линии в матрице пикселей.
Зачем самому?
http://antigrain.com/ никто не отменял.
Самому писать аналог мягко говоря глупо.

Здравствуйте, Ravlyk, Вы писали:

R>Здравствуйте, Аноним, Вы писали:

R>Распаралельте рисование нескольких кусков (2,4,...) изображения в локальные битмапы (лучше просто массивы пикселей), а затем их (уже готовые) выведите (скопируйте) на один общий dc.
R>При этом можно обойтись без блокировок (кроме вывода на общий dc).

Благодарю! Вспоминаю, что кажется когда-то давно в универе что-то подобное уже слышал — в качестве описания стандартного способа распараллеливания обработки изображений. Но почему-то я совсем забыл про эту возможность.. Благодарю от души за идею — мне кажется её реализовать будет не очень трудно + надеюсь на реальный прирост производительности.

Но вот сомневаюсь в 2х вещах:
1) — придётся осуществлять динамически выбор dc внутри функций. То есть код будет выглядеть так Polyline (DCs[get_num_thread()],points[...])- но надеюсь, что это не сильно затормозит работу.
2) Боюсь, что обращение к points (он общий для обоих кусков изображения) тоже может привести к блокировкам, а создавать 2 экземпляра points нежелательно.

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

Здравствуйте, Аноним, Вы писали:

А>2) Боюсь, что обращение к points (он общий для обоих кусков изображения) тоже может привести к блокировкам, а создавать 2 экземпляра points нежелательно.

Если из points во время растеризации будет только чтение, а запись туда будет заведомо завершена заранее, то делать блокировку не нужно.
Или я не понял о чем вы?

А>Боюсь, что в итоге придётся создать по отдельному экземпляру растеризатора на каждый кусок изображения, но это очень накладно будет.

Это зависит от реализации. Я делал несколько алгоритмов обработки изображений с таким распаралеливанием, без блокировок. Прирост есть, но не очень большой (что-то около 20%, уже точно не помню).

Здравствуйте, Аноним, Вы писали:

А>3) Тогда я распараллелил 1й блок – подготовка к рисованию. Этот блок тоже представляет собой for (i), где i меняется от 1 до 10-100 тысяч. Тело цикла – весьма затратный метод с выполнением разных вычислений и заполнений некоего массива. Шаги друг от друга не зависят. Поставил parallel for – выигрыш был порядка 1-2%. Ужас.

А в свойствах проекта поддержку OpenMP не забыл включить?

Здравствуйте, Ravlyk, Вы писали:

R>Здравствуйте, Аноним, Вы писали:

А>>2) Боюсь, что обращение к points (он общий для обоих кусков изображения) тоже может привести к блокировкам, а создавать 2 экземпляра points нежелательно.

R>Если из points во время растеризации будет только чтение, а запись туда будет заведомо завершена заранее, то делать блокировку не нужно.
R>Или я не понял о чем вы?

А>>Боюсь, что в итоге придётся создать по отдельному экземпляру растеризатора на каждый кусок изображения, но это очень накладно будет.

R>Это зависит от реализации. Я делал несколько алгоритмов обработки изображений с таким распаралеливанием, без блокировок. Прирост есть, но не очень большой (что-то около 20%, уже точно не помню).

Вот попробовал Ваш подход, вроде даже начинает работать. Алгоритм пришлось конечно перепахать сильно.
У меня в процессе работы возник вопрос: а что Вы делаете с теми объектами, которые лежат сразу в 2х фрагментах изображения? Или у Вас все объекты — примитивы типа отрезок/окружность?

Здравствуйте, Аноним, Вы писали:

А>Вот попробовал Ваш подход, вроде даже начинает работать. Алгоритм пришлось конечно перепахать сильно.
А>У меня в процессе работы возник вопрос: а что Вы делаете с теми объектами, которые лежат сразу в 2х фрагментах изображения? Или у Вас все объекты — примитивы типа отрезок/окружность?

Ну я точно такую задачу не решал, я делал обработку входного растрового изображения в выходное растровое. А в Вашем случае можно:
1. Разбить примитивы на 2...n частей, лежащих внутри одного фрагмента.
2. Обрабатывать примитивы во всех фрагметах, которые они пересекают, но только до той части, которая находится в пределах фрагмента.

А>Вот попробовал Ваш подход, вроде даже начинает работать. Алгоритм пришлось конечно перепахать сильно.
А>У меня в процессе работы возник вопрос: а что Вы делаете с теми объектами, которые лежат сразу в 2х фрагментах изображения? Или у Вас все объекты — примитивы типа отрезок/окружность?

Как вариант — разбивать не по фрагментам, а по слоям, а потом накладывать слои один-на-другой

Здравствуйте, <Аноним>, Вы писали:

А>Вот попробовал Ваш подход, вроде даже начинает работать. Алгоритм пришлось конечно перепахать сильно.
А>У меня в процессе работы возник вопрос: а что Вы делаете с теми объектами, которые лежат сразу в 2х фрагментах изображения? Или у Вас все объекты — примитивы типа отрезок/окружность?

Если дороже операция отрисовки, то смысла распараллеливать мало.
А если дороже операция растеризации, то может имеет смысл растеризовать каждый объект отдельно, а потом их просто по очереди отрисовывать в одном потоке.
То есть производить разделение не изображения а объектов.

Здравствуйте, tinytjan, Вы писали:

T>Здравствуйте, <Аноним>, Вы писали:

А>>Вот попробовал Ваш подход, вроде даже начинает работать. Алгоритм пришлось конечно перепахать сильно.
А>>У меня в процессе работы возник вопрос: а что Вы делаете с теми объектами, которые лежат сразу в 2х фрагментах изображения? Или у Вас все объекты — примитивы типа отрезок/окружность?

T>Если дороже операция отрисовки, то смысла распараллеливать мало.
T>А если дороже операция растеризации, то может имеет смысл растеризовать каждый объект отдельно, а потом их просто по очереди отрисовывать в одном потоке.
T>То есть производить разделение не изображения а объектов.

1) Операция отрисовки — самая дорогая. Почему тогда, по Вашему мнению не имеет смысла её распараллеливать?


2) Я кстати вчера частично доделал алгоритм и прироста не получил. Даже напротив на 20% медленнее. Причём профилировщик показал, что в параллельной версии 70% времени сожрало преобразование координат.. А раньше это было только 40%. Я тут подумываю — неужто подгрузка в КЭШ всё портит? Но я в этом профан, даже не знаю как с этим бороться.

3) У меня очень много данных (в основном координаты) лежит в памяти (больше 100Мб) — эти данные читаются, преобразовываются (преобразование координат), а затем передаются на отрисовку. Вот я и подозреваю, что после распараллеливания взаимодействие RAM и cache — стало торомозить...

И благодарю всех, кто откликнулся!!!!!!!!!!!!!!!!!!!!!!!!!!!

Здравствуйте, Аноним, Вы писали:

А>2) Я кстати вчера частично доделал алгоритм и прироста не получил. Даже напротив на 20% медленнее. Причём профилировщик показал, что в параллельной версии 70% времени сожрало преобразование координат.. А раньше это было только 40%. Я тут подумываю — неужто подгрузка в КЭШ всё портит? Но я в этом профан, даже не знаю как с этим бороться.

А>3) У меня очень много данных (в основном координаты) лежит в памяти (больше 100Мб) — эти данные читаются, преобразовываются (преобразование координат), а затем передаются на отрисовку. Вот я и подозреваю, что после распараллеливания взаимодействие RAM и cache — стало торомозить...

Скачай Intel VTune, на месяц он бесплатный. Много интересного позволяет узнать

Здравствуйте, SergH, Вы писали:

SH>Здравствуйте, Аноним, Вы писали:

А>>2) Я кстати вчера частично доделал алгоритм и прироста не получил. Даже напротив на 20% медленнее. Причём профилировщик показал, что в параллельной версии 70% времени сожрало преобразование координат.. А раньше это было только 40%. Я тут подумываю — неужто подгрузка в КЭШ всё портит? Но я в этом профан, даже не знаю как с этим бороться.

А>>3) У меня очень много данных (в основном координаты) лежит в памяти (больше 100Мб) — эти данные читаются, преобразовываются (преобразование координат), а затем передаются на отрисовку. Вот я и подозреваю, что после распараллеливания взаимодействие RAM и cache — стало торомозить...

SH>Скачай Intel VTune, на месяц он бесплатный. Много интересного позволяет узнать
Скачал. Он, зараза, AMD не поддерживает! — Конечно следовало ожидать, но... я не ожидал.
Попробую дома — там у меня Intel, но там я чувствую всё тормозить будет жутко — машина медленная... Неужели VTune не поддерживает Amd??

Здравствуйте, <Аноним>, Вы писали:

А>Попробую дома — там у меня Intel, но там я чувствую всё тормозить будет жутко — машина медленная... Неужели VTune не поддерживает Amd??

Запустить можно. Работать нельзя. По крайней мере у меня не получилось.

> А>>2) Я кстати вчера частично доделал алгоритм и прироста не получил. Даже напротив на 20% медленнее. Причём профилировщик показал, что в параллельной версии 70% времени сожрало преобразование координат.. А раньше это было только 40%. Я тут подумываю — неужто подгрузка в КЭШ всё портит? Но я в этом профан, даже не знаю как с этим бороться.
>
> А>>3) У меня очень много данных (в основном координаты) лежит в памяти (больше 100Мб) — эти данные читаются, преобразовываются (преобразование координат), а затем передаются на отрисовку. Вот я и подозреваю, что после распараллеливания взаимодействие RAM и cache — стало торомозить...
>
> SH>Скачай Intel VTune, на месяц он бесплатный. Много интересного позволяет узнать
> Скачал. Он, зараза, AMD не поддерживает! — Конечно следовало ожидать, но... я не ожидал.
> Попробую дома — там у меня Intel, но там я чувствую всё тормозить будет жутко — машина медленная... Неужели VTune не поддерживает Amd??

Для AMD есть AMD Code Analyst. Он правда совсем убогий, но кое-что все-таки умеет. Причем бесплатно.

Здравствуйте, Аноним, Вы писали:

А>Скачал. Он, зараза, AMD не поддерживает! — Конечно следовало ожидать, но... я не ожидал.

Да, там используются всякие нестандартные счётчики в процессоре.
Т.е., AMD по идее поддерживать должен, но в "урезаном" режиме — самое интересное показать не сможет.

А>Попробую дома — там у меня Intel, но там я чувствую всё тормозить будет жутко — машина медленная...

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

Есть подозрение одно. Когда рисуем в битмапе "руками", то распараллеливание даст прирост. А если речь идет о GDI, то не факт. Рисование в DC — это драйвер и граф. железо. Насколько они распаралеливаются (позволяют работать с несколькими DC одновременно) — большой вопрос. С учетом кучи накладных расходов может получиться и заметно медленней. И можно прийти к серьезной зависимости от конфигурации драйвер+железо.

Здравствуйте, goto, Вы писали:

G>Есть подозрение одно. Когда рисуем в битмапе "руками", то распараллеливание даст прирост. А если речь идет о GDI, то не факт. Рисование в DC — это драйвер и граф. железо. Насколько они распаралеливаются (позволяют работать с несколькими DC одновременно) — большой вопрос. С учетом кучи накладных расходов может получиться и заметно медленней. И можно прийти к серьезной зависимости от конфигурации драйвер+железо.

Пока рисование идёт в памяти (memory DC), драйвер-и-железо (видеокарточка, видимо?) не задействованы. Задействована подсистема GDI, но в памяти даже она не должна особо блокировать работу. Хотя и может.

Кстати, можно попробовать как раз забить на обычную память и обычный GDI, а рисовать через DirectX — оно будет использовать то самое железо и драйвер, может быть получится быстрее — не мерял, не знаю. Процессор там, конечно, не такой же, как центральный, но зато часть алгоритмов рисования, по идее, должны быть реализованы аппаратно... В общем, попробовать.

Здравствуйте, SergH, Вы писали:

SH>Здравствуйте, goto, Вы писали:

G>>Есть подозрение одно. Когда рисуем в битмапе "руками", то распараллеливание даст прирост. А если речь идет о GDI, то не факт. Рисование в DC — это драйвер и граф. железо. Насколько они распаралеливаются (позволяют работать с несколькими DC одновременно) — большой вопрос. С учетом кучи накладных расходов может получиться и заметно медленней. И можно прийти к серьезной зависимости от конфигурации драйвер+железо.

SH>Пока рисование идёт в памяти (memory DC), драйвер-и-железо (видеокарточка, видимо?) не задействованы. Задействована подсистема GDI, но в памяти даже она не должна особо блокировать работу. Хотя и может.

Я совсем уж в бутылку не полезу , в системе GDI-драйвер-ускоритель я отнюдь не эксперт. Но часть ф-й GDI все-таки реализована аппаратно и подозреваю, что аппаратно отрисовывается и в memory DC (скорее всего при условии, что там все "compatible"). Иначе рисование в бэкбуфере во многих случаях не имело бы смысла, было бы очень медленным.

SH>Кстати, можно попробовать как раз забить на обычную память и обычный GDI, а рисовать через DirectX — оно будет использовать то самое железо и драйвер, может быть получится быстрее — не мерял, не знаю. Процессор там, конечно, не такой же, как центральный, но зато часть алгоритмов рисования, по идее, должны быть реализованы аппаратно... В общем, попробовать.

Тут действительно можно посоветовать посмотреть на OpenGL или DX. Им все-таки один раз скармливается геометрия, а потом можно просто камерой шевелить, если грубо.