Научная работа

Научная школа “Информационно-вычислительные технологии” действует с начала 90-х годов XX века и развивается на кафедре ЮНЕСКО по новым информационным технологиям математического факультета КемГУ. Ее руководителем с момента основания является профессор К. Е. Афанасьев. В настоящее время школа объединяет 24 научно-педагогических работника и обучающихся в университете, в том числе 1 доктора наук, 10 кандидатов наук, 6 аспирантов.

Численные методы

Обобщенный метод естественных соседей (Natural Element Method – NEM)

Метод сглаженных частиц (Smoothed Partical Hydrodinamics - SPH)

CИСТЕМЫ ПОДДЕРЖКИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

Информационно-вычислительный портал

Система удаленного доступа и управления распределенными вычислительными ресурсами

Виртуальная лаборатория

Система автоматического контроля корректности MPI-программ

Система оптимизации UPC-программ

Численные методы

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

Обобщенный метод естественных соседей (Natural Element Method – NEM)

К общим недостаткам бессеточных методов можно отнести сравнительно невысокую точность и трудность введения граничных условий. В стандартных бессеточных методах для построения интерполяционных функций дополнительно требуется обеспечить узловую связность. В связи с этим стали разрабатываться методы, сочетающие в себе сеточный и бессеточный подходы и использующие преимущества каждой из методологий. Характерными представителями этой группы методов являются бессеточный метод конечных элементов (Meshless Finite Element Method) и метод естественных соседей (Natural Element Method). Методы MFEM и NEM сохраняют преимущества классического метода конечных элементов, такие как простота функции формы в области определения, непрерывность между элементами, простота введения граничных условий. При этом эти методы имеют все преимущества бессеточных методов в силу того, что функции формы MFEM и NEM зависят только от положения узловых точек. В основе метода естественных соседей и бессеточного метода конечных элементов лежит метод Галеркина в слабой форме. Для интерполяции неизвестных функций используются соответственно функции формы Сибсона и Лапласа, базирующиеся на понятии естественных соседей.

Задачи, решенные с помощью данного метода:

Задача Л.В. Овсянникова о деформации жидкого эллипса

Движение вязкой жидкости в квадратной каверне с движущейся крышкой

Колебания жидкости в прямоугольном бассейне

Задача об обрушении столба жидкости

Задача об обрушении плотины при наличии слоя жидкости на основании

 

Задача о взаимодействии жидкости с горизонтальной поверхностью

Метод сглаженных частиц(Smoothed Partical Hydrodinamics - SPH)

Специфика бессеточных методов заключается в том, что для построения функций формы на разных временных шагах используются различные наборы расчетных узлов, которые могут свободно перемещаться, ввиду отсутствия между ними жестких связей. Вследствие этого, наиболее целесообразно использовать эти методы для решения тех задач, где область расчета подвергается значительными деформациям.
Одним из наиболее распространенных методов, относящихся к классу бессеточных, является метод сглаженных частиц – SPH (Smoothed Particle Hydrodynamics). В методе частиц знание связей между узлами не требуется ни на одном этапе численного решения задач, что обусловливает ряд его преимуществ перед другими методами, классифицируемыми как бессеточные, а именно:

¾ относительная простота программной реализации, ввиду отсутствия потребности в использовании сложных алгоритмов численного интегрирования, построения или адаптации сетки;

¾ использование простых в реализации алгоритмов определения свободных границ и границ раздела;

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

Задачи, решенные с помощью данного метода:

Задача Л.В. Овсянникова о деформации жидкого эллипса

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

 

Задача о падении капли в жидкость

В бассейн, заполненный несжимаемой жидкостью, падает капля жидкости той же плотности в поле силы тяжести.

Задача о разрушении плотины

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

Задача о всплытии бесконечного цилиндра с круглой формой основания в жидкости

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

Задача о входе и погружении бесконечного цилиндра с круглой формой основания в жидкость.

В бассейн, заполненный несжимаемой жидкостью, падает твердый цилиндр с круглой формой основания в поле силы тяжести.

Задача о входе и погружении бесконечного цилиндра с квадратной формой основания в жидкость.

CИСТЕМЫ ПОДДЕРЖКИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

Информационно-вычислительный портал

На протяжении нескольких последних лет на кафедре ЮНЕСКО по НИТ под руководством Константина Евгеньевича Афанасьева разрабатывается проект под названием «Информационно-вычислительный портал» (ИВП). Сайт проекта - icp.kemsu.ru. ИВП выступает платформой для интеграции нескольких информационных систем, образующих единый программный комплекс, позволяющий пользователю решать широкий перечень задач по разработке и оптимизации параллельных программ.

Состав ИВП:

¾    системаудаленного доступа и управления распределенными вычислительными ресурсами (УД и УРВР);

¾    система отладки MPI-программ;

¾    система оптимизации UPC-программ;

¾    система «Виртуальная лаборатория».

Все перечисленные компоненты являются авторскими разработками, выполненными под руководством К.Е. Афанасьева.

Основой ИВП является система УД и УРВР, предназначенная для организации проведения численного эксперимента на вычислительных ресурсах, предоставляемых по запросу пользователя в удаленном режиме.

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

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

Система «Виртуальная лаборатория»используется в качестве средства для анализа зависимости ускорения и эффективности параллельной программы от значений различных параметров задачи.

Рис. Структура информационно-вычислительного портала

Система удаленного доступа и управления распределенными вычислительными ресурсами

Система сочетает в себе возможности удаленного доступа и пакетной обработки заданий с графическим интерфейсом пользователя (свидетельство о государственной регистрации программы для ЭВМ №2008611206). Для обеспечения заданной функциональности в системе реализованы следующие возможности:

¾    хранение файлов пользовательских расчетных программ в виде исходного и/или бинарного кода, файлов начальных данных, результатов и другой информации;

¾    передача файлов с кодами программ, начальными данными или результатами между пользовательским приложением и базой данных (БД);

¾    создание, удаление и управление пользователем своими объектами (файлами, расчетами);

¾    хранение информации о доступных вычислительных ресурсах;

¾    отслеживание состояния расчетных программ на удаленных вычислительных ресурсах;

¾    определение очередности запуска программ;

¾    предоставление пользователю удобного web-интерфейса.

Система УД и УРВР построена по «клиент-серверной» архитектуре (рис. 1). Логически систему можно разбить на 2 взаимодействующие части:

¾    Система управления распределенными вычислительными ресурсами (СУ РВР). Она отслеживает состояние кластеров, загружает на них новые задания и сохраняет результаты. В эту подсистему входят менеджер вычислительных ресурсов, БД и кластерные агенты.

¾    Система удаленного доступа к распределенным вычислительным ресурсам (СУД РВР). Ее задача – предоставить пользователю интерфейс для размещения новых заданий в БД и получения результатов. Данная подсистема реализована с помощью web-доступа через специальный сервер приложений и включает в себя также интерфейс к системе отладки и «виртуальной лаборатории».

 

Рис. Архитектура СУД и УРВР

 

Для работы с системой используется web-браузер. Хранение пользовательской и служебной информации осуществляется на сервере БД. Пользователь взаимодействует с базой при помощи сервера приложений, который является промежуточным звеном в СУ РВР, выполняющим обращение к серверу БД и обработку данных перед их представлением пользователю. Сервер БД также участвует в обработке данных посредством хранимых процедур и функций.

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

На систему получено свидетельство о регистрации программы для ЭВМ в органе «Роспатент».

Рис. Свидетельства о регистрации СУД и УРВР и базы данных ИВП

Виртуальная лаборатория

Основным направлением использования данной подсистемы является исследование эффективности параллельных программ и получения сведений для их дальнейшей оптимизации. Через web-интерфейс пользователь загружает свою параллельную программу в систему, задает набор параметров исследования, а также диапазон их значений, и отправляет задачу на запуск. Система самостоятельно формирует последовательность запусков исследуемой программы с различными комбинациями параметров, выполняет расчеты и производит анализ зависимости времени и результатов выполнения программы от параметров запуска. Следует отметить, что один численный алгоритм может быть скомпилирован различными компиляторами для выполнения на кластерах с разными операционными системами и вычислительными архитектурами. Таким образом, система позволяет сравнивать эффективность выполнения программ в различных вычислительных средах. Результаты расчетов представляются в виде таблицы, с указанием всех использованных при запуске параметров. Блок анализа результатов вычислений позволяет получить значения эффективности и ускорения по выбранным пользователем расчетам, а также построить диаграммы, отражающие зависимость времени выполнения от набора использованных при запуске параметров. Результатом анализа является вывод о степени влияния каждого параметра параллельной программы на ее эффективность.

Другое направление использования данной системы – учебный процесс. «Виртуальной лабораторией» могут пользоваться студенты и преподаватели в рамках обучения курсам, связанным с высокопроизводительными вычислениями. Система позволяет организовать проведение виртуального лабораторного практикума студентов, у которых появляется возможность запускать учебные программы на реальных высокопроизводительных ресурсах. Задача обучающихся состоит в том, чтобы протестировать параллельную программу (написанную самостоятельно или предоставленную преподавателем) с использованием различного ПО, различных вычислительных ресурсов и входных параметров задания (может варьироваться число вычислительных узлов кластера, размерность матрицы в задачах линейной алгебры и пр.) По полученным экспериментальным данным студент должен построить графики ускорения и эффективности и сделать выводы.

Система автоматического контроля корректности MPI-программ

Все множество специфических ошибок, свойственных MPI-программам, можно разделить на 2 больших группы:

-          Локальные, возникающие в пределах только одного MPI-процесса.

-          Глобальные, следующие из взаимодействия нескольких MPI-процессов.

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

На рисунке изображена компонентная модель создаваемой программной системы. Для многих коммуникационных функций стандарта MPI в системе существует ряд проверок на появление глобальных и локальных ошибок. Локальные ошибки в пределах каждого MPI-процесса отыскиваются служебным потоком. Обнаружением глобальных ошибок занимаются серверы-анализаторы, которым MPI-процессы передают параметры вызываемых функций для обработки. Масштабируемость системы достигается благодаря тому, что таких серверов-анализаторов может быть множество и работа по обнаружению глобальных ошибок распределяется по всем серверам.

Рис. Компонентная модель системы отладки

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

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

На одной группе узлов кластера runner посредством ssh запускает процессы-анализаторы analyze.exe, а на другой – MPI-программу при помощи mpiexec. В функции MPI_Init порождается дополнительный служебный поток, занимающийся обнаружением локальных ошибок. Благодаря многоядерности современных процессоров, основной поток MPI-процесса, выполняющий действия пользователя, и служебный поток могут работать на разных ядрах. Поскольку нити работают асинхронно, то для обеспечения взаимодействия между ними в систему введена «очередь заданий», в которую при вызове MPI-функции добавляется тот или иной набор заданий на проверку возникновения локальных ошибок. Служебный поток при появлении заданий в очереди вынимает их и выполняет соответствующие действия. Кроме того, в функции MPI_Init каждый из процессов устанавливает 2 соединения с соответствующим сервером-анализатором. При этом распределение ветвей параллельного приложения по серверам происходит наиболее равномерным образом. Для каждого процесса из обслуживаемых некоторым сервером в пределах analyze.exe создается по одному потоку.

При вызове в параллельной программе многих коммуникационных операций их параметры передаются одной строкой на соответствующий сервер. Таких посылок MPI-процесс отправляет две: перед фактическим вызовом операции (PMPI-функции) и после неё. «Закрепленный» за данным процессом поток сервера производит парсинг принятой строки и заполняет элемент основной структуры данных сервера – списка сообщений (рис. 2). Затем на сервере производится ряд проверок, в ходе которых просматривается список сообщений, и выявляются глобальные ошибки. Если функция отработала корректно и посылка была успешно передана от отправителя получателю в случае операции точка-точка или все участвующие в групповой операции процессы отправили/получили свои порции данных, то соответствующие элементы списка удаляются.

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

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

В настоящее время разработаны алгоритмы для обнаружения системой следующих типов ошибок.

Локальные:

-                     процесс не вызвал одну или обе обязательные функции MPI_Initи MPI_Finalize;

-                     вызванная функция не была завершена (выполняя данную функцию, процесс завис);

-                     указанный тип передаваемых данных не определен;

-                     вторичное использование неосвобожденного объекта типа MPI_Request;

-                     отсутствие вызова функции ожидания неблокирующей операции;

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

Глобальные:

-                     потенциальные и реальные дедлоки, обусловленные операциями встречной отправки или приема;

-                     гонки данных, возникающие в результате того, что одной операции приема удовлетворяют несколько операций отправки;

-                     несоответствие типов данных в операциях отправки и приема;

-                     изменение данных, участвующих в коммуникационной операции, основной ветвью MPI-процесса во время неблокирующей передачи/приема;

-                     отсутствие вызова парной функции к операции типа точка-точка;

-                     несоответствие размеров сообщений в операциях передачи/приема;

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

Благодаря своей архитектуре, система отладки обладает низкими накладными расходами. Действительно, потоки, выполняющие программу пользователя; служебные потоки, отыскивающие локальные ошибки и серверы-анализаторы работают асинхронно, не ожидая друг друга. Что касается накладных расходов на сеть, то объемов данных, циркулирующих между серверами и MPI-процессами, крайне мал – это только параметры функций и управляющие сигналы.

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

    

Рис. Охранные документы на систему отладки MPI-программ

Система оптимизации UPC-программ

Еще одной подсистемой ИВП, предназначенной для помощи прикладному исследователю в процессе разработки параллельных приложений, является подсистема оптимизации UPC-программ (Unified Parallel C). Во время работы программы система собирает информацию по вызываемым функциям и подсчитывает совокупное время, проведенное программой в соответствующих вызовах. По окончанию работы строится визуализация, наглядно отображающая «узкие места» программы.

architecture_grey2_bw

Рис. Архитектура системы оптимизации UPC-программ