Изучение моделей параллельного программирования и оптимизация параллельных вычислений в исследовании операций

Введение

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

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

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

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

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

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

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

Рис. Основные слои выравнивания, охватываемые параллельными операциями приложений (источник: составлено автором)

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

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

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

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

MPI – это библиотека подпрограмм с привязками на Fortran, C и C++, а также открытый пример параллельного API, реализующий модель передачи сообщений посредством вызовов библиотечных функций.

Совокупность процессов с отдельными адресными пространствами координирует вычисления путем явной отправки и получения сообщений. Каждый процесс имеет отдельное адресное пространство, собственный счетчик программ и собственный стек вызовов. Однако программисту остается лишь реализовывать в процессах высокоуровневые конструкции, такие как синхронизация, связь и выравнивание данных. MPI поддерживает двухточечное взаимодействие между любыми двумя процессами. Он также допускает коллективные коммуникационные операции, когда группа процессов выполняет глобальные/коллективные операции, такие как сбор, рассеивание, сокращение и сканирование. В гетерогенной среде реализация MPI может связывать процессы с процессорами определенным образом для оптимизации производительности. Аналогичным образом реализация MPI может оптимизировать способ взаимодействия процессов во время глобальной операции. Например, в случае MPI_Reduce, если альтернативная структура обеспечивает лучшую производительность для базовой параллельной машины, взаимодействующим узлам не нужно создавать древовидную структуру. С другой стороны, OpenMP – это в основном неявный параллельный шаблон API, разработанный для многопроцессорных систем с общей памятью.

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

Конструкция разделов (источник: https://www.researchgate.net/figure/pragma-omp-parallel-for-is-used-for-a-loop-parallelization-for-an-Airfoil-application_fig4_315682752)

Конструкция разделения работы разделяет итерации цикла между разными потоками таким образом, что каждая итерация выполняется полностью одним потоком. Это пример парадигмы параллелизма данных (источник: https://www.researchgate.net/figure/pragma-omp-parallel-for-is-used-for-a-loop-parallelization-for-an-Airfoil-application_fig4_315682752)

Cilk – это расширение языка программирования C с параллельными конструкциями, аналогичными OpenMP. OpenMP и Cilk могут автоматически выбирать параллелизм для достижения хорошей производительности. Cilk++ привносит то же самое в язык C++.

Алгоритмы модели программирования и их фактическое применение в программном обеспечении

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

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

Мультикомпьютерная модель наследует модель Эккерта-фон Неймана для каждого узла машины. Это имеет важное практическое последствие: можно использовать стандартные языки, такие как Fortran, C и C++, если у них есть программная библиотека, помогающая решать проблемы коммуникации. Такое сочетание стандартного языка и библиотеки связи называется моделью передачи сообщений.

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

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

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

Модели программирования, лежащие в основе Fortran и C, очень похожи. Оба поддерживают структуры данных и инкапсуляцию. C++ – это надмножество C, включающее поддержку нескольких расширенных объектно-ориентированных конструкций. Модель объектно-ориентированного программирования имеет принципиально иной взгляд на организацию программы.

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

Заключение

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

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

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

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

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

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