Лекция 8. Параллельное программирование

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

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

«Ничем не скроешь фундаментальную трудность параллелизма», – так прозвучало заявление Мартина Одерски (Martin Odersky) в его приглашенном докладе на 20-й Международной конференции

«Конструирование компиляторов», состоявшейся в марте 2011 года в Германии под председательством Дженса Кнопа (Jens Knoop) [21]. Несмотря на многочисленные призывы и конкурсы, пока не появилось общих идей по новому поколению языков и систем программирования (ЯСП), в которых параллелизм имел бы самостоятельное значение, а не рассматривался бы (по понятным причинам) как пристройка к традиционному программированию.

 

 

8.1. Пространство решений

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

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

Разнообразие моделей параллельных вычислений и расширение спектра доступной архитектуры следует рассматривать как вызов разработчикам ЯСП, способных решать проблему создания методов компиляции многопо- точных программ для многопроцессорных конфигураций. Именно так го- ворит А. Хоар на многих авторитетных научных конференциях. Язык дол- жен допускать представление любых моделей параллелизма, проявляемого на уровне решаемой задачи или реализуемого с помощью реальной архи- тектуры, причем такое представление требует лаконичных форм и кон- структивных построений, гарантирующих сохранение свойств программ при их реорганизации. Не менее важна расширяемость языка по мере раз- вития средств и методов параллельных вычислений, темп которого превы- шает скорость осознания специалистами их возможностей.

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

 

 

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

 

Параллельные алгоритмы

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

– процессоров может быть много, и они могут обладать разными систе- мами команд;

– процессоры могут работать автономно или сообща выполнять общую работу;

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

– процессоры имеют свою локальную память и могут работать в общей памяти;

– соседние процессоры могут быть приспособлены к сверхбыстрому об- мену данными;

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

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

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

 

 

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

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

1. Не слишком ли возрастет трудоемкость жизненного цикла программы решения задачи с помощью параллельного алгоритма?

2. В какой мере при постановке задачи следует учитывать модель парал- лелизма?

3. Как обосновать и измерить выигрыш от разработки параллельного ал- горитма?

4. Насколько изменяется постановка задачи при переходе к параллель- ным алгоритмам?

5. Что дает парадигма параллельного программирования на уровне раз- работки параллельного алгоритма?

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

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

Основной аргумент – целесообразность учета естественного паралле- лизма на уровне постановки задачи, утрачиваемого при решении задачи по-

 

 

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

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

– Каким образом в определении алгоритма выделены части, выполняемые отдельными устройствами?

– Обязана ли реализация алгоритма использовать в точности представленный в его определении набор устройств?

– В каких случаях последовательный алгоритм можно рассматривать как параллельный, исполняемый на одном устройстве?

Следующая обойма вопросов касается категории «время» и связана с про- блемами синхронизации:

– Могут ли части параллельного алгоритма обладать своим независимым или централизованным отсчетом времени?

– Допустимо ли при синхронизации частей алгоритма противоречить его информационным связям и логике управления?

– Можно ли синхронизацию частей алгоритма рассматривать как частный случай асинхронности?

Особые сложности параллелизма вызывают вопросы доступа к памяти:

– Каким образом взаимодействующие части параллельного алгоритма об- мениваются данными?

– Полезно ли частям параллельного алгоритма изменять состояние общей памяти и памяти других частей?

– Может ли часть параллельного алгоритма воспрепятствовать использо- ванию своей памяти другими частями?

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

И все же, сколь ни сложен мир параллелизма, программистам предстоит его понять и освоить!

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

 

 

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

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

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

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

Исследования в области параллельного пограмирования осложнены не- четкостью речевой практики, отчасти обусловленной различиями в рас- кладке понятий в разных естественных языках. Например, английские тер- мины «thread» и «streem» нередко переводятся на русский как термин «по- ток», хотя первое – это «поток управления», а второе – «поток данных».

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