Суть параллельного программирования
Параллельная программа содержит несколько процессов, работающих совместно над выполнением некоторой задачи. Каждый процесс — это последовательная программа, а точнее — последовательность операторов, выполняемых один за другим. Последовательная программа имеет один поток управления, а параллельная — несколько.
Совместная работа процессов параллельной программы осуществляется с помощью их взаимодействия. Взаимодействие программируется с применением разделяемых переменных или пересылки сообщений. Если используются разделяемые переменные, то один процесс осуществляет запись в переменную, считываемую другим процессом. При пересылке сообщений один процесс отправляет сообщение, которое получает другой.
При любом виде взаимодействия процессам необходима взаимная синхронизация. Существуют два основных вида синхронизации — взаимное исключение и условная синхрониза-
20 Глава 1. Обзор области параллельных вычислений
ция. Взаимное исключение обеспечивает, чтобы критические секции операторов не выполнялись одновременно. Условная синхронизация задерживает процесс до тех пор, пока не выполнится определенное условие. Например, взаимодействие процессов производителя и потребителя часто обеспечивается с помощью буфера в разделяемой памяти. Производитель записывает в буфер, потребитель читает из него. Чтобы предотвратить одновременное использование буфера и производителем, и потребителем (тогда может быть считано не полностью записанное сообщение), используется взаимное исключение. Условная синхронизация используется для проверки, было ли считано потребителем последнее записанное в буфер сообщение.
Как и другие прикладные области компьютерных наук, параллельное программирование прошло несколько стадий. Оно возникло благодаря новым возможностям, предоставленным развитием аппаратного обеспечения, и развилось в соответствии с технологическими изменениями. Через некоторое время специализированные методы были объединены в набор основных принципов и общих методов программирования.
Параллельное программирование возникло в 1960-е годы в сфере операционных систем. Причиной стало изобретение аппаратных модулей, названных каналами, или контроллерами устройств. Они работают независимо от управляющего процессора и позволяют выполнять операции ввода-вывода параллельно с инструкциями центрального процессора. Канал взаимодействует с процессором с помощью прерывания — аппаратного сигнала, который говорит: "Останови свою работу и начни выполнять другую последовательность инструкций".
Результатом появления каналов стала проблема программирования (настоящая интеллектуальная проблема) — теперь части программы могли быть выполнены в непредсказуемом '''порядке. Следовательно, пока одна часть программы обновляет значение некоторой переменной, может возникнуть прерывание, приводящее к выполнению другой части программы, которая тоже попытается изменить значение этой переменной. Эта специфическая проблема (задача критической секции) подробно рассматривается в главе 3.
Вскоре после изобретения каналов началась разработка многопроцессорных машин, хотя в течение двух десятилетий они были слишком дороги для широкого использования. Однако сейчас все крупные машины являются многопроцессорными, а самые большие имеют сотни процессоров и часто называются машинами с массовым параллелизмом (massively parallel processors). Скоро даже персональные компьютеры будут иметь несколько процессоров.
Многопроцессорные машины позволяют разным прикладным программам выполняться одновременно на разных процессорах. Они также ускоряют выполнение приложения, если оно написано (или переписано) для многопроцессорной машины. Но как синхронизировать работу параллельных процессов? Как использовать многопроцессорные системы для ускорения выполнения программ?
Итак, при использовании каналов и многопроцессорных систем возникают и возможности, и трудности. При написании параллельной программы необходимо решать, сколько процессов и какого типа нужно использовать, и как они должны взаимодействовать.
Эти ре шения зависят как от конкретного приложения, так и от аппаратного обеспечения, на котором будет выполняться программа. В любом случае ключом к созданию корректной программы является правильная синхронизация взаимодействия процессов.
Эта книга охватывает все области параллельного программирования, но основное внимание уделяет императивным программам с явными параллельностью, взаимодействием и синхронизацией. Программист должен специфицировать действия всех процессов, а также их взаимодействие и синхронизацию. Это контрастирует с декларативными программами, например, функциональными или логическими, где параллелизм скрыт и отсутствуют чтение и запись состояния программы. В декларативных программах независимые части программы могут выполняться параллельно; их взаимодействие и синхронизация происходят неявно, когда одна часть программы зависит от результата выполнения другой. Декларативный подход тоже интересен и важен (см. главу 12), но императивный распространен гораздо шире. Кроме того, для реализации декларативной программы на стандартной машине необходимо писать императивную программу.
1.2. Структуры аппаратного обеспечения 21
Изучаются также параллельные программы, в которых процессы выполняются асинхронно, т.е. каждый со своей скоростью. Такие программы могут выполняться с помощью чередования процессов на одном процессоре или их параллельного выполнения на мультипроцессоре со многими командами и многими данными (MIMD-процессоре). К этому классу машин относятся также мультипроцессоры с разделяемой памятью, многомашинные системы с распределенной памятью и сети рабочих станций (см. следующий раздел). Несмотря на внимание к асинхронным параллельным вычислениям, в главе 3 мы описываем синхронную мультиобработку (SIMD-машины), а в главах 3 и 12 — связанный с ней стиль программирования, параллельного по данным.
