Лабораторная работа №1. Реализация алгоритма сдваивания для суммы чисел.
Постановка задачи: задана конечная сумма, которую необходимо посчитать 
. Количество элементов в этой сумме большое . Необходимо составить и реализовать алгоритм параллельного суммирования заданной конечной суммы ряда.
Описание решения. Задано некоторое количество процессов , которые мы можем использовать для решения поставленной задачи. Количество процессов задается в момент запуска программы. Необходимо распределить все элементы ряда по заданному количеству процессов. Такое распределение необходимо выполнить равномерно, чтобы количество элементов пересланных на разные процессы отличались между собой не более чем на 1. При этом нужно помнить, что количество элементов ряда и количество процессов могут быть абсолютно произвольными.
На каждом из процессов происходит подсчет своей частичной суммы, . После чего необходимо обменяться данными с использованием схемы сдваивания и получить итоговую сумму . Вариант схемы сдваивания для примера 8 процессов и 8 чисел приведен на рисунке ниже:
На первом этапе происходит обмен данными между соседними процессами, и подсчет первых пар. После чего половина процессов больше не участвуют в обмене. С остальными процессами происходит такая же работа. До тех, пока не останется только один процесс. На этом процессе и должна получиться итоговая сумма ряда.
Рекомендации:
1. Для тестирования корректности работы программы проще использовать ряд 
или 
, так как для этих рядов сумму ряда легко посчитать аналитически. После проверки корректности результат работы алгоритма, работоспособность алгоритма показывать на большом ряде случайных чисел.
2. При первой реализации алгоритма можно считать, что количество процессов будет равно степени двойки. В дальнейшем мы не сможем на это рассчитывать, и программа должна работать при произвольном количестве процессов. Единственное что точно можно гарантировать, что количество элементов ряда будет больше, чем количество процессов.
3. При запуске параллельной программы на многопроцессорной системе, только процесс с номером 0 выполняется в точке запуска. Остальные процессы могут выполняться на любом вычислительном узле многопроцессорной системы. Поэтому, весь необходимый диалог с пользователем организовать только в процессе 0, и на нем же следует собрать посчитанную сумму ряда и вывести ее на экран.
Лабораторная работа №2. Параллельный алгоритм для подсчета числа Pi.
Постановка задачи: необходимо посчитать число с заданной точностью. Точность расчетов задается в количестве точных знаков после запятой, например 30.
Описание решения.
Существует несколько разных способов подсчета числа . Например при помощи метода Монте Карло, при помощи подсчета интеграла или суммы некоторого числового ряда. Выбор того или иного способа решения не принципиален. Основная задача состоит в том, что написать параллельную реализацию выбранного алгоритма подсчета.
При запуске программы задается количество процессов, на которых должно производится вычисление числа . После запуска задается точность вычисления, точность вычисления может задаваться либо в количестве знаков после запятой , либо в погрешности Все требуемые вычисления распределяются равномерно по имеющимся процессам, после чего на каждом процессе происходит процесс вычисления. В конце работы, все результаты сводятся в один, на процессе 0 и выводятся на экран.
Рекомендации:
1. Все требуемые вычисления должны распределятся между процессами равномерно, т. е. с разницей в количестве элементов на один процесс, не больше чем на 1.
2. Если используется способ подсчета числа через метод Монте Карло, то обратить внимание на то, как именно оценивать точность вычисления.
Лабораторная работа №3. Реализация параллельного алгоритма перемножения матрицы на вектор.
Постановка задачи: Задана некоторая квадратная матрица размера и вектор длины . Необходимо вычислить результат выполнения операции , т.е.. вектор c. Размеры матрицы и вектора могут быть довольно большими .
Описание решения.
При запуске программы задается количество процессов, которые должны участвовать в процессе вычисления умножения матрицы на вектор. Размер матрицы и вектора указывается после запуска программы. Матрица и вектор формируется на процессе 0, после чего процесс 0 должен распределить матрицу и вектор по остальным процессам. Матрицу нельзя передавать целиком, необходимо использовать какую то декомпозицию матрицы, например ленточную или блочную, как на рисунке ниже:
При любой декомпозиции матрицы, процессы необходимо равномерно загрузить работой, для этого нужно минимизировать количество передач данных, и следить за тем, чтобы размеры передаваемых частей матрицы были почти одинаковы для всех процессов. При этом нужно помнить, что размер матрицы и количество процессов могут быть абсолютно произвольными. Можно гарантировать только то, что размер матрицы будет больше чем количество процессов.
После получения своей порции данных, процесс должен произвести необходимые вычисления и вернут результат работы на процесс 0. Итоговый вектор собирается на процессе 0.
Рекомендации:
1. Для тестирования корректности работы программы матрицу лучше всего заполнять следующим образом , а вектор — . В этом случае, результирующий вектор легко может быть посчитан, и его легко проверить с тем, что получилось у программы. В дальнейшем, матрица и вектор заполняются произвольным образом.
2. Лучше всего построить работу алгоритма таким образом, чтобы в самом начале была одна передача данных, и в конце еще одна. Все остальное время процессы занимаются вычислениями и данными не обмениваются.
