Сети сортировки: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Lira (обсуждение | вклад) Нет описания правки |
Lira (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
== Описание свойств и структуры алгоритма == | == Описание свойств и структуры алгоритма == | ||
=== Словесное описание алгоритма === | === Словесное описание алгоритма === | ||
'''Сети сортировки''' используется в качестве быстрого алгоритма сортировки больших объемов данных. Их основное преимущество заключается в предоставлении жесткого расписания, обеспечивающего безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить масштабируемые и не масштабируемые сети сортировки. К первым следует отнести [сеть сортировки простой вставкой], [сеть четно-нечетной перестановки], [сеть четно-нечетного слияния Бетчера] и [сеть битонной сортировки]. К не масштабируемым следует отнести ряд оптимальных с точки зрения времени выполнения сетей для 6, 9, 10, 12 и 16 процессоров | '''Сети сортировки''' используется в качестве быстрого алгоритма сортировки больших объемов данных. Их основное преимущество заключается в предоставлении жесткого расписания, обеспечивающего безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить масштабируемые и не масштабируемые сети сортировки. К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К не масштабируемым следует отнести ряд оптимальных (с точки зрения времени выполнения) сетей для 6, 9, 10, 12 и 16 процессоров [1]. | ||
=== Математическое описание === | === Математическое описание === | ||
| Строка 11: | Строка 10: | ||
Вычисляемые данные: упорядоченный массив. | Вычисляемые данные: упорядоченный массив. | ||
=== Вычислительное ядро алгоритма === | |||
=== Описание схемы реализации последовательного алгоритма === | |||
=== Последовательная сложность алгоритма === | |||
=== Информационный граф === | |||
=== Описание ресурса параллелизма алгоритма === | |||
=== Описание входных и выходных данных === | |||
=== Свойства алгоритма === | |||
== Программная реализация == | |||
=== Особенности реализации последовательного алгоритма === | |||
=== Описание локальности данных и вычислений === | |||
==== Описание локальности алгоритма ==== | |||
==== Описание локальности реализации алгоритма ==== | |||
===== Описание структуры обращений в память и качественная оценка локальности ===== | |||
===== Количественная оценка локальности ===== | |||
=== Возможные способы и особенности реализации параллельного алгоритма === | |||
=== Масштабируемость алгоритма и его реализации === | |||
==== Описание масштабируемости алгоритма ==== | |||
==== Описание масштабируемости реализации алгоритма ==== | |||
=== Динамические характеристики и эффективность реализации алгоритма === | |||
=== Выводы для классов архитектур === | |||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
== Литература == | == Литература == | ||
* Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с. | |||
Версия от 01:06, 7 декабря 2014
Описание свойств и структуры алгоритма
Словесное описание алгоритма
Сети сортировки используется в качестве быстрого алгоритма сортировки больших объемов данных. Их основное преимущество заключается в предоставлении жесткого расписания, обеспечивающего безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить масштабируемые и не масштабируемые сети сортировки. К первым следует отнести сеть сортировки простой вставкой, сеть четно-нечетной перестановки, сеть четно-нечетного слияния Бетчера и сеть битонной сортировки. К не масштабируемым следует отнести ряд оптимальных (с точки зрения времени выполнения) сетей для 6, 9, 10, 12 и 16 процессоров [1].
Математическое описание
Исходные данные: одномерный массив [math]\displaystyle{ n }[/math] чисел.
Вычисляемые данные: упорядоченный массив.
Вычислительное ядро алгоритма
Описание схемы реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Описание ресурса параллелизма алгоритма
Описание входных и выходных данных
Свойства алгоритма
Программная реализация
Особенности реализации последовательного алгоритма
Описание локальности данных и вычислений
Описание локальности алгоритма
Описание локальности реализации алгоритма
Описание структуры обращений в память и качественная оценка локальности
Количественная оценка локальности
Возможные способы и особенности реализации параллельного алгоритма
Масштабируемость алгоритма и его реализации
Описание масштабируемости алгоритма
Описание масштабируемости реализации алгоритма
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
Литература
- Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.