Подход к оценке локальности зернистых вычислительных процессов, логически организованных в двумерную структуру
Аннотация
При реализации алгоритмов на многопроцессорных вычислительных устройствах важнейшую роль для достижения высокой производительности играет локальность — вычислительное свойство алгоритма, отражаюшее степень использования памяти с быстрым доступом. Для суперкомпьютеров с распределенной памятью быстрой считается локальная память вычислительного узла. Параллельные алгоритмы с меньшим объемом и лучшей структурой коммуникационных операций обладают лучшей локальностью. В работе на основе схемы расщепления с весами построен новый параллельный алгоритм численного решения трехмерного линейного уравнения теплопроводности. Алгоритм ориентирован на компьютеры с распределенной памятью, сочетает конвейерный и естественый параллелизм, использует 2D структуру процессов. Схема расщепления обладает естественным параллелизмом. Ранее для случая 1D структуры процессов было показано, что использование конвейерного параллелизма вместо части естественного параллелизма приводит к меньшим объемам и лучшей структуре коммуникационных операций. Построенный 2D алгоритм обобщает известный 1D алгоритм. Использование двумерных структур позволяет уменьшить объем и улучшить структуру коммуникационных операций, уменьшить время разгона и торможения вычислений. Поэтому 2D алгоритм обладает лучшей локальностью по сравнению с использованием 1D структуры процессов. Вычислительные эксперименты на суперкомпьютере показали преимущество нового параллельного алгоритма. По аналогии с представленным алгоритмом можно получить и исследовать параллельные алгоритмы для других схем метода дробных шагов. На примере алгоритма, реализующего схему расщепления, представлен подход к получению асимптотических оценок объема коммуникационных операций зернистых (т.е. уровня макроопераций) параллельных вычислительных процессов, логически организованных в двумерную структуру. Оценки могут быть использованы для сравнения коммуникационных затрат при получении альтернативных вариантов параллельных алгоритмов.
