запоминающие устройства. И на сей раз, эту модель с высоким уровнем абстракции можно рассматривать как неудовлетворительную в плане практического применения ввиду ее чрезмерной упрощенности; ее также можно считать неудовлетворительной и с теоретической точки зрения, поскольку ей не хватает полноты определения. Но несмотря на все это, она представляет собой структуру, в рамках которой возможна разработка полезных алгоритмов.

И в самом деле, рассматриваемая задача (с учетом сделанных выше предположений) представляет собой пример могущества абстрагирования, ибо мы для ее решения можем воспользоваться сетями сортировки, которые изучались в разделе 11.2, внеся соответствующие изменения в абстракцию сортировки-слияния, которые делают ее пригодной для работы с большими блоками данных.

Определение 11.2. Компаратор слияния принимает на входе два отсортированных файла размером М и выдает на выход два отсортированных файла: один из них содержит М-й наименьший из 2М входных элементов, а другой содержит М-й наибольший из 2М входных элементов.

Эту операцию нетрудно реализовать: производится слияние двух входных файлов, затем на выход передаются первая половина и вторая половина файла, полученного в результате слияния.

Лемма 11.7. Мы можем выполнить сортировку файла размером N, поделив его на M/N блоков размером М с последующей сортировкой каждого файла, после чего используем сеть сортировки со встроенными в нее компараторами.

Чтобы установить этот факт, взяв за основу принцип нулей и единиц, требуются проявить определенную изобретательность (см. упражнение 11.61), однако изучение примера, подобного представленному на рис. 11.18, позволит убедиться в правильности этого утверждения.

Будем называть метод, описываемый леммой 11.7, поблочной сортировкой (block sorting). Но прежде чем использовать этом метод на конкретной машине, необходимо выбрать значения некоторых параметров модели. Наш интерес к этому методу обусловлен следующей рабочей характеристикой:

Лемма 11.8. Поблочная сортировка на Р процессорах с использованием сортировки Бэтчера с компараторами слияния может выполнить сортировку N записей примерно за (\gP)/2 параллельных шагов.

Под параллельными шагами (parallel steps) в данном контексте мы понимаем некоторую совокупность раздельных компараторов. Лемма 11.8 является прямым следствием лемм 11.3 и 11.7.

Чтобы реализовать компаратор слияния на двух процессорах, мы должны сделать так, чтобы оба они в процессе обмена копиями хранящихся в них блоков данных выполняли слияние (параллельно), при этом на одном из них оставалась половина с меньшими значениями ключей, а на другом - половина с большими значениями ключей. Если передача блоков происходит медленно по сравнению с быстродействием конкретного процессора, мы можем вычислить общее время, необходимое для сортировки, умножая стоимость передачи одного блока на (\gP)/2. Такая оценка предполагает принятие большого числа предположений, например, предполагается, что

передача многочисленных блоков данных производится параллельно, без затрат, что довольно редко имеет место в реальных компьютерах параллельного действия. Несмотря на все это, она представляет собой отправную точку для понимания того, что можно ожидать от практической реализации.

Если стоимость передачи блока данных определяется быстродействием отдельного процессора (еще одна идеальная цель, к которой можно только приблизиться на реальных машинах), то мы должны принимать в расчет время, затрачиваемое на начальную сортировку. Каждый процессор выполняет (N/P) \g{N/P) сравнений (параллельно), чтобы выполнить начальную сортировку N/P блоков, и примерно P(\gP)/2 этапов слияния типа {N/P)-c-(N/P). Если стоимость сравнения - а, а стоимость слияния на одну запись составляет Р, общее время выполнения приблизительно равно

а (N/P) IgiN/P) + Р (N/P) PilgP) 12.

Для сверхбольших Л и малых Р этот показатель - лучшее из того, на что можно рассчитывать в условиях метода параллельной сортировки, основанной на сравнении, поскольку в этом случае стоимость составляет a{N\gN)/P, которую можно считать оптимальной: любая сортировка требует N\gN сравнений и самое лучшее, что можно предпринять в этом случае - сделать Р из них одновременно. В случае больших значений Р преобладает второе слагаемое и стоимость приближается к значению N{P\gP)/2, которое можно считать субоптимальным, хотя все еще конкурентоспособным. Например, второе слагаемое составляет 256N/P стоимости сортировки 1 миллиарда элементов на 64 процессорах, в то время как вклад первого слагаемого составляет 32aN/P.

Когда значение Р достаточно велико, на некоторых машинах при передаче данных могут возникнуть узкие места. Если такое случится, применение идеального тасования, представленного на рис. 11.8, может быть использовано как средство управления издержками подобного рода. Именно по этим причинам в некоторых машинах имеются встроенные схемы низкоуровневых соединений, которые позволяют эффективно реализовать операции тасования.

Этот пример показывает, что в некоторых случаях можно обеспечить эффективную работу процессоров при решении задач сортировки файлов сверхбольших размеров. Чтобы знать, как это сделать наилучшим образом неизбежно потребуется проанализировать множество различных алгоритмов для данного типа параллельной машины и исследовать поведение используемой машины на модели при различных значениях ее параметров. Более того, может потребоваться совершенно другой подход к проблеме параллельной обработки данных. Тем не менее, предположение о том, что увеличение числа процессоров приводит к увеличению стоимости обмена данными между ними, является основополагающим для параллельных вычислений, а сети Бэтчера представляет собой эффективное средство управления такого рода затратами, что имеет место как на низком уровне, в чем мы имели возможность убедиться в разделе 11.2, так и на высоком уровне, в чем мы смогли убедиться в настоящем разделе.

Методы сортировки, описанные в этом разделе и в других местах данной главы, имеют определенные отличия от методов, которые мы изучали на протяжении глав 6-10, поскольку они предусматривают копирование и наличие ограничений, кото-

AALLPR AAEELL

EELOOS -i- LOOPRS

EG I NRT -I- AE EG I L

AELMPX i MNPRTX

AAAEEE - AAAEEE

LMNOOP -m- EGILLL

EGILLL -1- LMNOOP

PRRSTX - PRRSTX

рисунок 11.18. пример поблочной сортировки

Этот рисунок служит иллюстрацией того факта, что мы можем воспользоваться сетью, представленной на рис. 11.14 для сортировки блоков данных. Компараторы помещают выход в виде половины элементов с меньшими номерами на верхнюю из двух входных линии, а половину элементов с большими номерами - на нижнюю линию. Трех параллельных шагов оказывается достаточно.

рые не рассматриваются в обычном программировании. В главах 6-10 простых предположений, касающихся используемых нами данных, было достаточно, чтобы можно было сравнивать большое число различных методов решения одной и той же базовой задачи. В противоположность этому в данной главе мы сосредоточились на формулировании различных задач, но имели возможность рассматривать лишь немногие решения каждой из них. Эти примеры служат иллюстрацией того факта, что изменения ограничений, налагаемых внешней средой, предоставляют возможности для появления новых решений, а наиболее важная часть этого процесса состоит в нахождении полезных абстрактных формулировок конкретных задач.

Сортировка играет исключительно важное значение во многих практических приложений, и разработка эффективных методов сортировки является одной из главных задач, на решение которых должна быть ориентированы архитектура новых компьютеров и новые среды программирования. Памятуя истину, что новые достижения строятся на прошлом опыте, важно получить представление о совокупности технических средств, которые мы обсуждали в главах 6-10, в силу того факта, что появились новые революционные изобретения. Абстрактное мышление, которое понадобилось при изучении изложенного ранее материала, может оказаться необходимым, если вам придется разрабатывать быстродействующие процедуры сортировки для новых машин.

Упражнения

о 11.61. Воспользуйтесь принципом нулей и единиц (лемма 11.1) для доказательства леммы 11.7.

11.62. Реализовать последовательную версию поблочной сортировки с нечетно-четным слиянием Бэтчера: (/) воспользоваться стандартной сортировкой слиянием (программы 8.3 и 8.2) для сортировки блоков данных, ( ) воспользоваться стандартным обменным слиянием (программа 8.2) для реализации компараторов слияния и (ш) воспользоваться восходящим нечетно-четным слиянием Бэтчера (программа 11.3) для сортировки отдельных блоков.

11.63. Дать оценку время выполнения программы, описанной в упражнении 11.62, как функции от N и М для больших N.