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

[Igors]

Проверил с компилятором 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) так что там результат может быть совсем иным.

[niXman]

что такое OMP ?

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

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

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

[Igors]

что такое OMP ?

OpenMP 

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

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

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

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

И Вы не волнуйтесь, мне там еще с параллелизацией пахать и пахать. Вот например "запекание фотонной карты" - дивный алгоритм который я не знаю как положить на нитки. Мы с Вами обязательно это обсудим

[vaprele07]

Код:

#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]

Код:

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]

Заметьте разницу

При таком шикарном MAX_K (100000000) пройдет все что угодно - вот только где ж мне его взять если по задаче это от 50 до 5000 

[niXman]

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

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

Вот например "запекание фотонной карты"

Даже спрашивать не стану, что это такое
оО...какой я все же темный

[Igors]

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

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

[niXman]

(хотя они и требуют блокировок для подгрузки с диска)

а почему не загрузить весь файл за раз?

Сетевой вариант задачи живет долго и вполне счастливо

это вы про кластер?

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

Согласен. Я так понял, это все же кластер?

В общем пришли к банальной истине: задача должна иметь как сетевой вариант, так и поддержку multi-threading

А этот алгоритм, правильно спроектирован? Может корень проблемы в нем? Возможно вы боретесь с последствиями неправильной разработки алгоритма?

[Igors]

а почему не загрузить весь файл за раз?

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

Согласен. Я так понял, это все же кластер?

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

А этот алгоритм, правильно спроектирован? Может корень проблемы в нем? Возможно вы боретесь с последствиями неправильной разработки алгоритма?

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

niXman, мы весьма отвлеклись от темы, давайте переключаться в личку, с удовольствием отвечу на любые Ваши вопросы.

[niXman]

Не имею цели подколоть, но не знаю что такое кластер (здесь), правда

Вот кластер http://ru.wikipedia.org/wiki/IBM_Roadrunner
Ничё так, комп

niXman, мы весьма отвлеклись от темы

разве? я то думал мы все о той же проблеме рассуждаем

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

[vaprele07]

http://www.realcoding.net/articles/optimizatsiya-tsikla.html
http://parallel.ru/ куча литературы есть и по openMP
Это я не для автора а для широких масс