авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 | 2 || 4 |

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ На правах рукописи ...»

-- [ Страница 3 ] --

Y Y 25х 22х 20х 18х 16х 16х24 18х22 20х20 22х18 25х Y Y Рис. 3.8. Ресурсный прямоугольник Рис. 3.7. Ресурсный прямоугольник минимальной асимметрии- конечный минимальной асимметрии- начальный Приведм и исследуем уровневый алгоритм диспетчирования линейными гиперболическими полиэдралями ресурсных прямоугольников [81]. Уровневый алгоритм диспетчирования линейными гиперболическими полиэдралями ресурсных прямоугольников аналогичен разработанному в параграфе 2.4. В частности, для линейной полиэдрали гиперболических ресурсных прямоугольников с центральным элементом минимальной асимметрии k k k k j1 3k j1, j1 1, 2,, k k при соответствующие 2 2 построения уровневым алгоритмом по высоте приведены на рисунке 3.9.

46x34 38x 42x 32x 47x33 35x 39x 43x 48x 33x 36x 40x 44x 49x 31x 34x 37x 41x 45x 50x Рис. 3.9. Укладка гиперболической линейной полиэдрали ресурсных прямоугольников уровневым алгоритмом по высоте Эвристические меры ресурсных оболочек уровневого алгоритма по высоте для этой последовательности гиперболических ресурсных прямоугольников с центральным элементом минимальной асимметрии приведены в таблице 3.2.

Таблица 3.2. Эвристические меры ресурсных оболочек уровневого алгоритма по высоте Ресурсная Эвристическая Ресурсная Эвристическая k k оболочка мера оболочка мера 10 8357 0,69 16 163118 0, 11 9072 0,65 17 173126 0, 12 9978 0,60 18 182150 0, 13 10793 0,59 19 192158 0, 14 14196 0,72 20 238162 0, 15 148114 0, Отметим, что эвристические меры ресурсных оболочек уровневого 0,22.

алгоритма по высоте не превосходят значения Наряду с уровневым алгоритмом по высоте, исследуем уровневый алгоритм по протяжнности.

Для линейной гиперболической полиэдрали ресурсных прямоугольников с центральным элементом минимальной асимметрии k j1 3k j1, k k k j1 1, 2,, k k при соответствующие 2 2 построения уровневым алгоритмом по протяжнности приведены на рисунке 3.10.

50x 47x33 48x32 49x 44x36 45x35 46x 232 40x40 41x39 42x38 43x 36x44 37x43 38x42 39x 31x49 32x48 33x47 34x46 35x Рис. 3.10. Укладка гиперболической линейной полиэдрали ресурсных прямоугольников уровневым алгоритмом по протяжнности Эвристические меры ресурсных оболочек уровневого алгоритма по протяжнности для этой последовательности гиперболических ресурсных прямоугольников с центральным элементом минимальной асимметрии приведены в таблице 3.3.

Отметим, что эвристические меры ресурсных оболочек уровневого 0,18.

алгоритма по протяжнности не превосходят значения Таблица 3.3. Эвристические меры ресурсных оболочек уровневого алгоритма по протяжнности Ресурсная Эвристическая Ресурсная Эвристическая k k оболочка мера оболочка мера 10 6079 0,65 16 122158 0, 11 7290 0,65 17 126173 0, 12 8295 0,59 18 150179 0, 13 93107 0,59 19 158192 0, 14 99136 0,69 20 166232 0, 15 114148 0, Графики эвристической меры ресурсных оболочек уровневых алгоритмов по высоте и по протяжнности для этой линейной гиперболической полиэдрали ресурсных прямоугольников с центральным элементом минимальной асимметрии показаны на рисунке 3.11.

Рис. 3.11. Эвристические меры ресурсных оболочек уровневых алгоритмов для линейной гиперболической полиэдрали Видим, что график уровневого алгоритма по протяжнности расположен несколько ниже, что является более предпочтительным.

Для линейной гиперболической полиэдрали ресурсных прямоугольников горизонтальной формы с начальным элементом минимальной асимметрии k j1 3k j1, j1 k, k 1,, k k 1 k при соответствующие построения уровневым алгоритмом по высоте приведены на рисунке 3.12.

53x 48x32 40x 54x 44x 55x25 49x 41x 45x 56x 50x 42x 57x 46x 51x 58x 43x 47x 52x 59x Рис. 3.12. Укладка гиперболической линейной полиэдрали ресурсных прямоугольников горизонтальной формы уровневым алгоритмом по высоте Эвристические меры ресурсных оболочек уровневого алгоритма по высоте для этой последовательности гиперболических ресурсных прямоугольников горизонтальной формы с начальным элементом минимальной асимметрии приведены в таблице 3.4.

Отметим, что эвристические меры ресурсных оболочек уровневого алгоритма по высоте для этой последовательности гиперболических ресурсных прямоугольников горизонтальной формы с начальным элементом минимальной 0,25.

асимметрии не превосходят значения Таблица 3.4. Эвристические меры ресурсных оболочек уровневого алгоритма по высоте для гиперболических ресурсных прямоугольников горизонтальной формы Ресурсная Эвристическая Ресурсная Эвристическая k k оболочка мера оболочка мера 10 7657 0,63 16 158117 0, 11 8370 0,61 17 168130 0, 12 9178 0,57 18 180135 0, 13 12682 0,75 19 192146 0, 14 13886 0,72 20 201168 0, 15 146111 0, Наряду с уровневым алгоритмом по высоте, исследуем уровневый алгоритм по протяжнности.

Для линейной гиперболической полиэдрали ресурсных прямоугольников горизонтальной формы с начальным элементом минимальной асимметрии k j1 3k j1, j1 k, k 1,, k k 1 k при соответствующие построения уровневым алгоритмом по протяжнности приведены на рисунке 3.13.

59x 56x24 57x23 58x 53x27 54x26 55x 50x30 51x29 52x 47x33 48x32 49x 44x36 45x35 46x 40x40 41x39 42x38 43x Рис. 3.13. Укладка гиперболической линейной полиэдрали ресурсных прямоугольников горизонтальной формы уровневым алгоритмом по протяжнности Эвристические меры ресурсных оболочек уровневого алгоритма по протяжнности для этой последовательности гиперболических ресурсных прямоугольников горизонтальной формы с начальным элементом минимальной асимметрии приведены в таблице 3.5.

Отметим, что эвристические меры ресурсных оболочек уровневого алгоритма по протяжнности для этой последовательности гиперболических ресурсных прямоугольников горизонтальной формы с начальным элементом 0,23.

минимальной асимметрии не превосходят значения Таблица 3.5. Эвристические меры ресурсных оболочек уровневого алгоритма по протяжнности для гиперболических ресурсных прямоугольников горизонтальной формы Ресурсная Эвристическая Ресурсная Эвристическая k k оболочка мера оболочка мера 10 5780 0,68 16 117167 0, 11 6986 0,63 17 132178 0, 12 75109 0,73 18 147190 0, 13 90117 0,69 19 158198 0, 14 96129 0,66 20 171211 0, 15 111138 0, Графики эвристической меры ресурсных оболочек уровневых алгоритмов по высоте и по протяжнности для этой линейной гиперболической полиэдрали ресурсных прямоугольников горизонтальной формы с начальным элементом минимальной асимметрии показаны на рисунке 3.14.

Рис. 3.14. Эвристические меры ресурсных оболочек уровневых алгоритмов для гиперболических ресурсных прямоугольников горизонтальной формы Сравнение результатов не позволяет отдать предпочтение какому- либо из алгоритмов.

Для линейной гиперболической полиэдрали ресурсных прямоугольников вертикальной формы с конечным элементом минимальной асимметрии k j1 3k j1, k j1 1, 2,, k при соответствующие построения уровневым алгоритмом по высоте приведены на рисунке 3.15.

37x43 22x 25x 28x 31x 34x 38x 171 23x 26x 29x 32x 35x 39x 24x56 21x 27x 30x 33x 36x 40x Рис. 3.15. Укладка гиперболической линейной полиэдрали ресурсных прямоугольников вертикальной формы уровневым алгоритмом по высоте Эвристические меры ресурсных оболочек уровневого алгоритма по высоте для этой последовательности гиперболических ресурсных прямоугольников вертикальной формы с конечным элементом минимальной асимметрии приведены в таблице 3.6.

Таблица 3.6. Эвристические меры ресурсных оболочек уровневого алгоритма по высоте для гиперболических ресурсных прямоугольников вертикальной формы Ресурсная Эвристическая Ресурсная Эвристическая k k оболочка мера оболочка мера 10 8057 0,68 16 167117 0, 11 8669 0,63 17 178132 0, 12 10975 0,73 18 190147 0, 13 11790 0,69 19 198158 0, 14 12996 0,66 20 211171 0, 15 138111 0, Отметим, что эвристические меры ресурсных оболочек уровневого алгоритма по высоте для этой последовательности гиперболических ресурсных прямоугольников вертикальной формы с конечным элементом минимальной 0,23.

асимметрии не превосходят значения Наряду с уровневым алгоритмом по высоте, исследуем уровневый алгоритм по протяжнности.

Для линейной гиперболической полиэдрали ресурсных прямоугольников вертикальной формы с конечным элементом минимальной асимметрии k j1 3k j1, k j1 1, 2,, k при соответствующие построения уровневым алгоритмом по протяжнности приведены на рисунке 3.16.

37x43 38x42 39x41 40x 33x47 34x46 35x45 36x 28x52 29x51 30x50 31x49 32x 21x59 22x58 23x57 24x56 25x55 26x54 27x Рис. 3.16. Укладка гиперболической линейной полиэдрали ресурсных прямоугольников вертикальной формы уровневым алгоритмом по протяжнности Эвристические меры ресурсных оболочек уровневого алгоритма по протяжнности для этой последовательности гиперболических ресурсных прямоугольников вертикальной формы с конечным элементом минимальной асимметрии приведены в таблице 3.7.

Отметим, что эвристические меры ресурсных оболочек уровневого алгоритма по протяжнности для этой последовательности гиперболических ресурсных прямоугольников вертикальной формы с конечным элементом 0,25.

минимальной асимметрии не превосходят значения Таблица 3.7. Эвристические меры ресурсных оболочек уровневого алгоритма по протяжнности для гиперболических ресурсных прямоугольников вертикальной формы Ресурсная Эвристическая Ресурсная Эвристическая k k оболочка мера оболочка мера 10 5776 0,63 16 117158 0, 11 7083 0,61 17 130168 0, 12 7891 0,57 18 135180 0, 13 82126 0,75 19 146192 0, 14 86138 0,72 20 168201 0, 15 111146 0, Графики эвристической меры ресурсных оболочек уровневых алгоритмов по высоте и по протяжнности для этой линейной гиперболической полиэдрали ресурсных прямоугольников вертикальной формы с конечным элементом минимальной асимметрии показаны на рисунке 3.17.

Рис. 3.17. Эвристические меры ресурсных оболочек уровневых алгоритмов для гиперболических ресурсных прямоугольников вертикальной формы Сравнение результатов не позволяет отдать предпочтение какому- либо из алгоритмов.

Таким образом, в настоящем параграфе предлагается и исследуется эвристический уровневый алгоритм диспетчирования массивами заявок гиперболического типа. Устанавливается полиномиальная трудомкость предложенного уровневого алгоритма. Для базовых примеров массивов заявок гиперболического типа: ресурсных прямоугольников k j1 3k j1, k k k j1 1, 2,, k, ресурсных прямоугольников 2 2 k j1 3k j1, j1 k, k 1,, k k горизонтальной формы (преимущественные требования временного ресурса a j1 b j1 ), ресурсных k j1 3k j1, j1 1, 2,, k прямоугольников вертикальной формы ресурса a j1 b j1 ) строятся (преимущественные требования процессорного объемлющие прямоугольники с вычислением эвристических мер. Делаются выводы о качестве предложенного эвристического полиномиального уровневого алгоритма.

3.3. Угловой алгоритм для гиперболических заявок Угловой алгоритм диспетчирования линейными гиперболическими k a j1, b j1, b j1, a j1, j полиэдралями ресурсных прямоугольников j1 [81] аналогичен разработанному в параграфе 2.5. Основное отличие в том, что при локализации линейной круговой полиэдрали укладываемые прямоугольники выбирались слева- направо как при размещении по горизонтали, так и при размещении по вертикали. При локализации же линейной гиперболической полиэдрали укладываемые прямоугольники при размещении по горизонтали выбираются вправо от центрального элемента (используем свойство убывания высот b j1, j1 ), а при размещении по вертикали- влево от центрального элемента (используем свойство убывания оснований a j1, j1 ). В частности, для линейной гиперболической полиэдрали ресурсных прямоугольников с k j1 3k j1, центральным элементом минимальной асимметрии k k k j1 1, 2,, k при k 20 соответствующие построения приведены на 2 2 рисунке 3.18.

48x32 49x31 50x 34x 37x43 32x 33x 35x 207 38x42 46x34 47x 36x 39x41 44x36 45x 31x 40x40 41x39 42x38 43x Рис. 3.18. Укладка гиперболической линейной полиэдрали ресурсных прямоугольников угловым алгоритмом Эвристические меры ресурсных оболочек углового алгоритма для этой последовательности гиперболических ресурсных прямоугольников с центральным элементом минимальной асимметрии приведены в таблице 3.8.

Таблица 3.8. Эвристические меры ресурсных оболочек углового алгоритма для гиперболических ресурсных прямоугольников Ресурсная Эвристическая Ресурсная Эвристическая k k оболочка мера оболочка мера 10 7979 0,80 16 151154 0, 11 8787 0,73 17 161164 0, 12 9498 0,68 18 179179 0, 13 102106 0,63 19 189189 0, 14 110114 0,58 20 200207 0, 15 141122 0, Отметим, что эвристические меры ресурсных оболочек углового алгоритма для этой последовательности гиперболических ресурсных прямоугольников с центральным элементом минимальной асимметрии не превосходят значения 0,30.

При локализации линейной гиперболической полиэдрали с ресурсными прямоугольниками горизонтальной формы с начальным элементом минимальной асимметрии укладываемые прямоугольники выбираются слева- направо как при размещении по горизонтали, так и при размещении по вертикали. Однако, в этом случае при укладке по горизонтали вправо от центрального углового элемента высоты убывают, а при укладке по вертикали вверх основания возрастают вследствие чего центральные угловые элементы не связаны вершинно диагональным синтезом как в параграфе 2.5 и в начале настоящего параграфа. В частности, для гиперболической полиэдрали ресурсных прямоугольников горизонтальной формы с начальным элементом минимальной асимметрии k j1 3k j1, j1 k, k 1,, k k 1 k при соответствующие построения угловым алгоритмом приведены на рисунке 3.19.

51x 54x 46x 50x 53x 59x 45x 49x31 52x 58x 57x 44x36 47x33 48x 56x 40x40 41x39 42x38 43x 55x Рис. 3.19. Укладка гиперболической линейной полиэдрали ресурсных прямоугольников горизонтальной формы угловым алгоритмом Эвристические меры ресурсных оболочек углового алгоритма для этой последовательности гиперболических ресурсных прямоугольников горизонтальной формы с начальным элементом минимальной асимметрии приведены в таблице 3.9.

Таблица 3.9. Эвристические меры ресурсных оболочек углового алгоритма для гиперболических ресурсных прямоугольников горизонтальной формы Ресурсная Эвристическая Ресурсная Эвристическая k k оболочка мера оболочка мера 7755 10 0,64 16 0, 10170 11 0,81 17 0, 11078 12 0,75 18 0, 11986 13 0,70 19 0, 128100 14 0,67 20 0, 15 0, Отметим, что эвристические меры ресурсных оболочек углового алгоритма для этой последовательности гиперболических ресурсных прямоугольников горизонтальной формы с начальным элементом минимальной асимметрии не 0,31.

превосходят значения При локализации линейной гиперболической полиэдрали с ресурсными прямоугольниками вертикальной формы с конечным элементом минимальной асимметрии укладываемые прямоугольники выбираются слева- направо как при размещении по горизонтали, так и при размещении по вертикали. В этом случае также при укладке по горизонтали вправо от центрального углового элемента высоты убывают, а при укладке по вертикали вверх основания возрастают вследствие чего центральные угловые элементы не связаны вершинно диагональным синтезом как в параграфе 2.5 и в начале настоящего параграфа. В частности, для гиперболической полиэдрали ресурсных прямоугольников вертикальной формы с конечным элементом минимальной асимметрии k j1 3k j1, j1 1, 2,, k при k 20 соответствующие построения угловым алгоритмом приведены на рисунке 3.20.

29x 34x46 35x45 36x44 37x 40x 28x52 30x50 31x49 32x48 33x 39x 21x59 22x58 23x57 24x56 25x55 26x54 27x 38x Рис. 3.20. Укладка гиперболической линейной полиэдрали ресурсных прямоугольников вертикальной формы угловым алгоритмом Эвристические меры ресурсных оболочек углового алгоритма для этой последовательности гиперболических ресурсных прямоугольников вертикальной формы с конечным элементом минимальной асимметрии приведены в таблице 3.10.

Таблица 3.10. Эвристические меры ресурсных оболочек углового алгоритма для гиперболических ресурсных прямоугольников вертикальной формы Ресурсная Эвристическая Ресурсная Эвристическая k k оболочка мера оболочка мера 6974 10 0,69 16 0, 11 0,76 17 164132 0, 10189 12 0,71 18 0, 10698 13 0,64 19 0, 14 0,59 20 211162 0, 15 0, Отметим, что эвристические меры ресурсных оболочек углового алгоритма для этой последовательности гиперболических ресурсных прямоугольников вертикальной формы с конечным элементом минимальной асимметрии не 0,26.

превосходят значения Графики эвристической меры ресурсных оболочек разработанных и исследованных полиномиальных алгоритмов диспетчирования линейными гиперболическими полиэдралями ресурсных прямоугольников с центральным элементом минимальной асимметрии показаны на рисунке 3.21.

Рис. 3.21. Эвристические меры ресурсных оболочек полиномиальных алгоритмов диспетчеризации линейными гиперболическими полиэдралями Графики эвристической меры ресурсных оболочек разработанных и исследованных полиномиальных алгоритмов: уровневого и углового для линейных гиперболических полиэдралей ресурсных прямоугольников горизонтальной формы с начальным элементом минимальной асимметрии приведены на рисунке 3.22, для вертикальной формы с конечным элементом минимальной асимметрии- на рисунке 3.23.

Рис. 3.22. Эвристические меры ресурсных оболочек полиномиальных алгоритмов диспетчирования гиперболическими прямоугольниками горизонтальной формы Рис. 3.23. Эвристические меры ресурсных оболочек полиномиальных алгоритмов диспетчирования гиперболическими прямоугольниками вертикальной формы Таким образом, полиномиальные алгоритмы распределения процессорно временных ресурсов: центрально- кольцевой, уровневый и угловой могут быть рекомендованы для использования в диспетчерах Grid- систем.

Таким образом, в настоящем параграфе предлагается и исследуется эвристический угловой алгоритм диспетчирования массивами заявок гиперболического типа. Устанавливается полиномиальная трудомкость предложенного углового алгоритма. Для базовых примеров массивов заявок гиперболического типа: ресурсных прямоугольников k j1 3k j1, k k k j1 1, 2,, k, ресурсных прямоугольников 2 2 k j1 3k j1, j1 k, k 1,, k k горизонтальной формы (преимущественные требования временного ресурса a j1 b j1 ), ресурсных k j1 3k j1, j1 1, 2,, k прямоугольников вертикальной формы ресурса a j1 b j1 ) строятся (преимущественные требования процессорного объемлющие прямоугольники с вычислением эвристических мер. Делаются выводы о качестве предложенного эвристического полиномиального углового алгоритма.

3.4. Полиэдрали со свойством монотонности Рассмотрим k- модульную линейную полиэдраль ресурсных k k ai j, bi j, ai j 1, bi j 1 ai j, bi j прямоугольников с i 1 j упорядочиванием граней по вложению в пределах каждого i - го модуля (рисунок 3.24) [77].

,,..., 1- я полиэдраль 2- я полиэдраль k- я полиэдраль Рис. 3.24. k- модульная линейная полиэдраль ресурсных прямоугольников Выполнив кольцевой синтез кругового массива каждого модуля, придм к линейной полиэдрали из «k» ресурсных оболочек граней первоначальных модулей (рисунок 3.25).

...

Рис. 3.25. Линейная полиэдраль из «k» ресурсных оболочек Исходный массив относим к классу k- модульных линейных полиэдралей монотонной круговой составности, если построенное множество оболочек в свою k ai, bi, ai 1, bi 1 ai, bi, очередь упорядочено по вложению i i 1, 2,, k 1. Свойство монотонной составности k- модульной линейной полиэдрали кругового квадратичного типа обеспечивает кольцевой синтез указанного массива в две стадии: вначале, помодульно, затем, кольцевым синтезом ресурсных оболочек, полученных на первой стадии.

Введм понятие монотонной составности для k- модульной линейной полиэдрали из модулей гиперболического квадратичного типа, содержащих «k»

последовательно несравнимых граней с убывающими высотами и растущими основаниями [77]. С этой целью, применим центрально- угловой синтез граней i - го каждого гиперболического модуля в угловую полиэдраль вида (рисунок 3.26) Рис. 3.26. Центрально- угловой синтез граней гиперболического модуля В случае, когда i 1 - ая угловая полиэдраль допускает размещение внутри угловой координатной области предыдущей i - ой угловой полиэдрали для i 1, 2,, k 1, (рисунок 3.27) исходный массив относим в класс k- модульных линейных полиэдралей монотонной гиперболической составности.

Y.

..

0 Y Рис. 3.27. Вершинно- диагональное соединение центрально- углового синтеза граней k- модульной гиперболической полиэдрали Данное дополнительное свойство гиперболической монотонности позволяет на втором этапе центрально- углового синтеза гиперболических модулей получить координатную ресурсную оболочку граней исходного массива с вычислением измерений оболочки на первой стадии синтеза.

Таким образом, в настоящем параграфе вводится k- модульная линейная полиэдраль модулей кругового квадратичного типа. Кольцевая локализация модулей кругового типа используется для формирования «k» ресурсных оболочек модулей в линейную полиэдраль граней- оболочек. Круговой тип последней определяет свойство монотонности исходной k- модульной полиэдрали. На основании свойства монотонности вводится двухстадийная кольцевая локализация: помодульная и оболочечная. Понятие монотонной k- модульной полиэдрали обобщается на гиперболическую квадратичную типизацию модулей.

При этом используется центрально- угловая локализация модулей в ресурсные оболочки. Оболочки центрально- угловой локализации подвергаются вершинно диагональному синтезу в качестве второй стадии локализации исходного массива.

3.5. Выводы 1. Предложены, разработаны и исследованы полиномиальные алгоритмы диспетчирования, адаптированные к массивам заявок гиперболического квадратичного типа.

2. Проведн сравнительный анализ разработанных полиномиальных алгоритмов диспетчирования линейными гиперболическими полиэдралями: центрально- кольцевого, уровневого по высоте и протяжнности, углового.

Глава 4. Массивы заявок параболического типа 4.1. Алгоритм со среднересурсным уровнем Исследуем среднересурсный уровневый алгоритм диспетчирования линейными параболическими полиэдралями ресурсных прямоугольников k a j1, b j1 с низкими гранями, в которых высоты всех граней не выше j1 k max b j1 H (рисунок 4.1) a j1 b j1, среднересурсной величины H 0 j1 k j1 [81].

Y 6 8 10 12 14 16 18 0 Y Рис. 4.1. Параболическая полиэдраль с низкими ресурсными прямоугольниками Случай линейных параболических полиэдралей с высокими гранями, когда max b j1 H рассмотрен в следующем параграфе 4.2. Обозначим через H 0 j1 k уровень горизонтальной полосы 0 Y2 H. В целях большей наглядности описание алгоритма иллюстрируется базовым примером массива заявок параболического типа.

10. На первом шаге вдоль линии Y1 0 вертикально суперпозируются k q a j1, b j1 до наилучшего приближения уровня ресурсные прямоугольники j1 k k q b j1 H с недостатком (операция динамического интегрирования j1 k ресурсных прямоугольников по вертикали). Здесь q1 - число ресурсных прямоугольников, суперпозированных в первом слое. Строится начальная ресурсная оболочка (рисунок 4.2).

Y bk q1 ak q...

b(k-1) a(k-1) 0 Y Рис. 4.2. Начальная ресурсная оболочка 20. На втором шаге вдоль правой стороны достигнутой ресурсной оболочки Y1 ak 1 вертикально суперпозируются ресурсные прямоугольники k q1 q a j1, b j1 до наилучшего приближения уровня с недостатком j1 k q1 k q1 q b j1 H 0 (операция динамического интегрирования ресурсных j1 k q1 прямоугольников по вертикали). Здесь q2 - число ресурсных прямоугольников, суперпозированных во втором слое. Строится новая ресурсная оболочка (рисунок 4.3).

Y bk q1 a k q1 q ak q bk q1 q...

...

bk 121 q b(k-1) ak q1 a(k-1) 0 Y Рис. 4.3. Первая ресурсная оболочка 30. На следующем шаге вдоль правой стороны достигнутой ресурсной оболочки Y1 ak 1 ak q1 1 вертикально суперпозируются последующие k q1 q 2 q, b j ресурсные прямоугольники до наилучшего приближения a j j1 k q1 q 2 k q1 q 2 q H уровня с недостатком (операция динамического b j j1 k q1 q 2 интегрирования ресурсных прямоугольников по вертикали). Здесь q3 - число ресурсных прямоугольников, суперпозированных в третьем слое. Строится достигнутая ресурсная оболочка (рисунок 4.4).

Y bk q1 bk q1 q2 q a k q1 q 13 ak q bk q1 q2 ak q1 q2 q...

...

...

bk q1 q2 bk 121 q b(k-1) ak q1 1 ak q1 q2 a(k-1) 0 Y Рис. 4.4. Вторая ресурсная оболочка 40. Введнный таким образом алгоритм со среднересурсным уровнем повторяем до полного исчерпания ресурсных прямоугольников массива. Строится конечная ресурсная оболочка (рисунок 4.5).

Y bk q1 a k q1 q2 bk q1 q2 q 13 ak q1 1 b(0) bk q1 q2 ak q1 q2 q...

a(0)...

...

...

bk 9 q1 q2 bk 121 q...

b(k-1) ak q1 1 ak q1 q2 a(k-1) 0 Y Рис. 4.5. Конечная ресурсная оболочка Отметим, что количество операций работы алгоритма со среднересурсным уровнем составляет k операций сложения и k операций сравнения, т.е. алгоритм является полиномиальным.

Покажем, что в линейной параболической полиэдрали ресурсных j1 k j1, j1 1, k 1 Z прямоугольников высоты всех граней ниже k max b j1 H. Действительно, a j1 b j1, среднересурсной величины H 1 j1 k j1 так как a j1 j1, b j1 k j1, то k k 1 k 1k 1 2k k 1 k kj1 j12 k H2 2 j1 1 j1 k k 1 2 k 1 k k 2 1.

k k 1 k k 2 3 6 k 1 max b j1 при k 6.

k Следовательно, H k 1 j1 k В частности, для линейной параболической полиэдрали ресурсных j1 k j1, j1 1, k 1 Z 1 k прямоугольников при соответствующие построения алгоритмом со среднересурсным уровнем приведены на рисунке 4.6.

Здесь в центре прямоугольника указан его номер, соответствующий значению основания.

15 16 12 19 20 Рис. 4.6. Укладка алгоритмом со среднересурсным уровнем Время работы оптимального алгоритма [71] приведено в таблице 4.1.

Таблица 4.1. Время работы оптимального алгоритма Время работы оптимального алгоритма k 2.93GHz Intel Core 2 Duo E Дни Часы Минуты Секунды 20 - - 02 21 - - 07 22 - - 11 23 - 9 12 24 3 22 50 Видим, что время оптимальной укладки 23- х параболических прямоугольников превышает 94 часа. Графика оптимальной укладки приведена на рисунке 4.7 [71].

20 3 13 10 Рис. 4.7. Оптимальная укладка [71] Эвристические меры ресурсных оболочек оптимального алгоритма [69,71] для последовательности параболических ресурсных прямоугольников 1 k 1, 2 k 2,, k 1 1 приведены в таблице 4.2.

Таблица 4.2. Эвристические меры ресурсных оболочек оптимального алгоритма Ресурсная Эвристическая Ресурсная Эвристическая k k оболочка мера оболочка мера 14 1629 0,70 20 3242 0, 15 1930 0,62 21 3742 0, 16 2429 0,53 22 3551 0, 17 2336 0,61 23 3460 0, 18 2441 0,66 24 3861 0, 19 2448 0, Отметим, что эвристические меры ресурсных оболочек оптимального по 0,26.

площади алгоритма не превосходят значения Сравним качество приведнного алгоритма со среднересурсным уровнем с оптимальной укладкой в объемлющий прямоугольник минимальной площади, полученной в работах [69,71]. Приведм в таблице 4.3 результаты размещения алгоритмом со среднересурсным уровнем для последовательности параболических ресурсных прямоугольников j1 k j1, j1 1, 2,, k 1. Здесь L- горизонтальное и H- вертикальное измерения объемлющего прямоугольника алгоритма со среднересурсным уровнем, - погрешность площади ресурсной оболочки в % относительно оптимального значения.

Таблица 4.3. Сравнение алгоритмов со среднересурсным уровнем и оптимального L H L H,%,% k k 31 21 51 14 40,3 20 36, 33 24 53 15 38,9 21 33, 37 25 55 16 32,9 22 29, 38 28 61 17 28,5 23 34, 43 18 35,5 24 25, 63 50 19 34, График погрешности алгоритма со среднересурсным уровнем по сравнению с оптимальным алгоритмом приведн на рисунке 4.8.

Рис. 4.8. Погрешность полиномиального алгоритма со среднересурсным уровнем Заметим, что погрешность площади ресурсной оболочки относительно оптимального значения не превосходит 40,3%. что является подтверждением целесообразности использования предложенного алгоритма со среднересурсным уровнем при диспетчировании процессорно- временными ресурсами.

Эвристические меры ресурсных оболочек алгоритма со среднересурсным уровнем приведены в таблице 4.4.

Таблица 4.4. Эвристические меры ресурсных оболочек алгоритма со среднересурсным уровнем для параболических ресурсных прямоугольников Эвристическая мера Эвристическая мера k k 14 0,83 20 0, 15 0,78 21 0, 16 0,79 22 0, 17 0,71 23 0, 18 0,76 24 0, 19 0, Отметим, что эвристические меры ресурсных оболочек алгоритма со 0,34.

среднересурсным уровнем не превосходят значения График эвристической меры ресурсных оболочек разработанного и исследованного алгоритма со среднересурсным уровнем показан на рисунке 4.9.

Рис. 4.9. Эвристические меры ресурсных оболочек полиномиального алгоритма диспетчирования линейными параболическими полиэдралями Таким образом, полиномиальный алгоритм со среднересурсным уровнем может быть рекомендован для использования в диспетчерах Grid- систем.

Таким образом, в настоящем параграфе предлагается и исследуется полиномиальный эвристический алгоритм диспетчирования параболическими полиэдралями с низкими ресурсными прямоугольниками, в которых высоты всех граней не выше среднересурсной величины. Для базового примера массива заявок параболического типа с низкими гранями- ресурсных прямоугольников j1 k j1, j1 1, 2,, k 1, строятся объемлющие прямоугольники с вычислением ресурсных и эвристических мер. Указанные построения и вычисления сопоставляются с имеющимися в литературе оптимальными построениями ресурсных оболочек. Делаются выводы о качестве предложенного среднересурсного уровневого алгоритма диспетчеризации массивами заявок параболического типа.

4.2. Начально- уровневый алгоритм Приведм и исследуем начально- уровневый алгоритм диспетчирования линейными параболическими полиэдралями ресурсных прямоугольников k a j1, b j1 [80].

j1 10. За уровень принимаем высоту начального ресурсного прямоугольника b0 и получаем начальную ресурсную оболочку (рисунок 4.10).

Y b(0) a(0) Y Рис. 4.10. Начальная ресурсная оболочка 20. На втором шаге вдоль линии Y1 a0 вертикально суперпозируются q a j1, b j1 до наилучшего приближения уровня с ресурсные прямоугольники j1 q b j1 b0 недостатком (операция динамического интегрирования j1 ресурсных прямоугольников по вертикали). Здесь q1 - число ресурсных прямоугольников, суперпозированных во втором слое. Строится ресурсная оболочка полученной совокупности ресурсных прямоугольников (рисунок 4.11).

Y b(0) b(1) a(0) a(1) Y Рис. 4.11. Первая ресурсная оболочка 30. На третьем шаге вдоль правой стороны достигнутой ресурсной оболочки Y1 a0 max a j1 вертикально суперпозируются последующие 1 j1 q q1 q a j1, b j1 до наилучшего приближения уровня ресурсные прямоугольники j1 q1 q1 q b j1 b0 с недостатком (операция динамического интегрирования j1 q1 ресурсных прямоугольников по вертикали). Здесь q2 - число ресурсных прямоугольников, суперпозированных в третьем слое. Строится новая ресурсная оболочка (рисунок 4.12).

Y b(3) a(3) b(0) b(1) b(2) a(0)a(1) a(2) Y Рис. 4.12. Вторая ресурсная оболочка 40. На следующем шаге вдоль правой стороны достигнутой ресурсной оболочки Y1 a0 max a j1 a j1 вертикально суперпозируются max 1 j1 q1 q1 1 j1 q1 q q1 q 2 q a j1, b j последующие ресурсные прямоугольники до наилучшего j1 q1 q 2 q1 q 2 q b j1 b0 0 (операция динамического приближения уровня с недостатком j1 q1 q 2 интегрирования ресурсных прямоугольников по вертикали). Здесь q3 - число ресурсных прямоугольников, суперпозированных в четвртом слое.

50. Введнный таким образом начально- уровневый алгоритм повторяем до полного исчерпания ресурсных прямоугольников массива. Строится конечная ресурсная оболочка (рисунок 4.13).

Y b(3) a(3) b(2) b(1) a(6) b(6) a(5) b(5) b(4) a(4) a(0)a(1) a(2) Y Рис. 4.13. Конечная ресурсная оболочка Обозначим через C- количество шагов начально- уровневого алгоритма.

Горизонтальное измерение оболочки определяется как L L a0 max a j1 a j1 a j1.

max max C 2 C 1 j1 q1 q1 1 j1 q1 q q j 1 j1 q j j 1 j Вертикальное измерение оболочки H равно высоте начальной грани H b0.

Параметры определены выше, число ресурсных qj q1, q2, q прямоугольников, суперпозированных на j - м шаге в вертикальном слое.

Метод начально- уровневой параболической локализации проиллюстрируем на массивах j1 k j1 2, j1 1, k 1 Z 1 и Ck j1 2k j1, j1 0, k Z 1.

Покажем, что в линейной параболической полиэдрали ресурсных прямоугольников j1 k j1 2, j1 1, k 1 Z 1 высота начальной грани выше k a j1 b j1, b0 H. Действительно, так как среднересурсной величины H j1 k 1 k 1 j j a j1 j1, b j1 k j1, j1k j j k 1 1 1 1 2 2 то j1 1 k k k j1 k 1 k 2 1 k4 4 j1k j k x1 x dx k и H2. Следовательно, 2 3 4 12 j1 k4 k b0 k 1 k H 2.

12 Для массива натуральных параболических ресурсных прямоугольников j1 k j1 2, k 6 (рисунок 4.14) за уровень принимаем высоту начального ресурсного прямоугольника b0 25 и получаем начальную ресурсную оболочку (рисунок 4.15).

Y2 Y 25 4 Y1 Y Рис. 4.14. Параболический массив Рис. 4.15. Начальная ресурсная оболочка j1 k j1 2, k 6 с высокими гранями Второй (рисунок 4.16) и третий (рисунок 4.17) шаги начально- уровневого алгоритма диспетчеризации параболической линейной полиэдрали приводят к 1 9 25 25 2,29.

ресурсной оболочке с эвристической мерой 2 105 Y Y 12 12 Y Y Рис. 4.17. Конечная ресурсная оболочка Рис. 4.16. Первая ресурсная оболочка Эвристические меры ресурсных оболочек начально- уровневого алгоритма для последовательности натуральных параболических ресурсных прямоугольников 1 k 12, 2 k 22,, k 1 1 приведены в таблице 4.5.

Таблица 4.5. Эвристические меры ресурсных оболочек начально- уровневого алгоритма для последовательности натуральных параболических ресурсных прямоугольников Эвристическая мера Эвристическая мера k k 6 2,29 11 3, 7 2,69 12 3, 8 2,84 13 3, 9 3,11 14 3, 10 3,21 15 3, Покажем, что в линейной параболической полиэдрали ресурсных прямоугольников Ck j1 2k j1, j1 0, k Z 1 высота начальной грани выше k a j1 b j1, b0 H. Действительно, так как среднересурсной величины H j1 k a j1 Ck j1, b j1 2k j1, то Ck j1 2k j1 1 H2 3k. Следовательно, k j1 3 k.

b0 2k H 3k Для линейной параболической полиэдрали Ck j1 2k j1, k 4 (рисунок 4.18) начально- уровневый алгоритм дат ресурсную оболочку (рисунок 4.19) с 1 7 16 16 7 1,19.

эвристической мерой 2 81 Y2 Y 01 01 4 6 4 1 Y1 Y Рис. 4.18. Параболический массив Рис. 4.19. Ресурсная оболочка начально Ck j1 2k j1, k 4 с высокими уровневого алгоритма гранями Эвристические меры ресурсных оболочек начально- уровневого алгоритма для последовательности параболических ресурсных прямоугольников Ck0 2k, Ck1 2k 1,, Ckk 1 21, 11 приведены в таблице 4.6.

Таблица 4.6. Эвристические меры ресурсных оболочек начально- уровневого алгоритма Эвристическая мера k 4 1, 5 1, 6 2, 7 2, 8 3, В следующем параграфе 4.3 на этих базовых примерах будет проведено сравнение начально- уровневого с возвратным и ступенчатым алгоритмами.

Заметим, что для линейной параболической полиэдрали ресурсных прямоугольников с низкими высотами j1 k j1, j1 1, k 1 Z 1 предыдущего параграфа 4.1 при k 24 соответствующие построения начально- уровнем алгоритмом приведены на рисунке 4.20.

Рис. 4.20. Укладка параболической полиэдрали с низкими высотами начально- уровневым алгоритмом Соответствующие эвристические меры ресурсных оболочек среднересурсного уровневого алгоритма меньше, чем у начально- уровневого алгоритма локализации такой линейной параболической полиэдрали с низкими высотами. Приведнное сравнение показывает целесообразность применения среднересурсного уровневого алгоритма или начально- уровневого алгоритма в зависимости от того низкие или высокие грани в массиве заявок параболического типа.

Таким образом, в настоящем параграфе предлагается и исследуется полиномиальный эвристический алгоритм диспетчирования параболическими полиэдралями с высокими ресурсными прямоугольниками, в которых высота начальной грани выше среднересурсной величины. Для базовых примеров массивов заявок параболического типа с высокими гранями- ресурсных Ck j1 2k j1, j1 0, 1,, k, j1 k j1 2, j1 1, 2,, k прямоугольников и строятся объемлющие прямоугольники с вычислением эвристических мер.

Делаются выводы о качестве предложенного начально- уровневого алгоритма диспетчирования массивами заявок параболического типа.

4.3. Возвратный и ступенчатый алгоритмы Приведм и исследуем возвратный и ступенчатый алгоритмы диспетчирования линейными параболическими полиэдралями ресурсных k a j1, b j1 [80,133].

прямоугольников j1 * 10. Центральная грань j1 по некоторому уровню V является ближайшей к точке достижения этого уровня b j1 V 0.

* 20. Грани j1 j1 относим в левый, j1 j1 - в правый блок. К последним * * применяем уровневый алгоритм параграфа 4.1 для уровня V. А именно, грани правее центра, суперпозируем вертикально над гранью a j1 1, b j1 * * до наилучшего приближения с недостатком к уровню V суммарными высотами q b j1 V 0.

вертикальной полиэдрали Из оставшихся граней формируем j1 j1 * последующие вертикальные полиэдрали суммарной высоты V 0, подвергая последние динамической суперпозиции к предыдущим вдоль горизонтальной координаты. В итоге, получаем ресурсную оболочку правого блока A, B.

30. В возвратном алгоритме к левой стороне полученной оболочки a0, b суперпозируем начальную грань максимальной высоты, получая угловую область начального полиэдра (рисунок 4.21).

Y начальная грань b(0) центральная вершина суперпозиции в угловую область оболочка правого блока B Y A a(0) Рис. 4.21. Суперпозиция начальной грани и оболочки правого блока 40. В угловой области данного полиэдра вершинно- диагонально синтезируем линейную полиэдраль левого блока за вычетом начальной грани.

Вычисляем эвристическую меру получаемой ресурсной оболочки (рисунок 4.22) с измерениями max a0 A, A* - по горизонтали, maxb0, b1 B- по вертикали, * j a j1.

где A * j1 Y b(1) b(0) * b j * a(1) a j B Y A a(0) Рис. 4.22. Ресурсная оболочка первого шага алгоритма 50. Возвращаем вершинно- диагональный блок в первоначальное A, B начальную a0, b положение. Синтезируем с оболочкой правого блока и первую грань a1, b1.

60. В угловой области данного полиэдра вершинно- диагонально синтезируем линейную полиэдраль левого блока за вычетом начальной и первой граней. Вычисляем эвристическую меру получаемой ресурсной оболочки max a0 a1 A, A* 4.23) с измерениями по горизонтали, (рисунок max b0, b j1 B - по вертикали.

* Y b(0) * b j b(1) * a j B a(0) a(1) A Y Рис. 4.23. Ресурсная оболочка второго шага алгоритма 70. На последнем шаге осуществляем горизонтальный синтез с оболочкой * j a j1, b j A, B правого блока линейной полиэдрали левого блока и j1 вычисляем эвристическую меру получаемой ресурсной оболочки (рисунок 4.24) с измерениями A* A - по горизонтали, maxb0, B- по вертикали. Повторение возвратных перераспределений граней параболической полиэдрали продолжаем 0 или до исчерпания шагов алгоритма. Вариант с до получения эвристики меньшей эвристической мерой считаем наилучшим.

Y b(0) b(1) * b j B Y * a(0) a(1) a j1 A Рис. 4.24. Ресурсная оболочка конечного шага возвратного алгоритма Для ступенчатого алгоритма первые два шага полностью аналогичны соответствующим шагам возвратного алгоритма.

30. В ступенчатом алгоритме на третьем шаге вертикально суперпозируем A, B с гранью a1, b1 и ресурсную прямоугольную оболочку правого блока вычисляем эвристическую меру получаемой ресурсной оболочки (рисунок 4.25) с измерениями max a0 A, A* - по горизонтали, maxb0, b1 B- по вертикали.

Y A B b(0) b(1) * b j Y * a(0) a(1) a j Рис. 4.25. Третий шаг ступенчатого алгоритма 40. На четвртом шаге вертикально суперпозируем оболочку правого блока a j, b j и A, B * * с гранью вычисляем эвристическую меру получаемой 1 ресурсной оболочки (рисунок 4.26) с измерениями max a0 a1 A, A* - по горизонтали, max b0, b j1 B - по вертикали.

* Y A b(0) B b(1) * b j Y * a(0) a(1) a j Рис. 4.26. Четвртый шаг ступенчатого алгоритма 50. На конечном шаге осуществляем горизонтальный синтез оболочки A, B правого блока с последней гранью линейной полиэдрали левого блока a j, b j и вычисляем эвристическую меру получаемой ресурсной оболочки * * 1 (рисунок 4.27) с измерениями A A- по горизонтали, maxb0, B- по * 0 или до вертикали. Ступенчатый синтез продолжаем до получения эвристики исчерпания шагов алгоритма. Вариант с меньшей эвристической мерой считаем наилучшим.

Y b(0) b(1) * b j B Y * a(0) a(1) a j1 A Рис. 4.27. Конечный шаг ступенчатого алгоритма Отметим, что ресурсные оболочки, получаемые возвратным и ступенчатым алгоритмами идентичны.

Примером применения возвратного и ступенчатого алгоритмов выбираем массив j1 k j1 2, k 6 параграфа 4.2.

При определении центральной грани по среднему арифметическому высот ресурсных прямоугольников для линейной параболической полиэдрали k 1 k a j1, b j1 находим средний уровень b j b * и центральную грань j1, k j1 j1 ближайшую к точке достижения среднего уровня b j1 b 0. Алгоритмы с * таким способом определения центральной грани называем центральный возвратный и центральный ступенчатый.

Для линейной полиэдрали натуральных параболических ресурсных прямоугольников j1 k j1 2, k 6 имеем среднюю высоту b 11. Центральная грань j1 3. Оболочка граней j1 j1 правого блока приведена на рисунке 4.28.

* * 5 Рис. 4.28. Ресурсная оболочка граней правого блока Первую грань 1 25 суперпозируем с левой стороны правого блока и вершинно- диагонально синтезируем грани с j1 2, j1 3 в угловую область (рисунок 4.29).

5 1 Рис. 4.29. Ресурсная оболочка первого шага 1 6 25 25 2,43.

Вычисляем меру эвристики Возвращаем 2 105 вершинно- диагональный блок (грани 2 16, 3 9 ) в первоначальное положение.

Синтезируем с оболочкой правого блока первую и вторую грани 1 25, 2 16.

Вновь строим ресурсную оболочку (рисунок 4.30) и вычисляем меру эвристики 1 8 25 25 2,33.

2 105 Возвращаем вершинно- диагональный блок (грань 3 9 ) в первоначальное положение. Синтезируем с оболочкой правого блока первую, вторую и третью грани 1 25, 2 16, 3 9. Вновь строим ресурсную оболочку (рисунок 4.31) и 1 11 25 25 2,24.

вычисляем меру эвристики 2 105 25 16 3 5 1 4 1 2 4 2 Рис. 4.30. Ресурсная оболочка второго Рис. 4.31. Ресурсная оболочка третьего шага шага Видим, что более предпочтительным является третий шаг центрально уровневого алгоритма с меньшей эвристической мерой 2,24.

Эвристические меры ресурсных оболочек центрального (возвратного и ступенчатого) алгоритма для последовательности натуральных параболических ресурсных прямоугольников 1 k 12, 2 k 22,, k 11 приведены в таблице 4.7.

Таблица 4.7. Эвристические меры ресурсных оболочек центрального (возвратного и ступенчатого) алгоритма для натуральных параболических прямоугольников Эвристическая мера Эвристическая мера k k 6 2,24 11 3, 7 2,57 12 3, 8 2,76 13 3, 9 2,90 14 3, 10 3,15 15 3, При определении центральной грани по среднересурсной величине для k a j1, b j линейной параболической полиэдрали находим среднюю j1 k a j1 b j ресурсную величину H * и центральную грань j1, ближайшую к j1 точке достижения этого уровня b j1 H 0. Алгоритмы с таким способом * определения центральной грани называем среднересурсный возвратный и среднересурсный ступенчатый.

Для линейной полиэдрали натуральных параболических ресурсных прямоугольников j1 k j1 2, k 6 имеем среднюю ресурсную величину H 10.

Центральная грань j1 3. Оболочка граней j1 j1 правого блока приведена на * * рисунке 4.32.

9 3 Рис. 4.32. Ресурсная оболочка граней правого блока среднересурсного ступенчатого алгоритма На первом шаге вертикально суперпозируем эту ресурсную оболочку правого блока с гранью j1 2 (рисунок 4.33). Вычисляем эвристическую меру 1 9 25 25 2,29. На втором конечном получаемой ресурсной оболочки 2 105 шаге горизонтально суперпозируем ресурсную оболочку правого блока с гранью j1 2 - последней гранью линейной полиэдрали левого блока (рисунок 4.34) и 1 11 25 25 2,24.

вычисляем меру эвристики 2 105 9 3 9 1 2 3 1 Рис. 4.33. Ресурсная оболочка Рис. 4.34. Ресурсная оболочка второго первого шага среднересурсного шага среднересурсного ступенчатого ступенчатого алгоритма алгоритма Видим, что более предпочтительным является второй шаг среднересурсного ступенчатого алгоритма с меньшей эвристической мерой 2,24.

Эвристические меры ресурсных оболочек среднересурсного (возвратного и ступенчатого) алгоритма для последовательности натуральных параболических ресурсных прямоугольников 1 k 12, 2 k 22,, k 11 приведены в таблице 4.8.

Таблица 4.8. Эвристические меры ресурсных оболочек среднересурсного (возвратного и ступенчатого) алгоритма для натуральных параболических прямоугольников Эвристическая мера Эвристическая мера k k 6 2,24 11 3, 7 2,57 12 3, 8 2,76 13 3, 9 2,85 14 3, 10 3,04 15 3, При определении центральной грани балансным способом для линейной j1 * k a j1, b j1 находим протяжнность a j1 и L параболической полиэдрали j1 j1 * центральную грань j1, ближайшую к точке достижения этой величины b j1 L 0. Алгоритмы с таким способом определения центральной грани * называем балансный возвратный и балансный ступенчатый.

Для линейной полиэдрали натуральных параболических ресурсных прямоугольников j1 k j1 2, k 6 имеем протяжнность L 6 и центральную грань j1 4. Оболочка граней j1 j1 правого блока приведена на рисунке 4.35.

* * 4 Рис. 4.35. Ресурсная оболочка граней правого блока балансного ступенчатого алгоритма На первом шаге вертикально суперпозируем эту ресурсную оболочку правого блока с гранью j1 2 (рисунок 4.36). Вычисляем эвристическую меру 1 10 25 25 2,26. На втором шаге получаемой ресурсной оболочки 2 105 вертикально суперпозируем ресурсную оболочку правого блока с гранью j1 1 12 25 25 2,23.

(рисунок 4.37) и вычисляем меру эвристики 2 105 4 25 4 16 9 3 1 2 1 Рис. 4.36. Ресурсная оболочка Рис. 4.37. Ресурсная оболочка первого шага балансного второго шага балансного ступенчатого алгоритма ступенчатого алгоритма На третьем конечном шаге горизонтально суперпозируем ресурсную оболочку правого блока с гранью j1 3 - последней гранью линейной полиэдрали левого блока (рисунок 4.38) и вычисляем меру эвристики 1 15 25 25 2,26.

2 105 3 1 2 Рис. 4.38. Ресурсная оболочка третьего шага балансного ступенчатого алгоритма Видим, что более предпочтительным является второй шаг балансного ступенчатого алгоритма с меньшей эвристической мерой 2,23.

Эвристические меры ресурсных оболочек балансного (возвратного и ступенчатого) алгоритма для последовательности натуральных параболических ресурсных прямоугольников 1 k 12, 2 k 22,, k 11 приведены в таблице 4.9.

Таблица 4.9. Эвристические меры ресурсных оболочек балансного (возвратного и ступенчатого) алгоритма для натуральных параболических ресурсных прямоугольников Эвристическая мера Эвристическая мера k k 6 2,23 11 3, 7 2,49 12 3, 8 2,69 13 3, 9 2,92 14 3, 10 3,05 15 3, Графики эвристической меры ресурсных оболочек начально- уровневого и центрального, среднересурсного, балансного (возвратного и ступенчатого) полиномиальных алгоритмов диспетчирования линейными параболическими полиэдралями 1 k 12, 2 k 22,, k 1 1 показаны на рисунке 4.39.

Рис. 4.39. Эвристические меры ресурсных оболочек начально- уровневого, центрального, среднересурсного, балансного (возвратного и ступенчатого) алгоритмов для натуральных параболических ресурсных прямоугольников Видим, что центральный, среднересурсный и балансный (возвратный и ступенчатый) алгоритмы диспетчирования для натуральных параболических ресурсных прямоугольников имеют меньшую эвристическую меру ресурсных оболочек чем начально- уровневый алгоритм.

Другим примером применения возвратного и ступенчатого алгоритмов выбираем массив Ck j1 2k j1, k 4 параграфа 4.2. Для линейной полиэдрали параболических ресурсных прямоугольников Ck j1 2k j1, k 4, имеем среднюю 2k 1 1 25 1k b j1 k 1 5 6,2.

b j1 1.

* высоту Центральная грань k 1 j1 Уровневым алгоритмом для уровня b 6,2 формируем оболочку граней j1 j * правого блока (рисунок 4.40).

Y 0 6 Y Рис. 4.40. Ресурсная оболочка граней правого блока Начальную грань 1 16 суперпозируем с левой стороны правого блока и вершинно- диагонально синтезируем грань с j1 1 в угловую область (рисунок 1 8 16 16 1,19.

Вычисляем меру эвристики Возвращаем 4.41).

2 81 вершинно- диагональный блок (грань 4 8 ) в первоначальное положение.

Синтезируем с оболочкой правого блока начальную и первую грань 1 16, 4 8.

Вновь строим ресурсную оболочку (рисунок 4.42) и вычисляем меру эвристики 1 12 16 16 1,28.

2 81 Y2 Y 16 42 4 1 01 6 4 Y1 Y Рис. 4.41. Ресурсная оболочка Рис. 4.42. Ресурсная оболочка первого шага центрального второго шага центрального возвратного алгоритма возвратного алгоритма Видим, что более предпочтительным является вариант первого шага с левой суперпозицией начальной грани и вершинно- диагональным синтезом первой грани, как имеющий меньшую эвристическую меру 1,19.

Эвристические меры ресурсных оболочек центрального (возвратного и ступенчатого) алгоритма для последовательности параболических ресурсных прямоугольников Ck0 2k, Ck1 2k 1,, Ckk 1 21, 11 приведены в таблице 4.10.

Таблица 4.10. Эвристические меры ресурсных оболочек центрального (возвратного и ступенчатого) алгоритма для параболических прямоугольников Ck j1 2k j Эвристическая мера k 4 1, 5 1, 6 2, 7 2, 8 3, Для линейной полиэдрали параболических ресурсных прямоугольников Ck j1 2k j1, k 4, имеем среднюю ресурсную величину H 9. Центральная грань j1 1. Оболочка граней j1 j1 правого блока приведена на рисунке 4.43.


* * Y 0 4 6 Y Рис. 4.43. Ресурсная оболочка граней правого блока На первом шаге горизонтально суперпозируем эту ресурсную оболочку правого блока с гранью j1 0 - последней гранью линейной полиэдрали левого 1 11 16 16 1,24.

блока (рисунок 4.44) и вычисляем меру эвристики 2 81 Y 01 4 6 Y Рис. 4.44. Ресурсная оболочка среднересурсного ступенчатого алгоритма для Ck j1 2 k j1, k Эвристические меры ресурсных оболочек среднересурсного (возвратного и ступенчатого) алгоритма для последовательности параболических ресурсных прямоугольников Ck0 2k, Ck1 2k 1,, Ckk 1 21, 11 приведены в таблице 4.11.

Таблица 4.11 Эвристические меры ресурсных оболочек среднересурсного (возвратного и ступенчатого) алгоритма для параболических прямоугольников Ck j1 2k j Эвристическая мера k 4 1, 5 1, 6 2, 7 2, 8 3, Для линейной параболической полиэдрали ресурсных прямоугольников Ck j1 2k j1, k 4, имеем протяжнность L 5 и центральную грань j1 2.

* Оболочка граней j1 j1 правого блока приведена на рисунке 4.45.

* Y 0 6 4 Y Рис. 4.45. Ресурсная оболочка граней правого блока На первом шаге вертикально суперпозируем эту ресурсную оболочку правого блока с гранью j1 1 (рисунок 4.46). Вычисляем эвристическую меру 1 11 16 16 1,24. На втором шаге получаемой ресурсной оболочки 2 81 горизонтально суперпозируем ресурсную оболочку правого блока с гранью j1 2 - последней гранью линейной полиэдрали левого блока (рисунок 4.47) и 1 15 16 16 1,49.

вычисляем меру эвристики 2 81 Y Y 01 6 4 Y Y Рис. 4.47. Ресурсная оболочка второго Рис. 4.46. Ресурсная оболочка шага балансного ступенчатого алгоритма первого шага балансного ступенчатого алгоритма Видим, что более предпочтительным является первый шаг ступенчатого балансно- уровневого алгоритма с меньшей эвристической мерой 1,24.

Эвристические меры ресурсных оболочек балансного (возвратного и ступенчатого) алгоритма для последовательности параболических ресурсных прямоугольников Ck0 2k, Ck1 2k 1,, Ckk 1 21, 11 приведены в таблице 4.12.

Таблица 4.12. Эвристические меры ресурсных оболочек балансного (возвратного и ступенчатого) алгоритма для параболических прямоугольников Ck j1 2k j Эвристическая мера k 4 1, 5 1, 6 2, 7 2, 8 3, Графики эвристической меры ресурсных оболочек начально- уровневого, центрального, среднересурсного, балансного (возвратного и ступенчатого) полиномиальных алгоритмов диспетчирования линейными параболическими полиэдралями Ck0 2k, Ck1 2k 1,, Ckk 1 21, 11 показаны на рисунке 4.48.

Рис. 4.48. Эвристические меры ресурсных оболочек для параболических ресурсных прямоугольников Ck0 2 k, Ck1 2 k 1,, Ckk 1 21, Видим, что центральный, среднересурсный и балансный (возвратный и ступенчатый) алгоритмы диспетчирования для последовательности Ck0 2k, Ck1 2k 1,, параболических ресурсных прямоугольников Ckk 1 21, 11 имеют меньшую эвристическую меру ресурсных оболочек чем начально- уровневый алгоритм.

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

среднересурсной величины;

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

Показывается, что получаемые ресурсные оболочки в обоих локализациях совпадают. Для базовых примеров массивов заявок параболического типа с высокими гранями строятся объемлющие прямоугольники с вычислением эвристических мер. Приводится сравнительный анализ полиномиальных алгоритмов распределения процессорно- временных ресурсов для массивов заявок параболического типа. Делается вывод о целесообразности предложенных алгоритмов при диспетчеризации в Grid- системах.

4.4. Полиэдрали параболической однородности и монотонной составности Пусть имеется линейная параболическая полиэдраль из k 2m модулей ресурсных прямоугольников с идентичными координатными трапециями ресурсных оболочек транспонировано- симметричных модулей индексации i, k i (рисунок 4.49).

= i k i Рис. 4.49. Ресурсные оболочки транспонировано- симметричных модулей По совокупности указанных свойств k- модульная линейная параболическая полиэдраль ресурсных прямоугольников относится к однородно параболическому квадратичному типу [76].

Для полиэдрали однородно- параболического квадратичного типа применяем транспонированный синтез парных идентичных координатных трапеций- ресурсных оболочек параболических модулей (рисунок 4.50).

, Рис. 4.50. Транспонированный синтез ресурсных оболочек параболических модулей Полученные координатные блоки упорядочиваем в рамочную оболочку одним из указанных в главах 2, 3 способами.

Остановимся на моделях триодных ресурсных оболочек- трапециях и треугольниках. Для натуральных параболических ресурсных прямоугольников j1 k j1 2 локализацию строим в виде координатной трапеции с k k k j протяжнностью равной основаниями 1 и, j1 k 12 1 k k 1 k k 1 для k 1. При k 6 ресурсная оболочка имеет следующий вид (рисунок 4.51).

Y 4 Y Рис. 4.51. Ресурсная оболочка параболической линейной полиэдрали Параболической триодной полиэдралью представляем массив Ck j1 Ck 2j, 0 j1 j2 k в ближнем каноническом треугольнике. Локализацией j k Ck j1 2k, является координатная трапеция протяжнности равной j1 основаниями 1 и 2k 1 (рисунок 4.52).

Y k= Y k= 1 Y1 Y 1 3 1 2 Рис. 4.52. Ресурсная оболочка параболической триодной полиэдрали Вычислим триодную ресурсную оболочку параболического массива Ck j1 a j1 Ck 2j b j2, 0 j1 j2 k. С этой целью, установим быстрое убывание j k j Ck 2j b j2 b 1k j1, j1, j суммарных высот вертикальных слов H j1 j2 рассматриваемой совокупности ресурсных прямоугольников j j k j1 j j k Ck 1 a 1 Ck 2j1 b 2. Вычислим, далее, максимальный уровень j1 0 j2 H 0 b 1k и протяжнность горизонтального линейного полигона k Ck j1 a j1 a Lk k Таким образом, искомая ресурсная оболочка.

j1 1 в области Y1,Y2 ресурсных Y1 Y определяется неравенством 0 a 1k b 1k a 1, b 1, распределений. В модельном случае, имеем координатный треугольник с катетами 2 k (рисунок 4.53).

(b+1)k 2k 0 (a+1)k 2k Рис. 4.53. Триодные ресурсные оболочки параболических массивов Рассмотрим, далее, симметричные триодные ресурсные оболочки равнобедренные координатные прямоугольные треугольники (рисунок 4.54) по отношению к массиву триодной полиэдрали в каноническом треугольнике.

H(0) k 0 k L(k) = H(0) Рис. 4.54. Симметричные триодные ресурсные оболочки В условиях быстрого убывания суммарных высот вертикальных слов совокупности ресурсных прямоугольников ресурсных элементов H j1 b j1, j2, j1, и равенства максимальных величин уровня и j k протяжнности H 0 b0, j2 a j1 Lk имеем объемлющий графику j1 j треугольник ресурсной области 0 Y1 Y2 Lk H 0.

Введм, далее, понятие параболической монотонной составности. Пусть k модульная линейная полиэдраль ресурсных прямоугольников состоит из модулей параболического типа с ресурсными оболочками в виде координатных трапеций.

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

Правый фактор подвергаем инверсии изменения ориентации по вертикали и суперпозируем с левым фактором по линии основания одинаковой протяжнности с указанной выше точностью расположения ближайшей грани к линии факторизации модуля (рисунок 4.55).

линия инверсного синтеза Рис.4.55. Центрально- инверсный синтез факторов параболической ресурсной оболочки Образованные k блоков центрального инверсного синтеза первоначальных оболочек- трапеций принимаем в качестве линейной полиэдрали координатных граней- оболочек блоков (рисунок 4.56).

Рис. 4.56. Оболочка блока инверсного синтеза Свойство упорядоченности линейной полиэдрали вновь образованных граней по вложению определяет искомую монотонную параболическую составность k- модульной линейной полиэдрали в указанных условиях.

Прикладное значение выделенного класса параболической монотонности состоит в возможности начально- кольцевого синтеза оболочек на второй стадии локализации протяжнного массива ресурсных прямоугольников.

Таким образом, в настоящем параграфе идентичность триодных ресурсных оболочек пар инверсно- индексированных модулей линейной полиэдрали k модульной составности параболической квадратичной типизации принимается в качестве свойства однородности последней. Указывается синтез идентичных координатных трапеций в прямоугольную ресурсную оболочку. Приводится рамочная локализация массива оболочек синтеза парно- идентичных трапеций.

Алгоритм однородно- параболической локализации иллюстрируется на линейной полиэдрали натуральных параболических прямоугольников и бисочетательной триодной полиэдрали в качестве базовой параболической модели. Приводится обобщение модельного результата на составной бисочетательный массив.

Вводится понятие монотонной параболичности модульной линейной k полиэдрали и строится локализация центрально- инверсного синтеза оболочек.

4.5. Синтез ресурсных оболочек Рассмотрим парный синтез канонических ресурсных оболочек модельных элементов параболического и кругового квадратичных типов посредством вершинно- диагональной суперпозиции канонического квадрата в угловую область канонического ближнего треугольника с вершиной в качестве точки k k, центрального среднего уровня вертикалей треугольника, k 2m - чтное 2 число (рисунок 4.57).


k k k k/2 k, k k/ k Рис. 4.57. Парный синтез ресурсных оболочек параболического и кругового типов Построенная координатная ресурсная оболочка имеет измерения k k k k k k k k k k 1 2 2 k k и меру эвристики 2 2 2 k2 k k2 k 2 k 1 4 0,75 на 0,25 выше идеальной величины. Заметим, что 2 3 k2 горизонтальный и вертикальный синтез указанных выше канонических ресурсных 2k 2 k 2 1 3k 1 на 0,25 выше меры оболочек дат эвристическую меру 2 3 k 2 k 2 k предыдущего синтеза (рисунок 4.58).

k k k k k, k k k Рис. 4.58. Горизонтальный и вертикальный синтез ресурсных оболочек параболического и кругового типов Треугольник и квадрат служат вырожденными случаями по отношению к общим ресурсным трапециям с линейно- уровневой хордой и средним уровнем вертикалей в качестве определения центрально- угловой вершины угловой области. Вслед за парным синтезом модельных граней произведм синтез ресурсной линейно- уровневой трапеции и ресурсного прямоугольника (рисунок 4.59) по критерию эвристической меры.

угловая область b, a Рис. 4.59. Угловая область центрально- уровневой вершины С этой целью, находим центрально- уровневую точку на хорде трапеции как среднее высот, содержащихся в ней граней, и осуществляем вершинно диагональный синтез прямоугольной грани в угловую область центрально уровневой вершины (рисунок 4.60).

b a Рис. 4.60. Вершинно- диагональный синтез Ресурсная оболочка данной совокупности ресурсных прямоугольников образует решение задачи парного синтеза трапеции и прямоугольника. Измерения оболочки равны a b, согласно построениям рисунка 4.60.

Проиллюстрируем алгоритм вершинно- диагональной суперпозиции в угловую область с вершиной в качестве точки центрального среднего уровня.

Рассмотрим синтез параболической (рисунок 4.61) и круговой с ресурсными прямоугольниками горизонтальной формы (рисунок 4.62) линейных полиэдралей.

Y Y 4 3 0 0 5 1 6 Y Y Рис. 4.62. Ресурсные прямоугольники Рис. 4.61. Ресурсные прямоугольники кругового типа параболического типа Для линейной параболической полиэдрали строим ресурсную оболочку в виде координатной уровневой трапеции и находим средний уровень равный 9 (рисунок 4.63). Для ресурсных прямоугольников линейной круговой полиэдрали строим ресурсную оболочку начально- кольцевым алгоритмом параграфа 2.2 (рисунок 4.64).

Y Y 01 4 6 0 5 Y Y Рис. 4.64. Ресурсная оболочка круговых Рис. 4.63. Ресурсная оболочка граней параболических граней Вершинно- диагонально суперпозируем ресурсную оболочку в угловую область с вершиной в качестве точки центрального среднего уровня ресурсной трапеции (рисунок 4.65).

Y 01 4 6 Y Рис. 4.65. Синтез круговой и параболической ресурсных оболочек Получаем ресурсную оболочку с эвристической мерой 1 16 17 17 1,39.

(4.1) 2 98 Рассмотрим следующий синтез параболической (рисунок 4.66) и круговой (рисунок 4.67), с ресурсными прямоугольниками вертикальной формы, линейных полиэдралей.

Y Y 9 8 7 6 5 4 0 6 5 4 3 Y1 Y Рис. 4.66. Ресурсные Рис. 4.67. Ресурсные прямоугольники прямоугольники кругового типа параболического типа Для линейной параболической полиэдрали строим ресурсную оболочку в виде координатной уровневой трапеции и находим средний уровень равный 17 (рисунок 4.68). Для линейной круговой полиэдрали строим ресурсную оболочку начально- кольцевым алгоритмом параграфа 2.2 (рисунок 4.69).

Y 2 Y 6 5 4 3 9 8 6 5 Y Y Рис. 4.68. Ресурсная трапеция Рис. 4.69. Круговая ресурсная оболочка Вершинно- диагонально суперпозируем ресурсную оболочку в угловую область с вершиной в качестве точки центрального среднего уровня ресурсной трапеции (рисунок 4.70).

Y 6 5 4 3 8 6 Y Рис. 4.70. Синтез круговой и параболической ресурсных оболочек Получаем ресурсную оболочку с эвристической мерой 1 15 31 31 1,66.

(4.2) 2 217 Рассмотрим способ синтеза тех же параболической (рисунок 4.61) и круговой (рисунок 4.62) линейных полиэдралей с использованием ступенчатого алгоритма параграфа 4.3. Линейная параболическая полиэдраль ресурсных прямоугольников бертся в первоначальном виде, а круговая- локализуется начально- кольцевым алгоритмом в ресурсную оболочку с измерениями 9 3, как и выше (рисунок 4.64). Осуществим вертикальный синтез с первой гранью (рисунок 4.71) с определением эвристической меры полученной ресурсной 1 1116 16 1,03. Затем осуществляем вертикальный синтез оболочки 2 98 со второй гранью (рисунок 4.72), определяя эвристическую меру полученной 1 14 16 16 1,16.

ресурсной оболочки Наконец, осуществляем 2 98 горизонтальный синтез с последней второй гранью (рисунок 4.73) и вычисляем эвристическую меру полученной ресурсной оболочки 1 20 16 20 1,71.

2 98 Y2 Y Y 16 8 4 0 0 1 6 1 1 6 Y Y1 Y Рис. 4.72. Второй шаг Рис. 4.71. Первый Рис. 4.73. Третий шаг ступенчатого шаг ступенчатого ступенчатого алгоритма алгоритма алгоритма Вариант с меньшей эвристической мерой считаем наилучшим. В приведнном примере наиболее предпочтительным является распределение ресурсов первого шага. Видим, что эвристическая мера ресурсной оболочки синтеза полиэдралей ступенчатым алгоритмом со значением 1,03 лучше, чем алгоритмом вершинно- диагональной суперпозиции со значением 1,39 (4.1).

Рассмотрим способ синтеза указанных выше параболической (рисунок 4.66) и круговой (рисунок 4.67), с ресурсными прямоугольниками вертикальной формы, линейных полиэдралей с использованием ступенчатого алгоритма параграфа 4.3. Шаги алгоритма с соответствующими эвристическими мерами, равными 1,58 (для первого шага);

1,09 (для второго шага);

1,13 (для третьего шага) приведены на рисунках 4.74-4.76.

Y Y Y 25 16 9 0 12 3 Y1 12 3 Y1 12 3 11 Y Рис. 4.76. Третий шаг Рис. 4.74. Первый шаг Рис. 4.75. Второй шаг В рассмотренном примере диспетчеризация на втором шаге дат наименьшую эвристическую меру. Видим, что эвристическая мера ресурсной оболочки синтеза полиэдралей ступенчатым алгоритмом 1,09 лучше, чем алгоритмом вершинно- диагональной суперпозиции 1,66 (4.2). Проведнное исследование свидетельствует о целесообразности использования предложенного ступенчатого алгоритма при синтезе ресурсных оболочек.

Фундаментальное различие прямоугольности и триодности форм ресурсных оболочек линейных полиэдралей граней по критерию ресурсной меры в зависимости от квадратичной типизации локализуемого массива полагается в основу мотивации метода редукции треугольного планарного полиэдра к прямоугольной ресурсной области.

В отличие от кругового или гиперболического массива линейной полиэдрали ресурсных прямоугольников, обладающих прямоугольной ресурсной оболочкой по критерию ресурсной меры, параболическая линейная полиэдраль имеет триодную ресурсную оболочку по указанному критерию. Ресурсная рамка M M ресурсной области представляется в качестве оболочки первого типа, индуцируя проблему редукции триодных ресурсных оболочек параболической локализации к прямоугольным ресурсным оболочкам.

Укажем основные положения упомянутой редукции на модели канонической области двойной индексации- ближнего канонического треугольника. Метод уровневой факторизации с последующим транспонированием одного из факторов в инверсное положение с целью синтеза прямоугольной координатной области состоит в выделении квадрата k k 0 j1, 0 j2 в ближнем каноническом треугольнике 0 j1 j2 k 2 (рисунок 4.77).

k k/ 0 k/2 k Рис. 4.77. Выделение квадрата в поле двойной индексации Дополнительные треугольники перераспределяются инверсией верхнего к нижнему с синтезом вдоль гипотенузы последнего при редукции к горизонтальной оболочке (рисунок 4.78) и инверсией нижнего треугольника к верхнему с аналогичным синтезом- при редукции к вертикальной оболочке (рисунок 4.79).

k k/ k/ k Рис. 4.79. Синтез вертикальной Рис. 4.78. Синтез горизонтальной оболочки оболочки Необходимо заметить, что при данном преобразовании области двойной индексации область ресурсных распределений также преобразуется j1, j2 Y1,Y2. Например, параболическую триодную полиэдраль Ck j1 Ck 2j, j1 0, k Z 1, j2 0, k j1 Z 1, j синтезируем в вертикальную k Ck j1 1 2k, посредством вертикальной суперпозиции (рисунок 4.80) полосу j1 [75].

Y 1 01 3 3 1 Y Рис. 4.80. Параболическая триодная полиэдраль С этой целью, вертикальные слои первой части массива k 2 k j j Ck 2j, j, Y2 j Ck 0 Y1 дополним транспонированными слоями j1 0 j2 k второй части массива j1 k j1, j1 0, Z 1, суперпозируя последние 2k 1.

вертикально вниз от общего уровня Оценка k 2k j1 2 j1 2k 1, j1 0, Z 1 суммы первоначального и k j1 j j C j j2, показывает, что k j Ck j, 2 j транспонированного слов 1 j2 0 j2 данные слои суперпозируются аддитивно с возможными пустотами. В итоге, k Ck j1, получаем ресурсную оболочку 0 Y1 0 Y2 2k 1 (рисунок 4.81).

j1 Y Y2 1 ** * 1 1 ** 3 1 3 2 1 ** 1 1 ** * 01 3 3 1 Y1 Y Рис. 4.81. Метод уровневой факторизации при k= Таким образом, в настоящем параграфе вводится парный синтез канонических ресурсных оболочек модельных элементов на основе угловой вершинно- диагональной суперпозиции параболического и кругового массивов.

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

4.6. Выводы 1. Предложены, разработаны и исследованы полиномиальные алгоритмы диспетчирования, адаптированные к массивам заявок параболического квадратичного типа.

2. Приведена статистика сравнения с оптимальным алгоритмом, показывающая преимущества предложенного полиномиального алгоритма при учте качества заполнения ресурсной оболочки в сопоставлении с затрачиваемым временем на диспетчирование.

3. Проведн сравнительный анализ разработанных полиномиальных алгоритмов диспетчирования линейными параболическими полиэдралями: среднересурсного уровневого, начально- уровневого, возвратного и ступенчатого.

Глава 5. Анализ взаимодействия сторон компьютерного обслуживания 5.1. Аддитивная, ординарная, дополняемая формы базисного задания комбинаторного эксперимента Основная модель среды диспетчирования введена в главе 1 в качестве предмета динамического исчисления линейных полиэдралей при решении задачи диспетчирования множественным компьютерным обслуживанием. Наряду с внутренней проблематикой оптимальных действий системы обслуживания, анализу подлежит внешняя сторона взаимодействия Grid- системы и множества пользователей вычислительным ресурсом системы. Указанное взаимодействие составляет эксперимент спроса- предложения, подлежащий формальному определению [100-119,121,122,126,127]. Комбинаторный эксперимент является категорией. Определению подлежат базисные формы комбинаторного эксперимента.

Во множестве X всевозможных исходов эксперимента выделяем базис X i ik1 и меру P.

P X P X i ik 1 P X i, Если то элементарные подмножества i X i, i 1, 2,, k считаем аддитивным базисом по Байесу комбинаторного эксперимента: X \ X i ik 1, P 0. Здесь X- достоверный, - пустой, негативный исход.

Если подмножество X i ik 1 образует систему Даламбера, так что PX i X j P X i ik 1 P X i P X 1 X 2 X k, k i i j X \ X i ik 1 X co, то при P X co 0 система X i ik 1 называется ординарным базисом эксперимента X, а при P X co 0 - дополняемым базисом эксперимента X.

Данная классификация базисов комбинаторного эксперимента отвечает Z 1, Z 2 - распределений: круговому, трм основным квадратичным типам гиперболическому, параболическому, соответственно.

Обратимся к более детальным рассмотрениям. Модельным комбинаторным экспериментом считаем канонический линейный полигон в области k распределений (рисунок 5.1) с алгебраизацией единичных сдвигов S1j1 и j1 правильный гармонический полигон в области изображений (рисунок 5.2) с k, W1 exp i алгеброй поворотов Эйлера W1 j1.

j1 k k k W1 j S1j... j1 j1 0 k 1 Рис. 5.1. Канонический линейный Рис. 5.2. Правильный полигон в области распределений, гармонический полигон в области прообраз изображений, образ Канонический линейный полигон содержит единичные звенья- измерения в 0,1 Z 1, качестве базисных исходов, начальное звено представляющее негативный исход j1 0 (рисунок 5.3).

позитивные негативный исходы исход... k-1 k 1 Рис. 5.3. Комбинаторный эксперимент канонического линейного полигона Радиально- лучевое представление эксперимента правильного гармонического полигона имеет множество вершин единичной окружности в качестве базисных исходов, начальную вершину W10, отвечающую негативному исходу j1 0 (рисунок 5.4).

негативный исход позитивные W исходы Рис. 5.4. Радиально- лучевое представление эксперимента гармонического полигона Дуальное хордо- звенное представление эксперимента правильного гармонического полигона имеет множество хорд- звеньев правильного гармонического полигона в качестве базисных исходов, начальную хорду W, отвечающую негативному исходу 1 W1 j1 0 (рисунок 5.5).

1 W11 негативный исход позитивные W исходы Рис. 5.5. Хордо- звенное представление эксперимента гармонического полигона Z 1 - разностей 1- го порядка Хордо- звенной форме гармонических k 1 S1 1, 1W1 j1 W1k W10 0 сопоставляем кратные разности j1 2 S1 12,, k S1 1k W в действии на начальный отсчт 1 гармонического распределения W1 j1 и получаем эксперимент хорд Ньютона кратных порядков в качестве ординарной формы предыдущего хордо- звенного эксперимента (рисунок 5.6). Объемлющим исходом здесь служит вс множество кратных хорд, негативный исход представляется хордой нулевого порядка 0 начальной вершиной W10, отвечающей негативному исходу j1 0.

1 2 1,,, Рис. 5.6. Эксперимент хорд Ньютона кратных порядков Переход от эксперимента кратных хорд к радиально- лучевому распределению вершин полигона датся формулой Ньютона k S1 1 1 11 S1 1 j1, в действии на начальный отсчт W10.

Ck( j1 ) 11, k j j S1k j1 Полученную пару производящих форм принимаем в качестве производящего k Ck( j1 ) 11 f j аддитивного (см. формулу (1.1)) и ординарного j1 k 1 Ck j1 ) S1j1 f 0 (см. формулу (1.2)) представления комбинаторного k j1 ( j1 эксперимента. Здесь f 0 - начальный отсчт распределения со свойством k циклической замкнутости k f j1 k f j1, f j1 0. (5.1) j1 Последнее свойство побуждает к циклическому представлению канонического линейного полигона (рисунок 5.7) и определению класса комбинаторных экспериментов с аддитивной формой множества отсчтов f j1 kj1 0 и ординарной формой множества кратных разностей 11 f 0j1 0.

k j Рис. 5.7. Циклическое представление канонического линейного полигона Эквивалентность данных представлений обеспечивается точностью формы f Z 1 k и свойствами операторной алгебры сдвигов S1 над классом Z 1 k.

Производящее представление дополняемого базисного типа датся k j1 k S j k j выражением (см. формулу (1.3)).

k!

j1 Таким образом, в настоящем параграфе вводятся канонический линейный и правильный гармонический полигоны в качестве основополагающих комбинаторных экспериментов с алгебраизацией единичных сдвигов Z 1 - среды и поворотов Эйлера в среде изображений. Определяются радиально- лучевая и хордо- звенная форма Фурье- изображений распределений в каноническом линейном полигоне. Вводятся кратные хорды правильного гармонического полигона и кратные разности Ньютона. На данной основе строится исчисление разностей по Ньютону, кратные производящие формы сдвигов в циклической версии линейного полигона и определяются аддитивная, ординарная и дополняемая формы базисного задания комбинаторных экспериментов.

5.2. Усечение круговых, гиперболических и параболических моделей Определим понятие усечения полного комбинаторного эксперимента как j1 0, множества позитивных переход от одиночного негативного исхода исходов j1 1, k в полном комбинаторном эксперименте, к новому негативному исходу j1 L, прямой части усечения j1 0, L 1 и инверсной части усечения j1 L 1, k в усечении полного комбинаторного эксперимента.

Усечнный эксперимент канонического линейного полигона с новым негативным исходом j1 L, прямой частью усечения j1 0, L 1 и инверсной частью усечения j1 L 1, k изображн на рисунке 5.8.

новый прямая часть негативный инверсная часть усечения усечения исход L L+1 L+2... k-1 k 2... L- Рис. 5.8. Усечнный эксперимент канонического линейного полигона Усечнный эксперимент радиально- лучевого представления правильного гармонического полигона с новым негативным исходом W1L, прямой частью L 1 k и инверсной частью усечения W1 j усечения W1 j1 изображн на j1 0 j1 L рисунке 5.9.

новый прямая часть усечения негативный исход W1L инверсная часть усечения Рис. 5.9. Усечнный эксперимент радиально- лучевого представления гармонического полигона Усечнный эксперимент хордо- звенного представления правильного гармонического полигона с новым негативным исходом W1L W1L 1, прямой L 1 k 1W1 j1 и инверсной частью усечения 1W1 j частью усечения изображн на j1 0 j1 L рисунке 5.10.

прямая часть усечения новый W1L негативный исход W1L инверсная часть усечения Рис. 5.10. Усечнный эксперимент хордо- звенного представления гармонического полигона По отношению к общим комбинаторным экспериментам определение усечения датся в начале для класса точных форм- распределений циклической Z 1 k.

замкнутости Для распределений циклической замкнутости (5.1) основополагающее модельное соотношение усечения (рисунок 5.9) обобщается L 1 k f j1 f j1 f L, циклическим каноническим соотношением j1 0 j1 L вытекающим из аннулирования полного Z 1 - интеграла точной формы (5.1). Здесь первая сумма символизирует прямую часть усечения, вторая сумма- инверсную часть усечения- с относительными ориентированными мощностями 1 L 1 1 k f j1, f j1 слагаемыми единичной суммы f L j1 0 f L j1 L f L 1 L 1 1 k 1 f j1 f j1 f L f j1 f L 1.

f L j1 0 f L j1 L 1 j1 L В качестве модельного примера выбираем ординарное гармоническое распределение W1 j1 Z 1 k и получаем каноническое соотношение усечения L 1 k 1 L 1 k j1 L W1 j1 L, W1 W1 W W1L с относительными мощностями j1 j, j1 0 j1 L 1 j1 0 j1 L k 1 k j1 L j1 L 1 W1 L W1 W1 W1 j1 1 1.

в сумме составляющими 1:

j1 L j1 0 j1 Усечение распределений с циклической замкнутостью обобщаем на k a j1 W1 j1 0.

распределения с гармонической замкнутостью a j1 k a j1, j1 k a j1 J k a j1 Z 1, то Если - круговая первообразная распределения j1 каноническое соотношение усечения принимаем в форме L 1 k a j1 a j1 J k aL, первую сумму считаем прямой, вторую- инверсной j1 0 j1 L частью усечения с относительными мощностями L 1 k a j1, J aL a j1 - слагаемыми единичной суммы.

1 J k aL j1 0 j1 L k В общем классе k- циклических распределений данные выше выражения прямой и инверсной частей усечения комбинаторного эксперимента становятся чисто символическими величинами, поскольку требуют пересчта своих слагаемых даже при известном значении суммы как символа. Перейдм к решению данной задачи.

Основные факторы k- кратных первообразных трх квадратичных типов k - j1 k, j 1 j1 j выходят за пределы класса точных и класса Ck, k!

k 1 1 Ck j1 W1 j1 0, C k C 0, j гармонически замкнутых распределений а k k j1 1 2k kk k k 1k, параболическое, пирамидальное распределение,,, k! k! k! k ! k!

выходит также и за пределы класса циклических распределений.



Pages:     | 1 | 2 || 4 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.