MPI-программы

Материал из Department of Theoretical and Applied Mechanics
Перейти к: навигация, поиск

Блочная сортировка

[Подробное описание метода]
Sort.jpg

Это алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения. При реализации алгоритма сортировки внутри блока использовался метод пузырька. Сортировку каждого блока осуществлял отдельный процессор. На рис. представлена зависимость относительного времени выполнения от числа процессоров для 10000 элементов.

Метод Гаусса

[Подробное описание метода]

Gauss.jpg

Классический метод решения системы линейных алгебраических уравнений. Это метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе ступенчатого (или треугольного) вида, из которой последовательно, начиная с последних (по номеру) переменных, находятся все остальные переменные. При реализации строки между процессорами распределялись таким образом, что процессор с номером i выполнял строки последовательно с промежутком, равным общему количеству процессоров. На рис. представлена зависимость относительного времени выполнения от числа процессоров для матрицы размером 1000 на 1000.