Метод Гауса - паралельний алгоритм

· Масштабування і розподіл підзадач по процесорах

Основним видом інформаційної взаємодії підзадач є операція передачі даних від одного процесора всім процесорам обчислювальної системи

Як результат, для ефективної реалізації необхідних інформаційних взаємодій між базовими підзадачами, топологія мережі передачі даних повинні мати структуру гиперкуба або повного графа.

Метод зв'язаних градієнтів

· Метод зв'язаних градієнтів може бути застосований для вирішення системи лінійних рівнянь з симетричною, позитивно визначеною матрицею

· Матриця А є симетричною, якщо вона співпадає з своєю транспонованою матрицею

· тобто А=АТ

· Матриця А називається позитивно визначеною, якщо для будь-якого вектора x справедливе: xTAx>0.

· Після виконання n ітерацій методу зв'язаних градієнтів (n є порядок вирішуваної системи лінійних рівнянь), чергове наближення xn співпадає з точним рішенням.

67. Навести і описати паралельні методи сортування.

Сортування є однією з типових проблем обробки даних і звичайно розуміється як задача розміщення елементів неврегульованого набору значень

в порядку монотонного зростання або убування

Бульбашкове сортування:

послідовний алгоритм

// Последовательный алгоритм пузырьковой copтировки

BubbleSort(продублируйте A[], int n){

для (i=0; i<n-1; i++)

для (j=0; j<n-i; j++)

compare_exchange(,[j+1]);

· Трудомісткість обчислень має порядок о(n²)

· В прямому вигляді складний для розпаралелювання

Бульбашкове сортування: алгоритм чет-нечетной перестановки

Вводяться два різні правила виконання ітерацій методу:

· на всіх непарних ітераціях порівнюються пари (a1, a2), (a3, a4)..., (an-1,an) (при парному n)

· на парних ітераціях обробляються елементи (a2, a3), (a4, a5)... (an-2,an-1).

Сортування Шелла: паралельний алгоритм

Хай топологія комунікаційної мережі має вид N-мерного гиперкуба (тобто кількість процесорів рівна p=2N).

Дії алгоритму полягають в наступному:

· Перший етап (N ітерацій): виконання операції "порівняти і розділити" для кожної пари процесорів в гиперкубе. Формування пар процесорів відбувається за правилом - на кожній ітерації i, 0 Ј i < N, парними стають процесори, у яких відмінність в бітових представленні їх номерів є тільки у позиції N-i

· Другий етап: реалізація звичайних ітерацій паралельного алгоритму чет-нечетной перестановки. Ітерації виконуються до припинення фактичної зміни сортованого набору. Загальна їх кількість L може бути різною - від 2 до p.

· Швидке сортування

послідовний алгоритм.

·Алгоритм швидкого сортування, запропонованої Хоаром (Hoare C.A.R.), грунтується на послідовному розділенні сортованого набору даних на блоки меншого розміру таким чином, що між значеннями різних блоків забезпечується відношення впорядкованості (для будь-якої пари блоків всі значення одного з цих блоків не перевищують значень іншого блоку):

·На першій ітерації методу здійснюється розподіл початкового набору даних на перші дві частини - для організації такого розподілу вибирається деякий ведучий елемент і всі значення набору, менші провідного елемента, переносяться в перший формований блок, вся решта значень утворює другий блок набору

·На другій ітерації сортування описані правила застосовуються рекурсивно для обох сформованих блоків і т.д.

При оптимальному виборі провідних елементів після виконання log2n ітерацій початковий масив даних виявляється впорядкованим

Сортування з використанням регулярного набору зразків: паралельний алгоритм.

Перший етап: впорядковування блоків кожним процесором незалежне один від одного за допомогою звичайного алгоритму швидкого сортування; далі кожний процесор формує набір з елементів своїх блоків з індексами

0, m, 2m.,(p-1) m, де m=n/p2

Другий етап: всі сформовані на процесорах набори даних збираються на одному з процесорів системи і об'єднуються в ході послідовного зливання в одну впорядковану множину; з одержаної безлічі значень з елементів з індексами

формується набір провідних елементів, який передається всім процесорам;

на завершення етапу кожний процесор виконує розділення свого блоку на p частин з використанням одержаного набору провідних значень

Третій етап: кожний процесор розсилає виділені раніше частини свого блоку всій решті процесорів системи відповідно до порядку нумерації - частина j, 0Ј j<p, кожного блоку пересилається процесору з номером j

Четвертий етап: кожний процесор виконує злиття p одержаних частин в один відсортований блок.

· Розглянуті способи паралельного виконання трьох широко відомих методу впорядкування даних:

·Алгоритм бульбашкового сортування

·Сортування Шелла

·Швидке сортування

·Для алгоритму швидкого сортування приведено дві додаткові модифікації:

·Узагальнене швидке сортування

·Сортування з використанням регулярного набору зразків

· Представлена програмна реалізація методу узагальненого швидкого сортування

· Використаний порядок викладу паралельних методів сортування можна розглядати як приклад процесу послідовного вдосконалення паралельних обчислень з метою поліпшення показників прискорення і ефективності

68. ----

69.Навести і описати паралельні методи розв'язання диференціальних рівнянь у частинних похідних.

Завдання Пуассона, тобто рішення диференціальних рівнянь в приватних похідних, виражається наступними рівняннями:

- усередині області (8.1)

- на межі (8.2)

Вважатимемо, що область рішення є квадратною. Щоб знайти наближене рішення, визначимо квадратну сітку, включає точки (х _і. у_і), що задаються як

Таким чином, уздовж кожного краю сітки є п +2 точки. Слід знайти апроксимацію и (х,у) в точках (х _і,, у _і) вибраної сітки. Позначимо через и_ij значення і u (x_i, y_j), через h відстань мiж точками, рівне 1/(n+1). Тоді формула 8.1. для кожної з точок виглядатиме таким чином:

Обчислюємо значення u_ij в кожній точці сітки, які заміщують попередні значення, використовуючи вираз

Цей процес називається ітераціями Якобі і повторюється до отримання результату. Фрагмент програми для цього випадку такий:

70. ---

71. У вихідному коді програми на мові С вставити пропущені виклики процедур підключення МРІ, визначення кількості процесів і рангу процесів.

#include "mpi.h"

#include <stdio.h>

int main (int argc, char *argv[])

{

int myid, numproc;

MPI_Status status;

MPI_Init (&agrc &argv);

MPI_Comm_size (MPI_COMM_WORLD &numproc);

MPI_Comm_rank (MPI_COMM_WORLD &myid);

fprintf(stdout,”Process%d of %d\n”,myid,numproces);

MPI_Finalesize();

return 0;

}

72. Програма, яка виводить «Hello Word from process i for n».

#include "mpi.h"

#include <stdio.h>

int main (int argc, char *argv[])

{

int myid, numproc;

MPI_Status status;

MPI_Init (&agrc &argv);

MPI_Comm_size (MPI_COMM_WORLD &numproc);

MPI_Comm_rank (MPI_COMM_WORLD &myid);

fprintf(stdout,”Hello World from process%d for %d\n”,myid,numproces);

MPI_Finalesize();

return 0;

}

73. Програма генерації чисел в одному процесі і сумування їх у іншому процесі і надсилення результату в перший процес.

74. ---

75.---

76. ---

77. ---

78. Навести приклад найпростішої програми на мові С з використанням технології OpenMP, яка виводить прізвище студента.

int main ()

{ #pragma omp parallel

{ printf (“…………”);

} return 0;

}

79. ---

80. Написати програму з використанням бібліотеки OpenMP на мові С/С++ для вимірювання часу cумування квадратів чисел від 0 до 10000000. Для усереднення накладних витрат повторити достатню кількість операцій обчислення з метою отримання значень часу в межах доль секунди, повторити тестування декілька разів (наприклад, 10) і усереднити результати. А також написати аналогічну програму без бібліотеки OpenMP на мові C/C++ та виконати аналогічні дії по визначенню часу роботи програми. Порівняти отримані значення часу.

Пример 2 иллюстрирует применение функций omp_get_wtime() и

omp_get_wtick() для работы с таймерами в OpenMP. В данном примере

производится замер начального времени, затем сразу замер конечного време-

ни. Разность времён даёт время на замер времени. Кроме того, измеряется

точность системного таймера.

#include <stdio.h>

#include <omp.h>

int main(int argc, char *argv[])

{

Дата добавления: 2015-08-18