Параллельный алгоритм вычисления точек гиперплоскости фронта вычислений

Рассматривается параллельный алгоритм вычисления точек гиперплоскости фронта вычислений. Такая необходимость возникает при вычислении значений некоторой величины, определенной на многомерной прямоугольной области. Обычно речь идет о трехмерных областях, но материал изложен в общем виде, когда число измерений не меньше двух. Часто величина не имеет внутренних зависимостей между точками области, в этом случае вычисления в разных точках области производятся независимо, и их можно производить параллельно. Однако иногда внутренние зависимости имеются (например в методе Гаусса–Зейделя решения системы линейных уравнений), в этом случае последовательность обхода точек области важна. Общепринятый подход в этом случае состоит в формировании некоторой гиперплоскости (в трехмерном случае – обычной плоскости, в двумерном случае — прямой) фронта вычислений, которая линейно движется по области под некоторым углом. На каждом шаге движения этой гиперплоскости точки ее пересечения с областью можно обрабатывать независимо, и, следовательно, параллельно, но сами шаги движения гиперплоскости выполняются последовательно. Область пересечения гиперплоскости со всей областью на разных шагах движения гиперплоскости может представлять собой весьма сложную фигуру, а поиск всех точек области, лежащих на гиперплоскости на данном шаге, — нетривиальную задачу. Именно решению этой задачи (вычислению координат точек области, лежащих на пересечении с гиперплоскостью на данном шаге движения этой гиперплоскости) посвящена данная статья. При этом само вычисление можно производить параллельно по точкам гиперплоскости. Библ. 14.