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

• Смирнов, Сергей Андреевич
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Смирнов, Сергей Андреевич

Список терминов, условных обозначений и сокращений.

Введение

Глава 1. Современное состояние технологий интеграции программных ресурсов.

1.1. Применение грид-технологий и распределенных вычислений для решения сложных задач.

1.2. Интеграция ресурсов в распределенную систему.

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

2.1. Разработка сервисов математического программирования

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

2.3. Средства визуализации результатов вычислений.

2.4. Разработка сервисов безошибочных вычислений.

Глава 3. Решение задач.

3.1. Распределенный программный комплекс для моделирования структуры молекулярных соединений.

3.2. Безошибочные вычисления.

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

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

Актуальность темы. Любая работающая оптимизационная система представляет собой сложную систему, состоящую из разнородных компонентов: библиотек унифицированных или предметно-ориентированных («авторских») численных методов, средств доступа, средств обмена данными. Целью работы является разработка программных технологий и методов интеграция этого программного обеспечения в распределенную вычислительную среду

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

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

К настоящему времени создан обширный парк программного обеспечения для решения оптимизационных задач, который можно разбить на две основные группы: 1) коммерческие и свободно доступные (в исходных кодах) пакеты численных методов для задач оптимизации различных типов; 2) высокоуровневые средства оптимизационного моделирования на основе трансляторов алгебраических языков оптимизационного моделирования, например, AMPL (A Modeling Language for Mathematical Programming), GAMS (General Algebraic Modeling System) и др. Применение указанных трансляторов значительно сокращает трудоемкость этапов подготовки исходных данных (для их ввода в пакеты оптимизации) и обработки результатов решения. Помимо этого часто необходимо применять дополнительные программные средства: системы компьютерной алгебры, средства визуализации и др.

Несмотря на достаточную зрелость программных технологий в области оптимизации и технологий распределенных вычислений, мировой уровень развития распределенных систем оптимизации, как ни странно, невысок. Хорошо известным примером применения оптимизационных пакетов как удаленных сервисов был и остается портал «NEOS: server for optimization», http://www.neos-server.org. Данный проект функционирует по простейшей клиент-серверной модели, позволяя отправлять одиночные задачи оптимизации, заданные в формате одного из языков оптимизационного моделирования, одному из пакетов, установленных на серверах NEOS.

В конце 2006 года, в рамках работ над проектом COIN-OR (Computational Infrastructure for Operations Research), возникла инициатива OS (Optimization Services). Ее целью было создание широкого набора спецификаций, связанных с созданием систем оптимизационного моделирования, от описания задач и обнаружения сервисов-решателей, до управления ходом вычислений и обмена результатами решения.

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

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

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

Задачи исследования:

1. Анализ и сравнение различных технологий интеграции программных ресурсов в распределенные вычислительные среды.

2. Разработка методов создания программных сервисов доступа к математическим пакетам в распределенных средах.

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

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

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

Методы исследования. В основу разрабатываемых в диссертации систем положен сервис-ориентированный подход. При решении вычислительных задач использовались методы оптимизации и линейной алгебры. При разработке программного обеспечения использовались языки С++, Java, Python и Shell, архитектурный стиль REST, а также промежуточное программное обеспечение Ice.

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

На защиту выносятся:

1. Методы создания сервисов доступа к математическим пакетам, обеспечивающие интеграцию разнородных программных компонентов в распределенную среду.

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

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

Внедрение результатов работы. Результаты использованы: в работах по созданию сервисов решения задач линейного программирования, глобальной оптимизации и компьютерной алгебры для портала «Российская ГРИД-сеть для высокопроизводительных вычислений», http://grid.voskhod.ru (в рамках государственного контракта № 012/152 от 13 декабря 2010 г.); для определения состава углеродных наноструктур в осажденных пленках и камеры экспериментальной установки термоядерного синтеза ТОКАМАК Т-10 методами оптимизационной идентификации по экспериментальным данным рентгеновского рассеивания (грант РФФИ 09-07-00469-а «Распределенные вычисления электродинамической агрегации наночастиц для создания каркасной фрактальной основы наноматериалов»); для развертывания сервисов оптимизационного моделирования в инфраструктуре центра грид-технологий и распределенных вычислений Института Системного Анализа РАН.

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на: семинарах в Институте системного анализа РАН; на IV международной конференции «Распределённые вычисления и Грид-тех-нологии в науке и образовании» (Дубна, 2010); на 50, 51, 53 и 54 научных конференциях МФТИ (Долгопрудный, 2007, 2008, 2010, 2011); на III и V научно-практических конференциях «Современные информационные технологии и ИТ-образование» (Москва, 2008, 2010); на XVII международной конференции по вычислительной механике и современным прикладным программным системам (Алушта, Крым, 2011); на международной научно-практической конференции молодых ученых и специалистов «Технологии высокопроизводительных вычислений и компьютерного моделирования» (Амстердам, Нидерланды, 2012).

Публикации. По теме диссертации опубликовано 14 печатных работ, три из них в изданиях из списка ВАК [1-3].

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

Структура и объем диссертации. Общий объем диссертации составляет 159 страниц. Работа состоит из введения, трех глав, заключения и списка литературы (59 наименований).

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

Заключение

Опыт работы с созданными сервисами математического программирования и с сервисами символьных вычислений позволяет сказать, что для поисковых научно-исследовательских проектов, где требуется разработка проблемно-ориентированных распределенных вычислительных систем, применение КЕБТЫ-веб-сервисов заметно сокращает трудоемкость программной разработки. Они позволяют относительно легко получить (и, при необходимости, изменить) действующий прототип распределенной вычислительного сценария для решения той или иной вычислительной задачи.

Перечислим основные результаты работы:

1. Предложены методики создания сервисов доступа к математическим пакетам.

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

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

4. Полученные результаты применены для решения модельных и прикладных задач и внедрены в практику.

Список литературы диссертационного исследования кандидат технических наук Смирнов, Сергей Андреевич, 2012 год

1. Волошинов В., Смирнов С. Принципы интеграции программных ресурсов в научных вычислениях // Информационные технологии и вычислительные системы. 2012. № 3. С. 66-71.

2. Смирнов С. Разработка Grid-сервиса для системы компьютерной алгебры Maxima на основе промежуточного программного обеспечения Ice // Труды МФТИ. 2009. Т. 1, № 2. С. 200-205.

3. Волошинов В., Смирнов С. Программный комплекс для расчета ЯН-индекса публичной политики // Оценка состояния и развития гражданского общества России: Проблемы, инструменты и региональная специфика, Труды ИСА РАН. 2010. Т. 57. С. 80-103.

4. Boehm В. A spiral model of software development and enhancement // Computer. 1988. Vol. 21, no. 5. Pp. 61-72.

5. Mattsson M., Bosch J., Fayad M. Framework integration problems, causes, solutions // Communications of the ACM. 1999. Vol. 42, no. 10. Pp. 80-87.

6. Karjalainen M. DSP software integration by object-oriented programming: a case study of QuickSig // ASSP Magazine, IEEE. 1990. Vol. 7, no. 2. Pp. 21-31.

7. Vigder M., Gentleman W., Dean J. COTS Software Integration: State of the art: Tech. rep.: National Research Council of Canada, 1996.

8. Abts C., Boehm B. COTS software integration cost modeling study: Tech. rep.: University of Southern California, 1997.

9. Abts C., Boehm В., Clark E. COCOTS: A COTS software integration lifecycle cost model-model overview and preliminary data collection findings. 2000.

10. Sanner M. Python: a programming language for software integration and development // J Mol Graph Model. 1999. Vol. 17, no. 1. Pp. 57-61.

11. Adams P., Grosse-Kunstleve R., Hung L. et al. PHENIX: building new software for automated crystallographic structure determination // Acta Crys-tallographica Section D: Biological Crystallography. 2002. Vol. 58, no. 11. Pp. 1948-1954.

12. Andersson J., Johnson P. Architectural integration styles for large-scale enterprise software systems // Enterprise Distributed Object Computing Conference, 2001. EDOC'Ol. Proceedings. Fifth IEEE International / IEEE. 2001. Pp. 224-236.

13. Гамма Э., Хелм P., Джонсон P., Влиссидес Д. Приемы объектно-ориентированного проектирования. СПб.: Питер, 2001.

14. Foster I., Kesselman С. Scaling system-level science: Scientific exploration and IT implications // Computer. 2006. Vol. 39, no. 11. Pp. 31-39.

15. Booth D., Haas H., McCabe F. et al. Web services architecture. 2004. URL: http://www.w3.org/TR/2004/N0TE-ws-arch-20040211.

16. White J. High-level framework for network-based resource sharing. 1975.

17. Kendall S., Waldo J., Wollrath A., Wyant G. A Note on Distributed Computing, Sun Microsystems // Inc., Mountain View, CA. 1994.

18. Fielding R. Architectural styles and the design of network-based software architectures: Ph. D. thesis / University of California. 2000.

19. Richardson L., Ruby S. RESTful web services. O'Reilly Media, 2007.

20. Сухорослов О. Унифицированный интерфейс доступа к алгоритмическим сервисам в Web // Проблемы вычислений в распределенной среде, Труды ИСА РАН. 2009. Т. 46. С. 60-82.

21. Волошинов В., Естехин О., Сухорослов О. Архитектура и принципы реализации системы IARnet // Проблемы вычислений в распределенной среде: Модели обработки и представления данных. Динамические системы, Труды ИСА РАН. 2005. Т. 14. С. 13-25.

22. Sukhoroslov О. On using Ice middleware in the IARnet framework // XXI International Symposium on Nuclear Electronics k, Computing (NEC'2007): Abstracts. 2007. P. 48.

23. Modeling Language GNU MathProg, Language Reference, 4.34, 2008.

24. AMPL: A Modeling Language for Mathematical Programming. Brooks/Cole Publishing Company / Cengage Learning, 2002.

25. GNU Linear Programming Kit, Reference Manual, 4.38, 2009.

26. Gay D. Hooking your solver to AMPL // Numerical Analysis Manuscript. 1997. no. 93-10.

27. Посыпкин M. Параллельный эвристический алгоритм глобальной оптимизации // Труды ИСА РАН. 2008. Т. 32. С. 166-179.

28. Avogadro Free cross-platform molecule editor, http: / / avogadro.openmolecules.net.

29. Python Programming Language Official Website, http://www.python.org/.

30. Посыпкин M. Архитектура и программная организация библиотеки для решения задач дискретной оптимизации методом ветвей и границ на многопроцессорных вычислительных комплексах // Труды ИСА РАН. 2006. Т. 25. С. 18-25.

31. Henning М. A New Approach to Object-Oriented Middleware // IEEE Internet Computing. 2004. Vol. 8, no. 1. Pp. 66-75.

32. Тыртышников E. Методы численного анализа. ИЦ Академия М., 2007. С. 320.

33. Блехман И., Мышкис А., Пановко Я. Прикладная математика: предмет, логика, особенности подходов. С примерами из механики. УРСС М., 2005.

34. Бахвалов Н. Численные методы (анализ, алгебра, обыкновенные дифференциальные уравнения): Учебное пособие. Наука. Гл. ред. физ.-мат. лит., 1973. С. 632.

35. Житников В. Компьютеры, математика и свобода // Компьютерра. 2006. Т. 636, № 16. С. 40-43.

36. Тарнавский Т. Maxima: максимум свободы символьных вычислений (цикл статей) // LinuxFormat. 2006. № 81-86.

37. Сайт ассоциации пользователей Lisp, http://www.alu.org/.

38. McCarthy J. History of LISP // SIGPLAN Not. 1978. Vol. 13, no. 8. Pp. 217-223. URL: http://doi.acm.org/10.1145/960118.808387.

39. Boost.Process, http://www.highscore.de/boost/process/.

40. Karlsson B. Beyond the С++ Standard Library: An Introduction to Boost. Addison-Wesley Professional, 2006.

41. Веб-сайт CxxTest. http://cxxtest.tigris.org/.

42. Емельянов С., Афанасьев А., Волошинов В., др. Реализация Grid-вычислений в среде IARnet // Информационные технологии и вычислительные системы. 2005. № 2. С. 61-75.

43. Mongoose easy to use web server, http://code.google.eom/p/mongoose/.

44. Jython: Python for the Java Platform, http://www.jython.org/.

45. MathCloud REST API. http://www.mathcloud.org.

46. Locatelli M., Schoen F. Fast global optimization of difficult Lennard-Jones clusters // Computational Optimization and Applications. 2002. Vol. 21, no. 1. Pp. 55-70.

47. Doye J., Leary R., Locatelli M., Schoen F. Global optimization of Morse clusters by potential energy transformations // INFORMS Journal on Computing. 2004. Vol. 16, no. 4. Pp. 371-379.

48. Neumaier A. Molecular modeling of proteins and mathematical prediction of protein structure // SIAM review. 1997. Pp. 407-460.

49. Hammond K., Zain A., Cooperman G. et al. SymGrid: a framework for symbolic computation on the Grid // Euro-Par 2007 Parallel Processing. 2007. Pp. 457-466.

50. Германенко M. Программное обеспечение безошибочных дробно-рациональных вычислений и его применение для решения линейных систем // Вестник Нижегородского университета им. НИ Лобачевского. 2009. № 4. С. 172-180.

51. Панюков А., Германенко М. Безошибочное решение систем линейных алгебраических уравнений // Вестник Южно-Уральского государственного университета. Серия: Математика. Физика. Химия. 2009. № 10. С. 33-40.

52. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. Вильяме Паблишинг, 2005. С. 1296.

53. Лазарев И., Сухорослов О. Реализация распределенных вычислительных сценариев в среде MathCloud // Проблемы вычислений в распределенной среде/Под ред. СВ Емельянова, АП Афанасьева. Труды ИСА РАН. 2009. Т. 46. С. 6-23.

54. Гантмахер Ф. Теория матриц. 5 изд. Физматлит, 2004. С. 560.

55. Coppersmith D., Winograd S. Matrix multiplication via arithmetic progressions // Journal of symbolic computation. 1990. Vol. 9, no. 3. Pp. 251-280.

56. Smirnov S. On Development of RESTful web Service for a Computer Algebra System in MathCloud Environment // Distributed Computing and Grid-Technologies in Science and Education: Book of Abstr. of the 4th Intern. Conf. 2010.