Лучший параллельный метод вычисления интеграла двумерной функции

Question

В какой-то программе обработки чисел у меня есть функция, которая может быть просто 1 или 0 в трех измерениях. Я не знаю заранее функцию, но мне нужно знать общую «поверхность» функции, которая равна нулю. В аналогичной задаче я мог нарисовать прямоугольник поверх 2D-представления карты Соединенного Королевства. Функция равна 0 в море и 1 в земле. Мне нужно знать общую поверхность воды. Интересно, каков наилучший параллельный алгоритм или метод для этого?

Сначала я подумал о следующем подходе; а) разделить область 2D-карты на прямоугольную сетку. Для каждой точки, которая принадлежит центру каждой ячейки, проверьте, является ли это землей воды. Это можно сделать параллельно. В конце процедуры у меня будет матрица с единицами и нулями. Я получу область с некоторой точностью. Теперь я хочу повысить эту точность, поэтому б) выберите ячейки, которые находятся в граничных областях между нулями и единицами (каков наилучший критерий для этого?), И в этих ячейках снова разделите их на последовательные ячейки и повторите процесс пока не получишь желаемую точность. Я предполагаю, что в этом процессе критическими параметрами являются размер сетки для каждого нового этапа, а также способ хранения и проверки ячеек, которые принадлежат области границы. Наконец, наиболее оптимальный метод, с вычислительной точки зрения, - это метод, который выполняет минимальное количество проверок, чтобы получить значение общей поверхности с желаемой точностью.

Answer 1

Прежде всего, похоже, что вы говорите о функции 3D , например, для двух координат x и y у вас есть f(x, y) = 0, если (x, y) принадлежит морю и f(x, y) = 1в противном случае.

Сказав это, вы можете использовать следующий простой подход:

1. Разделите ваш прямоугольник на N под прямоугольников, где N - количество ваших процессоров (или ядер процессоров, илиузлы в кластере и т. д.)
2. Для каждого под прямоугольника используйте метод Монте-Карло для расчета поверхности воды.
3. Добавьте N значений для вычисления общей поверхностиводы.

Конечно, вы можете использовать любой другой метод для расчета поверхности, Mothe Carlo был просто примером.Но идея та же: разделите вашу проблему на N подзадач, решите их параллельно, затем объедините результаты.

Обновление: Для метода Монте-Карло оценка ошибки уменьшается как 1 /sqrt (N) где N - количество выборок.Например, чтобы уменьшить погрешность в 2 раза, необходимо увеличить количество точек выборки в 4 раза.

Answer 2

Я считаю, что ваше отношение разумно.

Выберите ячейки, которые находятся в граничных областях между нулями и единицами (каков наилучший критерий для этого?)

Каждая ячейка имеет 8 сорбирующих клеток (3x3) или 24 сорбирующих клетки (5x5).Если хотя бы одна из 9 или 25 ячеек содержит землю, и хотя бы одна из этих ячеек содержит воду - увеличьте точность для всего блока ячеек (3x3 или 5x5) и повторите запрос.

Когда точностьэто достаточно хорошо - вместо разделения, просто добавьте площадь земли к сумме.

Эффективность

Используйте очередь производителей-потребителей.Создайте n потоков, где n равно числу ядер на вашем компьютере.Все потоки должны выполнять одну и ту же работу:

• Извлечь гео-ячейку из очереди
• Если площадь ячейки все еще велика - разделите ее на ячейки 3x3 или 5x5, чтобыкаждая из разделенных ячеек проверяет сушу / море.Если есть смесь - поставьте в очередь все эти ячейки.Если это только земля: просто добавьте область.только море: ничего не делать.

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

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

Редактировать:

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