Параллельное программирование: введение

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

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

Естественный вопрос для разработчика - как ускорить выполнение программы? Конечно, можно посоветовать пользователю использовать более быстрый компьютер, но это решение очень ограничено, да и скорости компьютеров сейчас несильно увеличиваются. А вот что увеличивается - это количество ядер на компьютере.

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

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

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

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

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

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

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

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

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

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

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

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

При проектировании ЯПП работа ведется как в направлении создания дополнительных средств в существующих последовательных языках, так и в плане создания ЯПП на совершенно новых принципах.

Общий обзор нескольких языков параллельного программирования

• OpenMP: директивы компилятора для простого параллельного программирования
• MPI: библиотечные подпрограммы для реализации высокоэффективной переносимости
• Java: параллельность в языке программирования на основе ведущих объектов

OpenMP

OpenMP основывается на модели программирования "разветвление-объединение" (fork-join). Работа программы OpenMP начинается с одного потока. Когда программисту требуется добавить в программу параллелизм, выполняется разветвление на несколько потоков, чтобы создать группу потоков. Эти потоки выполняются параллельно в рамках фрагмента кода, который называется параллельным участком. В конце параллельного участка все потоки заканчивают свою работу и снова объединяются вместе. После этого исходный (или "главный") поток продолжает выполняться до тех пор, пока не начнется следующий параллельный участок (или не наступит конец программы).

Языковые конструкции в OpenMP определены как директивы компилятора, которые сообщают компилятору, что он должен делать, чтобы реализовать требуемый параллелизм. В C и C++ такие директивы называются "прагмы".

MPI

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

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

Java

Язык Java разрабатывался с встроенной поддержкой многопотоковости. Потоки — один из ключевых элементов технологии Java; они поддерживаются как на языковом (синтаксическом) уровне, так и на уровне виртуальной машины Java и библиотек классов. Во многих случаях потоки Java очень похожи на потоки POSIX (pthreads). Библиотеки классов Java предоставляют класс thread, который поддерживает широкий набор методов для запуска, выполнения и остановки потока, а также проверки его состояния.

Поддержка потоков в Java включает в себя сложный набор примитивов синхронизации на основе мониторов и переменных условия. На уровне языка методы внутри класса или блоки кода, для которых объявляется синхронизация, не выполняются параллельно. Такие методы или блоки выполняются под контролем мониторов, которые помогают убедиться, что данные, доступ к которым осуществляется в этих методах или блоках, остаются в согласованном состоянии. Каждый объект Java имеет собственный монитор, создание экземпляра и активация которого выполняется виртуальной машиной Java в момент первого использования. Мониторы работают примерно так же, как и пара переменной условия и мьютекса, как они определены в pthreads. Однако, в отличие от pthreads, можно прервать поток Java, пока он находится в состоянии ожидания, например, если он ожидает уведомления о событии или заблокирован при вызове ввода-вывода. Чтобы запустить новый поток в Java, обычно нужно создать подкласс класса Thread и определить пользовательский метод run(), выполняющий основную работу, которая должна быть распараллелена. 

Выбор системы обозначений параллельного программирования

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

• Переносимость: какие платформы необходимо поддерживать? Среда MPI приобрела такую популярность, в частности, потому, что работает в любых средах и на любых платформах. Однако, если планируется поддержка только оборудования с совместным использованием адресного пространства, то система обозначений на основе потоков может стать более удачным выбором.
• Производительность: управляемые и высокоуровневые среды выполнения сильно облегчают жизнь программиста. Учитывая высокую стоимость создания и обслуживания ПО, очень важно рассмотреть эти возможности. Но ради них придется и чем-то пожертвовать. Низкоуровневые API-интерфейсы (такие как потоки Windows, Pthreads или MPI), где программист напрямую управляет оборудованием, позволяют выполнять более тонкую оптимизацию. В случае, если требуется приспособиться к последнему вышедшему ядру, такая оптимизация приобретает очень большое значение.
• Выпуски последовательных и параллельных продуктов: программное обеспечение живет долго. Успешный разработчик ПО должен обеспечить поддержку самого разного оборудования. Следовательно, обслуживание как последовательной, так и параллельной версии ПО в рамках одного каркаса исходного кода может оказаться важным. Это может оказаться нелегкой задачей, если система обозначений параллельного программирования требует значительной переработки ПО для реализации параллелизма.
• Легкость в освоении: изучение нового языка может оказаться сложным. Если речь идет о группе разработчиков, затраты на обучение незнакомому языку могут быть слишком велики. Следовательно, очень важно, чтобы система обозначений параллельного программирования являлась расширением знакомого последовательного языка.

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

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