Специальные методы сортировки a

Параллельная сортировка-слияние
Как сделать так, чтобы несколько независимых процессоров работали совместно над одной задачей сортировки? Управляют ли процессоры внешними запоминающими устройствами или являются самостоятельными вычислительными системами, этот вопрос лежит в основе разработки алгоритмов для высокопроизводительных вычислительных систем. Тема параллельных вычислений в последнее время широко изучается. Разработано множество типов компьютеров с параллельными процессорами, и предложены разнообразные модели параллельных вычислений. Во всех этих случаях задача сортировки выступает как средство проверки эффективности и того, и другого.
Мы уже рассматривали вопросы параллельной обработки данных низкого уровня при изучении сортирующих сетей в разделе 11.2, когда говорили о возможности одновременного выполнения нескольких операций сравнения-обмена. Сейчас мы рассмотрим модель параллельных вычислений высокого уровня с использованием большого количества независимых универсальных процессоров (а не просто компараторов), имеющих доступ к одним и тем же данным. В этом случае мы также игнорируем многие практические аспекты, зато в данном контексте можно исследовать алгоритмические вопросы.
Абстрактная модель, которую мы будем использовать для представления параллельной обработки данных, основана на предположении, что сортируемые файлы распределяются между P независимыми процессорами. Мы полагаем, что имеются

• 
  N записей, подлежащих сортировке;
  
• 
  P процессоров, способных содержать (N/P) записей.
  

Присвоим этим процессорам метки 0, 1, ..., P - 1 и будем полагать, что входной файл находится в локальной памяти процессоров (то есть каждый процессор содержит N/P записей). Цель сортировки заключается в переупорядочении записей таким образом, чтобы N/P наименьших записей находились в памяти процессора 0, N/P следующих наименьших записей находились в памяти процессора 1 и так далее, по возрастанию. Как мы увидим далее, существует зависимость между P и общим временем выполнения - и хотелось бы получить количественную оценку этой зависимости, чтобы иметь возможность сравнивать различные стратегии.
Предложенная модель - одна из многих возможных моделей параллельной обработки данных, и для нее так же характерны многие упрощения относительно практического применения, как и для модели внешней сортировки (раздел 11.3). Например, эта модель не учитывает один из наиболее важных вопросов параллельной обработки данных: ограничения на обмен данными между процессорами.
Будем полагать, что стоимость этого обмена данными гораздо выше, чем стоимость обращения к локальной памяти, и что такой обмен наиболее эффективен, если он выполняется последовательно, большими блоками данных. В этом смысле каждый процессор рассматривает память других процессоров как внешние запоминающие устройства. Опять-таки, эта высокоуровневая абстрактная модель может быть неудовлетворительной с практической точки зрения ввиду ее чрезмерной упрощенности; ее также можно считать неудовлетворительной и с теоретической точки зрения, поскольку ей не хватает полноты определения. Но все же она представляет собой основу для разработки полезных алгоритмов.
Данная задача (с учетом сделанных предположений) представляет собой пример мощи абстрактного подхода, поскольку для ее решения можно воспользоваться сортирующими сетями, рассмотренными в разделе 11.2 - нужно лишь внести соответствующие изменения в абстракцию сортировки-слияния, которые сделают ее пригодной для работы с большими блоками данных.
Определение 11.2. Сливающий компаратор принимает на входе два упорядоченных файла размером M и выдает на выходе два упорядоченных файла: один из них содержит M меньших из 2M входных элементов, а другой - M больших из 2M входных элементов.
Эту операцию нетрудно реализовать: достаточно слить два входных файла и передать на выход первую и вторую половину полученного файла.
Лемма 11.7. Сортировку файла размером N можно выполнить, поделив его на N/M блоков размером M, отсортировав каждый файл, и воспользовавшись после этого сортирующей сетью, построенной из сливающих компараторов.
Существует хитроумное доказательство этого утверждения, основанное на принципе нулей и единиц (см. упражнение 11.61), однако можно убедиться в правильности этого утверждения, рассмотрев пример вроде рис. 11.18. 
Будем называть метод, описываемый в свойстве 11.7, поблочной сортировкой (block sorting). Прежде чем использовать этот метод на конкретной машине с параллельными процессорами, необходимо рассмотреть значения некоторых параметров. Нам будет интересна следующая характеристика производительности этого метода: