Наименование
проекта
Программная
система параллельных вычислений в задачах выбора глобально-оптимальных решений
“Абсолют Эксперт”
Краткое
описание
Программная
система “Абсолют Эксперт” предназначена для параллельного решения сложных задач
глобальной оптимизации, отличающихся многоэкстремальным характером
критериев и ограничений, существенной вычислительной трудоемкостью
функционалов, невыпуклостью и многосвязностью области поиска и др.
Задачи подобного вида широко распространены в различных областях науки и техники
(идентификация, восстановление зависимостей, оптимальное проектирование,
моделирование и т.п.). Возможность построения численных оценок решений таких
задач при реалистических временных затратах может быть обеспечена только при
применении самых эффективных методов глобального поиска и использовании
современных средств высокопроизводительной вычислительной
техники.
Алгоритмическую
основу системы составляет вычислительная схема редукции размерности, позволяющая
сводить решение многомерных задач к решению задач одномерной оптимизации.
Оптимизация получаемых в результате редукции многоэкстремальных задач
обеспечивается информационно-статистическими алгоритмами глобального поиска,
эффективность которых неоднократно подтверждалась в практических приложениях.
Возможность
параллельных вычислений обеспечивается применением множественных разверток типа
кривой Пеано, позволяющих порождать для решаемых многомерных задач семейства
информационно-совместимых задач одномерной оптимизации. Получаемые в результате
одномерные задачи могут решаться параллельно, при этом может быть обеспечено
совместное использование всей поисковой информации, порождаемой в процессе
вычислений. Подобная схема параллельных вычислений не требует каких-либо средств
единого управления и характеризуется высокими показателями масштабируемости и
надежности.
Цели проекта
Целью
проекта является разработка программного комплекса, позволяющего ставить и
решать (исследовать) задачи выбора оптимального варианта, моделью которых может
являться задача многокритериальной оптимизации, в которой критерии определены на
многомерном гиперпараллелепипеде с возможно наложенными функциональными
ограничениями.
Задачи
проекта:
- разработка расчетного приложения на основе последовательных
версий обобщенного алгоритма глобального поиска и индексного метода с одной и
множественными развертками;
-
разработка
расчетного приложения на основе параллельных версий (для систем на
распределенной памяти в первую очередь, для систем на общей памяти во вторую)
обобщенного алгоритма глобального поиска и индексного метода с одной и
множественными развертками;
- разработка
графического приложения, позволяющего выполнять постановку задачи оптимизации,
настройку методов поиска, динамическое отображение процесса поиска, в том числе
при параллельном решении;
-
реализация
интерфейса динамического обмена информацией между расчетным и графическим
приложениями.
Дополнительной
важной задачей проекта является реализация системы по принципу открытой
архитектуры, позволяющей максимально просто добавлять новую функциональность,
заменять имеющиеся модули и подсистемы. Решение данной задачи призвано
обеспечить возможность проведения сравнительных исследований по эффективности
различных механизмов внутренней реализации системы.
Коллектив
- Гергель Виктор Павлович, д.т.н.,
профессор, зам. зав. каф. МО ЭВМ. Научный руководитель.
- Сысоев Александр Владимирович,
ассистент каф. МО ЭВМ. Руководитель проекта.
- Виноградов Роман, магистр 2-го года
обучения. Исследователь.
- Рябов Василий, магистр 1-го года
обучения. Исследователь.
- Сидоров Сергей, магистр 1-го года
обучения. Исследователь.
- Субботина Екатерина, студентка 4-го курса.
Исследователь.
Текущие исследования
В настоящий
момент разработаны:
- реализации (последовательные и
параллельные
на
основе MPI) обобщенного алгоритма глобального поиска,
индексного метода с одной разверткой и индексного метода с множественными
развертками;
-
несколько
вариантов подсистем хранения и обработки поисковой
информации;
- первая версия графического
приложения, включая интерфейс динамического обмена информацией между
расчетной частью системы (функционирующей в параллельном режиме на системах с
распределенной
памятью)
и графическим приложением;
- первая версия автоматизированной подсистемы
тестирования реализаций методов.
Ведутся работы по направлениям:
- Разработка
и реализация параллельных версий существующих алгоритмов для использования в
системах с общей памятью (на основе технологии OpenMP).
Это направление может рассматриваться и как создание версий алгоритмов,
предназначенных непосредственно для многопроцессорных/многоядерных
вычислительных систем, и как необходимое условие для реализации следующего
направления.
-
Общее развитие и оптимизация программного комплекса, включая повышение
эффективности подсистемы обработки поисковой информации, расширение возможностей
визуальной подсистемы, реализацию техник и модификаций, повышающих эффективность
методов поиска.
Планируются работы по направлениям:
- Разработка
и реализация гибридных параллельных схем, предназначенных для кластеров с
SMP-узлами.
С учетом массового внедрения многоядерных архитектур очевидна перспектива
повсеместного распространения гетерогенных кластеров. Данное направление имеет
целью использовать дополнительные мощности, появляющиеся на каждом
вычислительном узле.
- Портирование
программного комплекса под 64-битные операционные системы. Необходимость данного
шага вызвана тем фактом, что в процессе решения оптимизационной задачи
происходит непрерывное накопление массива поисковой информации, на основе
которой на каждой итерации метода поиска делается выбор очередной точки
испытания. В многомерных задачах (уже при размерности порядка 10) объем
поисковой информации может превышать размеры виртуального адресного пространства
процесса в 32-разрядных операционных системах
- Реализация приложения, визуализирующего схему
межпроцессорного взаимодействия по собранной трассе и ход вычислений на каждом
процессе (для учебных и тестовых целей).
Публикации
- Sysoyev
A.V. Program system of parallel computations for solving the tasks of
global-optimum choice. VI International Congress on Mathematical Modeling/Book
of abstracts, 2004, p. 62.
- Сысоев
А.В. О проблеме расчета функционалов в программных системах глобальной
оптимизации. Труды Всероссийской конференции студентов, аспирантов и молодых
ученых “Технологии Microsoft в теории и практике программирования”,
2005,
М.: МГТУ им. Н.Э. Баумана, стр. 57.
- Сысоев А.В., Сидоров С.В.
Использование чисел расширенной точности в реализации индексного метода поиска
глобально-оптимальных решений. (Принято для опубликования в материалах пятого
Международного научно-практического семинара “Высокопроизводительные
параллельные вычисления на кластерных системах”, 2005).
- Рябов В.В., Сысоев А.В. Алгоритмы принятия
глобально-оптимальных решений и их модификации. Материалы
конференции “Технологии Microsoft в теории и практике программирования”,
2006, Н. Новгород, стр. 266 - 269.
- Сидоров С.В., Сысоев А.В. О распараллеливании
индексного метода поиска глобально-оптимальных решений. Материалы
конференции “Технологии Microsoft в теории и практике программирования”,
2006, Н. Новгород, стр. 273 - 276.
- Субботина Е.В., Сысоев А.В. Способы организации поисковой
информации в программной системе параллельного решения задач
глобально-оптимального выбора. Материалы конференции “Технологии
Microsoft в теории и практике программирования”, 2006, Н. Новгород,
стр. 284 - 288.
Материалы
- Презентация проекта
Участие в конференциях и семинарах
- VI International Congress on
Mathematical Modeling, Нижний Новгород, 2004.
- Всероссийская конференция студентов,
аспирантов и молодых ученых “Технологии Microsoft в теории и практике
программирования”, Москва, 2005.
- V Международный научно-практический
семинар “Высокопроизводительные параллельные вычисления на кластерных
системах”, Нижний Новгород, 2005.
- Конференция студентов, аспирантов и молодых ученых
“Технологии Microsoft в теории и практике программирования”, Нижний
Новгород, 2006