Алгоритмы распараллеливания одномерной схемы Годунова для кластерных вычислительных систем

О.С. Борщук, К.И. Михайленко (Уфа)

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

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

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

Первый из алгоритмов основан на стандартной схеме, когда по окончании расчета подобластей процессы обмениваются значениями своих теневых граней. Затем происходит расчет значений на новом временном слое.

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

Особенно эффективной представленная поэтапная организация пересылок должна быть для кластерных вычислительных систем, поддерживающих топологию типа «кольцо». Однако и для топологии «общая шина» поэтапная рассылка должна приводить к повышению эффективности вычислительного процесса на большом числе процессов. Такой эффект должен проявляться за счет уменьшения количества одновременно передаваемых сообщений.