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

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

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

Сообщений: 11445


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

Проверил с компилятором Intel
Результаты для 4 ниток, 2 процессора Intel Xeon по 2 ядра
Цитировать
                 1_100   1_200  1_400  2_100  2_200  2_400
---------------------------------------------------------
No threads      16       32       63      62      118     230
Custom impl.   19       28       46      50      79      135
GCC + OMP      18       28       48      57      87      149
Intel + OMP     10       18       35      32      57      108
В таблице время в секундах, колонка соответствует 1 тесту, напр. 2_200 значит: тест 2, выполняется 200 вычислений на точку. Сами тесты (1 и 2) отличаются трудоемкостью единичного вычисления.

Придется использовать Intel хотя забот с ним более чем достаточно и компилирует он совсем не быстро. Досадно что GCC проигрывает с таким разгромным счетом, но надо заметить что это OSX, т.е. POSIX. Судя по исходникам GCC 4.4, для POSIX используется простая реализация семафора (mutex + pthread_cond_wait). Для Linux используется гораздо более изощренная техника фьютексов (futex) так что там результат может быть совсем иным.
« Последнее редактирование: Декабрь 20, 2009, 14:12 от Igors » Записан
niXman
Гость
« Ответ #31 : Декабрь 20, 2009, 14:37 »

что такое OMP ?
Цитировать
Досадно что GCC проигрывает с таким разгромным счетом, но надо заметить что это OSX, т.е. POSIX. Судя по исходникам GCC 4.4, для POSIX используется простая реализация семафора (mutex + pthread_cond_wait)
смею заметить, то, что если время тратиться на синхронизацию, то это говорить лишь об одном - слишком часто происходит блокировка/деблокировка. в этом случае, не стоит расчитывать на чудеса, а спроектировать иной алгоритм.

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

Сообщений: 11445


Просмотр профиля
« Ответ #32 : Декабрь 20, 2009, 15:29 »

что такое OMP ?
OpenMP  Улыбающийся
смею заметить, то, что если время тратиться на синхронизацию, то это говорить лишь об одном - слишком часто происходит блокировка/деблокировка. в этом случае, не стоит расчитывать на чудеса, а спроектировать иной алгоритм.
В данном конкретном случае под "синхронизацией" понимается "старт и финиш" задачи для которой привлекаются все нитки. Это расчет одного пикселя который может состоять из N (100, 200, 400 в тестах) подрасчетов (распределяемых между нитками). Каждый подрасчет может быть более или менее трудоемким (зависит от многих исходных данных). Проблемы возникают из-за того что время расчета пикселя достаточно мало (меньше миллисекунды).

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

И Вы не волнуйтесь, мне там еще с параллелизацией пахать и пахать. Вот например "запекание фотонной карты" - дивный алгоритм который я не знаю как положить на нитки. Мы с Вами обязательно это обсудим Улыбающийся
Записан
vaprele07
Гость
« Ответ #33 : Декабрь 20, 2009, 17:15 »

Код:
#include <qtest.h>

#include <omp.h>

class TestBenchmark : public QObject
{
Q_OBJECT

    void func() {}

private slots:

void simple2();
void simple2_omp();

void simple4();
void simple4_omp();
};

#define MAX_K 100000000


void TestBenchmark::simple2()
{
long i, j;

QBENCHMARK_ONCE {
for (i = 0; i < MAX_K; i++)
{
for (j = 0; j < 5; j++){
                            func();
                            func();
}
}
}
}

void TestBenchmark::simple2_omp()
{
long i, j;

QBENCHMARK_ONCE {
#pragma omp parallel for private(i, j, sum)
for (i = 0; i < MAX_K; i++)
{
for (j = 0; j < 5; j++){
                                func();
                                func();
}
}
}
}

void TestBenchmark::simple4()
{
long i, j;
QBENCHMARK_ONCE {
for (i = 0; i < MAX_K; i++)
{
for (j = 0; j < 10; j++){
                                func();
}
}
}
}


void TestBenchmark::simple4_omp()
{
long i, j;
QBENCHMARK_ONCE {
#pragma omp parallel for private(i, j, sum)
for (i = 0; i < MAX_K; i++)
{
for (j = 0; j < 10; j++){
                                func();
}
}
}
}

QTEST_MAIN(TestBenchmark)
#include "main.moc"
Заметьте разницу Подмигивающий

Записан
vaprele07
Гость
« Ответ #34 : Декабрь 20, 2009, 17:28 »

Код:
void TestBenchmark::simple3()
{
        long k, i, j;

        QBENCHMARK_ONCE {
                for (i = 0; i < MAX_K; i++)
                {

                        for (k = 0; k < 5; k++)

                            func();

                        for (j = 0; j < 5; j++)

                            func();
                }
        }
}

void TestBenchmark::simple3_omp()
{
        long k, i, j;

        QBENCHMARK_ONCE {
                #pragma omp parallel for private(i, j, k)
                for (i = 0; i < MAX_K; i++)
                {
                    for (k = 0; k < 5; k++)

                        func();

                    for (j = 0; j < 5; j++)

                        func();
                }
        }
}
А вот еще интереснее )
Вроде и инструкций больше а все равно быстрее))
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


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

Заметьте разницу Подмигивающий
При таком шикарном MAX_K (100000000) пройдет все что угодно - вот только где ж мне его взять если по задаче это от 50 до 5000  Плачущий
Записан
niXman
Гость
« Ответ #36 : Декабрь 20, 2009, 19:23 »

Цитировать
Понятно что заманчиво давать ниткам расчеты целых пикселей (а не "подрасчеты"). Но при этом мне надо гораздо больше распараллелить, появляется очень много массивов (где была 1 переменная), появляются конструкции указателей *** (понимаемые самим автором с трудом).
1. Данные общие?
2. Во время работы одной нитки, другая может изменить общие данные?
3. Если все же синхронизация ниток с общими данными не нужна, может каждой нитке передать копию данных? Ну и что, что памяти съест больше. Ныньче 2-4 гига на процесс не трагедия)

Цитировать
Вот например "запекание фотонной карты"
Даже спрашивать не стану, что это такое Шокированный
оО...какой я все же темный Смеющийся
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #37 : Декабрь 20, 2009, 20:30 »

1. Данные общие?
2. Во время работы одной нитки, другая может изменить общие данные?
3. Если все же синхронизация ниток с общими данными не нужна, может каждой нитке передать копию данных? Ну и что, что памяти съест больше. Ныньче 2-4 гига на процесс не трагедия)
Подавляющее большинство исходных данных общие и "только чтение" (хотя они и требуют блокировок для подгрузки с диска). Проблема в том что нет четкой "мишени" - в начале расчетов неизвестно какие пиксели и как считать, это выясняется по ходу дела. Сетевой вариант задачи живет долго и вполне счастливо, он разбивает результат(изображение) на N полос (или кадров) и запускает свою копию для каждой части. При этом однако дублируются все исходные данные. Склеивание полос, передача исходных данных по сети и результатов обратно - все это в сумме не так уж дешево. Часть данных строится динамически и это будет тоже повторено N раз. Уязвимое место - относительно короткие расчеты (особенно превью), тогда запуск сетевой бандуры не окупает себя.  В общем пришли к банальной истине: задача должна иметь как сетевой вариант, так и поддержку multi-threading  Улыбающийся

Записан
niXman
Гость
« Ответ #38 : Декабрь 20, 2009, 20:43 »

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

Цитировать
Сетевой вариант задачи живет долго и вполне счастливо
это вы про кластер?

Цитировать
Склеивание полос, передача исходных данных по сети и результатов обратно - все это в сумме не так уж дешево.
Согласен. Я так понял, это все же кластер?

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

Сообщений: 11445


Просмотр профиля
« Ответ #39 : Декабрь 20, 2009, 21:43 »

а почему не загрузить весь файл за раз?
Все файлы грузятся полностью и читаются всего 1 раз. Но не для всех распакованное содержимое держится в памяти, для многих оно хранится постранично. Если памяти достаточно - все будет в памяти, нет - будет подкачиваться с диска.

Согласен. Я так понял, это все же кластер?
Не имею цели подколоть, но не знаю что такое кластер (здесь), правда Улыбающийся Ну например, выходной имедж имеет 1000 строк. Пользователь может задать число полос, напр 4. Значит будут запущены 4 копии. Первая получит задачу сделать первые 250 строк, вторая - вторые 250 и.т.п. Возможно какая-то копия не рассчитает ни одного пикселя - нечего считать, но результат (черный пустой имедж) все равно будет. То есть разбивается "тупо", по числу строк. Но эта задача давно решена и успешно эксплуатируется.

А этот алгоритм, правильно спроектирован? Может корень проблемы в нем? Возможно вы боретесь с последствиями неправильной разработки алгоритма?
Да кто ж его знает где этот корень?  Улыбающийся Очень может быть я выбрал не лучший путь но в данном случае любой имеет трудности.

niXman, мы весьма отвлеклись от темы, давайте переключаться в личку, с удовольствием отвечу на любые Ваши вопросы.
Записан
niXman
Гость
« Ответ #40 : Декабрь 20, 2009, 23:04 »

Цитировать
Не имею цели подколоть, но не знаю что такое кластер (здесь), правда
Вот кластер http://ru.wikipedia.org/wiki/IBM_Roadrunner
Ничё так, комп Улыбающийся

Цитировать
niXman, мы весьма отвлеклись от темы
разве? Улыбающийся я то думал мы все о той же проблеме рассуждаем Подмигивающий

пысы
так, на всякий случай скажу, чтоб не вводить людей в заблуждение. кластер, состоит из нодов, каждый нод, в свою очередь содержит проц(или несколько)(нечто типа писишки). вот в совокупности, получается кластер. да, и еще. если программу скомпилить для такого кластера, она работать будет(скорее всего), но в пределах одного нода, не более. а дальше все в руках программиста Улыбающийся
Записан
vaprele07
Гость
« Ответ #41 : Декабрь 21, 2009, 05:20 »

http://www.realcoding.net/articles/optimizatsiya-tsikla.html
http://parallel.ru/ куча литературы есть и по openMP
Это я не для автора а для широких масс  Строит глазки
Записан
Страниц: 1 2 [3]   Вверх
  Печать  
 
Перейти в:  


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