Повышение эффективности кластерных систем обработки информации при решении оптимизационных задач: на примере задачи составления расписания занятий тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Милехина, Татьяна Викторовна

• Милехина, Татьяна Викторовна
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Милехина, Татьяна Викторовна

Введение.

Глава 1. Методы решения задач многокритериальной оптимизации.

1.1 Метод моделирования отжига (Simulated Annealing).

1.2 Генетические алгоритмы (Genetic Algorithms).

1.3 Табуированный поиск (Tabu Search).

1.4 Метод роящихся частиц (Particle Swann).

1.5 Алгоритм раскраски графа (Graph Coloring Algorithm).

1.6 Метод муравьиных колоний (Ant Colony Algorithm).

1.7 Метод пчелиной колонии (Bees Colony Algorithm).

1.8 Линейная свертка. Линейное целочисленное программирование. (Linear convolution. Linear integer programming).

1.9 Существующие подходы к решению задачи составления расписания.

1.10 Выводы.

Глава 2. Формализация задачи составления расписания занятий.

2.1. Составление расписания, как задача многокритериальной оптимизации.

2.1.1 Объекты расписания.

2.1.2 Множество критериев.

2.1.3 Влияние критериев на качество расписания.

2.1.4 Дополнительные параметры.

2.2. Метод решения задачи составления расписания.

2.3 Автоматическое назначение преподавателя.

2.4. Многокритериальная оптимизация в задаче составления расписания.

2.5. Выбор альтернатив в задаче составления расписания.

2.6 Коэффициенты важности критериев и параметров.

2.7 Вычисление критериальных функционалов.

2.7.1 Критерий «окна».

2.7.2 Эффективная загруженность дня.

2.7.3 Эффективная загруженность недели.

2.7.4 Пожелания преподавателей.

2.8 Алгоритм выбора аудитории для занятия.

2.9 Особенности составления расписания в МИЭТ.

2.10 Оценка качества полученного решения.

2.11 Выводы.

Глава 3. Особенности реализации параллельных программ на кластерных системах.

3.1 Основные типы и архитектуры многопроцессорных систем.

3.2 Основные характеристики производительности.

3.3 Основные проблемы разработки параллельного алгоритма.

3.4 Основные этапы разработки параллельных алгоритмов.

3.5 Выделение подзадач в задаче составления расписания занятий. Информационные зависимости.

3.6 Масштабирование задачи составления расписания.

3.7 Взаимодействие между подзадачами составления расписания.

3.8 Распределение подзадач между процессорами кластерной системы.

3.9 Параллельный алгоритм для кластерных систем решения задачи составления расписания.

3.10 Формирование подсписков. Динамическая балансировка загрузки узлов.

3.11 Обмен данными между узлами кластерной системы.

3.12 Выводы.

Глава 4. Исследование эффективности кластера для параллельного алгоритма составления расписания занятий.

4.1 Структура входных данных.

4.2 Оценка качества получаемых решений.

4.3 Вычислительный эксперимент.

4.4. Выводы.

Введение диссертации (часть автореферата) на тему «Повышение эффективности кластерных систем обработки информации при решении оптимизационных задач: на примере задачи составления расписания занятий»

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

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

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

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

Для достижения поставленной цели в работе решаются следующие основные задачи:

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

2. Постановка и формализация задачи составления расписания занятий в ВУЗе.

3. Разработка критериальных оценок качества решения задачи составления расписания.

4. Разработка алгоритма решения задачи составления расписания занятий.

5. Анализ методов распределения нагрузки для многопроцессорных систем с распределенной памятью.

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

7. Разработка параллельной программы, адаптированной для кластерных вычислителей с распределенной памятью.

8. Экспериментальное исследование эффективности предложенного алгоритма.

Объект и предмет исследования. Объектом исследования являются методы и алгоритмы решения оптимизационных задач.

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

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

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

1. Результаты анализа переносимости алгоритмов решения задачи составления расписания занятий на параллельную платформу.

2. Итерационный алгоритм решения задачи составления расписания. 1

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

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

5. Результаты практического исследования эффективности алгоритма и программы.

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

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

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на Всероссийских межвузовских научно-технических конференциях студентов и аспирантов «Микроэлектроника и информатика - 2007, 2008», «Актуальные проблемы информатизации. Развитие информационной инфраструктуры, технологий и систем - 2007», IV Международной научно-практической конференции «Современные информационные технологии и ИТ-образование» - 2009, Международной научно-практической конференции ГГЕ08'2010 «Информационные технологии. Электронные приборы и системы».

Публикации. По материалам диссертации опубликовано пять тезисов докладов и две статьи, одна из которых в журнале, рекомендуемом ВАК. Получены два свидетельства РФ на программу для ЭВМ.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Милехина, Татьяна Викторовна

4.4. Выводы.

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

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

3. Эффективность кластера при решении оптимизационной задачи зависит от числа используемых узлов и находится в интервале от 0,94 — 0,23. Ее снижение при увеличении числа узлов определяется латентностью системы коммутации.

4. Загруженность каждого ядра при выполнении счетных операций составляет 96%, что говорит об эффективном использовании вычислительной мощности узла и правильной стратегии балансировки.

Заключение.

Краткая характеристика выполненных исследований:

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

2. Формализована задача составления расписания занятий в ВУЗе, как задача многокритериальной оптимизации.

3. Разработан последовательный алгоритм составления расписания занятий в ВУЗе, основанный на минимизации целевой функции, вычисленной по методу линейной свертки.

4. Разработан параллельный алгоритм решения задачи составления расписания занятий, учитывающий архитектурные особенности кластерных систем обработки информации, обеспечивающий 90% загрузку узлов кластера и ее динамическую балансировку.

5. На языке С++ с использованием библиотеки MPI разработан программный модуль автоматического составления расписания занятий в ВУЗе, адаптированный для кластерных вычислительных систем с распределенной памятью и обеспечивающий 100% расстановку занятий в автоматическом режиме. На указанный программный модуль получено свидетельство об официальной регистрации.

6. Исследования предложенного алгоритма и разработанной на его основе программы, проведенные на вычислительном кластере МИЭТ-2008, подтвердили, что эффективность использования узлов кластера в процессе решения оптимизационной задачи достигает величины 90-96%.

Список литературы диссертационного исследования кандидат технических наук Милехина, Татьяна Викторовна, 2011 год

1. Подиновский В. В. Парето-Оптимальные решения многокритериальных задач / В. В. Подиновский, В.Д. Ногин. М.: Наука, 1982. - 254 с.

2. Блюмин C.JI. Введение в математические методы принятия решений / C.JI Блюмин, И.А. Шуйкова. Липецкий Государственный Педагогический Институт, Липецк 1999, 100стр.

3. William Н. Press, Saul A. Teukolsky, William Т. Vetterling, Brian P. Flannery "Numerical recipes in C: the art of scientific computing", Second Edition, Cambridge University Press, 1992, 994 стр

4. Dimitris Bertsimas, John Tsitsiklis "Simulated Annealing", Statistical Science, Vol.8,No l,p. 10-15, 1993.

5. Безгинов A.H Обзор существующих методов составления расписаний / А.Н. Безгинов, С.Ю. Трегубов // Информационные технологии и программирование выпуск 2(14), 2005г, с 5 — 19.

6. Панченко Т.В. Генетические алгоритмы: учебно-методическое пособие / под редакцией Ю.Ю. Тарасевича. Астрахань: Издательский дом «Астраханский университет», 2007г, 87 стр.

7. Michel Gendreau "An Introduction to Tabu Search", 2002

8. Available: http://www.ifi.uio.no/infheur/Bakffrunn/Intro to TS Gendreau.htm

9. Маляренко Илья Планирование и оптимизация: от Вергилия до. APS-системы // PC WEEK. 2006г. Электронный ресурс] - Режим доступа: http://www.pcweek.m/idea/article/detail.php?ID=72912

10. Дискретная математика. Электронный ресурс] — Режим доступа: http://pgap.chat.ru/zap/zap251 .htm

11. Rong Qu, Edmund Burke, Barry McCollum, Liam T.G. Merlot and Sau Y. Lee "A Survey of Search Methodologies and Automated Approaches for Examination Timetabling" // Computer Science Technical Report No. NOTTCS-TR-2006-4

12. Ахо Альфред, Хопкрофт Джон, Ульман Джефри Структуры данных и алгоритмы. : Пер. с англ. : Уч. пос. — М. : Издательский дом «Вильяме». — 2007. -400с. ISBN 5-8459-0122-7

13. Scheuermann, Bemd Ant Colony Optimization on Runtime Reconfigurable Architectures. : Dissertation . 20.12.2005.

14. Available: http://digbib.ubka.uni-karlsruhe.de/volltexte/1000003803

15. Муравьиный алгоритм. Электронный ресурс]http://ru.wikipedia.org/wiki/%D0%9C%D 1 %83%D 1 %80%D0%B0%D0%B2%D 1 %8C%D0%B8%D0%BD%D 1 %8B%D0%B9 %D0%B0%D0%BB%D0%B3%D0 %BE%D 1 %80%D0%B8%D 1 %82%D0%BC

16. Субботин C.A. Часть III. Интеллектуальные мультиагентные методы (Swarm Intelligence) / C.A. Субботин , Ан. А. Олейник., Ал. А. Олейник 2006.

17. Chin Soon Chong A Bee Colony Optimization Algorithm to Job Shop Scheduling / Chin Soon Chong, Malcolm Yoke Hean Low, Appa Iyer Sivakumar, Kheng Leng Gay. // Simulation Conference, 2006. WSC 06. Proceedings of the Winter, pages 1954-1961.

18. Ногин В.Д. Проблема сужения множества Парето: подходы к решению. // Искусственный интеллект и принятие решений № 15 2008, стр. 98-112.

19. В. Н. Шевченко, Н. Ю. Золотых. Линейное и целочисленное программирование. // Учебное пособие. Изд. Нижегородского Государственного Университета.- Нижний Новгород.- 2002.

20. Яндыбаева Н.В. Генетический алгоритм в задаче оптимизации учебного расписания. // Современные наукоемкие технологии — Изд. ООО Издательский дом «Академия Естествознания», №11, 2009, стр. 97-98.

21. Любченко A.B. Автоматизация процесса составления расписания занятий для кафедры ВУЗа. // Системи обробки інформації. Харків: ХВУ. -2007-№3 (61),-С. 150-152.

22. Береговых Ю. В., Васильєв Б. А., Володин Н. А. Алгоритм составления расписания занятий. // Искусственный интеллект. — №2. — 2009. С. 50-56.

23. Шаповалов Т.С., Пересветов В.В. Генетический алгоритм составления расписаний для распределенных гетерогенных вычислительных систем. // Вычислительные методы и программирование. — Т. 10 — 2009. — С. 13-29.

24. Ерунов В. П., Морковин И. И. Формирование оптимального расписания учебных занятий в ВУЗе. // Вестник ОГУ. 3. - 2001. - С. 55-63.

25. Каргапольцев С. К., Лашук Н. В. Применение искусственных нейронных сетей в задаче составления расписания учебных занятий. // Электронный источник, http://www.iumal.org/articles/2008/inf73.html

26. Веревкин В. И., Исмагилова О. М., Атавин Т. А. Автоматизированное составление расписания учебных занятий вуза с учетом трудности дисциплин и утомляемости студентов. // Журнал «Доклады Томского Государственного

27. Университета систем управления и радиоэлектроники». №1 (19) — часть 1. — 2009.-С. 221-225.

28. Расписание занятий. Описания программ и закачка пробных версий. Электронный ресурс]

29. Режим доступа: http://soft.israelmfo.ru/programs/education/223

30. Басыров P. AVTORcKoe составление расписаний. Электронный ресурс] Режим доступа: http://www.softkev.info/reviews/review647.php

31. Расписание занятий Серия компьютерных программ. Электронный ресурс]

32. Режим доступа: http://www.raspisanie.com/

33. Университет 3.2.0.711. Электронный ресурс] Режим доступа: http://allsoft.ru/programpage.php7grp~l 1148

34. Scheduling Software for School and University Timetables Режим доступа: http://www.mimosasoftware.com/

35. Ректор-Программа Расписание: Продукты. Электронный ресурс] Режим доступа: http://www.rector.spb.ru/

36. Найханова JI. В. Методы и алгоритмы принятия решений в управлении учебным процессом в условиях неопределенности: Монография. / Л. В. Найханова, С. В. Дамбаева; Улан-Удэ: Изд-во ВСГТУ, 2004. - 164 с.

37. Жилина Г.А. «Методическое пособие и инструкции по составлению расписаний на ЦВМ» / Г.А. Жилина, М. В. Медведский, Л.С. Писаренко; Минское высшее инженерное зенитное ракетное училище противовоздушной обороны, 1976. 92с.

38. Давыдов С. В. Система автоматического построения расписания учебных занятий. / С. В. Давыдов Электронный ресурс]

39. Режим доступа: http://davidovsv.narod.ru/schedule/index.html

40. Черноруцкий И.Г. Методы принятия решений / И.Г. Черноруцкий. -СПб.: БХВ-Петербург. 2005. -416с. ISBN 5-94157-481-9

41. Богачёв К. Ю. Основы параллельного программирования. / К. Ю. Богачёв. М.: БИНОМ. Лаборатория знаний, 2003. - 342 С. ISBN 5-94774037-0

42. Гергель В. П. Основы параллельных вычислений для многопроцессорных вычислительных систем. Учебное пособие / В. П. Гергель, Р. Г. Стронгин, Нижний Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2003. 184 С.

43. Multiprocessing. Available: http://en.wikipedia.org/wiki/Multiprocessing

44. SISD. Available: http://en.wikipedia.org/wiki/SISD

45. MISD. Available: http://en.wikipedia.org/wiki/MISD

46. SIMD. Available: http://en.wikipedia.org/wiki/SIMD

47. MIMD. Available: http://en.wikipedia.org/wiki/MIMD

48. Классификации архитектур вычислительных систем. Электронный ресурс]

49. Режим доступа: http://www.parallel.ru/computers/taxonomy/

50. Ananth Grama Introduction to Parallel Computing, Second Edition. / Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar, Addison Wesley, 2003. -856 C.

51. Воеводин Вл. В. Параллельная обработка данных / Вл. В. Воеводин. Электронный ресурс] Режим доступа: http://www.parallel.ru/parallel/vvv/

52. Duncan A. Grove Performance Modelling of Message-Passing Parallel Programs. PhD Thesis, University of Adelaide, 2003. 313p.

53. Посыпкин M.A. Основы параллельного программирования / M.A. Посыпкин. Электронный ресурс] Режим доступа: http://posmik.narod.ru/curs/Vvedenie.2006.10.23 .ppt

54. Карпов А. Введение в проблематику разработки параллельных программ. / А. Карпов. Электронный ресурс] Режим доступа: http://www.viva64.eom/ru/a/0016/

55. Гергель В.П. Теория и практика параллельных вычислений / В.П. Гергель. Электронный ресурс]

56. Режим доступа: http://www.intuit.rii/departtTient/calculate/paralltp/4/l.html