Статья Вячеслава Любченко «Параллельные сортировки: быстрее, проще... умнее» («Открытые системы», 2004, № 5) вызвала дискуссию, предметом которой стал ряд достаточно спорных утверждений автора. Исторически, задача об обедающих философах была предложена для демонстрации коллизий между асинхронными параллельными процессами. На ней же рассматривались и различные способы разрешения возникающих конфликтов. Синхронизировав поведение философов, автор радикально решил все проблемы, однако, вместе с этим, исчезла и сама суть задачи: жесткое тактирование процесса, введение дополнительных ограничений не способствовало стимуляции их мышления. Философы превратились в винтиков конвейера по сортировке вилок.
Если же говорить серьезно, то разнообразные алгоритмы параллельной сортировки многократно рассматривались в различных источниках. Представленный в статье алгоритм конвейерной сортировки — это разновидность пузырьковой параллельной сортировки, суть которой заключается в одновременном сравнении соседних элементов и их обмене. При этом происходит чередование четного и нечетного элемента в качестве первого операнда на каждом последующем шаге. Небольшой отличительной чертой алгоритма конвейерной сортировки является сравнение первого и последнего элементов на первом и последующих нечетных шагах. Часто это укорачивает нахождение результата из-за обмена, прошедшего на первом шаге, однако такая перестановка на деле выполняется только один раз, так как в последующем первый элемент всегда будет меньше последнего (изменение последнего элемента возможно только в сторону увеличения его значения, а изменение первого элемента — только в сторону уменьшения). Поэтому, сравнив первый элемент с последним на самом первом шаге, в последующем можно этим не заниматься. В книге A. Grama, A. Gupta, G. Karypis, V. Kumar, Introduction to Parallel Computing (Addison Wesley, 2003) приведены и более эффективные алгоритмы (параллельная сортировка Шелла, быстрая параллельная сортировка и др.), и практически для всех методов даны оценки вычислительной сложности. С ними, а не с последовательными версиями, стоило бы сравнивать алгоритм, предлагаемый автором.
Следует отметить, что данная статья продолжает список публикаций автора, посвященных использованию параллельно работающих синхронных автоматов для решения различных задач. Это интересное направление, определяющее один из способов организации параллельных вычислений; используя его, можно получать интересные альтернативные реализации любых алгоритмов, так как подобная модель универсальна. Однако автор не ограничивается применением данной концепции для разработки программ, а пытается утверждать, что построенная на базе этих автоматов универсальная параллельная машина эффективнее существующих параллельных систем. Эта мечта о супервычислителе проскальзывает из работы в работу и никак не может захватить массы разработчиков, которые, судя по высказываниям автора, способны на создание только специализированных и низкоэффективных систем.
Отдельного анализа заслуживает предлагаемый способ оценки времени выполнения алгоритмов, базирующийся на понятии абстрактного времени. Автор сравнивает такты, каждый из которых включает несколько последовательных шагов между переходами-перекрестками. Однако при этом ничего не говорится о количестве таких шагов в разных тактах. Именно время выполнения линейных участков, соответствующих функциям переходов, игнорируемое в статье, и является чаще всего определяющим для времени выполнения программы. Подобное допустимо для абстрактных моделей, но вряд ли приведет к эффективному использованию реальных систем.
Отличие во времени выполнения параллельных ветвей программы характерно для вычислительных задач. Одновременное выполнение одного и того же алгоритма даже на одинаковых процессорах может также сильно отличаться по времени за счет различных по значениям данных, используемых в итерационных формулах. Проблема выливается в поиск методов эффективного использования вычислительных ресурсов за счет неоднородного перераспределения процессов и данных, а также за счет организации их асинхронного взаимодействия. Неоднородность вычислительной нагрузки и связанная с этим проблема эффективного использования ресурсов рассмотрена, например, в книге A.L. Lastovetsky, Parallel Computing on Heterogeneous Networks (John Wiley & Sons, 2003).
Вместе с тем, алгоритмы сортировки легко в первом приближении сопоставить по количеству операций сравнения и перестановок, выполняемых на каждом шаге. Можно также определить количество шагов, используемых для достижения результата в благоприятном, неблагоприятном и среднем случаях. Следует также отметить, что в реальной ситуации ресурсные ограничения ведут к модификации идеализированных алгоритмов, что вынуждает использовать комбинированные решения: сочетать последовательные и параллельные сортировки. Чаще всего сортировка на отдельных процессорах выполняется последовательно, после чего выполняется слияние упорядоченных фрагментов.
Александр Легалов (lai@fivt.krasn.ru) — профессор кафедры нейроЭВМ Красноярского государственного технического университета (Красноярск).
