Диссертация (1149731), страница 17
Текст из файла (страница 17)
При оптимальном распределении ресурсов∃ + () ⊆ () : > 0 тогда и только тогда, когда ∈ + (); иЛемма 3.3.⎛ = max ⎝⎞1+ ∑︁∈ + ()() () ⎠−,0 ,() ()где ∈ (), = | +()|.Доказательство. Воспользуемся обозначениями определенными при доказательстве леммы 3.2.Первое утверждение в лемме 3.2 определяет, что ресурсы должны выделяться вершинам с достаточно маленьким значением (), и мы определимподмножество вершин + (), которым должны быть выделены ресурсы.86Для упрощения обозначений предположим, что вершины пронумерованы впорядке возрастания значений () и будем ссылаться на операцию по ее номеру.Рассмотрим такое наибольшее , что ≥ () −∑︀=1 ().Отметим, чтовыражение в правой части неравенства равно 0, когда = 1, следовательно,такое существует при любых значениях .Согласно второму утверждению леммы 3.2 ресурсы должны быть выделены вершинам, для которых () ≤ (), с тем, чтобы сделать соответствующиесомножители целевой функции равными. На первом шаге, количество ресурсовравное () − () выделяется каждой вершине ∈ + ().
Таким образом, бу-∑︀=1 (() − ()). В итоге,∑︀оставшееся количество вычислительных ресурсов + =1 () − () распределяется между этими операциями:дет распределено общее количество ресурсов равное = () − () ++∑︀+()−()=1 ()=1=− (),∑︀где ∈ + ().Для завершения доказательства осталось заменить все вхождения () отношением()() .3.3.3. Распределение ресурсов между братьямиЛемма 3.4 определяет оптимальное распределение ресурсов между братьями в критическом (под)дереве.Необходимое условие оптимальности распределения ресурсов состоит втом, что количество вычислительных ресурсов, выделяемого каждому из братьев должно быть пропорционально наклону его функции качества.Пусть критическое (под)дерево; ∈ () корневые вершиныподдеревьев-братьев с линейными функциями качества, то есть (¯)() = (¯ ) + (¯ ), где лежит внутри области определения функции; ∈ Rколичество вычислительных ресурсов, которое должно быть распределеномежду этими поддеревьями.
При оптимальном распределении ресурсов ¯ =Лемма 3.4.1/(¯ )∑︀¯ . 1/( )87Доказательство.Качество всего плана зависит отmin{(¯ )(¯ )} = min{ (¯ ) + (¯ )¯ },где¯ = . Для того, чтобы максимизировать качество плана, мы должнымаксимизировать эту компоненту. Следовательно, мы должны распределить∑︀ресурсы так, что ¯ = и для всех , ∑︀ (¯ ) + (¯ )¯ = (¯ ) + (¯ )¯ .Следующие равенства показывают, что качество братьев остается равнымпри распределении порций ресурсов, определенных в формулировке леммы:1/(¯ )¯ ) + ∑︀ 1¯¯¯¯=( ( ) + ( )¯ = ( ) + ( ) ∑︀¯¯ = 1/( ) 1/( ) (¯ ) + ∑︀¯1¯ ) + (¯ ) ∑︀1/( ) = (¯ ) + (¯ )¯ ,=(1/(¯ )1/(¯ )и ограничение на общее количество ресурсов также выполняется:∑︁∑︀¯∑︁ 1/(¯ ) 1/( )∑︀¯ =¯ ) = ∑︀ 1/(¯ ) = .1/(3.4.
Алгоритм распределения ресурсовВ этом разделе описывается пошаговый приближенный алгоритм оптимального распределения фиксированного количества ресурсов для плана выполнения запроса.3.4.1. Алгоритм и структуры данныхЛеммы 3.3 и 3.4 в разделе 3.2 определяют стратегию оптимального распределения ресурсов между вершинами в дереве определенной структуры, аименно, деревьев представляющих собой путь от корня к листу (вертикальный88Рис.
3.3. Пример структуры гипер-вершинпуть) или между братьями одной родительской вершины. Поскольку леммыоснованы на линейном поведении функций качества, распределение ресурсовбудет происходить в несколько этапов, на каждом из которых будет распределяться некоторое количество вычислительных ресурсов.Для того, чтобы иметь возможность использовать утверждения лемм валгоритме, будем строить виртуальные гипер-вершины из определенных частейдерева плана выполнения запроса и применять соответствующую лемму приработе с каждой отдельной гипер-вершиной.Вершину будем называть точкой расщепления, если у нее несколько детей.
Виртуальные гипер-вершины строятся для критического (под)дерева последующим правилам:∙ Если критические (под)деревья листовые (гипер-)вершины-братья, тоони образуют новую, которая становитсяединственным ребенком родительской вершины.горизонтальную гипер-вершинувертикаль-∙ Любой путь от листа до точки расщепления образует новую, которая становится листовой для вершины расщепления.ную гипер-вершинуОчевидно, что хотя бы одно из описанных правил применимо, если планвыполнения запроса содержит не меньше двух операций.
Процесс построениягипер-вершин останавливается, когда все дерево плана выполнения запроса образует одну вертикальную гипер-вершину, поскольку корневая операция не может иметь братьев. Пример структуры гипер-вершин показан на рисунке 3.3.Функции качества оригинальных вершин дерева строятся из моделей качества соотвествующих операций. Функции качества гипер-вершин строятся вмомент образования гипер-вершины.89Леммы 3.3 и 3.4 основаны на том, что функции качества операций (и вершин) линейны.
К сожалению, функции качества гипер-вершин не всегда линейны, и мы заменяем их линейным приближением, что делает наш алгоритм распределения ресурсов приближенным. Функция качества горизонтальной гипервершины линейна согласно лемме 3.4. Функция качества вертикальной гипервершины в общем случае не линейна, и мы приблизим ее касательной, что корректно на определенном диапазоне значений аргумента функции.Диапазон значений аргумента функции качества для гипер-вершин строится на основе следующего набора правил:∙ Максимальное значение аргумента функции качества горизонтальнойгипер-вершины равно удвоенному минимуму из максимальных значенийаргументов функций качества, образующих ее вершин;∙ В качестве верхней границы аргумента функции качества вертикальнойгипер-вершины выбирается такое максимальное значение, при которомпри распределении ресурсов между образующими ее вершинами не изменится число = | + ()| из леммы 3.3.Весь процесс распределения ресурсов между операциями в дереве можетбыть описан псевдо-кодом алгоритма 1.Алгоритм 1 Алгоритм распределения ресурсовInput: Дерево плана выполнения запроса , распределяемое количество ресурсов .Output: Для каждой вершины ∈ ( ), определить выделенное количестворесурсов .Initialization(, )while > 0 & !isMaxQualityReached( ) doQualityEstimation( ) =CriticalSubtreeConstruction( ) =HypergraphConstruction( )ResourceAllocation(, )end whileНа этапе инициализации рекурсивным спуском по дереву плана каждойоперации в плане выполнения запроса выделяется минимальное количестворесурсов необходимое для ее выполнения и выравнивается ее функция качества.90Если сумма выделенных минимальных количеств ресурсов превосходит , алгоритм завершается, поскольку исполнение плана при заданных ограниченияхна количество доступного вычислительных ресурсов невозможно.Вершины в дереве, которые получили максимально возможное количестворесурсов, помечаются как насыщенные и исключаются из дальнейшего рассмотрения при распределении ресурсов, однако учитываются при построениифункций качества для гипер-вершин.После первичного распределения минимально необходимого объема ресурсов операциям происходит итеративное распределение свободного (не распределенного) количества вычислительных ресурсов небольшими порциями.
Размеры распределяемых порций ресурсов, определяются следующими правилами:∙ границы линейных сегментов кусочно-линейных функций качества вершин не должны нарушаться, и∙ качество критического поддерева не должно превосходить качество егобрата, если последний лежит вне критического поддерева.Инкрементальное выделение ресурсов продолжается до тех пор пока не будет распределен весь доступный объем вычислительных ресурсов или не будетдостигнуто максимально возможное качество плана.На шаге оценки качества используется рекурсивный спуск по дереву ипересчитывается качество достигнутое каждым подпланом.
На этой фазе такжепроисходит переоценка изменившихся статистик Q-множеств, анализируемых вплане, поскольку при выделении дополнительных ресурсов новые оценки могутповлиять на функции качества операций и всего плана.На каждой итерации пересчитывается критическое поддерево и системагипер-вершин и запускается рекурсивное распределение ресурсов внутри гипервершин, на основе соответствующей леммы.Псевдокод алгоритма 2 описывает процесс построения гипер-вершин.3.4.2.
Горизонтальная гипер-вершинаСогласно лемме 3.4, количество вычислительных ресурсов, выделяемое горизонтальной гипер-вершине, распределяется между братьями так, чтобы прирост качества у них был одинаковый.91Алгоритм 2 Алгоритм построения гипер-вершинInput: Операция ∈ ( ).Output: Гипер-вершина ℎ().=loopif |children()| > 1 thenfor all ℎ ∈ children() doℎ=Hypernode(ℎ)end forchildren()= HorisontalHypernode(ℎ())else if |children()| = 0 thenbreakelse=children()[0]end ifend loop=VerticalHypernode()Пусть - гипер-вершина с операциями , и - наклоны их функцийкачества, то есть для каждой функция качества имеет вид ( )() = ( ) +∑︀( ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
