Page 261 - Bkhargava_-_Grokaem_algoritmy

260 Глава 11. Что дальше?

Параллельные алгоритмы

Следующие три темы связаны с масштабируемостью и обработкой больших
объемов данных. Когда-то компьютеры становились все быстрее и быстрее.
Если вы хотели, чтобы ваш алгоритм работал быстрее, можно было подо­
ждать несколько месяцев и запустить программу на более мощном компью­
тере. Но сейчас этот период подошел к концу. Современные компьютеры
и ноутбуки оснащаются многоядерными процессорами. Чтобы алгоритм
заработал быстрее, необходимо преобразовать его в форму, подходящую
для параллельного выполнения сразу на всех ядрах!
Рассмотрим простой пример. Лучшее время выполнения для алгоритма
сортировки равно приблизительно О(п log п). Известно, что массив не­
возможно отсортировать за время О(п), если толъко не восполъзоватъся
параллельным алгоритмом! Существует параллельная версия быстрой сор­
тировки, которая сортирует массив за время О( п ).
Параллельный алгоритм трудно разработать. И так же трудно убедиться
в том, что он работает правильно, и понять, какой прирост скорости он
обеспечивает. Одно можно заявить твердо: выигрыш по времени не линеен.
Следовательно, если процессор вашего компьютера имеет два ядра вместо
одного, из этого не следует, что ваш алгоритм по волшебству заработает
вдвое быстрее. Это объясняется несколькими причинами.
о Затраты ресурсов на управление параллелизмом - допустим, нужно
отсортировать массив из 1000 элементов. Как разбить эту задачу для
выполнения на двух ядрах? Выделить каждому ядру 500 элементов ,
а затем объединить два отсортированных массива в один большой отсор­
тированный массив? Слияние двух массивов требует времени.

о Распределение нагрузки - допустим, необходимо выполнить 1 О задач,
и вы назначаете каждому ядру 5 задач. Однако ядру А достаются все
простые задачи, поэтому оно выполняет свою работу за 1 О секунд, тогда
как ядро В справится со сложными задачами только за минуту. Это оз­
начает, что ядро А целых 50 секунд простаивает, пока ядро В выполняет
всю работу! Как организовать равномерное распределение работы, чтобы
оба ядра трудились с одинаковой интенсивностью?

Если вас интересует теоретическая сторона производительности и мас­
штабируемости, возможно, параллельные алгоритмы - именно то, что вам
нужно!

www.trk.kg