Внешние сортировка и перестановка: различия между версиями

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

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

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

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

Дано: записи входных данных R0, R1, R2, . . изначально распределены чередующимся образом по D дискам в виде блоков, так что запись Ri находится в блоке bi/Bc, а блок ј хранится на диске j mod D.

Требуется: найти чередующееся представление переставленного (перестановочного) упорядочения -R(j(o), Ra(\)> R<J(2)> входных записей, обладающее следующим свойством: keyiRcr^)) < кеу(Д<7(,+1)) для всех i > 0.

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

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

 

Требуется: найти чередующееся представление переставленного (перестановочного) упорядочения Rcr^); Ra{1); Rcr{2) входных записей.

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

(2)

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

(3)

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

 

где N = pq и n = N/B.

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

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

где у – подматрица размером log n x log B матрицы A, расположенная в ее левом нижнем углу.

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

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

Одним из требований является выбор S - 1 элементов разбиения таким образом, чтобы корзины были примерно одинакового размера. В этом случае размеры корзин уменьшаются от одного уровня рекурсии к другому на относительный коэффициент 0{S), и, таким образом, существует O(logS n) уровней рекурсии. На каждом уровне рекурсии выполняется сканирование данных. По мере прохождения элементов через внутреннюю память они разбиваются на S корзин в онлайновом режиме. Когда буфер размером B заполняется для одной из корзин, его блок записывается на диски при следующем вводе-выводе, и другой буфер используется для хранения следующего набора входящих элементов для этой корзины. Таким образом, максимальное число корзин (и элементов разбиения) равно S = 0{MIB) = 0{m), а результирующее число уровней рекурсии равно @(logm n). Как выполнить каждый уровень рекурсии за линейное число операций ввода-вывода, обсуждается в [2,11,16].

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

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

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

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

Для удаления дубликатов, когда среди N элементов имеется в общей сложности K различных элементов, Арге и др. [3] используют модификацию сортировки слиянием для решения этой задачи за 0(nmax{l,logm(.Kyfi)}) операций ввода-вывода, что является оптимальным в модели сравнения [3]. Когда во время слияния дубликаты группируются вместе, они заменяются единственной копией элемента и подсчетом числа его вхождений. Этот алгоритм можно использовать для сортировки файла, предполагая, что группа одинаковых элементов может быть представлена одним элементом и подсчитанным числом появлений.

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

(6)

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

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

Транспонирование матрицы может быть таким же трудным, как и перестановка общего вида, когда B относительно велико (скажем, 1/2M) и N составляет O(M2); однако при меньших значениях B специальная структура перестановки упрощает процесс транспонирования. В частности, матрица может быть разбита на квадратные подматрицы из B2 элементов так, чтобы каждая подматрица содержала B блоков матрицы в порядке возрастания строк, а также B блоков матрицы в порядке возрастания столбцов. Таким образом, если B2 < M, транспонирование может быть произведено простой однопроходной операцией путем транспонирования по одной подматрице во внутренней памяти.

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

Предположив на данный момент, что имеется только один диск, D = 1, рассмотрим, как может измениться количество реализуемых упорядочений в результате ввода-вывода. С точки зрения увеличения числа реализуемых упорядочений, эффект от чтения дискового блока значительно больше, чем от его записи, поэтому достаточно рассмотреть только эффект от операций чтения. Во время операции чтения в блоке чтения имеется не более B элементов данных, и они могут быть размещены среди М элементов во внутренней памяти не более чем (B) способами, поэтому число реализуемых упорядочений увеличивается в (^) раз. Если блок никогда ранее не находился во внутренней памяти, то число реализуемых упорядочений увеличивается на дополнительный коэффициент В!, поскольку элементы в блоке могут быть переставлены между собой. (Этот дополнительный вклад B! может иметь место только один раз для каждого из N/B исходных блоков). Существует не более n + t < NlogN способов выбрать, какой дисковый блок участвует в t-й операции ввода-вывода (при произвольном объеме дискового пространства). Следовательно, число различных упорядочений, которые могут быть реализованы всеми возможными последовательностями t операций ввода-вывода, не превышает

(7)

Решение для t дает подходящую нижнюю границу Q(n\ogm n) перестановки для случая D = 1. Общая нижняя граница (3) теоремы 2 получается в результате деления на D.

Более сильную нижнюю границу можно получить в результате более тонкого рассуждения, которое считает входные операции отдельно от выходных [ ]. Для типичного случая, когда В log m = !(logN), нижняя граница ввода-вывода, вплоть до членов низшего порядка, равна 2nlogm n. Для патологического случая, когда В log m = o(logN), нижняя граница ввода-вывода, вплоть до членов низшего порядка, равна N/D.

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

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

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

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

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