Методические указания к лабораторным работам для студентов V курса фпмиИ



Скачать 275.63 Kb.
страница1/4
Дата06.11.2016
Размер275.63 Kb.
  1   2   3   4
Министерство образования и науки Российской Федерации
Новосибирский Государственный Технический Университет

Параллельные вычислительные методы


Методические указания

к лабораторным работам для студентов V курса ФПМиИ

(направление 010500 – Прикладная математики и информатика)

дневного отделения

НОВОСИБИРСК

2010

Составители: И.М. Куликов, к.ф.-м.н.



Д.Н. Горпинченко
Рецензент: В.А. Вшивков, д.ф.-м.н., профессор

Работа подготовлена на кафедре параллельных вычислительных технологий

© Новосибирский государственный технический университет, 2010 г.
ОГЛАВЛЕНИЕ


Лабораторная работа №1 4

Лабораторная работа №2 6

Лабораторная работа №3 9

Лабораторная работа №4 11

Лабораторная работа №5 14

Функции замера времени 19

Справочник по функциям MPI 19



Лабораторная работа №1



Параллельные методы сортировки данных.
Цель работы.

Изучение метода сортировки Батчера. Реализация сортировки Батчера на многоядерных архитектурах. Исследование алгоритмической сложности последовательной и параллельной реализаций сортировки.


Теоретическая часть.

Сортировка является одной из типовых проблем обработки данных, и обычно понимается как задача размещения элементов неупорядоченного набора, состоящего из значений в порядке монотонного убывания или возрастания .

Пусть дана последовательность целых чисел , где . Необходимо отсортировать данную последовательность по возрастанию. Для получения алгоритма сортировки, временная сложность которого меньше, чем необходимо выбирать для сравнения элементы, расположенные на каком-то шаге друг от друга, при этом шаг должен изменяться во время работы алгоритма. Эта идея была реализована в алгоритме сортировки Шелла, где шаг убывает. Однако проблема сортировки Шелла – невозможность одновременного выполнения сравнений и перестановок, что отсутствует в алгоритме Батчера. Приведём алгоритм сортировки Батчера:
Input: a[0..N-1], t, N = 2t

for p = 2t-1, 2t-2,..., 1 do

r = 0

d = p


for q = 2t-1, 2t-2,..., p do

for k = 0,..., N-d-1 do in parallel



if k&p = r then

if a[k] > a[k+d] then

swap(a[k], a[k+d])

end if

end if

end for

d = q – p

r = p


end for

end for



Output: a[0..N-1], a[i] < a[i+1]
Пример 1. Работы алгоритма сортировки Батчера.


p q r d

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

8 8 0 8
4 8 0 4

4 4 4 4

2 8 0 2

2 4 2 6



2 2 2 2

1 8 0 1
1 4 1 7


1 2 1 3


1 1 1 1

Результат



53 87 52 61 98 17 89 27 65 42 15 59 62 77 76 3













53 42 15 59 62 17 76 3 65 87 52 61 98 77 89 27










53 17 15 3 62 42 76 59 65 77 52 27 98 87 89 61






53 17 15 3 62 42 52 27 65 77 76 59 98 87 89 61







15 3 53 17 52 27 62 42 65 59 76 77 89 61 98 87










15 3 53 17 52 27 62 42 65 59 76 77 89 61 98 87



15 3 52 17 53 27 62 42 65 59 76 61 89 77 98 87




3 15 17 52 27 53 42 62 59 65 61 76 77 89 87 98










3 15 17 52 27 53 42 62 59 65 61 76 77 89 87 98

3 15 17 42 27 53 52 61 59 65 62 76 77 89 87 98

3 15 17 27 42 52 53 59 61 62 65 76 77 87 89 98




Практическая часть.

  1. Реализовать алгоритм сортировки Батчера для одноядерной архитектуры,

  2. Реализовать алгоритм сортировки Батчера для многоядерной архитектуры в соответствии с заданием,

  3. Оценить арифметическую сложность последовательной и параллельной реализаций метода,

  4. Посчитать теоретическое и практическое ускорение параллельной программы,

  5. Разработать и провести полную систему тестов сортировки массива в соответствии с заданием.


Варианты заданий.

  1. Сортировка массива с количеством элементов на количестве ядер кратных двум,

  2. Сортировка массива с количеством элементов на количестве ядер не кратных двум,

  3. Сортировка массива с количеством элементов на количестве ядер кратных двум,

  4. Сортировка массива с количеством элементов на количестве ядер не кратных двум,

  5. Сортировка массива с произвольным количеством элементов на произвольном количестве ядер.



  1   2   3   4


База данных защищена авторским правом ©bezogr.ru 2016
обратиться к администрации

    Главная страница