Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683

В сетях сортировки актуальна задача минимизации времени 
работы. Для значений n <= 10 известны сети, обладающие минимально 
возможным временем. Для шести процессоров известна сеть 
сортировки, выполняющаяся всего за 5 шагов (рис. 51). 
 
Рис. 50. Одновременное выполнение на шаге 5 компараторов (1, 2), (3, 4) и (5, 6) 
Рис. 51. Сеть сортировки для шести процессоров 

---

141 
 
Глава 
14. 
Технологии 
параллельного 
программирования: 
использование традиционных последовательных 
языков 
 
14.1. Принципы анализа параллельных алгоритмов 
При проведении анализа параллельных алгоритмов
 
рассматриваются 
две характеристики ‒ коэффициент ускорения и стоимость. 
Коэффициент 
ускорения
характеризует скорость работы параллельного алгоритма 
относительно 
наилучшего 
последовательного 
алгоритма. 
Для 
последовательного алгоритма сортировки необходимо O(N log N) операций. 
Для параллельного алгоритма сортировки (сложность O(N)) составит O(log 
N). 
Стоимость
вычисляется как произведение сложности алгоритма и 
количества необходимых для вычисления процессоров. Так для 
параллельного алгоритма сортировки O(N), при количестве процессоров 
равном числу входных записей, стоимость составит O(N
2
). То есть по
сравнению с алгоритмом последовательной сортировки, стоимость которого 
составляет O(N log N), параллельный алгоритм обладает большей 
стоимостью. Для того чтобы параллельный алгоритм сортировки имел 
смысл, число используемых процессоров не должно меняется при росте 
длины входных данных, и быть в значительной степени меньше 
предполагаемого объема входных данных