Этот трюк хорошо известен карточным фокусникам, которые называют его принципом Гилбрета. Трюк изобретен в бО-х годах Норманом Гилбретом (Norman Gilbreath) [см. Martin Gardner, Mathematical Magic Show (New York: Knopf, 1977), Chapter 7; N. Gilbreath, Genii 52 (1989), 743-744]. Для того чтобы решить, какой блок следует считывать следующим, нужна информация из блоков а и /?, но она занимает только малую долю всего объема а и Ь и, следовательно, можно хранить ее в отдельных файлах. Отсюда следует, что можно обойтись меньшими буферами для хранения считанных на полной скорости данных (см. упр. 23).

Рандомизированное разделение. Если нужно выполнить Р-путевое слияние на D дисках при условии, что Р и D достаточно велики, одновременное чтение информации с D дисков без конфликтов реализовать не удастся (если только не организовать большое количество буферов). Это связано с тем, что аналога принципу Гилбрета при Р > 2 не существует. Как бы мы ни организовали распределение блоков файла между дисками, всегда есть вероятность, что придется считывать множество блоков в оперативную память прежде, чем появится возможность их использовать, поскольку те блоки, которые действительно нужно обрабатывать, могут оказаться на одном и том же диске.

Предположим, что нужно выполнить 8-путевое слияние на 5 дисках и блоки 00О1О2 ..., 6012 • •, • • •, hohih2 ... по 8 серий разделены по такому прави.ту: Oj - на диск j mod D, bj - на диск (j + 1) mod D, hj - на диск (j + 7) mod D. Необходимо реализовать доступ к этим блокам в следующем порядке:

oo6ocodoeo foQohodiei 262301/1 619102/263 d4Ci/116292 azfeidde---- (19)

Тогда они появятся на соответствующих дисках

012340124001111 22222 2333333334..., (20) так что наилучший вариант для нас - вводить их следующим образом.

Такт 1 Такт 2 Такт 3 Такт 4 Такт 5 oo6oCodoeo fogohoCidi 616261/116 239162 ? ?ai0292?

(21)

Такт б Такт 7 Такт 8 Такт 9 ТЛЛаз? ??ез/з? 7 7464? ? ? ? ds ? К тому моменту, когда понадобится использовать блок d, придется уже прочесть de и еще 15 блоков следующих за ним данных, обозначенных через "?", вследствие переполнения на диске 3. А это нельзя сделать, не организовав семь буферов, в которых содержатся остатки от аз, 62, ci, 64, /з, 92 и 61. Таким образом, в нашем примере потребуется пространство в памяти для, по крайней мере, (16 + 8 + 5)В входных записей.

Вместо этого при использовании обычной процедуры распределения суперблоков при разделении дисков будем считывать блоки 0001020,304 на такте 1, 6061626364 - на такте 2, /10/11/12/13/14 - на такте 8, ddedrdsdg - на такте 9 (поскольку следующим нам понадобится суперблок dsdedrdgdg) и т. д. Использование стратегии SyncSort потребует буферов для хранения (Р + Z)DB записей и PDB указателей в оперативной памяти. Можно показать, что более динамичный подход, упомянутый выше, потребует не более половины этого объема буферов, но по-прежнему объем

необходимой оперативной памяти почти пропорционален PDB при больших Р ж D (см. упр. 24).

В работе R. D. Barve, Е. F. Grove, J. S. Vitter, Parallel Computing 23 (1997), 601-631, показано, что небольшая модификация этого подхода с независимыми блоками позволяет получить алгоритм, который практически полностью использует скорость обмена данными с диском, но при этом требует буферов всего лишь для 0{Р + DlogD) блоков вместо fl{PD). Предложенная в работе технология рандомизированного разделения (randomized striping) предполагает помещение блока j серии к на диск {xk +j) mod D, где x - случайное число, которое выбирается как раз перед тем, как будет впервые записана серия к. Вместо того чтобы постоянно использовать в качестве исходных данных D блоков по одному с каждого диска, применяется довольно простой механизм отслеживания наступления момента, когда не оказывается достаточного пространства для выполнения чтения вперед с определенных дисков. В приведенной выше работе доказано, что этот метод асимптотически стремится к оптимальному.

Для того чтобы реализовать Р-путевое слияние на D дисках с рандомизированным разделением, нужно организовать 2D -h Р + Q - I буферов плавающего ввода, каждый для одного блока из В записей. Исходные данные, как правило, считывают-ся в £) из этих буферов, называемых активными буферами чтения. В то же время Р из оставшихся буферов содержат лидирующие блоки, записи из которых в текущий момент участвуют в слиянии. Такие буфера называются активными буферами слияния. Оставшиеся D-\-Q - l прочих "разношерстных" буферов либо пусты, либо содержат данные, которые понадобятся позже. Неотрицательный параметр Q можно увеличить в процессе настройки системы, чтобы уменьшить вероятность возникновения ситуации, когда придется выполнять повторное чтение с любого из дисков.

Блоки всех серий можно скомпоновать в хронологическом порядке, как в (19): первыми идут блоки О каждой серии, за ними следуют другие, поддерживая при этом порядок, в котором освобождаются активные буфера слияния. Как было показано выше, такой порядок определен последними ключами в каждом блоке, так что несложно предсказать, какой из блоков может потребоваться первым.

Вновь рассмотрим пример (19), приняв Р = 8, £) = 5и<Э = 4. Теперь в нашем распоряжении имеется только 2D + Р + Q - 1 - 21 буферов для исходных блоков вместо 29, которые нужны были ранее для обеспечения максимальной скорости считывания. Будем использовать смещения

Хх =3, Х2 = 1, xz =4, Xi = 1, Х5 = 0, Хб = 4, = 2, а:8 = 1 (22)

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

Диск Блоки О

ео fl 02 diCi

bo do ho Cl /2 03 5

go dl 62 bi hi /3 de

ao d2 gi 63 62

Co /0 rfsfli 92 64

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

Активные слияния

Цикл 1 Цикл 2 Цикл 3 Цикл 4 Цикл 5 Цикл 6 Цикл 7

Активные считывания

ео ЬодойоСо fidodid2fo «2/1062913 «261 h giai

64/2/1163 92 ci аз/362 64 ? dsde ? ?

Прочие

(--------)

ЬоСо(ео9о----)

eofogo{did2fi--)

di(d2 623/1912- ) (i2e2(i3ai/i6i9ia2()

e3d4(/ii92----)

/ii 62 9203/3 64 (--)

В ожидании ао do ho ei /2

(24)

ao bo Co do----

ao bo Co do во fo go ho ao bo Co die 1/090/10 аг 61 Cods 62/291 о 026161463/291/10

В каждом очередном цикле поджидается первый в хронологическом порядке блок, который не участвовал в слиянии и не находится в прочих буферах. Это один из блоков, которые считываются в текущий момент в активный буфер ввода. Предполагается, что компьютер работает значительно быстрее, чем НМД, и, таким образом, все блоки, находящиеся перед тем, который ожидается, уже задействованы в процессе слияния до завершения ввода. Предполагается также, что в нашем распоряжении имеется достаточный объем буферов и выполнение слияния не задерживается из-за отсутствия места для размещения результата (см. упр. 26). Когда завершится цикл ввода, блок, который мы ожидаем, немедленно классифицируется как принадлежащий активному буферу слияния, а опустевший буфер слияния, который, таким образом, выведен из этой категории, будет использоваться в составе активных буферов чтения. Другие D - 1 активных буферов чтения выбираются среди D - I наименее важных прочих буферов. Буфера этой последней группы ранжируются в хронологическом порядке по содержимому. В следующем цикле нам придется ожидать первый блок, еще не вовлеченный в слияние и не представленный в прочих буферах. Любой из прочих буферов, предшествующих этому блоку в хронологическом порядке, становится частью группы активных буферов слияния прежде, чем начнется очередной цикл ввода, но другие - показанные выше в скобках - сохранят свой статус прочего буфера в следующем цикле. Однако в следующий цикл с сохранением статуса может быть перенесено не более Q из этих буферов в скобках, поскольку придется передать D - I прочих буферов в группу активных буферов чтения сразу после того, как будет получен сигнал о готовности к вводу. Любой дополнительный буфер из группы прочих может явно очищаться, как если бы содержащаяся в нем информация еще и не считывалась. Такая очистка выполняется, например, в цикле 4 в (24): невозможно обработать все шесть блоков d2e2d3/i9i02 в течение цикла 5, поскольку Q = 4. Так что придется повторно прочесть 91 и а2. В противном же случае чтение выполняется на полной скорости.

В упр. 29 доказано, что для любой заданной хронологической последовательности серий, которые должны быть слиты, метод рандомизированного разделения позволяет достичь в среднем минимального числа операций чтения с дисков, пропорционального r{D, Q + 2), где функция г табулирована в табл. 2. Например, если D = 4 и Q = 18, среднее время выполнения Р-путевого слияния L блоков данных с использованием 4 дисков и Р -t- 25 входных буферов будет не больше времени