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

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

 

ОБЩИЕ СВЕДЕНИЯ

---

Номер проекта 22-21-00686

НазваниеАлгоритмы и программные средства оптимизации выполнения параллельных программ в модели удаленного доступа к памяти

Руководитель Пазников Алексей Александрович, Кандидат технических наук

Организация финансирования, регион Федеральное государственное автономное образовательное учреждение высшего образования "Санкт-Петербургский государственный электротехнический университет "ЛЭТИ" им. В.И. Ульянова (Ленина)" , г Санкт-Петербург

Конкурс №64 - Конкурс 2021 года «Проведение фундаментальных научных исследований и поисковых научных исследований малыми отдельными научными группами»

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-418 - Оптимизация мультиархитектурных иерархических систем и параллельное мультипрограммирование

Ключевые слова разделяемые структуры данных, потокобезопасность, синхронизация, MPI, удаленный доступ к памяти, RMA, PGAS, масштабируемость, блокировки, ослабленная согласованность, коллективные операции, распределенные структуры данных

Код ГРНТИ50.07.05

---

 

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

---

Аннотация
Параллельные вычислительные технологии сегодня применяются повсеместно – от встроенных систем и мобильных устройств до систем с массовым параллелизмом, GRID-систем и облачных вычислительных систем (ВС). Алгоритмический и программный инструментарий параллельного программирования является базой при построении современных систем обработки больших данных, машинного обучения и искусственного интеллекта. При разработке параллельных программ для распределенных вычислительных систем (ВС) стандартом де-факто является модель передачи сообщений, представленная в первую очередь стандартом MPI (Message Passing Interface). Однако, вместе с тем, наравне с моделью передачи сообщений, в настоящий момент активно развивается модель удаленного доступа к памяти (Remote Memory Access, RMA), которая также реализована в стандарте MPI. В отличие от модели передачи сообщений, в рамках RMA каждый процесс получает доступ к памяти других процессов непосредственно, без явной отправки и получения сообщений. Программы в модели RMA оперируют распределенными сегментами памяти, доступными для RMA-вызовов, которые формируют распределенные структуры данных. Кроме того, модель RMA позволяет разделить фазы коммуникаций и синхронизации (decoupling communication and synchronization). За счет этого, применеие модели RMA позволяет сократить объем накладных расходов и повысить масштабируемость, минимизировать время выполнения параллельных программ. Опыт использования удаленного доступа к памяти во многих приложениях показал, что RMA позволяет повысить эффективность данных приложений и составляет серьезную конкуренцию модели передачи сообщений. Вместе с тем, несмотря на перспективность данного подхода, для модели RMA не решен ряд задач, связанный с обеспечением масштабируемого доступа к распределенным структурам данных. В первую очередь, для данной модели необходимо решить ряд задач, связанных с организацией масштабируемых структур и реализации фундаментальных примитивов синхронизации. Кроме того, для эффективного выполнения операций с данными структурами, необходимо разработать и реализовать алгоритмы коллективных обменов в модели RMA. В качестве фундаментальных примитивов синхронизации, будут реализованы алгоритмы для атомарных снимков (atomic snapshots). Данные структуры относятся к одним из основных линеаризуемых (linearizable) структур данных и являются одними из основных при разработке параллельных программ, поскольку позволяют решить задачу читателей и писателей (readers-writers problem). Планируется адаптировать известные алгоритмы реализации неблокируемых (как lock-free, так и wait-free) алгоритмов атомарных снимков для модели RMA. Атомарные снимки могут быть основной для построения более сложных структур и алгоритмов (например, для реализации протокола консенуса). Также в модели RMA необходимо разработать эффективные масштабируемые распределенные структуры данных. Для обеспечения высокой масштабируемости распределенных структур данных в модели RMA планируется использовать метод ослабления порядка выполнения операций (relaxation). Данный метод позволит устранить «узкие места» (bottlenecks) в структуре данных и существенно повысить пропускную способность. Суть метода заключается в следующем. В памяти каждого процесса параллельной программы расположена последовательная структура данных. При добавлении элементов в структуру данных каждым потоком выбирается (случайным образом или в соответствии с заданным алгоритмом) процесс (группа процессов) из множества процессов системы, после чего новый элемент помещается в соответствующую структуру данных. При извлечении элементов из распределенной структуры данных процесс выбирает подмножество процессов и запрашивает элементы, находящиеся в их локальных структурах данных. После этого в соответствии с заданным критерием выбирается наиболее подходящий элемент, который возвращается после вызова данной функции. В качестве структур данных в рамках проекта будут реализованы очереди, стеки и очереди с приоритетом. Распределенные стеки и очереди с ослабленным порядком выполнения операций не обеспечивают строгий порядок FIFO/LIFO выполнения операций: например, результатом операции pop извлечения элемента из стека не обязательно является в точности последний вставленный элемент, но также элемент, стоящий в окрестности последнего элемента – «рядом» с ним. В ослабленной очереди с приоритетом должна быть реализована операция удаления не минимального (максимального) элемента, а только элемента, близкого по значению к минимальному (максимальному). Другим подходом, направленным на обеспечение высокой масштабируемости разделяемых структур данных, является применение неблокирующих методов синхронизации (non-blocking synchronization), к которым относятся алгоритмы и структуры данных, свободные от блокировок (lock-free), ожиданий (wait-free) и препятствий (obstruction-free). В настоящий момент отсутствуют эффективные масштабируемые реализации таких структур данных для ВС с распределенной памятью. Тем не менее, во многих программах, разработанных при использовании моделей RMA и PGAS необходимо организовывать масштабируемое выполнение операций с разделяемыми структурами данных, элементы которых распределены между процессами. Данный проект направлен на решение данной проблемы путем создания комплекса неблокируемых структур данных в модели RMA. Для этого планируется реализовать набор оригинальных методов и алгоритмов, позволяющих учитывать особенности модели RMA и архитектур распределенных ВС (мультиархитектура, иерархическая структура). Экспериментально будет подтверждена применимость и высокая эффективность неблокируемой синхронизации не только для ВС с общей памятью, но и для ВС с распределенной памятью. В существующих программах в модели RMA имеют место параллельные обращения к множеству сегментов структуры, рассредоточенных по вычислительным узлам. В текущем стандарте MPI пользователи могут использовать только линейный (последовательный) алгоритм, который является неоптимальным в большинстве случаев, когда структуры данных позволяют параллельное обращение к сегментам. В связи с этим остро стоит задача создания эффективных масштабируемых алгоритмов реализации операций в модели RMA. В данном проекте будут построены такие алгоритмы для основных схем информационных обменов (трансляционный, коллекторный, трансляционно-циклический). Данные алгоритмы позволят сократить время выполнения информационных обменов и минимизировать общее время выполнения MPI-программ. Таким образом, в результате работ по проекту будет создан комплекс алгоритмов и программного обеспечения, решающий ключевые задачи для обеспечения масштабируемого выполнения параллельных программ в модели RMA на распределенных ВС. Данный инструментарий позволит сократить время выполнения параллельных программ и повысить эффективность использования распределенных ВС.

---

 

ОТЧЁТНЫЕ МАТЕРИАЛЫ

---