© Воеводин Вл.В.

Варианты заданий на использование MPI.

Воеводин В.В., Воеводин Вл.В.

Задание 1.

Имеется вычислительная система, состоящая из $P$ процессоров, каждый из которых имеет быструю память величиной $m$ для хранения обрабатываемых данных и результатов. Известно, что время выполнения одной арифметической операции $+,-,\times$, намного меньше, чем время передачи одного числа от процессора к процессору. Известно также, что выгоднее по времени передавать большие пакеты данных, причем чем больше пакет, тем лучше.

  1. Составить программу решения систем линейных алгебраических уравнений с квадратной невырожденной матрицей порядка $n$ методом Гаусса (любой вариант метода) с использованием языков Си и MPI.
  2. Провести испытание программы на системе $Ax=b$, где


    \begin{displaymath}a_{ij}=a_{ji},\quad a_{ij}=i \quad \mbox{для}\quad j\ge i,\quad b_i=ni-{{i(i-1)} \over {2}}.\end{displaymath}

    Решение $x=(1,1,\dots,1)$.
  3. Найти эксперементально зависимость времени $t=t(n,p,m)$ решения системы как функции параметров $n,p,m$ и вычислить коэффициенты потерь


    \begin{displaymath}\tau (n,p,m)=p\cdot t(n,p,m)/t_\circ (n)-1,\end{displaymath}

    где $t_\circ (n)$ есть время, необходимое только для выполнения арифметических операций при решении системы порядка $n$ на одном процессоре.
  4. Добиться того, чтобы при заданном $m$ программа решала систему максимально возможного (по главному члену) порядка.

Литература

  1. В.А. Ильин, Г.Д. Ким. Линейная алгебра и аналитическая геометрия. М:,Изд-во МГУ, 1998, стр.13,101.
  2. В.В. Воеводин. Вычислительные основы линейной алгебры. М:,Наука, 1977, стр.293-295.



Задание 2. Перемножение квадратных матриц порядка $n$ любым способом

Тест: любой

Литература

  1. В.А. Ильин, Г.Д. Ким. Линейная алгебра и аналитическая геометрия. М:, Изд-во МГУ, 1998, стр. 13,15.
  2. В.В. Воеводин. Вычислительные основы линейной алгебры. М:, Наука, 1977,стр.293-295.



Задание 3. Обращение матриц методом Жордана

Тест: матрица $A$ из системы уравнений

матрица $A^{-1}$:


\begin{displaymath}a_{ij}=\left \{\matrix{ 2, & i=j \cr -1, & \vert {i-j}\vert =1 \cr 0, & \mbox{в остальных случаях}\cr }\right.\end{displaymath}

Литература

  1. В.А. Ильин, Г.Д. Ким. Линейная алгебра и аналитическая геометрия. М:, Изд-во МГУ, 1998, стр. 13,32-35.
  2. В.В. Воеводин. Численные методы алгебры (теория и алгоритмы). М:, Наука, 1966, стр. 64-67, 106-110.



Задание 4. Написать параллельную программу поиска всех решений задачи размещения N ферзей на шахматной доске K*K. Решением считается такое размещение, при котором ферзи не бьют друг друга.

Входные параметры программы:

  • P - число параллельных процессов;
  • N - количество ферзей;
  • K - размер доски.
Замечание. Хорошая параллельная программа подразумевает, что, по возможности, выполняются следующие условия:
  1. Работа в параллельных процессах не дублируется.
  2. Вычислительная нагрузка на каждый процесс примерно одинакова.
  3. При увеличении числа процессоров в n раз (и соответствующем увеличении числа процессов), время решении задачи уменьшается, в идеальном случае, в n раз.
Поддержка в Интернет:
лаборатория Параллельных информационных технологий НИВЦ МГУ Rambler's Top100