Справочник по функциям mpi 19 Лабораторная работа №1




Скачать 265.11 Kb.
НазваниеСправочник по функциям mpi 19 Лабораторная работа №1
страница1/6
Дата публикации24.03.2013
Размер265.11 Kb.
ТипСправочник
vbibl.ru > Математика > Справочник
  1   2   3   4   5   6
ОГЛАВЛЕНИЕ


Лабораторная работа №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   5   6

Добавить документ в свой блог или на сайт


Похожие:

Справочник по функциям mpi 19 Лабораторная работа №1 iconЛабораторная работа №1,2
Лабораторная работа №2. Организация переписка с помощью электронной почты (E-mail). 22

Справочник по функциям mpi 19 Лабораторная работа №1 iconЭта книга так же рассказывает и об архитектуре, затрагивая вопросы...
Подробный справочник по функциям встроенного языка, интерфейсу и архитектуре дизассемблера ida Pro 01 с уточнением особенностей младших...

Справочник по функциям mpi 19 Лабораторная работа №1 iconСправочник Учетных систем 9 2 Справочник типов запросов к Учетным...
Взаимодействие системы «дбо bs-client. Частный клиент» с учетными системами банка

Справочник по функциям mpi 19 Лабораторная работа №1 iconСправочник Учетных систем 10 2 Справочник типов запросов к Учетным...
Взаимодействие системы «дбо bs-client. Частный клиент» с учетными системами банка

Справочник по функциям mpi 19 Лабораторная работа №1 iconКурсовая работа по экономической теории на тему: «Сбережения и инвестиции в рыночной экономике»
Данная работа будет посвящена функциям сбережений и инвестиций в рыночной экономике. Самое общее определение указанных понятий можно...

Справочник по функциям mpi 19 Лабораторная работа №1 iconСправочник заведующего кдл. 2011. № С. 61-78. Тамбовское областное...
Сравнение двух фенотипических методов выявления продукции беталактамаз расширенного спектра госпитальными штаммами Klebsiella pneumoniae//...

Справочник по функциям mpi 19 Лабораторная работа №1 iconСправочник заведующего кдл. 2011. № С. 73-79. Тамбовское областное...
Использование технологии пцр-реальное время для выявления и дифференциации вирусов папилломы человека высокого канцерогенного риска//...

Справочник по функциям mpi 19 Лабораторная работа №1 iconЛабораторная работа №2. 13 Работа с базами данных lotus notes 13...
Проблемы возникают при выборе средств автоматизации документооборота, поскольку в настоящее время существует большое количество программных...

Справочник по функциям mpi 19 Лабораторная работа №1 iconЛабораторная работа №1 по дисциплине «организация ЭВМ и систем»
Работа выполняется с целью изучения структуры микропроцессора (МП) кр580ВМ80А и практического овладения аппаратно программными средствами...

Справочник по функциям mpi 19 Лабораторная работа №1 iconЛабораторная работа №2 Тема: Нормализация данных

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница