Диссертация (Оптимизация обработки вложенных запросов в многопроцессорной базе данных), страница 7

таблицу 2.4:Таблица 2.4 Численные результатыk=8NПроцессораP=0.5P=0.6P=0.7P=0.5P=0.65P=0.7r=11.3821n2.2790 n3.8206 n1.4785 n2.6868 n4.2260 nr =21.7375 n2.5766 n3.7073 n1.9375 n3.1356 n4.1909 nr =41.7500 n2.2560 n2.8140 n2n2.7950 n3.2200 nr =82.2800 n2.9250 nВремя выполненияk=8,p=[0.5,0.6,0.7], ∆=0.4; k=8,p=[0.5,0.6,0.7], ∆=0.55432101-processor2-processor4-processor8-processorРис.2.2.

Время выполнения на i-м процессоре k элементарных запросов приквазиоптимальном порядке их распределения по процессорам для упорядоченныхстобцов таблицы2.3.5. Обработки запроса для неупорядоченных столбцов таблицыестественныйпорядокраспределения.ГеометрическаяпрогрессияПустьвремявыполненияэлементарногозапросаподчиняетсязаконугеометрической прогрессииВремя выполнения на i-м процессоре k/r элементарных запросов из общего числа kэлементарных запросов при естественном порядке их распределения по процессорам,кодга данные в столбцах неупорядочены равно:=()() ,.В самом деле, в соответствии с теоремой 1[1] имеем:=+…++=Можно представить(в другом виде)() ,)(так как=+…+(1++…+или)(=().Очевидно, что эти два выражения идентичны, так как=().Однако, последнее выражение длядаетвозможностьпоказать, чтооптимальный алгоритм обеспечивает меньшее время вычисления запроса r процессорами.2.3.6.

Квазиоптимальныйпорядокраспределения.Геометрическая прогрессияВремя выполнения2.3.6.1.Время выполнения на i-м процессоре k/r элементарных запросов из общего числа kэлементарных запросов при квазиоптимальном порядке их распределения по процессорам,кодга данные в столбцах неупорядочены равно: (для простоты записей будем считать, чтоk/r есть целое четное число):)(=().В самом деле, в соответствии с теоремой 1 имеем:(*.или(=(**)(.или=()(*.или)(=(2.3.6.2.))(=() ,.Соотношения времени выполнения на i-м и-мпроцессорахДля естественного порядка распределения элементарных запросов непосредственноиз выражения для,, r >1, имеем неравенства:Для квазиоптимального порядка распределения элементарных запросов наосновании выражений дляпри,, r >1,имеем неравенства:В самом деле, неравенствовыполняется тогда и только тогда,когдаили когдаили когдаНеравенствовыполняется, когдаили когда,что выполняется прии так далее.Наконец, неравенствовыполняется, когдаили когда,что естественно выполняется приОбобщая, находим, что все исходные неравенствавыполняются приМаксимальный разброс времени выполнения запросов здесь составляет:() n.Приследующая цепочка неравенств:при этом неравенствоили есливыполняется, если(r.Напротив, неравенствовыполняется, если,(rАналогично, прии вообще, приНаконец, при).имеем неравенства:,,имеем:имеем:Максимальный разброс времени выполнения обработки запросовПри(составляет:) n.Минимальная и максимальная границы времени выполненияИмея в виду, чтотак как (1+)<(1+,) или,и также выполняется,так какилинаходим, что минимальная и максимальная границы времени выполненияприоптимальном распределении лежат внутри минимальной и максимальной границы приестественном распределении.Максимальный разброс времени выполнения обработки запросов на r процессорахсоставляет:- при естественном порядке(,- при квазиоптимальном порядке(() n, при) n,,.Абсолютное уменьшение границ времени выполнения запросов при использованииоптимального распределения вместо естественного распределения равно:((=)().,Относительноеуменьшениеграницвременивыполнениязапросовприоптимальном распределении=(,2.3.6.3.Эффективность квазиоптимального распределенияВремя выполнения на i-м процессоре k/r элементарных запросов из общего числаk элементарных запросов при квазиоптимальном порядке их распределения попроцессорам равно (здесь, как и ранее, k/r есть целое четное число)=()().Максимальное время завершения обработки k/r элементарных запросов на всехпроцессорах в частных случаях равно:- для r =1() ,- дляпри(()(= ((*() * ,при(* )+- дляпри,при()- для=.Приведем ряд численных результатов для этих формул при k=8; a=1.15, 1.2,1.25,1.3;p=0.6,0.7, см.

таблицу 2.5:Таблица 2.5 Численные результатыk=8N-Процессора1.151.2P=0.6P=0.7P=0.6P=0.7r=13.0601n4.2239 n3.3135 n4.7008 nr =23.1167 n3.8340 n3.5573 n4.4547 nr =42.5960 n2.8620 n3.1499 n3.5082 nr =k2.6600 n3.5832 nk=81.25N-ПроцессораP=0.6P=0.7P=0.6P=0.7r=13.5995 n5.2511 n3.9227 n5.8861 nr =24.0807 n5.1990 n4.7018 n6.0897 nr =43.8610 n4.3379 n4.7649 n5.3924 nr =kВремя выполнения1.3765432104.7684 n6.2749 nk=8,p=[0.6,0.7], a=1.15; a=1.2, k=8,p=[0.6,0.7], a=1.15; a=1.2,k=8,p=[0.6,0.7], a=1.25; a=1.2, k=8,p=[0.6,0.7], a=1.15; a=1.3,1-processor2-processor4-processor8-processorРис.2.3. Время выполнения на i-м процессоре k элементарных запросов приквазиоптимальном порядке их распределения по процессорам для неупорядоченныхстобцов таблицы2.3.7.

Обработки запроса для упорядоченных столбцов таблицыестественныйпорядокраспределения.ГеометрическаяпрогрессияПустьвремявыполненияэлементарногозапросаподчиняетсязаконугеометрической прогрессииВремя выполнения на i-м процессоре k/r элементарных запросов из общего числа kэлементарных запросов при естественном порядке их распределения по процессорам,когда в стобцах упорядочены равно:= ()() ,.Можно представить(в другом виде) ,)(.Очевидно, что эти два выражения идентичны, так как=().Однако, последнее выражение длядает возможность показать, чтооптимальный алгоритм обеспечивает меньшее время вычисления запроса r процессорами.2.3.8.

Квазиоптимальныйпорядокраспределения.Геометрическая прогрессия2.3.8.1.Время выполненияВремя выполнения на i-м процессоре k/r элементарных запросов из общего числа kэлементарных запросов при квазиоптимальном порядке их распределения по процессорам,когда данные в столбцах упорядочены равно (для простоты записей будем считать, что k/rесть целое четное число):= ()(2.3.8.2.).Соотношения времени выполнения на i-м и-мпроцессорахДля естественного порядка распределения элементарных запросов непосредственноиз выражения для,, r >1, имеем неравенства:Для квазиоптимального порядка распределения элементарных запросов наосновании выражений дляпри,, r >1,имеем неравенства:В самом деле, неравенствовыполняется тогда и только тогда,когдаили когдаили когдаНеравенствовыполняется, когдаили когда,что выполняется прии так далее.Наконец, неравенствовыполняется, когдаили когда,что естественно выполняется приОбобщая, находим, что все исходные неравенствавыполняются приМаксимальный разброс времени выполнения запросов здесь составляет:() ,Приследующая цепочка неравенств:при этом неравенствоили если.выполняется, если(r.Напротив, неравенствовыполняется, если,(rАналогично, прии вообще, приНаконец, при).имеем неравенства:,,имеем:имеем:Максимальный разброс времени выполнения обработки запросов присоставляет:().Минимальная и максимальная границы времени выполненияПоэтомуминимальная и максимальная границы времени выполненияприоптимальном распределении лежат внутри минимальной и максимальной границы приестественном распределении.Максимальный разброс времени выполнения обработки запросов на r процессорахсоставляет:- при естественном порядке().- при квазиоптимальном порядке(() , при) ,,.Абсолютное уменьшение границ времени выполнения запросов при использованииоптимального распределения вместо естественного распределения равно:(Относительное)уменьшение.границвременивыполнениязапросовприоптимальном распределении=(,2.3.8.3.Эффективность квазиоптимального распределенияВремя выполнения на i-м процессоре k/r элементарных запросов из общего числаk элементарных запросов при квазиоптимальном порядке их распределения попроцессорам, когда данных в стобцах упорядочены равно (здесь, как и ранее, k/r естьцелое четное число)= ()().Максимальное время завершения обработки k/r элементарных запросов на всехпроцессорах в частных случаях равно:- для r =1() ,- дляпри(()() * ,при= ((*((* )+- дляпри,при()- для=.Приведем ряд численных результатов для этих формул при k=8; a=1.15, 1.2,1.25,1.3;p=0.6,0.7, см.

таблицу 2.6:Таблица 2.6 Численные результатыN-Процессораk=81.15P=0.61.2P=0.7 nP=0.6P=0.7r=11.8361n2.9567 n1.9881 n3.2906 nr =21.8700 n2.6838 n2.1344 n3.1183 nr =41.5576 n2.0034 n1.8899 n2.4557 nr =k1.8620 n2.1499 nk=81.25N-ПроцессораP=0.6P=0.7P=0.6P=0.7r=12.1597 n3.6758 n2.3536 n4.1203 nr =22.4484 n3.6393 n2.8211 n4.2628 nr =42.3166 n3.0365 n2.8589 n3.7747 nr =kВремя выполнения1.35432103.3379 n3.7649 nk=8,p=[0.6,0.7], a=1.15; a=1.2, k=8,p=[0.6,0.7], a=1.15; a=1.2,k=8,p=[0.6,0.7], a=1.25; a=1.2, k=8,p=[0.6,0.7], a=1.15; a=1.3,1-processor2-processor4-processor8-processorРис.2.4.

Время выполнения на i-м процессоре k элементарных запросов приквазиоптимальном порядке их распределения по процессорам для неупорядоченныхстобцов таблицыВыводы по главе 21. Определенысоотношениявременивыполнениявложенногозапросавмногопроцессорной базе данных для естественного и квазиоптимального порядкаих распределения длятаблицы.неупорядоченных идляупорядоченных столбцов2. Определены минимальная и максимальная границы времени выполнения группэлементарныхзапросовквазиоптимальноговпорядкаотдельныхпроцессорахраспределениядляэлементарныхестественногозапросовидлянеупорядоченных и для упорядоченных столбцов таблицы.3. Доказанаэффективностьквазиоптимальногораспределениянаосновеабсолютного и относительного уменьшения границ времени выполнения запросовпри использовании квазиоптимального распределения вместо естественногораспределения, что является важным решением для оптимизации обработкизапросов в многопроцессорных базах данных авиационно-космических систем.3. Оптимизация числа процессоров при выполнении вложенныхзапросовВведение3.1.Вработе[10]предложенпланоптимизацииповременивыполненияконъюнктивных вложенных запросов при обращении к однопроцессорной базе данных наоснове упорядочивания элементарных запросов.Минимальное время вложенного запроса для неупорядоченных данных таблицдостигается при совместной обработке объединенного множества элементарных запросовв порядке, определяемым условиями теоремы 1, и для упорядоченных данных таблицдостигается при совместной обработке объединенного множества элементарных запросовв порядке, определяемым условиями теоремы 2.В работе методика формирования плана оптимизации развита на случай обработкивложенных запросов многопроцессорными базами данных,актуальныхзадачразработкиметодикиоптимизациичто является одной изобработкизапросоввмногопроцессорных базах данных авиационно-космических систем.3.2.Квазиоптимальноераспределениеномеровэлементарныхзапросов по процессорамВ работе [9]оптимизации,предложен, а в работе [10]когдараспределениеобоснованэлементарныхквазиоптимальный методзапросовпопроцессорамосуществляется в соответствии с правилом, показанным в таблице 3.1, где в i-ой строкетаблицыуказаны номера элементарных запросов выполняемых i-м процессором впорядке слева направо, при этом мы используем (для простоты изложения) в качествезначения числа элементарных запросов k целое четное число, и число процессоров rотвечает условию [k/r]r=k.