Синхронное параллельное программирование
Часть 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-х годах благодаря изобретению быстродействующих компьютеров. Наверное, правильней сказать, что быстродействующие компьютеры появились для удовлетворения нужд инженеров и ученых. Во всяком случае, самые быстродействующие машины с наибольшей памятью всегда используются в научных расчетах. Раньше у таких машин были векторные процессоры, сегодня это машины с массовым параллелизмом, имеющие десятки и сотни процессоров. Численное моделирование постоянно применяется во всех научных и инженерных областях — от разработки новых лекарств, моделирования климата, конструирования самолетов и автомобилей до определения, где сверлить нефтяную скважину, и изучения перемещения загрязнений в водоносных слоях.
Несмотря на множество научных компьютерных приложений и численных моделей, постоянно используются три основных метода: сеточные, точечные и матричные вычисления.Сеточные вычисления применяются в численном решении уравнений в частных производных и других приложениях (таких как обработка изображений), когда пространственная область разбивается на множество точек. Точечные вычисления используются в моделях, имитирующих взаимодействие отдельных частиц, таких как молекулы или звездные объекты. Матричные вычисления применяются всегда, когда нужно решить систему одновременно действующих уравнений.
В данной главе представлены примеры сеточных, точечных и матричных вычислений. Для каждого метода описаны возможные алгоритмы и разработана последовательная программа. Затем составлены параллельные программы, сначала с помощью разделяемых переменных, а затем — передачи сообщений. Также показано, как оптимизировать программы, чтобы повысить их производительность.
