Статья

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

Скачать в PDF

Ключевые слова Операция динамического интегрирования ресурсных прямоугольников по вертикали с превышением; операция динамического интегрирования ресурсных прямоугольников по вертикали с минимальным отклонением; Grid-система; централизованная структура системы диспетчирования; мульти-сайтный режим обслуживания; неэвклидова эвристическая мера; массив заявок кругового типа; алгоритм полиномиальной трудоёмкости; уровневый с избытком алгоритм; волновой уровневый алгоритм.
Библиографический список 1. Саак А.Э. Локально-оптимальные ресурсные распределения // Информационные технологии. – 2011. – № 2. – С. 28-34.
2. Саак А.Э. Алгоритмы диспетчеризации в Grid-системах на основе квадратичной типизации массивов заявок // Информационные технологии. – 2011. – № 11. – С. 9-13.
3. Саак А.Э. Диспетчеризация в Grid-системах на основе однородной квадратичной типизации массивов заявок пользователей // Информационные технологии. – 2012. – № 4. – С. 32-36.
4. Саак А.Э. Сравнительный анализ полиномиальных алгоритмов диспетчеризации в Grid-системах // Информационные технологии. – 2012. – № 9. – С. 28-32.
5. Саак А.Э. Полиномиальные алгоритмы распределения ресурсов в Grid-системах на основе квадратичной типизации массивов заявок // Информационные технологии. – 2013. – № 7. Приложение. – 32 с.
6. 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, volume 1971 of Lecture Notes in Computer Science, pages 191–202, Indiа, 2000. Springer.
7. Magoulиs, F., Nguyen, T., Yu, L. Grid resource management: toward virtual and services compliant grid computing, Numerical analysis and scientific computing. CRC Press, UK, 2009.
8. Magoulиs F. (ed.). Fundamentals of grid computing: theory, algorithms and technologies, Numerical analysis and scientific computing. CRC Press, UK, 2010.
9. 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, USA, 2010.
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. 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.
12. Саак А.Э. Управление ресурсами и заявками пользователей в Grid-системах с централизованной архитектурой // Труды ХII Всероссийского совещания по проблемам управления ВСПУ-2014. Москва, 16-19 июня 2014 г. – М.: Институт проблем управления им. В.А. Трапезникова РАН, 2014. – С. 7489-7498.
13. Foster I., Kesselman C. The Grid in a nutshell. In: Nabrzyski J., Schopf J., Weglarz J. (eds.) Grid Resource Management: state of the art and future trends. Kluwer, 2003.
14. Jacob B., Brown M., Fukui K., Trivedi N. (2005) Introduction to grid computing. IBM Corp., USA.
15. Christodoulopoulos, K., Sourlas, V., Mpakolas, I., Varvarigos, E. A comparison of centralized and distributed meta-scheduling architectures for computation and communication tasks in Grid networks // Computer Communications. – 2009. – No. 32. – P. 1172-1184.
16. Feitelson, D., Rudolph, L. Toward convergence in job schedulers for parallel supercomputers. In Job Scheduling Strategies for Parallel Processing, Feitelson D., Rudolph L. (eds.). – Spring-er-Verlag, 1996. Lecture Notes in Computer Science. – Vol. 1162. – P. 1-26.
17. Ye D., Zhang G. On-Line Scheduling of Parallel Jobs. In R. Krбlovič and O. Sэkora, ed., SIROCCO 2004. – Vol. LNCS 3104. – P. 279-290.
18. Caramia M., Giordani S., Iovanella A. Grid scheduling by on-line rectangle packing // Networks. – 2004. – Vol. 44, No. 2. – P. 106-119.
19. Korf R., Moffitt M., Pollack, M. Optimal rectangle packing // Annals of Operations Research. – 2010. – Volume 179, Number 1. – P. 261-295.
20. Huang E., Korf R. Optimal rectangle packing: an absolute placement approach // Journal of Artificial Intelligence Research. – 2012. – No. 46. – P. 47-87.

Comments are closed.