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

[непроверенная версия]

Версия 04:13, 7 декабря 2014

Содержание

1 Описание свойств и структуры алгоритма
2 Программная реализация
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 с.

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