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

[vaprele07]

Вот здесь много материалов по теме: http://software.intel.com/ru-ru/

[niXman]

Табличку скачать не получается

[niXman]

Все равно многого не понятно.

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

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

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

Выбирайте.

[Igors]

У меня в чистом виде реализован вариант "2". Ну можно еще добавить что относительно небольшая часть расчетов (5-10%) не распараллелена и выполняется главной ниткой

[niXman]

Если это так, и принцип делегирования реализован !правильно!, то самое время подумать над кластером.


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

[Igors]

Если это так, и принцип делегирования реализован !правильно!, то самое время подумать над кластером.

Про делегирование ничего не слышал Главная нитка помещает задачи в очередь. Как только в очереди окажется N (размер кластера) задач - все рабочие нитки снимаются со своих семафоров и начинают брать задачи из очереди (также кластером из N задач). N в моих руках, управляемо. Послав все задачи, главная нитка засыпает на семафоре но перед этим досылает еще по одной "псевдо-задаче" (для каждой рабочей нитки). Получив задачу-терминатор, рабочая нитка засыпает на своем семафоре. Последняя засыпающая открывает семафор главной нитке. Это все

[niXman]

Из описания правильно.
Допустим. У вас 4 ядра, и 4 рабочих нитки.
1. скажите, рабочие нитки загружены на 100 процентов?
2. сколько раз(за время своей жизни), в сумме, происходит блокировка разделяемого ресурса нитками?

[niXman]

Про делегирование ничего не слышал

Из википедии:

# передача, уступка полномочий. Делегирование - такая организация работы, при которой руководитель распределяет между подчиненными конкретные задания. Также делегирование есть передача подчиненному задачи или действия, которое должен осуществить руководитель, вместе с необходимыми для этого полномочиями.

Как только в очереди окажется N (размер кластера)

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

[niXman]

Вот здесь много материалов по теме: http://software.intel.com/ru-ru/

Вот было любопытно, посмотреть, что вы такого порекомендовали. Но, оказалось, что ваша ссылка, равносильна этой: http://www.*

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

[Igors]

Из описания правильно.
Допустим. У вас 4 ядра, и 4 рабочих нитки.
1. скажите, рабочие нитки загружены на 100 процентов?
2. сколько раз(за время своей жизни), в сумме, происходит блокировка разделяемого ресурса нитками?

1) Увы, совсем не на 100% (принимаем 100% = все 4 загружены до упора). Типичная загрузка только 65-70%, а очень хотелось бы большего. Остальное idle, а когда N неудачно -  появляется довольно мощный overhead (монитор показывает его как "system" красным).

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

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

[Igors]

Добрый день

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

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

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

[niXman]

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

[Igors]

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

Трудно понять, мудрено выражаетесь Так в архитектуре или реализации? (часто это употребляется в смысле стратегия/тактика). Насчет видения - ну я пока ничего не вижу, буду благодарен за свежие идеи (пусть и экспериментальные).

[niXman]

Трудно понять, мудрено выражаетесь

даже и не думал.

Так в архитектуре или реализации?

возможно и там, и там..

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

не понял сравнения.

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

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

я задавал вопрос:

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

вы так и не ответили.

[Igors]

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

Извините за возможные непонятки, мой ответ был

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

То есть при использовании OpenMP блокировок нет вообще, все потери на синхронизации. Повторюсь также про трудоемкость 1 пикселя (для вычисления которого привлекаются все нитки)
32 sec / (80 * 1000)