Печать страницы - Параллельные вычисления

Название: Параллельные вычисления
Отправлено: Igors от Февраля 22, 2010, 19:57

Добрый день

Задача типа "близок локоть да не укусишь" :) Вот максимально упрощенное описание: есть "точки" значения в которых должны быть вычислены, а потом осреднены с соседними. Схема такая:

*------*-----*-----* (первый блок из 4 точек)
*------*-----* (второй блок из 3 точек)
*------*---*........* (третий блок из 100 точек)
и.т.п

Осреднение происходит для точек одного блока, однако одна и та же точка может входить в любое число блоков

Код:

struct Point {
  float mBaseVal;   // начальное значение - считается 1 раз и больше не меняется
  float mCalcVal;   // выходное значение (с учетом всех осреднений)
  float mBaseW;    //  "собственный" вес точки (обычно 1.0f)
  float mCalcW;     //  вес точки с учетом всех осреднений

  void Calculate( float weight )
  {
    mBaseW = mCalcW = weight;
    mBaseVal = mCalcVal = CalculatePoint(...):    
  }

  void Blur( const Point & src )  
  {
    mCalcVal = (mCalcVal * mCalcW + src.mBaseVal * src.mBaseW) / (mCalcW + src.mBaseW);
    mCalcW += src.mBaseW;
  }
};

И все прекрасно, и проблем никаких, но вот когда я вычисляю точки параллельно, в разных нитках - тогда "ой". Вычислив точку, я не могу ее сразу осреднить т.к. соседняя может быть еще не вычислена. Ждать ее бесполезно - дело умрет на блокировках. Конечно, есть "общее" решение - сделать 2 прохода, первый вычисляет (параллельно), второй осредняет. Но здесь это очень накладно, нужно приложить массу усилий чтобы повторить всю последовательность блоков точек. Есть ли свежие идеи? Как выкрутиться?

Спасибо

Название: Re: Параллельные вычисления
Отправлено: BlackTass от Февраля 24, 2010, 23:44

А топологическая сортировка точек не поможет в этом случае?

Название: Re: Параллельные вычисления
Отправлено: Igors от Февраля 26, 2010, 13:49

Цитата: BlackTass от Февраля 24, 2010, 23:44

А топологическая сортировка точек не поможет в этом случае?

Если б у меня был массив/контейнер этих точек - то и проблемы бы не было. Просчитал все, потом пробежался еще раз и осреднил (ну запомнил бы индексы "блоков""). А у меня есть исходные треугольники. Для каждого из них:

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

Название: Re: Параллельные вычисления
Отправлено: BlackTass от Февраля 26, 2010, 22:14

ну вообще рекурсивные алгоритмы плохо поддаются распарелливанию. Только если изначальные треугольники отдавать в разные треды. Нельзя ли раскрутить рекурсию в циклы? Тогда будет проще параллелить.

Название: Re: Параллельные вычисления
Отправлено: Igors от Февраля 28, 2010, 13:11

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

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

Название: Re: Параллельные вычисления
Отправлено: BlackTass от Марта 01, 2010, 15:10

Ну тоже как вариант. И вполне нормальный кстати.

Russian Qt Forum

Программирование => Алгоритмы => Тема начата: Igors от Февраля 22, 2010, 19:57