Приложения и стили программирования
Параллельное программирование обеспечивает способ организации программного обеспечения, состоящего из относительно независимых частей. Оно также позволяет использовать множественные процессоры. Существует три обширных перекрывающихся класса приложений — многопоточные системы, распределенные системы и синхронные параллельные вычисления — и три соответствующих им типа параллельных программ.
Напомним, что процесс— это последовательная программа, которая при выполнении имеет собственный поток управления. Каждая параллельная программа содержит несколько процессов, поэтому имеет несколько потоков. Однако термин многопоточный обычно означает, что программа содержит больше процессов (потоков), чем существует процессоров для их выполнения. Следовательно, процессы на процессорах выполняются по очереди. Многопоточная программная система управляет множеством независимых процессов, например таких:
• оконные системы на персональных компьютерах или рабочих станциях;
• многопроцессорные операционные системы и системы с разделением времени;
• системы реального времени, управляющие электростанциями, космическими аппаратами и т.д.
Эти системы разработаны как многопоточные программы, поскольку организовать код и структуры данных в виде набора процессов намного проще, чем реализовать огромную последовательную программу. Кроме того, каждый процесс может планироваться и выполняться независимо. Например, когда пользователь нажимает кнопку мыши персонального компьютера, посылается сигнал процессу, управляющему окном, в котором в данный момент находится курсор мыши. Этот процесс (поток) может выполняться и отвечать на щелчок мыши. Приложения в других окнах могут продолжать при этом свое выполнение в фоновом режиме. Второй широкий класс приложений образуют распределенные вычисления, в которых компоненты выполняются на машинах, связанных локальной или глобальной сетью. По этой причине процессы взаимодействуют, обмениваясь сообщениями.
Вот примеры:
• файловые серверы в сети;
• системы баз данных для банков, заказа авиабилетов и т.д.;
• Web-серверы сети Internet;
26 Глава 1. Обзор области параллельных вычислений
• предпринимательские системы, объединяющие компоненты производства;
• отказоустойчивые системы, которые продолжают работать независимо от сбоев в компонентах.
Такие системы пишутся для распределения обработки (как в файловых серверах), обеспечения доступа к удаленным данным (как в базах данных и в Web), интеграции и управления данными, распределенными по своей сути (как в промышленных системах), или повышения надежности (как в отказоустойчивых системах). Многие распределенные системы организованы как системы типа клиент-сервер. Например, файловый сервер предоставляет файлы данных для процессов, выполняемых на клиентских машинах. Компоненты распределенных систем часто сами являются многопоточными программами.
Синхронные параллельные вычисления — третий широкий класс приложений. Их цель — быстро решить данную задачу или за то же время решить большую задачу. Примеры синхронных вычислений:
• научные вычисления, которые моделируют и имитируют такие явления, как глобальный климат, эволюция солнечной системы или результат действия нового лекарства;
• графика и обработка изображений, включая создание спецэффектов в кино;
• крупные комбинаторные или оптимизационные задачи, например, планирование авиаперелетов или экономическое моделирование.
Программы решения таких задач требуют больших вычислительных мощностей. Для дости-••жения высокой производительности они выполняются на параллельных процессорах, причем обычно количество процессов (потоков) равно числу процессоров. Параллельные вычисления описываются в виде программ, параллельных по данным, в которых все процессы выполняют одни и те же действия, но с собственной частью данных, или в виде программ, параллельных по задачам, в которых различные процессы решают различные задачи.
В данной книге рассмотрены все три вида приложений и, что более важно, показано, как их программировать. В многопоточных программах процессы (потоки) взаимодействуют, используя разделяемые переменные. В распределенных системах взаимодействие процессов обеспечивается с помощью обмена сообщениями или удаленного вызова операций. При выполнении синхронных параллельных вычислений процессы взаимодействуют, используя или разделяемые переменные, или передачу сообщений, в зависимости от аппаратного обеспечения, на котором выполняется программа. В части 1 этой книги показано, как написать программу, использующую для взаимодействия и синхронизации разделяемые переменные. Часть 2 описывает передачу сообщений и удаленные операции. В части 3 подробно рассмотрено синхронное параллельное программирование, ориентированное на научные вычисления.
Существует немало параллельных программных приложений, однако в них используется лишь небольшое число моделей решений, или парадигм. В частности, существует пять основных парадигм: 1) итеративный параллелизм, 2) рекурсивный параллелизм, 3) "производители и потребители" (конвейеры), 4) "клиенты и серверы", 5) взаимодействующие равные. С использованием одной или нескольких из этих парадигм и программируются приложения.
Итеративный параллелизм используется, когда в программе есть несколько процессов (часто идентичных), каждый из которых содержит один или несколько циклов. Таким образом, каждый процесс является итеративной программой. Процессы программы работают совместно над решением одной задачи; они взаимодействуют и синхронизируются с помощью разделяемых переменных или передачи сообщений. Итеративный параллелизм чаще всего встречается в научных вычислениях, выполняемых на нескольких процессорах.
Рекурсивный параллелизм может использоваться, когда в программе есть одна или несколько рекурсивных процедур, и их вызовы независимы, т.е. каждый из них работает над своей частью общих данных.
Рекурсия часто применяется в императивных языках программирования, особенно при реализации алгоритмов типа "разделяй и властвуй" или "перебор с воз-
1 4. Итеративный параллелизм: умножение матриц 27
вращением" (backtracking). Рекурсия является одной из фундаментальных парадигм и в символических, логических, функциональных языках программирования. Рекурсивный параллелизм используется для решения таких комбинаторных проблем, как сортировка, планирование (задача коммивояжера) и игры (шахматы и другие).
Производители и потребители — это взаимодействующие процессы. Они часто организуются в конвейер, через который проходит информация. Каждый процесс конвейера является фильтром, который потребляет выход своего предшественника и производит входные данные для своего последователя. Фильтры встречаются на уровне приложений (оболочки) в операционных системах типа ОС Unix, внутри самих операционных систем, внутри прикладных программ, если один процесс производит выходные данные, которые потребляет (читает) другой процесс.
Клиенты и серверы — наиболее распространенная модель взаимодействия в распределенных системах, от локальных сетей до World Wide Web. Клиентский процесс запрашивает сервис и ждет ответа. Сервер ожидает запросов от клиентов, а затем действует в соответствии с этими запросами. Сервер может быть реализован как одиночный процесс, который не может обрабатывать одновременно несколько клиентских запросов, или (при необходимости параллельного обслуживания запросов) как многопоточная программа. Клиенты и серверы представляют собой параллельное программное обобщение процедур и их вызовов: сервер выполняет роль процедуры, а клиенты ее вызывают. Но если код клиента и код сервера расположены на разных машинах, обычный вызов процедуры использовать нельзя. Вместо этого необходимо использовать удаленный вызов процедуры или рандеву, как это описано в главе 8.
Взаимодействующие равные — последняя парадигма взаимодействия. Она встречается в распределенных программах, в которых несколько процессов для решения задачи выполняют один и тот же код и обмениваются сообщениями. Взаимодействующие равные используются для реализации распределенных параллельных программ, особенно при итеративном параллелизме и децентрализованном принятии решений в распределенных системах. Некоторые приложения и схемы взаимодействия описаны в главе 9.
В следующих пяти разделах приводятся примеры, иллюстрирующие применение каждой модели. В примерах представлена программная нотация, используемая во всей книге. (Обзор нотации дается в разделе 1.9.) Еще больше примеров приведено в тексте и упражнениях последующих глав.
