AOP_Tom3 (1021738), страница 99
Текст из файла (страница 99)
С!1Ьгеа|Ь, Сепй 52 (1989), 743 744). Для того чтобы решит|и какой блок следует считывать следующим, нужна информация из блоков н и г, но она занимает только малую долю исего объема а и Ь и, следовательно, можно хранить ее и отдельных файлах. Отсюда следует, что можно обойтись меньшими буферами для хранения считанных на полной скорости данных (сзк упр. 23). Рандомизнрованное разделение. Если нужно выполнить Р-пугеиое слияние на Р дисках при условии, что Р и Р достаточно велики, одновременное чтение информации с Р дисков без конфликтов реализовать не удастся (если только не организовать большое количество буферов).
Это связано с тем, что аналога принципу Гилбрета при Р > 2 не сущестиует. Как бы мы ни организовали распределение блоков файла между дисками, всегда есть вероятность, что придется считывать множество блоков в оперативную память прежде, чем пояиится иозмо|кность их использовать, носка|ьку те блоки, которые действительно нужно обрабатывать, могут оказаться на одном и том же диске. Предположим, что нужно выполнить 8-путевое слияние на 5 дисках и блоки ада|аз..., ЬоЬ!Ьг..., ..., Ьойгйг...
по 8 серий разделены по такому правилу: о,— на диск,~ шойР, 6, — на диск Ц + 1) пюйР, ..., Ь. — на диск (~ + 7) |пой Р. Необходимо реализовать доступ к этим блокам в следующем порядке: аоЬосойоеогодойойге| йгегйза,у, Ь|д,аг/гез йвс|?||Ьгдг азгзелйзйв .. (19) Тогда они появятся на соответствующих дисках 01234 01240 01111 22222 23333 33334 ..., (20) так что наилучший вариант для нас — вводить их следующим образом.
Такт 1 Такт 2 Такт 3 Такт 4 Такт 5 аоЬо со йово Уодопос| й| е| ег Ьг Ьгйв йгйздг Ьг д ? а|агдг? Такт 6 Такт 7 Такт 8 Такт 9 ? /|~газ? д ? ез1з? ?? йзев? ??? й.? К тому моменту, когда понадобится использовать блок йз, придется уже прочесть йв и еще 15 блоков следующих за ним данных, обозначенных через "?", игледствие переполнения на диске 3.
А это нельзя сделать, не организовав семь буферов, и которых содержатся остатки от аз, Ьг, с|, ел, Уз дг и 6|. Таким образом, и нашем примере потребуется пространство и памяти для, по крайней мере, (16+ 8+ 5)В входных записей. Вместо этого при использовании обычной процедуры распределения суперблокои при разделении дисков будем считыиать блоки ада|а|агав на такте 1, ЬоЬ|ЬгЬз64— на такте 2, ..., Ьойгбгбз?|4 — на такте 8, йзйвйтйзйд — на такте 9 |поскольку следующим нам понадобится суперблок йзйвйтйзйд) и т.
д. Использование стратегии Бупсбогг потребует буферов для хранения (Р+ 3)РВ записей и РРВ указателей и оперативной памяти. Можно показать, что более динамичный подход, упомянутый выше, потребует не более полонины этого объема буферои, но по-прежнему объем хз —— 3, хг — — 1, хз = 4, хз — — 1, хз — — О, хз = 4, хт — — 2, хз = 1 (22) (это цифры в числе я) для серий а, Ь,, Ь. Таким образом, если перечислить данные блоки в хронологическом порядке, на соответстнующнх дисках будет содержаться следующее. Диск Блоки О: ео 1: Ьа до Ьо ез 2: уо 4 ег 3: ао дз 4: со Уо дза~ аг дзс~ )2 аз дз Ь, Уз дз уз ез Ьг яг е4 (23) необходимой оперативной памяти почти пропорционален РРВ при больших Р и Р (см.
упр. 24). В работе В. Р. Ватке, Б. Г. Осоке, Л. Б. Ъ'Ы1ег, Рата!!е! Согприз!па 23 (1997), 601 — 631, показано, что небольшая модификация этого подхода с независимыми блоками позволяет получить алгоритм, который практически полностью использует скорость обмена данными с диском, но при этом требует буферов всего лишь для 0(Р + Р 1оаР) блоков вместо П(РР). Предложенная в работе технология раидомиэирооаииого разделения (гапдотггед г!г!р!пд) предполагает помещение блока у серии Ь на диск (хь + г) пюд Р, где хг — случайное число, которое выбирается как раз перед тем, как будет нпервые записана серия Ь. Вместо того чтобы постоянно использовать н качестве исходных данных Р блоков по одному с каждого диска, применяется довольно простой механизм отслеживания наступления момента, когда не оказывается достаточного пространства для выполнения чтения вперед с определенных дискон, В приведенной выше работе доказано, что этот метод асимптотически стремится к оптимальному.
Для того чтобы реализовать Р-путевое слияние на Р дисках с рандомизиронанным разделением, нужно организовать 2Р+ Р + Я вЂ” 1 буферов плавающего анода, каждый для одного блока из В записей. Исходные данные, как правило, считываются н Р из этих буферов, называемых активными буферами чтения. В то же время Р из оставшихся буферов содержат лидирующие блоки, записи из которых в текущий момент участвуют в слиянии. Такие буфера называются активными буферами слияния. Оставшиеся Р+ Я вЂ” 1 прочих "разношерстных' буферов либо пусты, либо содержат данные, которые понадобятся позже.
Неотрицательный параметр Я можно унеличить в процессе настройки системы, чтобы уменьшить вероятность возникновения ситуации, когда придется выполнять повторное чтение с любого из дисков. Блоки всех серий можно скомпоновать в хронологическом порядке, как в (19): первыми идут блоки О каждой серии, за ними следуют другие, поддерживая при этом порядок, в котором освобождаются активные буфера слияния. Как было показано ныше, такой порядок определен последними ключами в каждом блоке, так что несложно предсказать, какой из блоков может потребоваться первым.
Вновь 1эассмотрим пример (19), принян Р = 8, Р = 5 и сг = 4. Теперь н нашем распоряжении имеется только 2Р + Р + Я вЂ” 1 = 21 буферов для исходных блоков вместо 29, которые нужны были ранее для обеспечения максимальной скорости считынания. Будем использовать смещения "Случайные" смещения в (22) в сочетании с последовательным разделением внутри каждой серии, будут стремиться к минимизации "заторов" в любой отдельной хронологической последовательности, В данном случае система будет работать следующим образом. Активные слияния Активные считывания Прочие В о>кидании Ц икл 1 соЬодоаосо — — — — — — — — ( — — — — — — — — ) ао Цнк"1 2 ?11?01?11?г>0 ао Ьосо(еОУО ) 1?о Цикл 3 агЬоегд11?з аоЬ0001>о — — — — еоУодо(>11?гЛ ) Ьо (24) Цикл 4 аге>Ь>д>а> аоЬосоО?00010УОЬО 111(Игегаз)>д>аг — ) е1 Цикл 5 114 У>Ь>ез до ао Ьо со 1?1 ез>ОУОЬО 1?г ег ага> 11 Ь1 д>аг() >г Цикл 6 с>аз?зЬгез агЬ>со1гзег?гд>?10 еза>4(Ь>дг — — ) с~ цикл 7 ? 1>зао? ? аг51 01 4езугд>ЬО Ь>Ьгдгазузе4( — — ) 1зз В каждом очередном цикле поджидается первый в хронологическом порядке блок, который не участвовал в слиянии и не находится в прочих буферах.
Это один из блоков, которые считываются в текущий момент в активный буфер ввода. Предполагается, что компьютер работает значительно быстрее, чем НМД, и., таким образом, все блоки, находящиеся перед тем, который ожидается, уже задействованы в процессе слияния до завершения ввода. Предполагается также, что в нашем распоряжении имеется достаточный объем буферов и выполнение слияния не задерживается нз-за отсутствия места для раззиещения результата (см. упр. 26). Когда завершится цикл ввода, блок, который мы ожидаем, немедленно классифицируется как принадлежащий активному буферу слияния, а опустевший буфер слияния, который, таким образом, выведен из этой категории, будет использоваться в составе активных буферов чтения. Другие П вЂ” 1 активных буферов чтения выбираются среди 11 — 1 наименее важных прочих буферов.
Буфера этой последней группы ранжируются в хронологическом порядке по содержимому. В следующем цикле нам придется ожидать первый блок, еще не вовлеченный в слияние и не представленный в прочих буферах. Любой из прочих буферов, предшествующих этому блоку в хронологическом порядке, становится частью группы активных буферов слияния прежде, чем начнется очередной цикл ввода, но другие — показанные выше в скобках — сохранят свой статус прочего буфера в следующем цикле. Однако в следующий цикл с сохранением статуса может быть перенесено не более Я из этих буферов в скобках, поскольку придется передать 11 — 1 прочих буферов в группу.
активных буферов чтения сразу после того, как будет получен сигнал о п>тонности к вводу. Любой дополнительный буфер иэ группы прочих может явно очищаться, как если бы содержащаяся в нем информация еще и не считыналась. Такая очистка выполняется, например, в цикле 4 в (24): невозможно обработать все шесть блоков Аег4,?>д>аг и течение цикла 5, поскольку Я = 4. Так что придется повторно прочесть д> и аг. В противном же случае чтение выполняется на полной скорости.
В упр. 29 доказано, что для любой заданной хронологической последовательности серий, которые должны быть слиты, метод рандомизированного разделения позволяет достичь в среднем минимального числа операций чтения с дисков, пропорционального г(Р, (',>+ 2), где функция г табулироваиа в табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
