Статья

Название статьи О КАЧЕСТВЕ ДИСПЕТЧЕРИЗАЦИИ ЛИНЕЙНЫХ ПОЛИЭДРАЛЕЙ ТОЧНЫХ ФОРМ
Автор А.Э. Саак, В.В. Курейчик
Рубрика РАЗДЕЛ I. МОДЕЛИРОВАНИЕ И ПРОЕКТИРОВАНИЕ
Месяц, год 04, 2015
Индекс УДК 004.272.43
DOI
Аннотация Для управления распределением вычислительно-временных ресурсов Grid-систем в качестве теоретической основы алгоритмического обеспечения диспетчирования с полиномиальной трудоемкостью определена среда ресурсных прямоугольников, в которой массивы заявок пользователей классифицируются на круговой, гиперболический и параболический квадратичные типы. Рассматриваются Grid-системы централизованной архитектуры с мульти-сайтным диспетчированием. Для оценки качества диспетчирования эвристических алгоритмов используется неэвклидова эвристическая мера, учитывающая как площадь, так и форму занятой ресурсной области. Возможный минимум эвристической меры достигается при укладке в квадратную оболочку, не содержащую пустот. Адаптированность эвристических полиномиальных алгоритмов была показана для кругового типа линейных полиэдралей, оптимальная укладка которых в минимальный объемлющий квадрат содержала пустоты. Определяются линейные полиэдрали ресурсных прямоугольников, для которых существует квадратная ресурсная оболочка, не имеющая пустот, называемые линейными полиэдралями точной формы и расширяется понятие кругового типа линейных полиэдралей. Цель работы исследовать адаптированность полиномиальных алгоритмов для класса линейных полиэдралей с безпустотной квадратной ресурсной оболочкой. Анализируются линейные полиэдрали, индуцированные элементами совершенного квадрирования квадрата. Минимальный порядок совершенного простого и совершенного составного квадрирования квадрата индуцирует две линейные полиэдрали, минимальный размер квадрата совершенного простого квадрирования индуцирует три линейные полиэдрали. Для указанных линейных полиэдралей проводится диспетчирование и вычисляются эвристические меры ресурсных оболочек начально-кольцевого, уровневого, углового уровневого и алгоритма последовательных приближений. Показывается сохранение свойства адаптированности исследуемых полиномиальных алгоритмов для линейных полиэдралей точных форм кругового типа.

Скачать в PDF

Ключевые слова Линейные полиэдрали точных форм; линейные полиэдрали кругового типа; Grid-система; диспетчирование; неэвклидова эвристическая мера; полиномиальная трудоёмкость алгоритма; квадрирование квадрата; начально-кольцевой алгоритм; уровневый алгоритм; угловой уровневый алгоритм; алгоритм последовательных приближений.
Библиографический список 1. Саак А.Э. Локально-оптимальные ресурсные распределения // Информационные технологии. – 2011. – № 2. – С. 28-34.
2. Саак А.Э. Алгоритмы диспетчеризации в Grid-системах на основе квадратичной типизации массивов заявок // Информационные технологии. – 2011. – № 11. – С. 9-13.
3. Саак А.Э. Диспетчеризация в Grid-системах на основе однородной квадратичной типизации массивов заявок пользователей // Информационные технологии. – 2012. – № 4. – С. 32-36.
4. Саак А.Э. Полиномиальные алгоритмы распределения ресурсов в Grid-системах на основе квадратичной типизации массивов заявок // Информационные технологии. – 2013. – № 7. Приложение. – 32 с.
5. Magoulиs F., Nguyen T., Yu L. (2009). Grid resource management: toward virtual and services compliant grid computing, Numerical analysis and scientific computing. CRC Press, UK.
6. Magoulиs F. (ed.). (2010) Fundamentals of grid computing: theory, algorithms and technologies, Numerical analysis and scientific computing. CRC Press, UK.
7. Antonopoulos N., Exarchakos G., Li M., Liotta A. (eds.). (2010). Handbook of research on p2p and grid systems for service-oriented computing: models, methodologies and applications. IGI Global publisher, USA.
8. Li M., Baker M. (2005). The grid: core technologies. John Wiley & Sons Ltd, England.
9. Hamscher V., Schwiegelshohn U., Streit A., Yahyapour R. Evaluation of job-scheduling strategies for grid computing // In Proceedings of the 7th International Conference on High Performance Computing, HiPC-2000. Vol. 1971 of Lecture Notes in Computer Science, Indiа, Springer, 2000. – P. 191-202.
10. Rahman M., Ranjan R., Buyya R., Benatallah B. A taxonomy and survey on autonomic management of applications in grid computing environments // Concurrency Computat.: Pract. Exper. – 2011. – No. 23. – P. 1990-2019.
11. Krauter K., Buyya R., Maheswaran M. A taxonomy and survey of Grid resource management systems for distributed computing // Softw. Pract. Exper. – 2002. – Vol. 32, No. 2. – P. 135-164.
12. Iosup A., Epema D. H. J., Tannenbaum T., Farrellee M., Livny M. Inter-operating Grids through delegated matchmaking // In 2007 ACM/IEEE Conference on Supercomputing (SC 2007). – New York: ACM Press, 2007. – P. 1-12.
13. Patel S. Survey Report of Job Scheduler on Grids // International Journal of Emerging Research in Management &Technology. – 2013. – Vol. 2, No. 4. – P. 115-125.
14. Assunзгo M., Buyya R. Architectural elements of resource sharing networks. In Li K., Hsu C., Yang L., Dongarra J., Zima H. (eds.) // Handbook of research on scalable computing technologies. – 2010. – Vol. 2. – P. 517-550.
15. Netto M., Buyya R. Resource Co-allocation in Grid Computing Environments. In Antonopoulos, N., Exarchakos G., Li,M., Liotta A. (eds.) // Handbook of research on p2p and grid systems for service-oriented computing: models, methodologies and applications. – IGI Global publisher, 2010. – Vol. 1. – P. 476-494.
16. Саак А.Э. Управление ресурсами и заявками пользователей в Grid-системах с централизованной архитектурой // Труды ХII Всероссийского совещания по проблемам управления ВСПУ-2014. Москва, 16-19 июня 2014 г. – М.: Институт проблем управления им. В.А. Трапезникова РАН, 2014. – С. 7489-7498.
17. Саак А.Э. Сравнительный анализ полиномиальных алгоритмов диспетчеризации в Grid-системах // Информационные технологии. – 2012. – № 9. – С. 28-32.
18. Korf R. Optimal rectangle packing: New results // In Proceedings of the fourteenth international conference on automated planning and scheduling (ICAPS 2004). Whistler, British Columbia, Canada, June 3-7, 2004. – P. 142-149.
19. Korf R., Moffitt M., Pollack M. Optimal rectangle packing // Annals of Operations Research. – 2010. – Vol. 179, No.1. – P. 261-295.
20. Caramia M., Giordani S., Iovanella A. Grid scheduling by on-line rectangle packing // Networks. – 2004. – Vol. 44, No. 2. – P. 106-119.
21. Duijvestijn A.J.W. Simple perfect squared square of lowest order // J. Combin. Theory. – 1978. Ser. B. – No. 25. – P. 240-243.
22. Duijvestijn A.J.W., Federico P.J., Leeuw P. Compound perfect squares. Amer. Math. Monthly. – 1982. – No.89. – P. 15-32.
23. Gambini I. A method for cutting squares into distinct squares // Discrete Applied Math. – 1999. – No. 98. – P. 65-80.

Comments are closed.