Сети сортировки: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 2: Строка 2:
 
=== Словесное описание алгоритма ===
 
=== Словесное описание алгоритма ===
  
'''Сети сортировки''' используются для быстрой сортировки больших объёмов данных. Их основное преимущество заключается в предоставлении жёсткого расписания, обеспечивающего параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить масштабируемые и немасштабируемые сети сортировки. К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных с точки зрения времени выполнения]] сетей для 6, 9, 10, 12 и 16 процессоров [1].
+
'''Сети сортировки''' используются для параллельной сортировки больших объемов данных. Каждая сеть сортировки задаёт
 +
расписание, обеспечивающее безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить сети сортировки, правила создания которых известны для произвольного числа процессоров, и сети, известные только для массивов некоторых фиксированных размеров.
 +
 
 +
К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 9, 10, 12 и 16 процессоров [1].
  
 
=== Математическое описание ===
 
=== Математическое описание ===

Версия 21:51, 23 февраля 2015

Содержание

1 Описание свойств и структуры алгоритма

1.1 Словесное описание алгоритма

Сети сортировки используются для параллельной сортировки больших объемов данных. Каждая сеть сортировки задаёт расписание, обеспечивающее безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить сети сортировки, правила создания которых известны для произвольного числа процессоров, и сети, известные только для массивов некоторых фиксированных размеров.

К первым следует отнести сеть сортировки простой вставкой, сеть четно-нечетной перестановки, сеть четно-нечетного слияния Бетчера и сеть битонной сортировки. К немасштабируемым следует отнести ряд оптимальных, с точки зрения времени выполнения сортировки, сетей для 6, 9, 10, 12 и 16 процессоров [1].

1.2 Математическое описание

Исходные данные: одномерный массив [math]n[/math] чисел.

Вычисляемые данные: упорядоченный массив.

1.3 Вычислительное ядро алгоритма

1.4 Описание схемы реализации последовательного алгоритма

1.5 Последовательная сложность алгоритма

1.6 Информационный граф

1.7 Описание ресурса параллелизма алгоритма

1.8 Описание входных и выходных данных

1.9 Свойства алгоритма

2 Программная реализация

2.1 Особенности реализации последовательного алгоритма

2.2 Описание локальности данных и вычислений

2.2.1 Описание локальности алгоритма

2.2.2 Описание локальности реализации алгоритма

2.2.2.1 Описание структуры обращений в память и качественная оценка локальности
Профиль доступа к памяти


2.2.2.2 Количественная оценка локальности

2.3 Возможные способы и особенности реализации параллельного алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Описание масштабируемости алгоритма

2.4.2 Описание масштабируемости реализации алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

  1. Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.
  2. Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.