Коллектив

• Мееров И.Б.– научный руководитель
• Линёв А.В.
• Сысоев А.В.
• Козинов Е.А.
• Лебедев И.Г.
• Лебедев С.А.
• Малова А.Ю.
• Сысоева Т.А.
• Филиппенко С.С.

Цель проекта

Долгосрочная цель проекта заключается в создании собственного высокопроизводительного прямого решателя разреженных СЛАУ большой размерности с симметричной положительно определенной матрицей, ориентированного на современные вычислительные системы, включая системы с гетерогенной архитектурой (в настоящий момент на базе GPU), а далее, возможно, на базе Intel® Many Integrated Core.

Результаты

В рамках НИР получены следующие основные результаты:

1. Определен набор сторонних прямых решателей для сравнения производительности. Используются широко распространенные открытые решатели SuperLU и MUMPS, а также один из наиболее быстрых коммерческих решателей Intel MKL PARDISO.
2. Выбраны тестовые наборы данных – симметричные положительно определенные матрицы из коллекции университета Флориды.
3. Разработан прототип прямого решателя (последовательная версия). За отчетный период выполнена модификация решателя с целью улучшения производительности.  Доработан алгоритм переупорядочивания,  реализованы усовершенствованные алгоритмы выполнения символической фазы разложения Холецкого, в том числе алгоритм определения числа ненулевых элементов и несколько алгоритмов выделения «супернодов», включая алгоритм выделения «ослабленных супернодов» (relaxed supernode) с возможностью настройки степени огрубления (добавления нулевых элементов в структуру матрицы). Реализован алгоритм выполнения численной фазы разложения Холецкого, основанный на супернодальном подходе. Обеспечена интеграция с функциями BLAS из библиотеки Intel MKL. Для базовой версии отлажена параллельная реализация, выполнена первая попытка построения параллельной версии для супернодальной версии.
4. Cобраны и проанализированы результаты вычислительных экспериментов, в частности результаты работы собственного и сторонних решателей в различных версиях алгоритмов на тестовых наборах данных. Анализ результатов экспериментов, как и следовало ожидать, подтвердил информацию об определяющем влиянии стадии переупорядочивания на время работы численной фазы и требования по памяти, а также наибольший вклад численной фазы в суммарное время работы. Результаты показали, что последовательная версия решателя авторов на большинстве тестовых задач опережает по скорости решатель SuperLU, но проигрывает решателям MUMPS и Intel MKL PARDISO при N 105 – 106. Отставание зависит от задачи. Для некоторых задач оно составляет 1,5-5 раз, что наряду со сравнением с SuperLU подтверждает качество текущей реализации и оставляет хорошие шансы  на ее дальнейшее развитие. Для некоторых задач время работы на тестовой системе оказывается существенно хуже, что вызвано требованиями по памяти, превышающими имеющиеся возможности (16GB). В дальнейшем планируется продолжить работы по уменьшению требований по памяти, как путем улучшения алгоритма переупорядочивания для сокращения заполненности портрета фактора, так и путем оптимизации программной реализации численной фазы разложения Холецкого.
5. Определены направления дальнейших исследований. Работу предполагается вести в следующих направлениях:
   - реализация многоуровневого переупорядочивателя на базе метода вложенных сечений с возможным подключением алгоритма минимальной степени (в одной из версий) на некотором шаге метода.
   - оптимизация численной фазы разложения Холецкого.
   - распараллеливание численной фазы разложения Холецкого (супернодальный подход) для систем с общей памятью.
6. Текущие результаты работы доложены на международной научно-практической конференции «Современные информационные технологии и ИТ-образование» (Долгопрудный, МФТИ, 9-10 ноября 2011г.) и ХI всероссийской конференции «Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, ННГУ, 1–3 ноября 2011г.; тезисы доклада опубликованы в материалах конференции).

<< вернуться  |   Документ от: 24.01.2012 11:31