Сети сортировки: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Lira (обсуждение | вклад) |
Lira (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
== Описание свойств и структуры алгоритма == | == Описание свойств и структуры алгоритма == | ||
| − | |||
=== Словесное описание алгоритма === | === Словесное описание алгоритма === | ||
| − | '''Сети сортировки''' используется в качестве быстрого алгоритма сортировки больших объемов данных. Их основное преимущество заключается в предоставлении жесткого расписания, обеспечивающего безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить масштабируемые и не масштабируемые сети сортировки. К первым следует отнести [сеть сортировки простой вставкой], [сеть четно-нечетной перестановки], [сеть четно-нечетного слияния Бетчера] и [сеть битонной сортировки]. К не масштабируемым следует отнести ряд оптимальных с точки зрения времени выполнения сетей для 6, 9, 10, 12 и 16 процессоров | + | '''Сети сортировки''' используется в качестве быстрого алгоритма сортировки больших объемов данных. Их основное преимущество заключается в предоставлении жесткого расписания, обеспечивающего безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить масштабируемые и не масштабируемые сети сортировки. К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К не масштабируемым следует отнести ряд оптимальных (с точки зрения времени выполнения) сетей для 6, 9, 10, 12 и 16 процессоров [1]. |
=== Математическое описание === | === Математическое описание === | ||
| Строка 11: | Строка 10: | ||
Вычисляемые данные: упорядоченный массив. | Вычисляемые данные: упорядоченный массив. | ||
| + | === Вычислительное ядро алгоритма === | ||
| + | === Описание схемы реализации последовательного алгоритма === | ||
| + | === Последовательная сложность алгоритма === | ||
| + | === Информационный граф === | ||
| + | === Описание ресурса параллелизма алгоритма === | ||
| + | === Описание входных и выходных данных === | ||
| + | === Свойства алгоритма === | ||
| + | == Программная реализация == | ||
| + | === Особенности реализации последовательного алгоритма === | ||
| + | === Описание локальности данных и вычислений === | ||
| + | ==== Описание локальности алгоритма ==== | ||
| + | ==== Описание локальности реализации алгоритма ==== | ||
| + | ===== Описание структуры обращений в память и качественная оценка локальности ===== | ||
| + | ===== Количественная оценка локальности ===== | ||
| + | === Возможные способы и особенности реализации параллельного алгоритма === | ||
| + | === Масштабируемость алгоритма и его реализации === | ||
| + | ==== Описание масштабируемости алгоритма ==== | ||
| + | ==== Описание масштабируемости реализации алгоритма ==== | ||
| + | === Динамические характеристики и эффективность реализации алгоритма === | ||
| + | === Выводы для классов архитектур === | ||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Литература == | == Литература == | ||
| − | + | * Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
Версия 04:06, 7 декабря 2014
Содержание
- 1 Описание свойств и структуры алгоритма
- 1.1 Словесное описание алгоритма
- 1.2 Математическое описание
- 1.3 Вычислительное ядро алгоритма
- 1.4 Описание схемы реализации последовательного алгоритма
- 1.5 Последовательная сложность алгоритма
- 1.6 Информационный граф
- 1.7 Описание ресурса параллелизма алгоритма
- 1.8 Описание входных и выходных данных
- 1.9 Свойства алгоритма
- 2 Программная реализация
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Описание локальности данных и вычислений
- 2.3 Возможные способы и особенности реализации параллельного алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
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 Литература
- Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.
