в рамках Конкурса компании Intel по финансированию перспективных научных исследований (2001 г.)

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

Основные результаты выполнения проекта состоят в следующем:

·  Сформирован важный класс вычислительно-трудоемких задач (задачи интегрирования, поиска глобально-оптимальных решений сложных многоэкстремальных функций при невыпуклых ограничениях, решение систем нелинейных уравнений, восстановления зависимостей, построения множества неулучшаемых решений в многокритериальных задачах принятия решений), которые могут быть эффективно решены на многомашинных системах кластерного типа;

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

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

·  Разработана программная система “Абсолют Эксперт”, предназначенная для параллельного решения задач выбора глобально-оптимальных вариантов, модель которых может быть представлена в виде набора оптимизируемых критериев и множества функционалов-ограничений, заданных на многомерном пространстве непрерывных и дискретных параметров. Алгоритмическую основу системы составляет вычислительная схема редукции размерности, позволяющая сводить решение многомерных задач к решению задач одномерной оптимизации. Возможность параллельных вычислений обеспечивается применением множественных разверток типа кривой Пеано, позволяющих порождать для исходных многомерных задач семейства информационно-совместимых задач одномерной оптимизации, дальнейшее решение которых обеспечивается информационно-статистическими алгоритмами глобального поиска.

С использованием системы был решен ряд тестовых задач с размерностями от двух до пяти.

Также была исследована задача идентификации параметров производственного блока модели экономики России, разрабатываемая в ВЦ РАН для оценки динамики теневого оборота в 1995-2003 гг. В задаче введены ряд функционалов (производственных функций), общее число параметров в которых равно 12. На основе функционалов формируются два ограничения и критерий, основанный на предположении, что производитель функционирует с целью максимизации его капитализации.

В результате решения задачи с использованием системы “Абсолют Эксперт” была получена оптимальная точка, лучшая, чем найденная полным перебором на сетке с 8 точками на размерность. При этом время решения на кластере ННГУ составило 80 секунд вместо 4 часов на 512 процессорах суперкомпьютера МВС-1000М при использовании метода перебора.

<< вернуться  |   Документ от: 24.08.2005 20:23