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

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


Смотрите также:
Цель лабораторной ознакомится с различными методами сортировки данных...
«нейроинформатика, её приложения и анализ данных»...
Базы данных, базы знаний и экспертные системы 2...
«Алгоритмы сортировки одномерных массивов»...
Порядок работы на официальном сайте «Реестра государственных контрактов...
Курсовая работа состоит в выполнении 2-х последовательных заданий: 1) задания по быстрому поиску...
План Прикладная политология, ее цели, методы...
Программа дисциплины Компьютерные методы анализа социологических данных (Введение в...
Программа дисциплины «Компьютерные методы анализа социологических данных» (Введение в...
О автор: Тенгиз Куправа www kuprava ru сновы статистического анализа...
Реферат по дисциплине  на тему: «»...
Учебная программа дисциплины Методология и методы психолого-педагогических исследований...



Загрузка...
страницы:   1   2   3   4
скачать
Министерство образования и науки Российской Федерации


Новосибирский Государственный Технический Университет





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


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

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

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

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


НОВОСИБИРСК

2010


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

Д.Н. Горпинченко





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


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


© Новосибирский государственный технический университет, 2010 г.


ОГЛАВЛЕНИЕ




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

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

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

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

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

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

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



^

Лабораторная работа №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/4
Дата24.08.2011
Размер1 Mb.
ТипЛабораторная работа, Образовательные материалы
Добавить документ в свой блог или на сайт

страницы:   1   2   3   4
плохо
  1
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх