Каскадное слияние
Cтраница 3
Каскадное слияние, как и несбалансированное слияние, зависит от возможности подсистемы ввода-вывода поддерживать одновременно ввод-вывод в несбалансированной форме. На сбалансированных системах с двумя каналами каскадное слияние не будет работать эффективно. [31]
Вторая строчка рис. 15.15; 7, Тъ и Те - те три ленты, которые будут исчерпаны на первом просмотре слияния. Они получают строки, как при каскадном слиянии. В третьей строчке рис. 15.15 показан идеальный уровень для каскадного слияния, который был бы достигнут, если бы каскадное распределение было бы продолжено. В четвертой строчке показан идеальный уровень, который был бы достигнут, если бы распределение выполнялось под многоэтапное слияние. [32]
Метод фиктивных величин может быть применен к каскадному слиянию. Настройка фиктивными величинами перемещает строки для достижения идеального уровня. По этой причине выбор горизонтального или вертикального распределения, а также соответствующих распределений между уровнями не влияет на производительность слияния. На рис. 15.5 показано вертикальнее распределение, которое пытается достичь уровня 14, 11, 6 на трех лентах вывода. Исчерпание наступает после распределения 24 строк. Фиктивные величины с Do no Da показаны сбоку от распределений на лентах. [33]
Размещение строк для каскадного слияния может быть вертикальным, горизонтальным или смешанным; настройка между уровнями может происходить при помощи частичных просмотров или фиктивных величин. Если идеальный уровень не достигнут, то издержки при каскадном слиянии обычно больше, чем при многоэтапном. [34]
 |
Настройка фиктивными величинами. [35] |
Интересный и эффективный, хотя и несколько сложный, подход для распределения при каскадном слиянии был создан для пакета сортировки SODA ( Sequential Ordering of DAta) для UNIVAC III. Он рассматривается здесь, потому что алгоритм частичного просмотра для каскадного слияния ранее не был опубликован в широкой литературе. [36]
Каскадное слияние формально является ( k - 1) - поточным слиянием и во многом схоже с многоэтапным слиянием. С точки зрения практики разница между ними в том, что каскадное слияние более мощно при большом количестве лент, а многоэтапное - при малом. [37]
 |
Компромиссное слияние из трех этапов. [38] |
Строчки с шестой по одиннадцатую на рис. 15.15 показывают построение уровня 3 для каждой ленты. Ленты с 6 по 4 - это те ленты, которые получают строки как при каскадном слиянии. Ленты с 3 по 1 получают приращение как при многоэтапном слиянии. На рис. 15.16 показано слияние, которое бы получилось, если бы формирование строк прекратилось в данный момент. [39]
 |
Компромиссное слияние с тремя этапами. [40] |
Это название отражает то место, какое это слияние занимает между предельными случаями, которыми являются многоэтапное и каскадное слияния. Эта промежуточность вытекает из формы этапов слияния, выполняемых в течение просмотра слияния. У многоэтапного слияния степени k - 1 на один частичный просмотр приходится один этап. У каскадного - на один просмотр приходится k - 1 отдельных этапов. [41]
Вторая строчка рис. 15.15; 7, Тъ и Те - те три ленты, которые будут исчерпаны на первом просмотре слияния. Они получают строки, как при каскадном слиянии. В третьей строчке рис. 15.15 показан идеальный уровень для каскадного слияния, который был бы достигнут, если бы каскадное распределение было бы продолжено. В четвертой строчке показан идеальный уровень, который был бы достигнут, если бы распределение выполнялось под многоэтапное слияние. [42]
На восьми лентах каскадное предпочтительнее многоэтапного при 145 строках, а многоэтапное предпочтительнее каскадного при 45 строках. В общем случае, в силу своей способности просматривать строки, каскадное слияние более эффективно при большом числе строк, тогда как многоэтапное эффективнее при меньшем их числе. Для достижения нового уровня при каскадном слиянии надо обработать намного больше строк, и эта тенденция становится особенно ярко выраженной на высоких уровнях. Однако и при меньших совокупностях строк бывает, что каскадное слияние предпочтительнее. Это случается тогда, когда уровни очень близки к совершенным уровням каскадного слияния. При плохом уровне каскадного слияния уменьшению числа перемещаемых строк могут способствовать методы частичных просмотров. При большом количестве лент число строк, при котором каскадное слияние становится предпочтительным, намного меньше. При малом количестве лент ( например, k 4) многоэтапное слияние превосходно во всех отношениях. [43]
При каскадном слиянии исчерпываются все ленты, при многоэтапном - только одна. Ленты, которые исчерпываются в течение просмотра, получают строки так, как если бы выполнялось каскадное слияние. [44]
Частичность каждого просмотра является общей чертой компромиссного и многоэтапного слияний. Однако при компромиссном слиянии перемещается больше строк - условие, которое при некоторых значениях k и N приводит к большей эффективности, чем у многоэтапного слияния. Аналогично, для некоторых значений k и N больше строк перемещается при слияниях высоких степеней, приводя к большей эффективности, чем у каскадного слияния. [45]
Страницы: 1 2 3 4