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

Синхронное параллельное программирование


Часть 3

Синхронное параллельное программирование

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

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

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

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

Мы уже приводили несколько примеров синхронных параллельных программ: умножение матриц, адаптивные квадратуры, алгоритмы, параллельные по данным, порождение простых чисел и обработка изображений. (В упражнениях в конце каждой главы описаны многие другие задачи.) Рассмотрим важную тему высокопроизводительных вычислений, связанную с применением параллельных машин к решению задач большого размера в науке и инженерии.


В главе 11 рассмотрены три основных класса научных приложений: 1) сеточные вычисле­ния для приближенных решений дифференциальных уравнений в частных производных, 2) точечные вычисления для моделирования систем взаимодействующих тел и 3) матричные вычисления для решения систем линейных уравнений. Для каждого класса приведена типич-

20 В дальнейшем, если речь не идет о других видах параллелизма, слово "синхронные" иногда опуска­ется. — Прим ред.

404                                                      Часть 3 Синхронное параллельное программирование

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

В программах использованы языковые механизмы и методы программирования, описан­ные в частях 1 и 2. В главе 12 рассмотрены дополнительные языки, компиляторы, библиотеки и инструментарий для высокопроизводительных параллельных вычислений. Отдельные темы посвящены библиотеке ОрепМР для параллелизма с разделенной памятью, распараллели­вающим компиляторам, параллельным по данным, и функциональным языкам, абстрактным моделям, языку программирования High-Performance Fortran (HPF) и инструментальной системе Глобус для научных метавычислений.



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

Ускорение и эффективность

Как уже отмечалось, главная цель параллельного программирования — решить задачу бы­стрее. Уточним эту цель. Производительность программы определяется общим временем ее выполнения (работы). Пусть для решения некоторой задачи с помощью последовательной программы, выполняемой на одном процессоре, нужно время Т,, а с помощью параллельной программы, выполняемой на.р процессорах, — Тр. Тогда ускорение (speedup — S) параллельной программы определяется как 5= TJTp.



Например, пусть время работы последовательной программы равно 600 с, а время выпол­нения параллельной программы на 10 процессорах— 60с. Тогда ускорение параллельной программы равно 10. Такое ускорение называется линейным (или идеальным), поскольку программа на 10 процессорах работает в 10 раз быстрее. Обычно ускорение программы, вы­полняемой на р процессорах, оказывается меньше р. Такое ускорение называется менее, чем линейным (subhnear). Иногда ускорение оказывается более, чем линейным (superlinear), т.е. больше р; так бывает, когда данных в программе так много, что они не умещаются в кэш од­ного процессора, но после разделения их можно разместить в кэшах р процессоров.

Двойником ускорения является эффективность (Efficiency — Е) — мера того, насколько хорошо параллельная программа использует дополнительные процессоры. Она определяется следующим образом.

E=S/p=T,/(p*Tp)

Если программа имеет линейное ускорение, ее эффективность равна 1,0. Эффективность меньше 1,0 означает, что ускорение менее, чем линейное, а больше — что ускорение более, чем линейное.

Ускорение и эффективность относительны. Они зависят от количества процессоров, раз­мера задачи и используемого алгоритма. Например, часто эффективность параллельной программы с ростом числа процессоров снижается; например, при малом числе процессоров эффективность может быть близка к 1,0 и уменьшаться с ростом/». Аналогично параллельная программа может быть весьма эффективной при решении задач больших (но не малых) раз­меров. Говорят, что параллельная программа масштабируема, если ее эффективность посто­янна в широком диапазоне количеств процессоров и размеров задач. Наконец, ускорение и эффективность зависят от используемого алгоритма — параллельная программа может оказаться эффективной для одного последовательного алгоритма и неэффективной для другого. Поэтому лучшей мерой будет абсолютная эффективность (или абсолютное ускорение), для которой Tt — время работы программы по наилучшему из известных последовательных алгоритмов.



Ускорение и эффективность зависят от общего времени выполнения. Обычно программа имеет три фазы — ввод данных, вычисления, вывод данных. Предположим, что в последова­тельной программе фазы ввода и вывода данных занимают по 10% от времени выполнения, а фаза вычислений — остальные 80%. Предположим также, что фазам ввода и вывода прису-



В нашем примере доля фазы вычислений, которую можно распараллелить, равна 80 96, или 0,8. Следовательно, если ускорение этой фазы бесконечно, то общее ускорение все равно ос­танется равным 1/(1—0,8), т.е. 5. Однако общее ускорение на/? процессорах в действительно­сти меньше. Например, если ускорение вычислительной фазы на 10 процессорах равно 10, то общее ускорение — 1/(0,2+0,8/10), или приблизительно 3,57.

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

Накладные расходы и дополнительные проблемы

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



В наибольшей степени на производительность влияет используемый алгоритм, поэтому для получения высокой производительности нужно начинать с хорошего алгоритма. Этот вопрос будет затрагиваться при изучении каждого из приложений в главе 11. Иногда наилучший параллельный алгоритм для решения задачи отличается от наилучшего последовательного алгоритма. Однако по­ка предположим, что нам дан хороший последовательный алгоритм, и его нужно распараллелить.

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

406                                                      Часть 3. Синхронное параллельное программирование

стоит в том, чтобы распараллелить вычисления и назначить процессам процессоры так, что­бы сбалансировать вычислительную нагрузку. Пусть Гсотр

— это время работы последовательной программы. Для достижения идеального ускорения на р процессорах нужно так сбалансиро­вать нагрузку, чтобы время работы каждого процессора было близко к Т^^/р. Если один процессор загружен больше, чем другой, часть времени тот будет простаивать. Таким обра­зом, общее время вычислений и производительность будут определяться временем работы наиболее загруженного процессора.

Кроме последовательных компонентов, у параллельной программы есть еще три источни­ка накладных расходов: 1) создание процессов и их диспетчеризация, 2) взаимодействие и 3) синхронизация. Их нельзя исключить, поэтому вторая проблема — минимизировать их. К сожалению, накладные расходы взаимозависимы, и уменьшение одного может привести к увеличению других.

В параллельной программе есть много процессов, которые нужно создавать и планиро­вать. Стандартный способ, уменьшить эти расходы — на каждом процессоре создавать один процесс.


Это дает наименьшее число процессов, использующих данное число процессоров. Кроме того, если на каждый процессор приходится по одному процессу, то отсутствуют рас­ходы, связанные с переключением контекста при переходе процессора от выполнения одного 'процесса к другому. Однако приостановка процесса приводит к простою его процессора. Если бы в программе было больше процессов, мог бы выполняться один из них. Также, когда процес­сы выполняют различные объемы работы, вычислительную нагрузку сбалансировать намного легче, если процессов больше, чем процессоров. Наконец, некоторые приложения намного проще программируются с помощью рекурсивных или мелкомодульных процессов. Итак, па­раллельное программирование требует разрешения противоречий между числом процессов, ба­лансировкой нагрузки и накладными расходами при создании и планировании процессов.

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

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


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

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

Часть 3 Синхронное параллельное программирование                                                      407

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

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


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

Глава 11 Научные вычисления

Существует два традиционных метода научных исследований — теория и эксперимент. Например, теоретическая физика занимается построением моделей, объясняющих физиче­ские явления, а экспериментальная физика — их изучением, часто для того, чтобы подтвер­дить или опровергнуть гипотезы. Теперь появился третий тип исследований — численное мо­делирование, в котором явления имитируются с помощью компьютеров, причем основной во­прос— "Что будет, если...?". Например, физик, применяющий численное моделирование, может написать программу, моделирующую эволюцию звезд или слияние ядер.

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

Несмотря на множество научных компьютерных приложений и численных моделей, постоянно используются три основных метода: сеточные, точечные и матричные вычисле­ния.Сеточные вычисления применяются в численном решении уравнений в частных про­изводных и других приложениях (таких как обработка изображений), когда пространст­венная область разбивается на множество точек. Точечные вычисления используются в моделях, имитирующих взаимодействие отдельных частиц, таких как молекулы или звездные объекты. Матричные вычисления применяются всегда, когда нужно решить сис­тему одновременно действующих уравнений.

В данной главе представлены примеры сеточных, точечных и матричных вычислений. Для каждого метода описаны возможные алгоритмы и разработана последовательная программа. Затем составлены параллельные программы, сначала с помощью разделяемых переменных, а затем — передачи сообщений. Также показано, как оптимизировать программы, чтобы по­высить их производительность.


Содержание раздела