Отчет ИВМ СО РАН за 2013 год

Программа № 15 «Информационные, управляющие и интеллектуальные технологии и системы»

Блок 1. Развитие и программная реализация методов концептуального OLAP-моделирования при конструировании сложных систем.

С целью поддержки адаптивного манипулирования объектами анализа OLAP (on-line analitical processing) на основе концептуальной аналитической модели разработаны методические и алгоритмические средства представления и применения знаний о кубах-концептах. Предложена продукционная модель представления знаний о кубах-концептах, упорядоченных отношением Галуа в виде концептуальной решетки кубов. Модель основана на свойствах концептуальной решетки, согласно которым: надкуб любого куба-концепта решетки содержит наибольший объем (множество показателей) и наименьшее содержание (множество измерений), а подкуб, наоборот — содержит наибольшее содержание и наименьший объем. То есть, при переходе по ребру решетки от подкуба к надкубу происходит расширение объема и сокращение содержания и аналогично, при переходе по ребру решетки от надкуба к подкубу происходит сокращение объема и расширение содержания. Таким образом, модель правил, представляющая концептуальную решетку многомерных кубов, отражает отношения между кубами-концептами решетки и между объемом и содержанием кубов-концептов.

Разработан алгоритм определения оптимального куба-концепта для частной аналитической задачи на множестве всех доступных объектов анализа предметной области. Алгоритм заключается в последовательном добавлении объектов анализа в пользовательский запрос и определении объема и содержания оптимального куба-концепта на основе применения правил вывода. Возможность выявления аналитических зависимостей между объектами анализа позволяет значительно повысить эффективность аналитической обработки данных и способствует обнаружению новых знаний для принятия управленческих решений.

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

Решена задача динамического отображения данных об объектах мониторинга на электронной карте. Автоматически формируется информационная карточка объекта мониторинга с отображением текущих значений показателей гиперкуба данных для фиксированных значений измерений. Информационная карточка отображается для объектов картографических слоев, к которым была осуществлена картографическая привязка многомерных данных, или к объектам динамически сформированных виртуальных слоев. Для выполнения нового среза гиперкуба в составе средств геомоделирования разработан блок управления многомерных данных. Блок управления исполняет роль фильтра для фиксации представляющих аналитический интерес измерений. Разработан инструмент для построения картограмм, соответствующих значениям наиболее значимого измерения.

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

Блок 3. Разработка средств поддержки размещения заказов.

Продолжены работы по доработке и развитию автоматизированной системы поддержки процессов планирования, размещения и контроля муниципального заказа (АСП МЗ ) в связи с изменениями действующего законодательства. В связи с принятием и ожидаемым вступлением в действие Федерального закона от 05.04.2013 года № 44-ФЗ осуществлена модернизация системы в части поддержки новых способов закупок, изменения справочников и классификаторов, доработки пользовательского интерфейса. Для системы разработаны средства автоматизированного обновления программного обеспечения, а также модернизирован протокол пакетного обмена данными с целью контроля используемых версий программного обеспечения. Новая версия системы подготовлена к опытной эксплуатации в муниципальных учреждениях г. Красноярска.

В рамках доработки системы в АСП МЗ внедрены средства контроля корректности использования символов различных алфавитов в описании закупок и свойствах лотов. Указанные средства обнаруживают признаки некорректного ввода и блокируют дальнейшую работу пользователя до исправления ошибок.

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

(Отделы Прикладной информатики, Информационно-телекоммуникационных технологий)

Программа № 18 «Алгоритмы и математическое обеспечение для вычислительных систем сверхвысокой производительности»

Блок 1. Вычислительные алгоритмы для решения уравнений Навье-Стокса вязкого теплопроводного газа.

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

В качестве тестовой задачи рассмотрено сверхзвуковое обтекание клина в двумерном канале вязким теплопроводным газом. Применение нового метода не требует согласования триангуляций на соседних временных слоях. Это значительно облегчает динамическое разрежение или сгущение триангуляций по пространству для оптимизации вычислительной работы или улучшения аппроксимации в пограничных слоях и ударных волнах. Для решения систем алгебраических уравнений ввиду значительного диагонального преобладания использовался метод Якоби в комбинации с внешними итерациями по нелинейности. Созданный метод реализован для высокопроизводительных вычислительных систем. Полученный пакет программ позволяет проводить численные эксперименты в широком диапазоне чисел Маха и Рейнольдса.

На рис. IV.1 показано распределение плотности газа в канале. Числа Маха и Рейнольдса равны соответственно M = 4 и Re = 400. Состояния соответствуют моментам времени t = 6.0 (a) и t = 20.0 (b) (В. В. Шайдуров, Г. И. Щепановская, М. В. Якубович).

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

Для OpenMP-версии алгоритма проведено исследование влияния технологии HyperThreading, зависимости ускорения от размерности задачи и количества используемых потоков. Анализ результатов показал следующие особенности.

1. Накладные расходы, связанные с синхронизацией в OpenMP-версии, невелики.

2. Для получения максимального ускорения OpenMP-версии программы выгодно использовать технологию HyperThreading (HT) с загрузкой максимально возможного количества логических ядер. При имеющихся в нашем распоряжении 12-ти физических ядрах программе было доступно максимально 24 логических ядра при включенной HT и 12 — при выключенной. Эксперименты показали, что время выполнения программы на 24 нитях при включенной HT в среднем на 14 % меньше времени выполнения этой же программы на 12-ти нитях без технологии HT (рис. IV.2).

3. Использование оптимизации компилятора существенно (больше, чем в 2 раза) уменьшает время работы последовательной программы (табл. IV.1). Поскольку компилятор никак не оптимизирует код CUDA, то время выполнения CUDA-версий программы не зависело от опций компиляции (табл. IV.1).

В табл. IV.1 и на рис. IV.3 приведены данные по ускорению нескольких параллельных OpenMP- и CUDA-версий программ.

Версия	Размерность сетки (количество шагов по времени)
Версия	80*80 (400)	160*160 (800)	320*320 (1600)	640*640 (3200)	1280*1280 (6400)
последовательная, без оптимизации	20.16	159.40	1268.46	10107.80	*
последовательная, оптимизация O2	9.99	78.97	626.72	4980.61	39598.90
последовательная, оптимизация O3	9.87	78.08	619.80	4936.25	39202.91
OpenMP(12)**, без оптимизации и HT	1.98	12.52	103.45	819.06	6519.87
OpenMP(12)**, оптимизация O2 без HT	0.92	7.13	56.10	444.15	3535.53
OpenMP(24)**, с оптимизацией O2 и HT	0.91	6.17	49.93	388.20	3080.91
CUDA версия 1	2.55	13.06	74.02	***	***
CUDA версия 2	3.20	8.27	42.60	308.82	***
* — результат за разумное время не получен. — приведены результаты на 12-ти нитях при отключенной технологии HT и на 24 — при включенной HT. * — не удалось запустить ядро из-за нехватки количества регистров.

Таблица IV.1. Время выполнения различных версий программы

Следует отметить, что потенциал оптимизации CUDA-версий программы пока не исчерпан. Прежде всего, планируется оптимизировать расчет параметров запуска ядра, в том числе с использованием специального инструмента CUDA Occupancy Calculator, который предоставляет возможность рассчитать оптимальную загрузку GPU, исходя из его архитектуры, количества потоков в блоке, количества блоков в сетке, размера используемой распределенной памяти, числа регистров на поток. Кроме того, при больших размерностях расчетных сеток возникает типичная для CUDA проблема аппаратного ограничения количества регистров на массиве потоковых мультипроцессоров (Streaming Multiprocessor, SM). Решение данной проблемы — это оптимизация кода с целью уменьшения количества требующихся регистров GPU и использование нескольких видеокарт.

На первый взгляд сравнение технологий OpenMP и CUDA применительно к нашему алгоритму демонстрирует преимущества OpenMP. Однако хочется заметить следующее. Некорректно сравнивать количество ядер GPU (в нашем случае 448 ядра на видеокарту) и количество ядер CPU (у нас 12 физических или 24 логических ядра). В архитектуре ядра GPU можно найти только один аналог составляющих ядра CPU — арифметико-логическое устройство. Правильнее сравнить ядро CPU c потоковым мультипроцессором (SM), который кроме ядер GPU содержит такие признаки ядра CPU, как разнообразные устройства управления и иерархию памяти. При этом следует также учитывать, что архитектура SM на GPU создавалась под работу с графикой, тогда как архитектура CPU оптимизирована в некотором смысле универсально, для работы с огромным числом приложений.

Таким образом, в нашем исследовании проводилось сравнение технологии OpenMP на 12 ядрах CPU и технологии NVIDEA CUDA на 14 потоковых мультипроцессорах. В таком ракурсе наши результаты с учетом дальнейшего развития CUDA-версий следует интерпретировать как выигрышные для графических процессоров (Е. Д. Карепова, Е. В. Дементьева, А. А. Ефремов).

Рис. IV.2. Время выполнения OpenMP-версии программы (основная ось) и достигнутое ускорение относительно лучшей последовательной версии (дополнительная ось). Сравнение расчетов при включенной и выключенной поддержке технологии HyperThreading

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

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

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

Рис. IV.4. Волновые картины в задаче Лэмба для блочной среды с упругими прослойками: линии уровня нормального напряжения; а — массив из 6 блоков, б — массив из 15 блоков

Расчеты в полной постановке были выполнены по программе 2Dyn_Granular на многопроцессорном кластере МВС-100К Межведомственного суперкомпьютерного центра РАН. Сравнение показало хорошее соответствие результатов, но при этом расчеты на кластере с применением MPI из-за большой размерности разностной сетки в прослойках потребовали на порядок большего времени, чем расчеты по упрощенной модели на GPU с применением технологии CUDA.

На рис. IV.5 приведены результаты расчетов на GPU задачи Лэмба с касательной нагрузкой для многоблочной среды на основе упрощенной модели, которые показали, что увеличение числа блоков приводит к появлению за фронтом падающей поперечной волны размытого волнового фронта, связанного с передачей вращательного движения блоков. Это служит подтверждением того, что многоблочную среду с податливыми прослойками можно приблизить обобщенным континуумом, в уравнениях которого учитывается несимметрия тензора напряжений, вызванная вращательным движением блоков, и моментные напряжения, связанные с искривлением регулярной блочной структуры из-за неоднородности вращений.

Задача об импульсном воздействии на блочную упругую среду решалась на основе двумерных и пространственных уравнений моментного континуума Коссера с помощью программ 2Dyn_Cosserat и 3Dyn_Cosserat, зарегистрированных в Роспатенте. Были обнаружены специфические низкочастотные маятниковые волны, вызванные не поступательным перемещением, а вращением блоков. Установлено, что осредненная модель и модель моментного континуума Коссера дают качественно близкие волновые картины, если толщина прослоек много меньше характерного размера блоков.

Получено пространственно одномерное точное решение задачи о сдвиговом деформировании слоя вязкоупругой моментной среды под действием периодического изменения скорости на границе. Анализ амплитудно-частотных характеристик выявил наличие резонансного пика касательного напряжения на частоте собственных колебаний вращательного движения блоков, не зависящей от толщины слоя. В серии расчетов трехмерной задачи для массива моментной среды показано, что при периодическом изменении локализованного вращательного момента на границе на частоте собственных колебаний происходит резонансное возбуждение среды, которое проявляется в увеличении амплитуды угловой скорости и меньшем ослаблении волны по мере ее распространения вглубь массива по сравнению с нерезонансными частотами (рис. IV.6) (В. М. Садовский, О. В. Садовская, М. П. Варыгина, М. А. Похабова).

Рис. IV.6. Пространственная задача о периодическом действии сосредоточенного вращательного момента: схема нагружения (а) и поверхности уровня угловой скорости для резонансной (б) и нерезонансной (в) частот

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

(Отделы Вычислительной математики, Вычислительной механики деформируемых сред)

Отчет ИВМ СО РАН за 2013 год

Программы фундаментальных исследований Президиума РАН