Диссертация (1149731), страница 16

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 16)

Уточнение постановки задачиПоставленную в главе 2 задачу 2.4 о распределении ресурсов между операциями в плане выполнения запроса, переформулируем в новых терминах дереваи его вершин.Задача состоит в том, чтобы найти ∈ R для каждой операции ∈ ( )так, чтобы оценка ожидаемого качества результата приближенного выполненияплана была максимальна для любого заданного общего количества вычислительных ресурсов.Для заданного дерева плана и фиксированного количества ресурсов ∈ R задача распределения ресурсов ставится следующимобразом: arg max¯ ∈¯ (¯ ).Определение 3.6.Предполагая решение задачи распределения ресурсов, определим функцию качества для дерева плана, аналогичную функции качества вершины.Для дерева плана выполнения запроса его функция качества ( ) : R → Q определяется следующим образом: ∀ ∈ R ( )( ) =Определение 3.7.max¯ ∈¯ (¯ ).803.2.4.

Предположения о функциях качестваМы предполагаем, что функция относительного качества от выделенногообъема ресурсов неубывающая непрерывная ограниченная, то есть выполняются следующие условия:∙ Для каждой вершины ∈ ( ) известно минимальное количество вычислительных ресурсов, необходимое для выполнения операции, () ∈ R.Это количество ресурсов обеспечивает определенный уровень качества,а операция не может быть выполнена с использованием меньшего количества ресурсов. Кроме того, мы будем использовать обозначение вслучаях, когда из контекста понятно, о какой вершине идет речь.∙ Для каждой вершины ∈ ( ) известно количество вычислительныхресурсов () ∈ R такое, что выделение большего объема ресурсов навыполнение операции не приводит к росту относительного качества.∙ Для любого количества ресурсов между максимальным и минимальным,функция качества неубывающая, то есть ∀ ∈ ( ), ∀1 , 2 ∈ R : 1 <2 ()(1 ) ≤ ()(2 ).При приближенном вычислении среднего значения по некоторому атрибуту внутри операции минимальное количество ресурсов определяется стоимостью анализа аргумента мощности 1.

Например, для точного вычисления среднего значения необходимо провести полное сканирование аргумента операции,определяющее максимальное количество вычислительных ресурсов.Если операция не допускает приближенного исполнения, то минимальноеи максимальное количества ресурсов для этой операции равны стоимости ееточного исполнения, и распределение ресурсов между такими операциями вплане тривиально.Мы также предполагаем, что функция качества любой операции можетбыть аппроксимирована всюду определенной в R кусочно-линейной функцией:⎧⎪ < 0⎨ 0,∀ ∈ ( ) ()() = () + ()( − ), ≤ < ⎪⎩ () + ()(− ), ≤81где ∈ [0, ] количество линейных сегментов, () наклон на соответствующемсегменте, и () + ()( − ) = +1 ().Предположение о линейном приближении не является излишне ограничительным, поскольку функции качества возвращают только оценки качества.Мы также предполагаем, что каждый линейный сегмент имеет нетривиальныйнаклон, то есть () > 0.3.3.

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

На каждом шаге алгоритма применение точного решения будет корректно.Предположим, что минимальное количество ресурсов выделено каждойоперации в плане выполнения запроса. Этот шаг является необходимым, поскольку в противном случае выполнение плана даже приближенно становитсяневозможным.Оставшееся свободное количество ресурсов может быть дополнительнораспределено между вершинами в дереве, чтобы улучшить качество всего плана. Таким образом, имея некоторое распределение ресурсов ¯ ∈ ¯ мы будем строить новое расширяющее распределение ресурсов ¯′ ∈ ¯′ такое, что∀ ∈ ( ) ≤ ′ , где ∈ ¯ , ′ ∈ ¯′ .Когда каждой вершине выделено некоторое количество вычислительныхресурсов, мы можем оценить какого качества может достигнуть каждая опе-82рация и все дерево. Также мы можем определить каким линейным сегментомфункции качества вершины описывается дальнейшее изменение качества каждой операции при увеличении количества ресурсов, ей выделенного.Отметим, что при распределении дополнительного количества ресурсовдерево плана снова приходит в состояние, когда каждая операция достигланекоторого текущего качества.

Для того, чтобы упростить обозначения, будемрассматривать только порции ресурсов, которые будут выделены в дополнениек уже выделенным для каждой операции. Как только дополнительное количество ресурсов выделяется операции, ее функция качества пересчитывается так,как если бы уже выделенное количество было минимальным.Более формально, в дальнейшем в этом разделе мы будем работать с приростами ресурсов и рассматривать в каждый момент времени только один линейный сегмент функции качества: ∀ ∈ ( ) ()( ) = ()+(), где ∈ [ , ], = − , ∈ [0, ], и () = ()() = () + ()( − ).Мы будем говорить об оптимальном распределении ресурсов, имея ввидуоптимальное распределение между операциями в плане дополнительного количества ресурсов, однозначно определяющее оптимальное расширяющее распределение.3.3.1. Критическое поддеревоВычислительные ресурсы должны быть выделены только тем операциям,которые оказывают влияние на качество результата.

Эти операции составляюткритическое (под)дерево. Любой алгоритм, решающий проблему распределенияресурсов должен работать только с критическим (под)деревом.Для распределения ресурсов ¯ ∈ ¯ множество вершинкритического (под)дерева это подмножество вершин дерева плана выполнения запроса () ⊆ ( ), которое может быть построено рекурсивно:∙ если ∈ ( ) корень , тогда ∈ ();∙ если (¯)(¯ ) = min∈(()) ()(¯¯ ), где () ∈ (), ¯определяется распределением ресурсов ¯ , то ∈ ().Множество ребер критического (под)дерева это подмножество ребердерева плана () ⊆ ( ): если ребро ∈ ( ) связывает 1, 2 ∈ () в ,Определение 3.8.83то ∈ ().Иными словами, операция ∈ ( ) принадлежит критическому(под)дереву , если качество (под)дерева с корнем в минимально среди качества (под)деревьев-братьев и вершина () критическая.

Ребра соответствующего критического (под)дерева совпадают с ребрами исходного дереваплана выполнения запроса.В дальнейшем мы не будем указывать распределение ресурсов, по которому строится критическое поддерево, поскольку оно не существенно, так какмы будем искать оптимальное распределение дополнительного количества ресурсов.Докажем оптимальность распределения ресурсов среди операций критического (под)дерева.Для каждой операции ∈ ( ) ∖ () = 0 для любого оптимального распределения ресурсов.Доказательство. Предположим, что у вершины ∈/ () есть критическиеЛемма 3.1.братья.

Качество всего плана зависит от min∈() ((¯)(¯ )) = ()(¯¯ ),где () ∋ , ; и (¯)(¯ ) > ()(¯¯ ). Для увеличения этой компонентымы должны выделить ресурсы (под)дереву с корнем в , то есть ¯ > 0.В случае, когда ¯ > 0, качество результата не увеличивается. Таким образом, для каждой операции вне критического (под)дерева = 0.Предположим, что у вершины ∈/ () нет братьев. В этом случае у есть предок, описанный в предыдущем пункте, и поэтому = 0.Отметим, что качество плана выполнения запроса совпадает с качествомкритического (под)дерева.3.3.2. Распределение ресурсов вдоль путиВ случае, когда критическое (под)дерево, представляет собой путь, функция качества плана строится как произведение функций качества операций, егосоставляющих.Лемма 3.2 определяет необходимые условия распределения ресурсов между вершинами, образующими путь, в случае, если их функции качества линейны.84Пусть - критический путь, ∈ R количество вычислительных ресурсов, которое необходимо распределить; функция качества каждойвершины ∈ () - линейна, то есть ()() = () + (), где лежитвнутри области определения функции.

При оптимальном распределении ресурсов выполняются следующие условия:()∙ если = 0 и > 0, то ()() + ≤ () ,Лемма 3.2.∙()если > 0 и > 0, то ()() + = () + ,где , ∈ ()Доказательство.При оптимальном распределении ресурсов необходимо мак-симизировать значение функции∏︁ (¯ ) =(())∈ ()при следующих ограничениях: =∏︁(∈ ()∑︀∈ () ()+ )()и ≥ 0, где ¯ = { , ∈ ()}распределение ресурсов. Мы опустим постоянную компоненту∏︀∈ () ()вдальнейшем доказательстве.Пусть () =()()для каждой вершины ∈ (), и пусть ¯ распределениересурсов, удовлетворяющее условиям из постановки задачи оптимизации, тоесть, ≥ 0 и =∑︀∈ () .Докажем, что если () + < () + и > 0, то распределение ресурсов ¯ не оптимально. Пусть = ( ,()+ −()−)2и=()+ +()+.2Построим распределение ресурсов ¯ такое, что = + , = − , и = , ∈/ {, }. Покажем, что при таком распределении ресурсов значениецелевой функции будет выше, то есть (¯ ) > (¯ ).Если = 0, то () + − () − ≥ 2 или () − () − ≥ .∏︀ (¯ ) − (¯ )=∈ ()∖{,} (() + )(() + )(() + ) − (() + )(() + ) =(() + + )() − (() + )(() + ) =(() + )() + () − (() + )() − (() + ) =85 () − (() + ) ≥ 2 > 0.В противном случае, если > 0, то =()+ −()−,2и(() + )(() + ) = 2(() + )(() + ) = ( − )( + ) = 2 − 2 .Следовательно, (¯ ) > (¯ ).Таким образом, оптимальное распределение ресурсов ¯ обладает следующими свойствами:∙ если > 0 и > 0, то () + = () + ,∙ если = 0 и > 0, то () + ≤ ().Следующая лемма 3.3 определяет необходимые условия, подобные определенным в лемме 3.2, при дополнительных ограничениях на диапазон аргументовфункций качества операций, составляющих путь.Пусть - критический путь, ∈ R количество вычислительных ресурсов, которое необходимо распределить, функция качества каждойвершины ∈ () - линейна, то есть ()() = () + (), где лежит внутри области определения функции.

Характеристики

Список файлов диссертации