Диссертация (1149731), страница 18
Текст из файла (страница 18)
Пусть = 1/ . Если общее количество ресурсов, выделяемое ,равно , то = .Построение функции качества горизонтальной гипер-вершины очевидно:начальное качество совпадает с исходным качеством братьев, коэффициент на- праклона вычисляется на основе наклонов братьев и равен 1 . Пусть вые границы линейных сегментов функций качества братьев, тогда праваяграница линейного сегмента функции качества гипер-вершины равна = }.min {3.4.3. Вертикальная гипер-вершинаРабота с вертикальными гипер-вершинами устроена несколько сложнее.Пусть - вертикальная гипер-вершина с вершинами , и ( ) = ( )/( ), где и определены в лемме 3.3.
Также положим, что =(). Согласно лемме оптимальное распределение количества вычислительных ресурсов ∑︀∈92достигается, когда{︃ =( + )/ − ( ),0,если ( + )/ − ( ) > 0в других случаях,где и , соответственно, сумма и число таких ( ), для которых ( + )/ −( ) > 0. Очевидно, что это выражение положительно для минимальных значений ( ), поскольку / среднее арифметическое значений ( ).Для построения функции качества гипер-вершины алгоритм выбираетподмножество вложенных вершин с минимальным значением ( ).
Ресурсы будут выделяться только вершинам из этого подмножества. Выделяемые количества ресурсов не должны превосходить максимальные, определенные в функциях качества вершин. Также, после распределения ресурсов выросшее значение( ) не должно превышать следующее минимальное, и достигнутое качество недолжно превышать качество некритических братьев.∏︀Точная функция качества гипер-вершины вычисляется как ∈ (() +() ).
При работе алгоритма используется ее линейное приближение касательной. Область определения приближения определяется на основе правил определенных в подразделе 3.4.1. Как только количество ресурсов выделяется гипервершине, оно распределяется между вложенными вершинами.Предложенный алгоритм распределения ресурсов является приближенным, поскольку при работе с вертикальными гипер-вершинами используютсялинейные приближения их функций качества.
Однако, меньшие порции ресурсов, распределяемые на каждой итерации, приводят к увеличению числа итераций и уменьшению ошибки, что позволяет найти баланс между стоимостьюраспределения ресурсов и точностью ответа.3.4.4. Вычислительная сложностьВычислительная сложность алгоритма зависит от числа операций в планевыполнения запроса и количества линейных сегментов в функциях качествакаждой из операций.
Помимо обычных вершин дерева плана алгоритм оперирует с гипер-вершинами. Поскольку любая гипер-вершина содержит хотя быодно ребро из первоначального дерева плана, число гипер-вершин не превосходит − 1, и общее число вершин и гипер-вершин оценивается как 2.93На каждой итерации распределения ресурсов происходит несколько обходов дерева. В худшем случае стоимость обхода дерева оценивается числомвершин в нем, то есть 2. Эта оценка применяется к процедурам вычислениякачества поддеревьев, выравнивания функций качества, и выделения ресурсов.Обход дерева с такой оценкой стоимости также происходит при выделении минимального количества ресурсов операциям.При вычислении ограничений, связанных с некритическими братьями, также необходим проход всех поддеревьев внутри вертикальной гипервершины.
В худшем случае сложность этого этапа оценивается числом поддеревьев − 1 умноженным на общее число вершин 2. Следовательно,общая сложность одной итерации распределения ресурсов оценивается как(3 * 2 + 2 ( − 1)) = ( 2 ).Пусть максимальное число линейных сегментов в функциях качестваопераций. При грубой оценке общее число линейных сегментов равно ;дополнительные линейные сегменты возникают из ограничений, связанных снекритическими братьями и мощностью вертикальных гипер-вершин, которыхбудет не больше .Каждая итерация распределения ресурсов не может покрыть нескольколинейных сегментов и нарушить границы функций качества. Поэтому верхняяграница на число итераций распределения ресурсов равна 3 , и конечнаясложность всего алгоритма оценивается как ( 5 ).Некоторые из верхних оценок представленных выше никогда не достигаются одновременно.
Например, если длина вертикального пути равна , товсе вершины дерева плана включены в него и, следовательно, у них нет братьев, в том числе критических, поэтому соответствующий множитель в оценкесложности алгоритма равен 1. Аналогично, если критическое дерево включает в себя все операций, у вершин нет некритических братьев и алгоритм нерассматривает связанные с ними ограничения.Алгоритм распределения ресурсов имеет полиномиальную сложность от числа операций в плане выполнения запроса и количествалинейных сегментов в функциях качества каждой из операций.Утверждение 3.1.Таким образом, предложенный алгоритм распределения ресурсов обеспечивает достаточно быстрые вычисления при работе с планами, содержащимидесятки операций.943.5. ЭкспериментыДля анализа поведения предложенного приближенного алгоритма распределения ресурсов была проведена серия экспериментов.
Все эксперименты использовали реализацию на Java, запускаемую на машине со следующими характеристиками: i5 2.67 GHz CPU, 8 Gb RAM, 64 bit операционной системой.В экспериментах оценивались производительность и точность алгоритма.Эффективность оценивалась в терминах времени, необходимого для распределения ресурсов в плане выполнения запроса, и числа итераций основного циклаалгоритма.Для оценки точности приближенного алгоритма необходимо знать точнуюфункцию качества плана. Поскольку алгоритм оптимального распределениянедоступен, и точная функция качества не может быть построена, мы использовали его приближение.Ошибка предложенного алгоритма вызвана использованием линейныхприближений функций качества гипер-вершин.
Очевидно, что ошибка становится несущественной при достаточно маленьких порциях ресурсов, распределяемого на каждой итерации. Поэтому для оценки точного распределенияресурсов мы использовали предложенный алгоритм с дополнительным ограничением на количество ресурсов, распределяемого на каждом шаге.Отметим, что предложенный алгоритм оперирует с функциями качества,полученными из моделей качества операций, а не на основе выполнения плана.Оценивать характеристики алгоритма будем в зависимости от числа операций в плане выполнения запроса, топологии дерева плана, числа линейныхсегментов в функциях качества операций.
Для полноценной оценки алгоритма все эксперименты проводились на синтетически сгенерированных планах ифункциях качества операций. Проведение экспериментов на реальных данныхпозволило бы оценить модели стоимости и качества, но не свойства предложенного алгоритма, что остается вне рамок этой работы.Случайные планы выполнения запросов генерировались с ∈{5, 10, 15, 20, 25} операциями. Функции качества каждой операции генерировались с различным числом линейных сегментов, изменявшемся в диапазоне от1 до , где ∈ {1, 2, 3, 4, 5}. Минимальное и максимальное количество ресурсовнеобходимое для исполнения каждой операции также выбиралось случайно в95абРис. 3.4. Среднее число итераций и время работы алгоритма распределенияресурсов для различных плановдиапазоне [0, 100].
Топология дерева плана определялась случайно, после чего вычислялось количество бинарных операций (вершин расщепления), чтобыоценить насколько этот параметр влияет на поведение алгоритма.Наиболее интересные результаты экспериментов приведены ниже.Рисунок 3.4а показывает, как число итераций алгоритма распределенияресурсов, зависит от дерева плана выполнения запроса: числа операций и числа линейных сегментов в функциях качества операций. Для каждой пары (, )для эксперимента было случайно сгенерировано 300 планов. Для каждого плана выполнения запроса с помощью предложенного приближенного алгоритмараспределялось количество ресурсов равное = + ( − ), где ∈ {0.25, 0.5, 0.75, 1}.
Результаты этого же эксперимента с замерами абсолютного времени работы алгоритма показаны на рисунке 3.4б. На показаны результаты эксперимента, в котором для каждого плана распределялось количестворесурсов равное = + 0.5 * ( − ), а число бинарных операцийв планах определялось средним значением для этого числа операций в дереве.Заметим, что среднее число итераций и среднее абсолютное время работы алгоритма растет при увеличении числа операций в плане и количества линейныхсегментов в функциях качества вершин.Результаты экспериментов по оценке точности приближенного алгоритма распределения ресурсов отражены на рисунке 3.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
