Внешние сортировка и перестановка

Ключевые слова и синонимы

Сортировка во внешней памяти

Постановка задачи

Нотация. Основные свойства магнитных дисков и многодисковых систем можно отразить с помощью широко используемой модели с параллельными дисками (PDM), которая кратко представлена ниже в ее актуальной форме, разработанной Виттером и Шрайвер [16]:

  N – размер задачи (в единицах элементов данных); 
  M – размер внутренней памяти (в единицах элементов данных); 
  В – размер блока для поблочной передачи (в единицах элементов данных); 
  D – количество независимых дисковых накопителей; 
  P – количество процессоров;

где [math]\displaystyle{ M \lt N }[/math] и [math]\displaystyle{ 1 \le DB \le M/2 }[/math]. Предполагается, что элементы данных имеют фиксированную длину. За одну операцию ввода-вывода каждый из D дисков может одновременно передать блок из B смежных элементов данных. (В оригинальной статье 1988 года [2] допускалось, что за одну операцию ввода-вывода с одного и того же диска могут поступать D блоков, что на практике нереально). Если [math]\displaystyle{ P \le D }[/math], каждый из P процессоров может управлять примерно D/P дисками; если D < P, с каждым диском работают примерно P/D процессоров. Объем внутренней памяти составляет M/P на процессор; P процессоров соединены сетью межсоединений.

Некоторые из перечисленных выше параметров PDM удобно указывать в единицах дисковых блоков, а не в единицах элементов данных; получаемые в результате формулы часто упрощаются. Будем обозначать строчными буквами

(1) [math]\displaystyle{ n = \frac{N}{B}, m = \frac{M}{B}, q = \frac{Q}{B}, z = \frac{Z}{B} }[/math]

размер входных данных задачи, размер внутренней памяти, размер спецификации запроса и размер выходных данных запроса, соответственно, в единицах дисковых блоков.

Основными показателями производительности в модели PDM являются:

1. количество выполненных операций ввода-вывода,

2. объем используемого дискового пространства,

3. время выполнения внутренних (последовательных или параллельных) вычислений.

Для краткости в данном обзоре будут рассматриваться только первые два показателя. Большинство алгоритмов выполняются за оптимальное процессорное время, по крайней мере, для однопроцессорного случая. В идеале алгоритмы и структуры данных должны использовать линейный объем памяти, то есть O(N/B) = O(n) дисковых блоков.

Задача 1 (Внешняя сортировка)

Дано: записи входных данных [math]\displaystyle{ R_0, R_1, R_2, ... }[/math] изначально распределены в виде чередующихся полос по D дискам в виде блоков, так что запись [math]\displaystyle{ R_i }[/math] находится в блоке [math]\displaystyle{ \lfloor i/B \rfloor }[/math], а блок ј хранится на диске j mod D.

Требуется: найти чередующееся представление перестановочного упорядочения [math]\displaystyle{ R_{\sigma(0)}, R_{\sigma(1)}, R_{\sigma(2)}, ... }[/math] входных записей, обладающее следующим свойством: [math]\displaystyle{ key(R_{\sigma(i)}) \le key(R_{\sigma(i + 1)}) }[/math] для всех [math]\displaystyle{ i \ge 0 }[/math].

Операция перестановки представляет собой частный случай сортировки, в котором собственно перестановка, описывающая конечное расположение записей, задана явно и не требует выявления, например, путем сравнения ключей.

Задача 2 (Перестановка)

Дано: те же исходные предположения, что и в задаче внешней сортировки. Кроме того, задана перестановка [math]\displaystyle{ \sigma }[/math] целых чисел {0, 1, 2, ... N — 1}.

Требуется: найти чередующееся представление перестановочного упорядочения [math]\displaystyle{ R_{\sigma(0)}, R_{\sigma(1)}, R_{\sigma(2)}, ... }[/math] входных записей.

Основные результаты

Теорема 1 [2, 12]. Количество операций ввода-вывода, необходимых для сортировки N = nB элементов данных с использованием D дисков в среднем и наихудшем случаях, составляет

(2) [math]\displaystyle{ Sort(N) = \Theta (\frac{n}{D} log_m \; n). }[/math]

Теорема 2 [2]. Количество операций ввода-вывода, необходимых для перестановки N элементов данных с использованием D дисков в среднем и наихудшем случаях, составляет

(3) [math]\displaystyle{ \Theta \bigg( min \bigg\{ \frac{N}{D}, Sort(N) \bigg\} \bigg). }[/math]

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

Теорема 3 [2]. При наличии D дисков количество операций ввода-вывода, необходимых для транспонирования матрицы [math]\displaystyle{ p \times q }[/math] из развертывания по строкам на развертывание по столбцам, равно

(4) [math]\displaystyle{ \Theta \bigg( \frac{n}{D} log_m \; min \{ M, p, q, n \} \bigg), }[/math] где [math]\displaystyle{ N = pq }[/math] и [math]\displaystyle{ n = N/B. }[/math]

Транспонирование матриц является частным случаем более общего класса перестановок, называемых перестановками типа «перестановка битов и дополнение» (bit-permute/complement, BPC), которые, в свою очередь, являются подмножеством класса перестановок типа «перемножение битовых матриц и дополнение» (bit-matrix-multiply/complement, BMMC). BMMC-перестановки определяются неособенной матрицей A размера log N x log N, содержащей только нули и единицы, и вектором длины log N с такими же элементами. Элемент с двоичным адресом [math]\displaystyle{ x }[/math] отображается перестановкой на двоичный адрес, заданный [math]\displaystyle{ Ax \oplus c }[/math], где [math]\displaystyle{ \oplus }[/math] обозначает поразрядное исключающее «ИЛИ». BPC-перестановки являются частным случаем BMMC-перестановок, в котором A является матрицей перестановок, то есть каждая строка и каждый столбец A содержат по одному значению 1. В число BPC-перестановок входят транспонирование матрицы, бит-реверсивная перестановка (которая возникает при быстром преобразовании Фурье), обращение векторов, перестановка элементов гиперкуба и переблокировка матрицы. Кормен и коллеги [6] характеризуют оптимальное число операций ввода-вывода, необходимое для выполнения любой заданной BMMC-перестановки, исключительно как функцию от соответствующей матрицы A, а также дают оптимальный алгоритм ее реализации.

Теорема 4 [6]. При наличии D дисков количество операций ввода-вывода, необходимых для выполнения BMMC-перестановки, заданной матрицей A и вектором c, равно

(5) [math]\displaystyle{ \Theta \bigg( \frac{n}{D} \bigg( 1 + \frac{rank( \gamma )}{log \; m} \bigg) \bigg) , }[/math] где [math]\displaystyle{ \gamma }[/math] – подматрица размером [math]\displaystyle{ log \; n \times log \; B }[/math] матрицы A, расположенная в ее левом нижнем углу.

Двумя основными парадигмами внешней сортировки являются распределение и слияние, которые будут рассмотрены далее для модели PDM.

Сортировка распределением

Сортировка распределением [9] представляет собой рекурсивный процесс, который использует набор из S - 1 элементов разбиения для распределения элементов на S несовпадающих «корзин». Все элементы в одной корзине предшествуют всем элементам в следующей корзине. Сортировка завершается рекурсивной сортировкой отдельных корзин и объединением их в единый, полностью отсортированный список.

Одним из требований является выбор S - 1 элементов разбиения таким образом, чтобы корзины были примерно одинакового размера. В этом случае размеры корзин уменьшаются от одного уровня рекурсии к другому на относительный коэффициент [math]\displaystyle{ \Theta(S) }[/math], и, таким образом, существует [math]\displaystyle{ O(log_S \; n) }[/math] уровней рекурсии. На каждом уровне рекурсии выполняется сканирование данных. По мере прохождения элементов через внутреннюю память они разбиваются на S корзин в онлайновом режиме. Когда буфер размером B заполняется для одной из корзин, его блок записывается на диски при следующем вводе-выводе, и для хранения следующего набора входящих элементов, предназначенных для этой корзины, используется другой буфер. Таким образом, максимальное число корзин (и элементов разбиения) равно [math]\displaystyle{ S = \Theta(M/B) = \Theta(m) }[/math], а результирующее число уровней рекурсии равно [math]\displaystyle{ \Theta(log_m \; n) }[/math]. Как выполнить каждый уровень рекурсии за линейное число операций ввода-вывода, обсуждается в [2,11,16].

Еще более эффективным способом сортировки распределением, и при этом детерминированным, является метод BalanceSort, разработанный Нодином и Виттером [11]. В ходе процесса разбиения алгоритм отслеживает, насколько равномерно на данный момент каждая корзина была распределена между дисками. Он поддерживает инвариант, который гарантирует хорошее распределение по дискам для каждой корзины.

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

Ортогональным подходом является чередование содержимого каждой корзины по дискам, чтобы операции чтения выполнялись поочередно. В результате операции записи должны работать с дисками независимо друг от друга, поскольку во время каждой записи содержимое нескольких корзин будет записываться на несколько полос. Коррекция и восстановление ошибок в этом случае могут производиться эффективно путем выделения во внутренней памяти одного буфера размером с блок для каждой корзины. Буфер постоянно обновляется, чтобы включать информацию о четности (исключающее ИЛИ) блоков, записанных на текущую полосу, а после записи D - 1 блоков информация о четности в буфере может быть записана в последний (D-й) блок полосы.

В этом новом сценарии основной цикл алгоритма сортировки распределением, как и раньше, заключается в чтении одного блока памяти за раз и разбиении элементов на S корзин. Однако, в отличие от предыдущего варианта, блоки для каждой отдельной корзины будут располагаться на дисках в смежных полосах. Поэтому у каждого блока есть заранее определенное место, куда он должен быть записан. При обычном циклическом упорядочивании полос (например, ... , 1, 2, 3, ... , D, 1, 2, 3, ... , D, ... ) блоки из разных корзин могут «столкнуться» в том смысле, что их нужно будет записать на один и тот же диск, и последующие блоки в тех же корзинах также будут сталкиваться. Виттеру и Хатчинсону [15] удалось разрешить эту проблему с помощью техники рандомизированного зацикливания. Для каждой из S корзин они определяют порядок дисков в полосе для этой корзины с помощью случайной перестановки {1, 2, .... , D}. S случайных перестановок выбираются независимым образом. Если два блока (из разных корзин) случайно сталкиваются во время записи на один и тот же диск, то один блок записывается на диск, а другой остается в очереди на запись. С высокой вероятностью последующие блоки из этих двух корзин будут записаны на разные диски и, таким образом, не столкнутся. Для случая, когда существует небольшой запас доступного буферного пространства для временного кэширования блоков в очередях на запись, Виттер и Хатчинсон [15] показывают, что с высокой вероятностью запись происходит оптимально.

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

Сортировка слиянием

Парадигма слияния в некотором смысле ортогональна парадигме распределения из предыдущего раздела. Типичный алгоритм сортировки слиянием работает следующим образом [9]: на этапе «формирования прогонов» сканируется n блоков данных, по одной загрузке в память за раз; каждая загрузка в память сортируется в один «прогон», который затем выводится на серию полос на дисках. По завершении этапа формирования прогонов имеется N/M = n/m (отсортированных) прогонов, каждый из которых разбит на полосы на дисках. (При реализации алгоритма на практике можно использовать выбор с замещением для получения прогонов из 2M элементов данных в среднем при M >> B [9]). После того, как начальные прогоны сформированы, начинается этап слияния. При каждом проходе фазы слияния за один раз объединяется R прогонов. Для каждого слияния R прогонов сканируются, и их элементы объединяются в онлайновом режиме по мере их прохождения через внутреннюю память. Для перекрытия операций ввода-вывода и вычислений используется двойная буферизация. За один раз может быть объединено не более [math]\displaystyle{ R = \Theta(m) }[/math] прогонов, а итоговое число проходов составляет [math]\displaystyle{ O(log_m \; n) }[/math].

Для достижения оптимальной границы сортировки (2) каждый проход слияния должен выполняться за O(n/D) операций ввода-вывода, что легко сделать для случая с использованием одного диска. В более общем случае с несколькими дисками каждая операция параллельного чтения во время процесса слияния должна в среднем выдать следующие [math]\displaystyle{ \Theta(D) }[/math] блоков, необходимых для слияния. Задача состоит в том, чтобы обеспечить размещение этих блоков на разных дисках так, чтобы они могли быть прочитаны за одну операцию ввода-вывода (или небольшое постоянное число таких операций). Сложность же заключается в том, что подлежащие слиянию прогоны были сформированы во время предыдущего прохода слияния. Их блоки были записаны на диски в предыдущем проходе без знания того, как они будут взаимодействовать с другими прогонами в последующих слияниях.

Метод жадной сортировки (Greed Sort) Нодина и Виттера [12] был первым оптимальным детерминированным EM-алгоритмом для сортировки с использованием нескольких дисков. Он работает путем ослабления процесса слияния с последним проходом для фиксации слияния. Аггарвал и Плакстон [1] разработали оптимальный детерминированный метод сортировки слиянием на основе алгоритма параллельной сортировки гиперкуба Sharesort. Чтобы гарантировать равномерное распределение во время слияния, они используют две высокоуровневые схемы слияния, в которых планирование почти не учитывается. Как и Greed Sort, алгоритм Sharesort теоретически оптимален (т. е. отличается от оптимального не более чем на константный коэффициент), но этот константный коэффициент больше, чем у методов сортировки распределением.

Один из наиболее практичных методов сортировки основан на алгоритме простой рандомизированной сортировки слиянием (SRM) Барве и коллег [5], который Кнут назвал [9] «рандомизированным чередованием». Каждый прогон чередуется полосами по дискам, но со случайной начальной точки (это единственное место в алгоритме, где используется случайность). В процессе слияния следующий требуемый блок с каждого диска считывается в память, а если места недостаточно, то наименее нужные блоки «сбрасываются» (без применения каких-либо операций ввода-вывода), чтобы освободить место.

Для дальнейшего улучшения эффективности сортировки слиянием требуется более тщательное составление расписания предварительной выборки для прогонов. Барве и др. [4], Каллахалла и Варман [8], Шах и коллеги [13], а также другие исследователи разработали конкурентоспособные и оптимальные методы предварительной выборки блоков в параллельных системах ввода-вывода. Хатчинсон и др. [7] продемонстрировали мощную двойственность между параллельной записью и параллельной предварительной выборкой, которая дает простой способ вычисления оптимальных расписаний предварительной выборки и кэширования при использовании нескольких дисков. Более того, они показали, что такая же двойственность существует между распределением и слиянием, а также использовали это открытие для получения доказательно оптимальной и очень практичной сортировки слиянием с использованием параллельных дисков. Вместо того, чтобы использовать случайные начальные точки и циклическое упорядочивание полос, как в алгоритме SRM, Хатчинсон и др. [7] упорядочивают полосы независимо для каждого прогона, основываясь на стратегии случайного зацикливания, рассмотренной в разделе «Сортировка распределением».

Обработка дубликатов: пакетная сортировка

Для удаления дубликатов, когда среди N элементов имеется в общей сложности K различных элементов, Арге и др. [3] используют модификацию сортировки слиянием для решения этой задачи за [math]\displaystyle{ O(n \; max \{ 1,log_m (K/B) \} ) }[/math] операций ввода-вывода, что является оптимальным в модели сравнения [3]. Когда во время слияния дубликаты группируются вместе, они заменяются единственной копией элемента и подсчетом числа его вхождений. Этот алгоритм можно использовать для сортировки файла, предполагая, что группа одинаковых элементов может быть представлена одним элементом и подсчитанным числом появлений.

Более сложный случай сортировки, называемый пакетной сортировкой, имеет место, когда среди N элементов есть K различных ключевых значений, но все элементы содержат различную вторичную информацию, которая должна сохраняться, и поэтому не могут быть объединены с помощью подсчета. Матиас и др. [10] разработали оптимальные алгоритмы сортировки распределением для пакетной сортировки, используя

(6) [math]\displaystyle{ O(n \; max \{ 1,log_m \; min \{ K, n \} \} ) }[/math]

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

Перестановка и транспонирование

Перестановка представляет собой частный случай сортировки, в котором ключевые значения N элементов данных образуют перестановку {1, 2, ... , N}. Граница ввода-вывода (3) для перестановки может быть реализована одним из оптимальных алгоритмов сортировки, за исключением крайнего случая B log m = o (log n), когда быстрее переместить элементы данных по одному неблокирующим способом. Метод перемещения элементов по одному тривиален, если D = 1, но при использовании нескольких дисков могут возникать узкие места на отдельных дисках; одним из решений для выполнения перестановки за O(N/D) операций ввода-вывода является применение рандомизированных стратегий балансировки из работы [16].

Транспонирование матрицы может быть таким же трудным, как и перестановка общего вида, когда B относительно велико (скажем, 1/2M) и N составляет [math]\displaystyle{ O(M^2) }[/math]; однако при меньших значениях B специальная структура перестановки упрощает процесс транспонирования. В частности, матрица может быть разбита на квадратные подматрицы из [math]\displaystyle{ B^2 }[/math] элементов так, чтобы каждая подматрица содержала B блоков матрицы в порядке возрастания строк, а также B блоков матрицы в порядке возрастания столбцов. Таким образом, если [math]\displaystyle{ B^2 \lt M }[/math], транспонирование может быть произведено простой однопроходной операцией путем транспонирования по одной подматрице во внутренней памяти.

Быстрое преобразование Фурье и сети перестановок

Вычисление быстрого преобразования Фурье (БПФ) во внешней памяти состоит из ряда операций ввода-вывода, которые позволяют выполнять каждое вычисление, подразумеваемое ориентированным графом (также называемым «бабочкой») БПФ, пока его аргументы находятся во внутренней памяти. Вычисления в сети перестановок состоят из абстрактного (фиксированного) шаблона операций ввода-вывода, так что может быть реализована любая из N! возможных перестановок; элементы данных могут быть переупорядочены только тогда, когда они находятся во внутренней памяти. Сеть перестановок может быть реализована серией из трех БПФ.

Алгоритмы для БПФ быстрее и проще, чем для сортировки, поскольку вычисления неадаптивны по своей природе и, таким образом, схема коммуникаций фиксирована заранее [16].

Нижние границы для операций ввода-вывода

Следующее доказательство нижней границы перестановки (3) теоремы 2 принадлежит Аггарвалу и Виттеру [2]. Идея доказательства состоит в том, чтобы для каждого [math]\displaystyle{ t \ge 0 }[/math] вычислить число различных упорядочений, которые реализуются последовательностями из t операций ввода-вывода. Значение t, при котором число различных упорядочений впервые превышает N!/2, является нижней границей среднего числа операций ввода-вывода (и, следовательно, числа таких операций в наихудшем случае), необходимых для выполнения перестановки.

Предположив на данный момент, что имеется только один диск, D = 1, рассмотрим, как может измениться количество реализуемых упорядочений в результате ввода-вывода. С точки зрения увеличения числа реализуемых упорядочений, эффект от чтения дискового блока значительно больше, чем от его записи, поэтому достаточно рассмотреть только эффект от операций чтения. Во время операции чтения в блоке чтения имеется не более B элементов данных, и они могут быть размещены среди М элементов во внутренней памяти не более чем [math]\displaystyle{ \binom{M}{B} }[/math] способами, поэтому число реализуемых упорядочений увеличивается в [math]\displaystyle{ \binom{M}{B} }[/math] раз. Если блок никогда ранее не находился во внутренней памяти, то число реализуемых упорядочений увеличивается на дополнительный коэффициент В!, поскольку элементы в блоке могут быть переставлены между собой. (Этот дополнительный вклад B! может иметь место только один раз для каждого из N/B исходных блоков). Существует не более [math]\displaystyle{ n + t \le N \; log \; N }[/math] способов выбрать, какой дисковый блок участвует в t-й операции ввода-вывода (при произвольном объеме дискового пространства). Следовательно, число различных упорядочений, которые могут быть реализованы всеми возможными последовательностями t операций ввода-вывода, не превышает

(7) [math]\displaystyle{ (B!)^{N/B} \bigg( N (log \; N) \binom{M}{B} \bigg)^t. }[/math]

Положив, что выражение в (7) не меньше N!/2, и упростив его за счет взятия логарифма, получаем результат

(8) [math]\displaystyle{ N \; log \; B + t \bigg( log \; N + B \; log \frac{M}{B} \bigg) = \Omega (N \; log \; N). }[/math]

Решение для t дает подходящую нижнюю границу [math]\displaystyle{ \Omega(n \; log_m \; n) }[/math] перестановки для случая D = 1. Общая нижняя граница (3) теоремы 2 получается в результате деления на D.

Более сильную нижнюю границу можно получить в результате более тонкого рассуждения, которое считает входные операции отдельно от выходных [7]. Для типичного случая, когда [math]\displaystyle{ В \; log \; m = \omega (log \; N) }[/math], нижняя граница ввода-вывода, вплоть до членов низшего порядка, равна [math]\displaystyle{ 2n \; log_m \; n }[/math]. Для патологического случая, когда [math]\displaystyle{ В \; log \; m = o(log \; N) }[/math], нижняя граница ввода-вывода, вплоть до членов низшего порядка, равна N/D.

Поскольку перестановка – это частный случай сортировки, то, следовательно, нижняя граница перестановки применима и к сортировке. В маловероятном случае, когда [math]\displaystyle{ В \; log \; m = o(log \; n) }[/math], нижняя граница перестановки составляет только [math]\displaystyle{ \Omega(N/D) }[/math], и в этом случае для получения полной нижней границы (2) теоремы 1 [2] необходимо использовать модель сравнения. В типичном случае, когда [math]\displaystyle{ В \; log \; m = \Omega (log \; N) }[/math], модель сравнения для доказательства нижней границы сортировки не нужна; сложность сортировки в этом случае возникает не из-за определения порядка данных, а из-за перестановки (или маршрутизации) данных.

Доказательство, использованное выше для перестановок, работает и для перестановочных сетей, в которых схема коммуникаций абстрактна (фиксирована). Поскольку выбор дискового блока фиксирован для каждого t, то здесь нет члена N log N, как в (7), и, соответственно, нет аддитивного члена log N во внутреннем выражении, как в (8). Следовательно, решение для t дает нижнюю границу (2), а не (3). Нижняя граница следует непосредственно из рассуждения о подсчете; в отличие от вывода сортировки, она не требует модели сравнения для случая [math]\displaystyle{ В \; log \; m = o(log \; n) }[/math]. Эта нижняя граница также непосредственно применима к БПФ, поскольку сети перестановок могут быть образованы из трех последовательных БПФ. Нижняя граница для транспонирования включает потенциальный аргумент, основанный на отношении совместности [2].

Для задачи пакетной сортировки, в которой N элементов принимают в общей сложности K различных ключевых значений (но вторичная информация каждого элемента отлична от других), Матиас и др. [10] вывели соответствующую нижнюю границу.

Вышеупомянутые нижние границы предполагают, что элементы данных в некотором смысле «неделимы», то есть они не разделяются на части и не собираются заново каким-то волшебным образом для получения желаемого результата. Предполагается, что нижняя граница сортировки (2) остается верной даже при снятии предположения о неделимости. Однако для искусственно сформулированной задачи, связанной с транспонированием, снятие предположения о неделимости может привести к получению более быстрых алгоритмов. Верна ли эта гипотеза, является сложной теоретически открытой проблемой.

Применение

Сортировка и операции, подобные ей, составляют значительную долю компьютерных вычислений [9], а также находят множество применений в базах данных. Кроме того, сортировка является важной парадигмой при разработке эффективных EM-алгоритмов, как показано в [14], где можно найти несколько приложений. С некоторыми техническими оговорками, многие задачи, которые могут быть легко решены за линейное время во внутренней памяти, такие как перестановка, ранжирование списка, оценка дерева выражений и поиск связных компонентов в разреженном графе, требуют такого же количества операций ввода-вывода в PDM, как и сортировка.

Открытые вопросы

Несколько интересных задач остаются нерешенными. Одной из сложных теоретических проблем является доказательство нижних границ для перестановки и сортировки без предположения о неделимости. Другой вопрос заключается в том, как определить стоимость ввода-вывода для каждой отдельной перестановки как функцию от некоторой простой характеристики перестановки – например, от количества инверсий. Постоянной целью является разработка оптимальных EM-алгоритмов и перевод теоретических достижений в заметные улучшения в практическом применении. Любопытные проблемы и возможности в разработке и анализе алгоритмов возникают в связи с появлением новых архитектур, таких как сети рабочих станций, иерархические устройства хранения, дисковые накопители с возможностями обработки, устройства хранения на основе микроэлектромеханических систем (МЭМС). Недавно были представлены активные (или интеллектуальные) диски, в которых дисковые накопители имеют некоторые возможности обработки и могут фильтровать информацию, отправляемую на хост-компьютер, для «расширения» узкого места в виде операций ввода-вывода, особенно в масштабных приложениях баз данных. Энергонезависимая память на основе МЭМС может стать промежуточным уровнем в иерархии памяти между DRAM и дисками. В конечном итоге она может обеспечить лучшие по сравнению с дисками параметры задержки и пропускной способности при меньшей стоимости за бит, чем у DRAM.

Ссылка на код

Две системы для разработки алгоритмов внешней памяти, TPIE и STXXL, можно загрузить с сайтов http://www.cs.duke.edu/TPIE/ и http://sttxl.sourceforge.net/, соответственно. Обе системы включают подпрограммы для сортировки и перестановки и облегчают разработку более продвинутых алгоритмов.

См. также

• Модель ввода-вывода

Литература

1. Aggarwal, A., Plaxton, C.G.: Optimal parallel sorting in multi-level storage. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, vol. 5, pp. 659-668. ACM Press, New York (1994)

2. Aggarwal, A., Vitter, J.S.: The Input/Output complexity of sorting and related problems. In: Communications of the ACM, 31 (1988), pp. 1116-1127. ACM Press, New York (1988)

3. Arge, L., Knudsen, M., Larsen, K.: A general lower bound on the I/O-complexity of comparison-based algorithms. In: Proceedings of the Workshop on Algorithms and Data Structures. Lect. Notes Comput. Sci. 709,83-94 (1993)

4. Barve, R.D., Kallahalla, M., Varman, P.J., Vitter, J.S.: Competitive analysis of buffer management algorithms. J. Algorithms 36, 152-181 (2000)

5. Barve, R.D., Vitter, J.S.: A simple and efficient parallel disk mergesort. ACM Trans. Comput. Syst. 35,189-215 (2002)

6. Cormen, T.H., Sundquist, T., Wisniewski, L.F.: Asymptotically tight bounds for performing BMMC permutations on parallel disk systems. SIAM J. Comput. 28,105-136 (1999)

7. Hutchinson, D.A., Sanders, P., Vitter, J.S.: Duality between prefetching and queued writing with parallel disks. SIAM J. Comput. 34,1443-1463 (2005)

8. Kallahalla, M., Varman, P.J.: Optimal read-once parallel disk scheduling. Algorithmica 43,309-343 (2005)

9. Knuth, D.E.: Sorting and Searching. The Art of Computer Programming, vol. 3, 2nd edn. Addison-Wesley, Reading (1998)

10. Matias, Y., Segal, E., Vitter, J.S.: Efficient bundle sorting. SIAM J. Comput. 36(2), 394-410 (2006)

11. Nodine, M.H., Vitter, J.S.: Deterministic distribution sort in shared and distributed memory multiprocessors. In: Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, June-July 1993, vol.5, pp. 120-129, ACM Press, New York (1993)

12. Nodine, M.H., Vitter, J.S.: Greed Sort: An optimal sorting algorithm for multiple disks. J. ACM 42,919-933 (1995)

13. Shah, R., Varman, P.J., Vitter, J.S.: Online algorithms for prefetching and caching on parallel disks. In: Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, pp. 255-264. ACM Press, New York (2004)

14. Vitter, J.S.: External memory algorithms and data structures: Dealing with Massive Data. ACM Comput. Surv.33(2), 209-271 (2001) Revised version available at http://www.cs.purdue.edu/homes/jsv/Papers/Vit.IO_survey.pdf

15. Vitter, J.S., Hutchinson, D.A.: Distribution sort with randomized cycling.J.ACM.53(2006)

16. Vitter, J.S., Shriver, E.A.M.: Algorithms for parallel memory I: Two-level memories. Algorithmica 12,110-147(1994)