Параллельные сортировки на общей памяти

Слайд 2

Сортировка на линейных сетях

Если число процессоров равно числу сортируемых значений , то

Сортировка на линейных сетях Если число процессоров равно числу сортируемых значений ,
сортировку можно осуществить, передавая сети в каждом цикле одно значение. Первый процессор читает поданное значение, сравнивает его с текущим и передает его большее значение своему соседу. Остальные процессоры делают то же самое : сохраняют меньшее из двух значений и пересылают большее следующему звену в цепочку.

Слайд 3

Сортировка на линейных сетях

A.

Сортировка на линейных сетях A.

Слайд 4

Сортировка на линейных сетях

B.

Сортировка на линейных сетях B.

Слайд 5

Сортировка на линейных сетях

В.

Сортировка на линейных сетях В.

Слайд 6

Характеристики :

В общем случае алгоритм выполняет 2 * (N — 1) +

Характеристики : В общем случае алгоритм выполняет 2 * (N — 1)
1 (т.е. O(N)), действий.
В работе принимают участие N процессоров => стоимость алгоритма равна O(N ), что эквивалентно самым медленным нашим сортировкам.

Сортировка на линейных сетях

Слайд 7

Четно-нечетная сортировка перестановками

В четно нечетной сортировке сравниваются соседние значения и при необходимости

Четно-нечетная сортировка перестановками В четно нечетной сортировке сравниваются соседние значения и при необходимости переставляются.
переставляются.

Слайд 8

Четно-нечетная сортировка перестановками

Пример для списка : 15, 18, 13, 12, 17, 11, 19, 16,

Четно-нечетная сортировка перестановками Пример для списка : 15, 18, 13, 12, 17, 11, 19, 16, 14
14

Слайд 9

Четно-нечетная сортировка перестановками

Все сравнения происходят параллельно, поэтому всякий проход цикла выполняет два сравнения

Четно-нечетная сортировка перестановками Все сравнения происходят параллельно, поэтому всякий проход цикла выполняет
и общее время работы равно O(N).
Стоимость алгоритма равна величине N/2 * O(N) — несколько меньше, чем у предыдущего алгоритма, но все равно порядка O(N^2).

Характеристики

Слайд 10

Другие алгоритмы

Если у нас список без повторений, то мы можем отсортировать его

Другие алгоритмы Если у нас список без повторений, то мы можем отсортировать
с помощью подсчета. С одним процессором на каждое входное значение местоположение каждого элемента можно определить за O(N) сравнений. Нам требуется N процессоров, поэтому стоимость такого подхода равна O(N^2).
Еще существуют способы параллельного слияния двух списков, реализующие оптимальную стоимость O(N). При использовании не более чем N/ log(N) процессоров. Разбив список на N/ log(N) частей, и отсортировав каждую из них эффективным
Имя файла: Параллельные-сортировки-на-общей-памяти.pptx
Количество просмотров: 43
Количество скачиваний: 0