При внимательном рассмотрении метода Гаусса можно заметить, что все вычисления сводятся к однотипным вычислительным операциям над строками матрицы коэффициентов системы линейных уравнений. Как результат, в основу параллельной реализации алгоритма Гаусса может быть положен принцип распараллеливания по данным. В качестве базовой подзадачи можно принять тогда все вычисления, связанные с обработкой одной строки матрицы A и соответствующего элемента вектора b.
Рассмотрим общую схему параллельных вычислений и возникающие при этом информационные зависимости между базовыми подзадачами.
Для выполнения прямого хода метода Гаусса необходимо осуществить (n-1) итерацию по исключению неизвестных для преобразования матрицы коэффициентов A к верхнему треугольному виду.
Выполнение итерации i, 0 <= i < n-1, прямого хода метода Гаусса включает ряд последовательных действий. Прежде всего, в самом начале итерации необходимо выбрать ведущую строку, которая при использовании метода главных элементов определяется поиском строки с наибольшим по абсолютной величине значением среди элементов столбца i, соответствующего исключаемой переменной xi. Зная ведущую строку, подзадачи выполняют вычитание строк, обеспечивая тем самым исключение соответствующей неизвестной xi. При выполнении обратного хода метода Гаусса подзадачи выполняют необходимые вычисления для нахождения значения неизвестных. Как только какая-либо подзадача i, 0 < i < n-1, определяет значение своей переменной xi, это значение должно быть использовано всеми подзадачами с номерами k, k < i, для выполнения корректировки значений элементов вектора b.
Выделенные базовые подзадачи характеризуются одинаковой вычислительной трудоемкостью. Вместе с этим, следует учитывать, что по мере выполнения вычислений часть подзадач будет завершать свои вычисления (например, после того, как строка подзадачи использовалась в качестве ведущей при прямом ходе метода Гаусса). Решение этой проблемы может состоять, например, в укрупнении подзадач – тем более, что обычно размер матрицы, описывающей систему линейных уравнений, оказывается большим, чем число доступных вычислительных элементов (т.е., p