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

На правах рукописи

Смирнов Сергей Андреевич

Разработка программного обеспечения распределенных систем для решения задач оптимизации

05.13.01 - Системный анализ, управление и обработка информации (информационно-вычислительное обеспечение)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

2 2 НОЯ 2012

Москва - 2012

005055579

Работа выполнена на кафедре распределенных вычислений факультета инноваций и высоких технологий Московского физико-технического института (государственного университета).

Научный руководитель: доктор физико-математических наук,

профессор,

Афанасьев Александр Петрович

Официальные оппоненты: Бухановский Александр Валерьевич.

доктор технических наук, профессор Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, директор НИИ Наукоемких компьютерных технологий

Фараджев Игорь Александрович, кандидат физико-математических наук, доцент

Институт Системного Анализа РАН, заведующий лабораторией 9-5 «Взаимодействие человека и компьютера»

Ведущая организация: Федеральное государственное бюджет-

ное учреждение науки Вычислительный центр им. A.A. Дородницына Российской академии наук

Защита состоится « 17 » декабря 2012 г. в 13°° часов на заседании диссертационного совета Д.002.086.02 при Институте Системного Анализа РАН, расположенном по адресу: 117312, Москва, проспект 60-летия Октября, 9.

С диссертацией можно ознакомиться в библиотеке Института Системного Анализа РАН, расположенном по адресу: 117312, Москва, проспект 60-летия Октября, 9.

Автореферат разослан « 16 » ноября 2012 г.

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

Ученый секретарь диссертационного совета,

доктор технических наук, профессор Пропой А.И.

Общая характеристика работы

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

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

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

К настоящему времени создан обширный парк программного обеспечения для решения оптимизационных задач, который можно разбить на две основные группы: 1) коммерческие и свободно доступные (в исходных кодах) пакеты численных методов для задач оптимизации различных типов; 2) высокоуровневые средства оптимизационного моделирования на основе трансля-

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

Несмотря на достаточную зрелость программных технологий в области оптимизации и технологий распределенных вычислений, мировой уровень развития распределенных систем оптимизации, как ни странно, невысок. Хорошо известным примером применения оптимизационных пакетов как удаленных сервисов был и остается портал «NEOS: server for optimization», http://www.neos-sei-ver.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. Возникает возможность использовать пакет для решения подзадач в сложных распределенных вычислительных сценариях.

Был реализован сервис решения задач линейного программирования для среды IARnet2 на основе пакета GLPK. Библиотека GLPK предоставляет пользователю возможности решения задач линейного программирования, в том числе с целочисленными переменными. Использование GLPK возможно двумя способами: через API, либо через консольное приложение. В первом варианте пользователь имеет полный доступ ко всем функциям GLPK. В случае консольного приложения пользователь имеет возможность записать задачу в одном из поддерживаемых GLPK форматов и запустить приложение glpsol из состава GLPK, которое само вызовет необходимые функции API GLPK и вернет результат в требуемом формате. При реализации сервиса использовался первый способ, как позволяющий более гибко использовать все возможности библиотеки GLPK.

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

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

Существует ряд бесплатных солверов с открытым исходным кодом, поддерживающих ввод данных на языке AMPL [1, 4]. Пакет lp_solve обеспечивает решение задач линейного программирования и частично целочисленных задач линейного программирования. Пакет IPOPT позволяет решать задачи нелинейного программирования методом внутренней точки. Пакет BONMIN обеспечивает решение частично целочисленных задач нелинейного программирования, используя в своей реализации пакет IPOPT. Благодаря применению языка AMPL, пакеты имеют унифицированный интерфейс: получая на вход так называемый стаб задачи и файл с опциями солвера, они возвращают решение задачи в виде файла стандартного для среды AMPL формата. Повторяя этот интерфейс, данные три пакета были объединены в одни сервис решения задач математического программирования в среде MathCloud.

Также были реализованы варианты сервиса, принимающие на вход пакет задач, которые требуется решить параллельно. Было создано три реализации такого интерфейса: для параллельного решения на одной многоядерной машине, для кластера с PBS, а также для запуска заданий в грид средствами glite-адаптера сервера Everest в MathCloud.

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

алгебраических языков моделирования как AMPL и GAMS распространяются на коммерческой основе. При этом библиотеки, используемые разработчиками математических пакетов, для работы с файлами алгебраического языка распространяются бесплатно. Такие библиотеки обладают довольно широкой функциональностью, например, давая разработчику возможность не только вычислять значения целевой функции и функций ограничений, по также и первые, и вторые производные методом автоматического дифференцирования. Естественно, использование алгебраического языка моделирования для ввода данных в солвер уступает по производительности работе непосредственно с API солвера [5, 6]. Однако эта разница, как правило, не так критична, особенно учитывая удобства работы с солверами посредством алгебраических языков моделирования.

Поддержка описаний задач на алгебраическом языке моделирования AMPL была реализована в библиотеке BnB-Solver следующим образом [7]. Пользователь описывает модель задачи и задаёт значения параметров в текстовых AMPL-файлах, передаёт эти файлы транслятору AMPL, получая так называемый «стаб», который считывается солвером средствами библиотеки ASL. Эта библиотека позволяет «AMPL-совместимым» солверам получить все необходимые для решения задачи данные и, главное, обеспечивает автоматическое вычисление значений функций вместе с первыми и вторыми производными.

Пользователь готовит XML-описание задачи и передаёт его, вместе с предварительно сгенерированным стабом, приложению BnB-Solver. Последнее, используя XML-описание задачи и стаб, создаёт объект с методами для вычисления значений целевой функции и её градиента с использованием библиотеки ASL. Также создаётся программный объект солвера, который и осуществляет поиск решения.

Средства визуализации результатов вычислений. Редакторы вычислительных сценариев, всевозможные сервисы пакетов оптимизации, си-

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

Система Avogadro представляет собой развитый редактор молекул, предназначенный для межплатформенного использования в вычислительной химии, молекулярном моделировании, биоинформатике, науках о материалах и смежных областях. Редактор обладает гибким механизмом визуализации и высокой расширяемостью за счет механизма встраиваемых расширений (plug-ins) и возможности создания сценариев на языке Python. Программный комплекс BNB-Grid предназначен для решения задач оптимизации на распределенных системах, состоящих как из настольных систем, так и многопроцессорных кластеров и суперкомпьютеров. BNB-Grid запускает и организует взаимодействие параллельных приложений, решающих задачу с помощью библиотеки BNB-Solver на различных вычислительных узлах. В результате формируется иерархическая распределенная система: на верхнем уровне работы распределяются между параллельными приложениями, а далее они распределяются по процессорам средствами библиотеки BNB-Solver. Библиотека BNB-Solver предназначена для поиска глобального экстремума на многопроцессорных вычислительных комплексах. Интеграция BNB-Grid и редактора осуществлена с помощью промежуточного программного обеспечения Ice (Internet Communication Engine). Для целей интеграции в редакторе был специально разработан модуль расширения, взаимодействующий с BNB-Grid через его 1се-интерфейс и предоставляющий пользователю возможность

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

Сервисы безошибочных вычислений реализованы на основе системы компьютерной алгебры Maxima. Они позволяют взаимодействовать с системой посредством языка команд Maxima. При этом результат выполнения операции возвращается в форме пригодной для непосредственного использования в последующих командах. Первая версия сервиса была сделана для системы IAR.net. Сервис представлял собой ресурс-фабрику, порождающую по запросу пользователя ресурсы-процессы, которые, в свою очередь, обеспечивали непосредственное взаимодействие с системой Maxima. Таким образом каждый пользователь работал со своим личным экземпляром системы. Такая архитектура подразумевает существование состояния, хранимого между вызовами сервиса на стороне сервера. Хранение состояния на сервере позволяет ускорить выполнение запросов к сервису так как отпадает необходимость запуска отдельного процесса Maxima для каждого запроса. Вторая версия сервиса [2J, базировавшаяся на промежуточном программном обеспечении Ice, делала работу с сервисом более удобной и надежной. Следующая версия, разработанная для среды IARnet2, обладала заметно расширенной функциональностью: возможностями досрочного прерывания выполнения команд и передачи файлов, а также повышенной, за счет улучшенного контроля синтаксиса передаваемых клиентом команд, надежностью. Далее описываются версии сервиса для среды MathCloud [8, 9].

Особенностью всех разработанных сервисов Maxima является наличие состояния у сервиса. При этом с точки зрения пользователя работа с сервисом происходит как будто состояния нет. Так делалось, чтобы не расходовать

при каждом запросе к сервису время на запуск самой системы компьютерной алгебры. В случае операций, выполняемых за короткое время в сервисах на основе технологий распределенных объектов, такая оптимизация целесообразна. С другой стороны, при работе с сервисами MathCloud, накладные расходы на один вызов уже сравнимы с запуском системы. При этом поддержание работы постоянно запущенных процессов Maxima довольно трудоемко с точки зрения сложности кода. Целесообразнее использовать пакетный режим работы с Maxima. Он намного стабильнее: пропадает необходимость контролировать ввод пользователя, так как в пакетном режиме Maxima не зависает. Также упрощается отмена заданий, так как достаточно завершить сам процесс системы компьютерной алгебры. Кроме того, на основе имеющегося опыта использования сервисов Maxima, можно сказать, что обработку результатов расчетов удобнее всего делать также в Maxima и передавать данные между вызовами с помощью файлов в «родных» форматах системы. В таком случае отпадает необходимость в большей части функциональности существующих сервисов и их можно заменить предельно простыми сервисами командной строки, обменивающимися файлами.

В третьей главе описано использование разработанного инструментария для решения модельных и прикладных задач. Комплекс для моделирования структуры молекулярных соединений апробируется на задаче поиска молекулярных кластеров с потенциалом межатомного взаимодействия Морзе. Сервисы символьных вычислений используются для безошибочного решения таких задач как обращение матриц, LU-разложение матриц и др. Кроме того, описывается опыт применения технологий распределенных вычислений в статистических исследованиях [3].

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

энергию взаимодействия двух частиц через г>(г), где г — расстояние между ними, то суммарная энергия кластера имеет вид

л"-1 лг

Е(Х) = Е(Хи.., Х„) = Е Е " (И* - Л^11) ■ «

¿=1 jЫ+l

где — это координаты 1-го атома, а || ■ || — евклидова норма. Искомая конфигурация X* = {Х1,..., А'дг) определяется в результате решения задачи глобальной оптимизации Е(Х*) = пипхедз" Е(Х).

Исследователи используют различные выражения для потенциала у(г). Наиболее распространены потенциалы: Ленарда-Джонса, ь(г) = — Морзе, и(г) = — I)2 — 1, где р — параметр, определяющий «ширину потенциальной ямы».

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

Учитывая важность этой задачи, представляется целесообразной разработка универсальных инструментов для поиска и исследования конфигураций атомов с минимальной энергией взаимодействия. Формулируются требования к этим инструментам. В соответствие с этими требованиями был разработан прототип комплекса программ для создания, оптимизации, редактирования и хранения конфигураций молекулярных кластеров [10, 11].

Безошибочные вычисления. Одной из известных проблем вычислительной математики, является решение систем линейных уравнений

Ах = у,х 6 Я?, у е А = [а,т,],ттг = 1 : ЛГ,п = 1 : ЛГ, (2)

где матрица А является, т.н. плохо-обусловленной.

Известным примером плохо-обусловленных матриц являются матрицы Гильберта. Формальное определение матрицы Гильберта размера N х N выглядит следующим образом: Ядг =- [Лт,п]^,п=1, где 1гт,п = (тп + п- I)-1. Эти матрицы широко применяются в теории и численных методах аппроксимации произвольных функций многочленами (при обработке сигналов, коррекции ошибок и т.п.). Известно, что зависимость числа обусловленности матриц Гильберта от ее размерности имеет оценку cond(Hf/) = e3'5 'v, например, уже для N = 10 это составит 1.6 • 1016. Это свойство делает вычисление обратной к матрице Гильберта нетривиальной задачей для традиционных программных средств на основе арифметики с плавающей точкой ограниченной разрядности.

Сервис Maxima для IARnet2 применялся в экспериментах по распределенному безошибочному обращению матриц. Обращение матриц осуществлялось в два этапа: на первом этапе вычислялось ее LU-разложение, на втором — параллельно вычислялись столбцы обратной матрицы.

Далее представлен распределённый и частично параллельный сценарий безошибочного обращения плохо обусловленных матриц в инфраструктуре MathCloud [12-14]. Сценарий основан на блочной декомпозиции матрицы и на дополнении Шура. Этот подход использует параллелизм при умножении промежуточных прямоугольных матриц. Кроме того данный сценарий обеспечивает всестороннее тестирование систем проектирования и управления сценариям среды MathCloud.

Использован хорошо известный в теории матриц способ их обращения, основанный на блочной декомпозиции и на так называемой формуле Шура (или дополнении Шура). Пусть М квадратная матрица N х N, представленная в виде четырёх блоков М = N[! = N — Лг.4, квадратные матрицы, a U, Na х -Л/д; и У, Nq х (N — NA). —

А и

V В

, где А, Na х Na, и В, NBx NB,

прямоугольные. Определим квадратную матрицу 5 = В-У- А-1 • и размера (УУ — Лта) х (ЛГ — А'л), т.н. дополнение Шура блока А матрицы М. Известно: если существует М"1, тогда (возможно, после некоторых перестановок) существуют А"1 и 5-1, причем М~1 может быть поделена на четыре подматрицы того же размера (как А, II, V, В) как показано ниже

3 М~

3 A-^S-^M'1 =

А~г +A~l-U ■ S"1 ■ V A"1 - A'1 ■ U ■ S~l

-s-1 V- A-1 S"1

(3)

Такое представление М~х позволяет ускорить её вычисление в результате параллельного обращения и умножения подматриц меньшего размера, чем у исходной матрицы М. Упрощённая блок-схема (не все информационные зависимости указаны) сценария показана на рис. 1. Для обозначения передачи данных между блоками используются два типа стрелок. Сплошная — означает, что входящие данные необходимы для совершения следующего шага вычислений, например, умножение (A"1U)S~1 может быть выполнено лишь после того как будут готовы произведение (A~lU) и обратная матрица S~x. Пунктирные стрелки означают, что для следующего шага достаточно готовности хотя бы одного из входов. Например, и VA"1, и A~lU достаточно для вычисления VA~lU = (VA~l)U = V(A~1U). Овалами выделены блоки, допускающие параллельное выполнение.

В сценарии обращения применялись сервисы двух типов: простой сервис «cats», сшивающий два входных файла в один выходной, и сервис «maxima», предоставляющий доступ к процессу Maxima для проведения вычислений.

Распределенный алгоритм LU-разложения также основан на дополнении Шура. Пусть, как и ранее, квадратная матрица M[N х N] разбита на четыре блока А, U, V, В, причем подматрица А обратима:

M[NxN],M =

A U V В

,A=[NAXNA],B = [(Л* - NA) х (N - NA)} (4)

УА'1и = У{л~1и) || (УА'^и

Т ,

А~'[/ 5'1 У А~'={А'11/А'1) || (/Г1 V А~') А'1+А'' и5"' У А~'

(?)

-(I) 4) -I) -I)

Рис. 1. Оценка эффективности распараллеливания

Ш-разложением матрицы А является тройка матриц Ь, II, Р, где Ь — нижняя треугольная матрица, II — верхняя треугольная матрица, Р — матрица перестановок, причем А = Р ■ Ь-11.

Легко проверить, что если 5 — дополнение Шура для матрицы М. то

М[ЛГ х ЛГ], М =

А и 1А 0 А и

V В УА'1 1з . 0 Б

(5)

Пусть А = Рд ■ Ь,4 ■ 11а, £ = Р5 • ■ — Ьи-разложения матриц А и ¿>. Так как Р — матрицы перестановок и, следовательно, Рд1 = Р\, то А'1 = и^Ь^рТ. Кроме того, 5 = В - УА~1Ь' = В - Уи^Ь^Р^и. Таким образом, ИТ-разложение матрицы М можно представить следующим образом:

ЬА О 1 Г и А ь-А1РХи рЦуи^ Ьз\ [ о и3

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

М ■■

Ра 0

0

(6)

Л=Р,ЬАи

.4

1/3(И/2)А3

(№)л3

Б = В - (V иА-х)(ГА1 РТА11)

(№2)л3

I

—Р Ь3~и 5

1/3(Ы/2)лЗ

1

м=

Р4 о 1 ^ о иА г.;ртАи о Р1V б',,1 [о и*

Рис. 2. Схема и оценки эффективности распараллеливания Ш-разложения

два вычислительных модуля, использующих арифметику чисел с плавающей точкой фиксированной длины. Также предположим, что модули оснащены стандартными алгоритмами линейной алгебры (включая алгоритмы обращения квадратных матриц методом Гаусса, Ш-разложения и умножения прямоугольных матриц). Напомним три известных факта вычислительной математики: обращение матрицы размера пхп методом Гаусса требует п3 операций; произведение двух пхп матриц также требует п3 операций (без учёта асимптотически более быстрых алгоритмов Штрассена или Копперсмита-Виногра-да); Ш-разложение требует |п3 операций.

Пусть N — четное и Лгд -— N/2. тогда легко видеть (см. оценки трудоёмкости справа на рис. 2), что распределённое обращение «стоит» те же §ЛГ3 арифметических операций, что и при работе одного «вычислителя». К сожалению, такие оценки плохо применимы к символьным вычислениям, т.к. их трудоёмкость зависит ещё от количества цифр в «рациональной записи» операндов. Далее будут представлены только экспериментальные значения временных затрат.

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

Приведенный выше алгоритм LU-разложения был реализован как сценарий «ssmir-lu-1» в среде MathCloud. Он содержит два блока «maxima», которые могут выполняться параллельно. Кроме того, в сценарии присутствует блок «nVW_ ММ_Ьу2х2 », выполняющий параллельное умножение матриц. Данный сценарий был использован в качестве составного сервиса (<<nWV_ ММ _Ьу2х2») в основном сценарии. Таким образом, одновременно работало до четырех экземпляров Maxima.

Для тестирования созданного распределенного приложения, замеров времени работы и, наконец, для демонстрации возможностей системы MathCloud, был создан еще один сценарий. С точки зрения создания «композитных» сценариев, из уже существующих, — это сценарий «третьего уровня вложенности». Здесь, как «библиотечная процедура», используются представленный ранее сценарий LU-разложения, ssmir-lu-1 («Третий» уровень из-за того, что сценарий ssmir-lu-1, в свою очередь, включает сценарий перемножения матриц). В данном сценарии LU-разложение параллельно вычисляется двумя способами: сценарием ssmir-lu-1 и одним процессом Maxima с помощью вызовов get_lu_factors (lu_factor(Ю), производящих собственно LU-разложение, а затем представляющих результат в виде тройки матриц Р, L и U. После вычисления LU-разложений производится сравнение результатов. Часть результатов проведенных численных экспериментов сведена в табл. 1.

Таблица 1. Эффективность распределенного сценария Ш-разложения в МаЛОоис!

N Б81ШГ-1и-1, сек. (мин.) get_lu_f actors асЬог (М) ), сек. (мин.) Ускорение

200 84 (1) 89 (1) 106%

300 270 (5) 388 (6) 144%

400 708 (12) 1132 (19) 160%

500 1575 (26) 2648 (44) 168%

Основные результаты работы

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

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

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

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

Список работ, опубликованных по теме диссертации

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

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

3. Волошинов В., Смирнов С. Программный комплекс для расчета ЯН-индекса публичной политики // Оценка состояния и развития граждан-

ского общества России: Проблемы, инструменты и региональная специфика, Труды ИСА РАН. 2010. Т. 57. С. 80-103.

4. Волошинов В., Неверов В., Смирнов С. Использование распределенной среды REST-сервисов для решения трудоемких вычислительных задач // Материалы XVII Международной конференции по вычислительной механике и современным прикладным программным системам (ВМ-СППС'2011). 2011. С. 235-237.

5. Смирнов С. Сравнительный анализ различных программных средств ввода данных оптимизационных задач в пакеты численных методов // Труды 54-й научной конференции МФТИ «Проблемы фундаментальных и прикладных естественных и технических паук в современном информационном обществе». Инновации и высокие технологии. 2011. С. 35-36.

6. Smirnov S. Using modeling and automatic differentiation tools in a framework for parallel large-scale global optimization / / International Young Scientists Conference "High Performance Computing and Simulation": Book of abstracts. 2012. P. 79.

7. Смирнов С. Применение алгебраических языков моделирования в системе распределённого решения задач глобальной оптимизации // Труды 53-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук». Т. 9. 2010. С. 55-56.

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

9. Smirnov S. On Development of RESTful web Service for a Computer Algebra System in MathCIoud Environment // Distributed Computing and Grid-Tech-

nologies in Science and Education: Proceedings of the 4th Intern. Conf. 2010. Pp. 230-235.

10. Смирнов С. Прототип компьютерной системы для визуализации и моделирования молекулярных кластеров с использованием вычислительного комплекса BNB-Grid // Труды 51-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук». Т. 9. 2008. С. 10-12.

11. Смирнов С. Распределенный программный комплекс для моделирования структуры молекулярных соединений // Сб. трудов III Международной научно-практической конференции «Современные информационные технологии и ИТ-образование». Под редакцией проф. В. А. Сухомлина. 2008.

12. Voloshinov V., Smirnov S. Error-free inversion of ill-conditioned matrices in distributed computing system of RESTful-services of computer algebra //Distributed Computing and Grid-Technologies in Science and Education: Book of Abstr. of the 4th Intern. Conf. 2010.

13. Voloshinov V., Smirnov S. Error-free inversion of ill-conditioned matrices in distributed computing system of RESTful-services of computer algebra // Distributed Computing and Grid-Technologies in Science and Education: Proceedings of the 4th Intern. Conf. 2010. Pp. 257-263.

14. Волошинов В., Смирнов С. Безошибочное обращение плохо обусловленных матриц в распределенной среде RESTful веб-сервисов символьных вычислений // Современные информационные технологии и ИТ-образование. Сборник докладов научно-практической конференции: учебно-методическое пособие. Под ред. проф. В.А. Сухомлина. 2010. С. 595-603.

Подписано в печать:

13.11.2012

Заказ № 7844 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 vvww.autoreferat.ru

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

Введение

Глава 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. Полученные результаты применены для решения модельных и прикладных задач и внедрены в практику.

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.