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

( Бьерн Страуструп, создатель языка С++ )

Д ля того чтобы в настоящее время разрабатывать программное обеспечение, необходимы практические знания параллельного и распределенного программирования. Теперь перед разработчиками приложений все чаще ставится задача, чтобы отдельные программные составляющие надлежащим образом выполнялись в Internet или Intranet. Если программа (или ее часть) развернута в одной или нескольких таких средах, то к ней предъявляются самые жесткие требования по части производительности. Пользователь всегда надеется, что результаты работы программ будут мгновенными и надежными. Во многих ситуациях заказчик хотел бы, чтобы программное обеспечение удовлетворяло сразу многим требованиям. Зачастую пользователь не видит ничего необычного в своих намерениях одновременно загружать программные продукты и данные из Internet. Программное обеспечение, предназначенное для приема телетекста, также должно быть способно на гладкое воспроизведение графических изображений и звука после цифровой обработки (причем без прерывания). Программное обеспечение Web-сервера нередко выдерживает сотни тысяч посещений в день, а часто посещаемые почтовые серверы— порядка миллиона отправляемых и получаемых сообщений. При этом важно не только количество обрабатываемых сообщений, но и их содержимое. Например, передача данных, содержащих оцифрованные музыку, видео или графические изображения, может «поглотить» всю пропускную способность сети и причинить серьезные неприятности программному обеспечению сервера, которое не было спроектировано должным образом. Обычно мы имеем дело с сетевой вычислительной средой, состоящей из компьютеров с несколькими процессорами. Чем больше функций возлагается на программное обеспечение, тем больше к нему предъявляется требований. Чтобы удовлетворить минимальные требования пользователя, современные программы должны быть еще более производительными и интеллектуальными. Программное обеспечение следует проектировать так, чтобы можно было воспользоваться преимуществами компьютеров, оснащенных несколькими процессорами. А поскольку сетевые компьютеры — это скорее правило, чем исключение, то целью проектирования программного обеспечения должно быть его корректное и эффективное выполнение при условии, что некоторые его составляющие будут одновременно выполняться на различных компьютерах. В некоторых случаях используемые компьютеры могут иметь совершенно различные операционные системы с разными сетевыми протоколами! Чтобы справиться с описанными реалиями, ассортимент разработок программных продуктов должен включать методы реализации параллелизма посредством параллельного и распределенного программирования.

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

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

Параллельное и распределенное программирование— это два базовых подхода к достижению параллельного выполнения составляющих программного обеспечения (ПО). Они представляют собой две различные парадигмы программирования, которые иногда пересекаются. Методы параллельного программирования позволяют распределить работу программы между двумя (или больше) процессорами в рамках одного физического или одного виртуального компьютера. Методы распределенного программирования позволяют распределить работу программы между двумя (или больше) процессами, причем процессы могут существовать на одном и том же компьютере или на разных. Другими словами, части распределенной программы зачастую выполняются на разных компьютерах, связываемых по сети, или по крайней мере в различных процессах. Программа, содержащая параллелизм, выполняется на одном и том же физическом или виртуальном компьютере. Такую программу можно разбить на процессы (process) или потоки (thread). Процессы мы рассмотрим в главе 3 , а потоки — в главе 4 . В изложении материала этой книги мы будем придерживаться того, что распределенные программы разбиваются только на процессы. Многопоточность ограничивается параллелизмом. Формально параллельные программы иногда бывают распределенными, например, при PVM-программировании ( P arallel V irtual M achine — параллельная виртуальная машина). Распределенное программирование иногда используется для реализации параллелизма, как в случае с MPI-программированием (Message Passing Interface — интерфейс для передачи сообщений). Однако не все распределенные программы включают параллелизм. Части распределенной программы могут выполняться по различным запросам и в различные периоды времени. Например, программу календаря можно разделить на две составляющие. Одна часть должна обеспечивать пользователя информацией, присущей календарю, и способом записи данных о важных для него встречах, а другая часть должна предоставлять пользователю набор сигналов для разных типов встреч. Пользователь составляет расписание встреч, используя одну часть ПО, в то время как другая его часть выполняется независимо от первой. Набор сигналов и компонентов расписания вместе образуют единое приложение, которое разделено на две части, выполняемые по отдельности. При чистом параллелизме одновременно выполняемые части являются компонентами одной и той же программы. Части распределенных приложений обычно реализуются как отдельные программы. Типичная архитектура построения параллельной и распределенной программ показана на рис. 1.1.

Рис 1.1 Типичная архитектура построения параллельной и распределенной программ

Параллельное приложение, показанное на рис. 1.2, состоит из одной программы, разделенной на четыре задачи. Каждая задача выполняется на отдельном процессоре, следовательно, все они могут выполняться одновременно. Эти задачи можно реализовать в 1.2, состоит из трех отдельных программ, каждая из которых выполняется на отдельном компьютере [3]. При этом программа 3 состоит из двух отдельных частей (задачи А и задачи D), выполняющихся на одном компьютере. Несмотря на это, задачи А и D являются распределенными, поскольку они реализованы как два отдельных процесса. Задачи параллельной программы более тесно связаны, чем задачи распределенного приложения. В общем случае процессоры, связанные с распределенными программами, находятся на различных компьютерах, в то время как процессоры, связанные с программами, реализующими параллелизм, находятся на одном и том же компьютере. Конечно же, существуют гибридные приложения, которые являются и параллельными, и распределенными одновременно. Именно такие гибридные объединения становятся нормой.

Программы, надлежащее качество проектирования которых позволяет воспользоваться преимуществами параллелизма, могут выполняться быстрее, чем их последовательные эквиваленты, что повышает их рыночную стоимость. Иногда скорость может спасти жизнь. В таких случаях быстрее означает лучше. Иногда решение некоторых проблем представляется естественнее в виде коллекции одновременно выполняемых задач. Это характерно для таких областей, как научное программирование, математическое и программирование искусственного интеллекта. Это означает, что в некоторых ситуациях технологии параллельного программирования снижают трудозатраты разработчика ПО, позволяя ему напрямую реализовать структуры данных, алгоритмы и эвристические методы, разрабатываемые учеными. При этом используется специализированное оборудование. Например, в мультимедийной программе с широкими функциональными возможностями с целью получения более высокой производительности ее логика может быть распределена между такими специализированными процессорами, как микросхемы компьютерной графики, цифровые звуковые процессоры и математические спецпроцессоры. К таким процессорам обычно обеспечивается одновременный доступ. МРР-компьютеры (Massively Parallel Processors — процессоры с массовым параллелизмом) имеют сотни, а иногда и тысячи процессоров, что позволяет их использовать для решения проблем, которые просто не реально решить последовательными методами. Однако при использовании МРР-компьютеров (т.е. при объединении скорости и «грубой силы») невозможное становится возможным. К категории применимости МРР-компьютеров можно отнести моделирование экологической системы (или моделирование влияния различных факторов на окружающую среду), исследование космического пространства и ряд тем из области биологических исследований, например проект моделирования генома человека. Применение более совершенных технологий параллельного программирования открывает двери к архитектурам ПО, которые специально разрабатываются для параллельных сред. Например, существуют специальные мультиагентные архитектуры и архитектуры, использующие методологию «классной доски», разработанные специально для среды с параллельными процессорами.

В качестве простейшей модели, отражающей базовые концепции параллельного программирования, рассмотрим модель PRAM (Parallel Random Access Machine — параллельная машина с произвольным доступом). PRAM — это упрощенная теоретическая модель с n процессорами, которые используют общую глобальную память. Простая модель PRAM изображена на рис. 1.2.

Рис 1-2 Простая модель PRAM

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

Таблица 1.1. Четыре базовых алгоритма считывания и записи данных

EREW Исключающее считывание/исключающая запись

CREW Параллельное считывание/исключающая запись

ERCW Исключающее считывание/параллельная запись

CRCW Параллельное считывание/параллельная запись

В этой книге мы будем часто обращаться к этим типам алгоритмов для реализации параллельных архитектур. Архитектура, построенная на основе технологии «классной доски», — это одна из важных архитектур, которую мы реализуем с помощью PRAM-м одели (см. главу 13). Необходимо отметить, что хотя PRAM — это упрощенная теоретическая модель, она успешно используется для разработки практических программ, и эти программы могут соперничать по производительности с программами, которые были разработаны с использованием более сложных моделей параллелизма.

PRAM — это способ построения простой модели, которая позволяет представить, как компьютеры можно условно разбить на процессоры и память и как эти процессоры получают доступ к памяти. Упрощенная классификации схем функционирования параллельных компьютеров была предложена M. Флинном (M.J. Flynn) [4] . Согласно этой классификации различались две схемы: SIMD (Single-Instruction, Multiple-Data — архитектура с одним потоком команд и многими потоками данных) и MIMD (Multiple-Instruction, Multiple-Data — архитектура со множеством потоков команд и множеством потоков данных). Несколько позже эти схемы были расширены до SPMD (Single-Program, Multiple-Data — одна программа, несколько потоков данных) и MPMD (Multiple-Programs, Multiple-Data — множество программ, множество потоков данных) соответственно. Схема SPMD (SIMD) позволяет нескольким процессорам выполнять одну и ту же инструкцию или программу при условии, что каждый процессор получает доступ к различным данным. Схема MPMD (MIMD) позволяет работать нескольким процессорам, причем все они выполняют различные программы или инструкции и пользуются собственными данными. Таким образом, в одной схеме все процессоры выполняют одну и ту же программу или инструкцию, а в другой все процессоры выполняют различные программы или инструкции. Конечно же, возможны гибриды этих моделей, в которых процессоры могут быть разделены на группы, из которых одни образуют SPMD-модель, а другие — MPMD-модель. При использовании схемы SPMD все процессоры просто выполняют одни и те же операции, но с различными данными. Например, мы можем разбить одну задачу на группы и назначить для каждой группы отдельный процессор. В этом случае каждый процессор при решении задачи будет применять одинаковые правила, обрабатывая при этом различные части этой задачи. Когда все процессоры справятся со своими участками работы, мы получим решение всей задачи. Если же применяется схема MPMD, все процессоры выполняют различные виды работы, и, хотя при этом все они вместе пытаются решить одну проблему, каждому из них выделяется свой аспект этой проблемы. Например, разделим задачу по обеспечению безопасности Web-сервера по схеме MPMD. В этом случае каждому процессору ставится своя подзадача. Предположим, один процессор будет отслеживать работу портов, другой — курировать процесс регистрации пользователей, а третий — анализировать содержимое пакетов и т.д. Таким образом, каждый процессор работает с нужными ему данными. И хотя различные процессоры выполняют разные виды работы, используя различные данные, все они вместе работают в одном направлении — обеспечивают безопасность Web-сервера. Принципы параллельного программирования, рассматриваемые в этой книге, нетрудно описать, используя модели PRAM, SPMD (SIMD) и MPMD (MIMD). И в самом деле, эти схемы и модели успешно используются для реализации практических мелко- и среднемасштабных приложений и вполне могут вас устраивать до тех пор, пока вы не подготовитесь к параллельному программированию более высокой степени организации.

Методы распределенного программирования позволяют воспользоваться преимуществами ресурсов, размещенных в Internet, в корпоративных Intranet и локальных сетях. Распределенное программирование обычно включает сетевое программирование в той или иной форме. Это означает, что программе, которая выполняется на одном компьютере в одной сети, требуется некоторый аппаратный или программный ресурс, который принадлежит другому компьютеру в той же или удаленной сети. Распределенное программирование подразумевает общение одной программы с другой через сетевое соединение, которое включает соответствующее оборудование (от модемов до спутников). Отличительной чертой распределенных программ является то, что они разбиваются на части. Эти части обычно реализуются как отдельные программы, которые, как правило, выполняются на разных компьютерах и взаимодействуют друг с другом через сеть. Методы распределенного программирования предоставляют доступ к ресурсам, которые географически могут находиться на большом расстоянии друг от друга. Например, распределенная программа, разделенная на компонент Web-сервера и компонент Web-клиента, может выполняться на двух различных компьютерах. Компонент Web-се pвepa может располагаться, допустим, в Африке, а компонент Web-клиента — в Японии. Часть Web-клиента может использовать программные и аппаратные ресурсы компонента Web-сервера, несмотря на то, что их разделяет огромное расстояние, и почти наверняка они относятся к различным сетям, функционирующим под управлением различных операционных сред. Методы распределенного программирования предусматривают совместный доступ к дорогостоящим программным и аппаратным ресурсам. Например, высококачественный голографический принтер может обладать специальным программным обеспечением сервера печати, которое предоставляет соответствующие услуги для ПО клиента. ПО клиента печати размещается на одном компьютере, а ПО сервера печати — на другом. Как правило, для обслуживания множества клиентов печати достаточно только одного сервера печати. Распределенные вычисления можно использовать для создания определенного уровня избыточности вычислительных средств на случай аварии. Если разделить программу на несколько частей, каждая из которых будет выполняться на отдельном компьютере, то некоторым из этих частей мы можем поручить одну и ту же работу. Если по какой-то причине один компьютер откажет, его программу заменит аналогичная программа, выполняющаяся на другом компьютере. Ни для кого не секрет, что базы данных способны хранить миллионы, триллионы и даже квадриллионы единиц информации. И, конечно же, нереально каждому пользователю иметь копию подобной базы данных. А ведь пользователи и компьютер, содержащий базу данных, зачастую находятся не просто в разных зданиях, а в разных городах или даже странах. Но именно методы распределенного программирования дают возможность пользователям (независимо от их местонахождения) обращаться к таким базам данных.

Возможно, самой простой и распространенной моделью распределенной обработки данных является модель типа «клиент/сервер». В этой модели программа разбивается на две части: одна часть называется сервером, а другая — клиентом. Сервер имеет прямой доступ к некоторым аппаратным и программным ресурсам, которые желает использовать клиент. В большинстве случаев сервер и клиент располагаются на разных компьютерах. Обычно между клиентом и сервером существует отношение типа «множество-к-одному», т.е., как правило, один сервер отвечает на запросы многих клиентов. Сервер часто обеспечивает опосредованный доступ к огромной базе данных, дорогостоящему оборудованию или некоторой коллекции приложений. Клиент может запросить интересующие его данные, сделать запрос на выполнение вычислительной процедуры или обработку другого типа. В качестве примера приложения типа «клиент/сервер» приведем механизм поиска (search engine). Механизмы (или машины) поиска используются для поиска заданной информации в Internet или корпоративной Intranet. Клиент служит для получения ключевого слова или фразы, которая интересует пользователя. Часть ПО клиента затем передает сформированный запрос той части ПО сервера, которая обладает средствами поиска информации по заданному пользователем ключевому слову или фразе. Сервер либо имеет прямой доступ к информации, либо связан с другими серверами, которые имеют его. В идеальном случае сервер находит запрошенное пользователем ключевое слово или фразу и возвращает найденную информацию клиенту. Несмотря на то что клиент и сервер представляют собой отдельные программы, выполняющиеся на разных компьютерах, вместе они составляют единое приложение. Разделение ПО на части клиента и сервера и есть основной метод распределенного программирования. Модель типа «клиент/сервер» также имеет другие формы, которые зависят от конкретной среды. Например, термин «изготовитель-потребитель» (producer-consumer) можно считать близким родственником термина «клиент/сервер». Обычно клиент-серверными приложениями называют большие программы, а термин «изготовитель-потребитель» относят к программам меньшего объема. Если программы имеют уровень операционной системы или ниже, к ним применяют термин «изготовитель-потребитель», если выше — то термин «клиент/сервер» (конечно же, исключения есть из всякого правила).

Несмотря на то что модель типа «клиент/сервер» — самая распространенная модель распределенного программирования, все же она не единственная. Используются также агенты — рациональные компоненты ПО, которые характеризуются самонаведением и автономностью и могут постоянно находиться в состоянии выполнения. Агенты могут как создавать запросы к другим программным компонентам, так и отвечать на запросы, полученные от других программных компонентов. Агенты сотрудничают в пределах групп для коллективного выполнения определенных задач. В такой модели не существует конкретного клиента или сервера. Это — модель сети с равноправными узлами (peer-to-peer), в которой все компоненты имеют одинаковые права, и при этом у каждого компонента есть что предложить другому. Например, агент, который назначает цены на восстановление старинных спортивных машин, может работать вместе с другими агентами. Один агент может быть специалистом по моторам, другой — по кузовам, а третий предпочитает работать как дизайнер по интерьерам. Эти агенты могут совместно оценить стоимость работ по восстановлению автомобиля. Агенты являются распределенными, поскольку все они размещаются на разных серверах в Internet. Для связи агенты используют согласованный Internet-протокол. Для одних типов распределенного программирования лучше подходит модель типа «клиент/сервер», а для других — модель равноправных агентов. В этой книге рассматриваются обе модели. Большинство требований, предъявляемых к распределенному программированию, удовлетворяется моделями «клиент/сервер» и равноправных агентов.

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

Декомпозиция — это процесс разбиения задачи и ее решения на части. Иногда части группируются в логические области (т.е. поиск, сортировка, вычисление, ввод и вывод данных и т.д.). В других случаях части группируются по логическим ресурсам (т.е. файл, связь, принтер, база данных и т.д.). Декомпозиция программного решения часто сводится к декомпозиции работ (work breakdown structure — WBS). Декомпозиция работ определяет, что должны делать разные части ПО. Одна из основных проблем параллельного программирования — идентификация естественной декомпозиции работ для программного решения. Не существует простого и однозначного подхода к идентификации WBS. Разработка ПО — это процесс перевода принципов, идей, шаблонов, правил, алгоритмов или формул в набор инструкций, которые выполняются, и данных, которые обрабатываются компьютером. Это, в основном, и составляет процесс моделирования. Программные модели — это воспроизведение в виде ПО некоторой реальной задачи, процесса или идеала. Цель модели— сымитировать или скопировать поведение и характеристики некоторой реальной сущности в конкретной предметной области. Процесс моделирования вскрывает естественную декомпозицию работ программного решения. Чем лучше модель понята и разработана, тем более естественной будет декомпозиция работ. Наша цель — обнаружить параллелизм и распределение с помощью моделирования. Если естественный параллелизм не наблюдается, не стоит его навязывать насильно. На вопрос, как разбить приложение на параллельно выполняемые части, необходимо найти ответ в период проектирования, и правильность этого ответа должна стать очевидной в модели решения. Если модель задачи и решения не предполагает параллелизма и распределения, следует попытаться найти последовательное решение. Если последовательное решение оказывается неудачным, эта неудача может дать ключ к нужному параллельному решению.

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

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

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

• инструкций;

• подпрограмм (функций или процедур);

• объектов;

• приложений.

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

На рис. 1.3 компонент (А + В) можно вычислить одновременно с компонентом (С - D) • Этот вид параллелизма обычно поддерживается директивами компилятора и не попадает под управление С++-программиста.

Рис. 1.3. Декомпозиция одной инструкции

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

ДСС-структуру программного решения можно распределить между объектами. Каждый объект можно назначить отдельному потоку или процессу. Используя стандарт CORBA (Common Object Request Broker Architecture — технология построения распределенных объектных приложений), все объекты можно назначить различным компьютерам одной сети или различным компьютерам различных сетей. Более детально технология CORBA рассматривается в главе 8. Объекты, реализованные в различных потоках или процессах, могут выполнять свои методы параллельно.

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

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

Язык С++ не содержит никаких синтаксических примитивов для параллелизма. С++-стандарт ISO также отмалчивается на тему многопоточности. В языке С++ не предусмотрено никаких средств, чтобы указать, что заданные инструкции должны выполняться параллельно. Включение встроенных средств параллелизма в других языках представляется как их особое достоинство. Бьерн Страуструп, создатель языка С++, имел свое мнение на этот счет:

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

Более того, Страуструп говорит: « Я считаю, что параллелизм в С++ должен быть представлен библиотеками, а не как языковое средство» . Авторы этой книги находят позицию Страуструпа и его рекомендации по реализации параллелизма в качестве библиотечного средства наиболее подходящими с практической точки зрения. В настоящей книге рассмотрен только этот вариант, и такой выбор объясняется доступностью высококачественных библиотек, которые успешно можно использовать для решения задач параллельного и распределенного программирования. Библиотеки, которые мы используем для усиления языка С++ с этой целью, реализуют национальные и международные стандарты и используются тысячами С++-программистов во всем мире.

Несмотря на существование специальных версий языка С++, предусматривающих «встроенные» средства параллельной обработки данных, мы представляем методы реализации параллелизма с использованием стандарта ISO (International Organization for Standardization — Международная организация по стандартизации) для С++. Мы находим библиотечный подход к параллелизму (при котором используются как системные, так и пользовательские библиотеки) наиболее гибким. Системные библиотеки предоставляются средой операционной системы. Например, поточно-ориентированная библиотека POSIX (Portable Operating System Interface — интерфейс переносимой операционной системы) содержит набор системных функций, которые в сочетании с языковыми средствами С++ успешно используются для поддержки параллелизма. Библиотека POSIX Threads является частью нового единого стандарта спецификаций UNIX (Single UNIX Specifications Standard) и включена в набор стандартов IEEE, описывающих интерфейсы ОС для UNIX (IEEE Std. 1003.1-2001). Создание нового единого стандарта спецификаций UNIX финансируется организацией Open Group, а его разработка поручена организации Austin Common Standards Revision Group. В соответствии с документами Open Group новый единый стандарт спецификаций UNIX:

• предоставляет разработчикам ПО единый набор API-функций, которые должны поддерживаться каждой UNIX-системой;

• смещает акцент с несовместимых реализаций систем UNIX на соответствие единому набору функций API;

• представляет собой кодификацию и юридическую стандартизацию общего ядра системы UNIX;

• в качестве основной цели преследует достижение переносимости исходного кода приложения.

Новый единый стандарт спецификаций UNIX, версия 3, включает стандарт IEEE Std. 1003.1-2001 и спецификации Open Group Base Specifications Issue 6. Стандарты IEEE POSIX в настоящее время представляют собой часть единой спецификации UNIX, и наоборот. Сейчас действует единый международный стандарт для интерфейса переносимой операционной системы. С++-разработчикам это только на руку, поскольку данный стандарт содержит API-функции, которые позволяют создавать потоки и процессы. За исключением параллелизма на уровне инструкций, единственным способом достижения параллелизма с помощью С++ является разбиение программы на потоки или процессы. Именно эти средства и предоставляет новый стандарт. Разработчик может использовать:

• библиотеку POSIX Threads (или Pthreads);

• POSIX-версию spawn ();

• семейство функций exec ().

Все эти средства поддерживаются системными API-функциями и системными библиотеками. Если операционная система отвечает 3-й версии нового единого стандарта UNIX, то С++-разработчику будут доступны эти API-функции (они рассматриваются в главах З и 4 и используются во многих примерах этой книги). Помимо библиотек системного уровня, для поддержки параллелизма в С++ могут применяться такие библиотеки пользовательского уровня, как MPI (Message Passing Interface — интерфейс для передачи сообщений), PVM (Parallel Virtual Machine — параллельная виртуальная машина) и CORBA (Common Object Request Broker Architecture — технология построения распределенных объектных приложений).

Интерфейс MPI — стандартная спецификация на передачу сообщений — был разработан с целью достижения высокой производительности на компьютерах с массовым параллелизмом и кластерах рабочих станций (рабочая станция — это сетевой компьютер, использующий ресурсы сервера). В этой книге используется MPICH-реализация стандарта MPI. MPICH — это свободно распространяемая переносимая реализация интерфейса MPI. MPICH предоставляет С++-программисту набор API-функций и библиотек, которые поддерживают параллельное программирование. Интерфейс MPI особенно полезен для программирования моделей SPMD (Single-Program, Multiple Data ^- одна программа , несколько потоков данных) и MPMD (Multiple-Program, Multiple-Data — множество программ, множество потоков данных). Авторы этой книги используют MPICH-реализацию библиотеки MPI для 32-узлового Linux-ориентированного кластера и 8-узлового кластера, управляемого операционными системами Linux и Solaris. И хотя в С++ нет встроенных примитивов параллельного программирования, С++-программист может воспользоваться средствами обеспечения параллелизма, предоставляемыми библиотекой MPICH. В этом и состоит одно из достоинств языка С++, которое заключается в его фантастической гибкости.

Программный пакет PVM позволяет связывать гетерогенную (неоднородную) коллекцию компьютеров в сеть для использования ее в качестве единого мощного параллельного компьютера. Общая цель PVM-системы — получить возможность совместно использовать коллекцию компьютеров для организации одновременной или параллельной обработки данных. Реализация библиотеки PVM поддерживает:

• гетерогенность по компьютерам, сетям и приложениям;

• подробно разработанную модель передачи сообщений;

• обработку данных на основе выполнения процессов;

• мультипроцессорную обработку данных (MPP, SMP) [5];

• «полупрозрачный» доступ к оборудованию (т.е. приложения могут либо игнорировать, либо использовать преимущества различий в аппаратных средствах);

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

PVM — это самая простая (по использованию) и наиболее гибкая среда, доступная для решения задач параллельного программирования, которые требуют применения различных типов компьютеров, работающих под управлением различных операционных систем. PVM-библиотека особенно полезна для объединения в сеть нескольких однопроцессорных систем с целью образования виртуальной машины с параллельно работающими процессорами. Методы использования библиотеки PVM в С++-коде мы рассмотрим в главе 6. PVM — это фактический стандарт для реализации гетерогенных кластеров, который легко доступен и широко распространен. PVM прекрасно поддерживает модели параллельного программирования MPMD (MIMD) и SPMD (SIMD). Авторы этой книги для решения небольших и средних по объему задач параллельного программирования используют PVM-библиoтeкy, а для более сложных и объемных — MPI-библиотеку. Обе библиотеки PVM и MPI можно успешно сочетать с С++ для программирования кластеров.

CORBA— это стандарт для распределенного кроссплатформенного объектно-ориентированного программирования. Выше упоминалось о применении CORBA для поддержки параллелизма, поскольку реализации стандарта CORBA можно использовать для разработки мультиагентных систем. Мультиагентные системы предлагают важные сетевые модели распределенного программирования с равноправными узлами (peer-to_peer). В мультиагентных системах работа может быть организована параллельно. Это одна из областей, в которых параллельное и распределенное программирование перекрываются. Несмотря на то что агенты выполняются на различных компьютерах, это происходит в течение одного и того же промежутка времени, т.е. агенты совместно работают над общей проблемой. Стандарт CORBA обеспечивает открытую, независимую от изготовителя архитектуру и инфраструктуру, которую компьютерные приложения используют для совместного функционирования в сети. Используя стандартный протокол IIOР (Internet InterORB Protocol — протокол, определяющий передачу сообщений между сетевыми объектами по TCP/IP), CORBA-ориентированная программа (созданная любым производителем на любом языке программирования, выполняемая практически на любом компьютере под управлением любой операционной системы в любой сети) может взаимодействовать с другой CORBA-ориентированной программой (созданной тем же или другим производителем на любом другом языке программирования, выполняемой практически на любом компьютере под управлением любой операционной системы в любой сети). В этой книге мы используем MICO-реализацию стандарта CORBA. MICO— свободно распространяемая и полностью соответствующая требованиям реализация стандарта CORBA, которая поддерживает язык С++.

Библиотеки MPICH, PVM, MICO и POSIX Threads реализованы на основе стандартов. Это означает, что разработчики ПО могут быть уверены, что эти реализации широко доступны и переносимы с одной платформы на другую. Эти библиотеки используются многими разработчиками ПО во всем мире. Библиотеку POSIX Threads можно использовать с С++ для реализации многопоточного программирования. Если программа выполняется на компьютере с несколькими процессорами, то каждый поток может выполняться на отдельном процессоре, что позволяет говорить о реальной параллельности программирования. Если же компьютер содержит только один процессор, то иллюзия параллелизма обеспечивается за счет процесса переключения контекстов. Библиотека POSIX Threads позволяет реализовать, возможно, самый простой способ введения параллелизма в С++-программу. Если для использования библиотек MPICH, PVM и MICO необходимо предварительно побеспокоиться об их установке, то в отношении библиотеки POSIX Threads это излишне, поскольку среда любой операционной системы, которая согласована с POSIX-стандартом или новой спецификацией UNDC (версия 3), оснащена реализацией библиотеки POSIX Threads. Все библиотеки предлагают модели параллелизма, которые имеют незначительные различия. В табл. 1.2 показано, как каждую библиотеку можно использовать с С++.

Таблица 1.2. Использование библиотек MPICH, PVM, MICO и POSIX Threads с С++

MPICH  Поддерживает крупномасштабное сложное программирование кластеров. Предпочтительно используется для модели SPMD. Также поддерживает SMP-, MPP- и многопользовательские конфигурации

PVM Поддерживает кластерное программирование гетерогенных сред. Легко

используется для однопользовательских (мелко- и среднемасштабных) ._____кластерных приложений. Также поддерживает МРР-конфигурации .

MICO Поддерживает и распределенное, и параллельное программирование.

Содержит эффективные средства поддержки агентно-ориентированного и мультиагентного программирования

POSIX Поддерживает параллельную обработку данных в одном приложении на

уровне функций или объектов. Позволяет воспользоваться преимуществами SMP- и МРР-конфигурации

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

Наиболее распространенными средами для параллельного и распределенного программирования являются кластеры, SMP- и МРР-компьютеры.

Кластеры — это коллекции, состоящие из нескольких компьютеров, объединенных сетью для создания единой логической системы. С точки зрения приложения такая группа компьютеров выглядит как один виртуальный компьютер. Под MPP-конфигурацией (Massively Parallel Processors — процессоры с массовым параллелизмом) понимается один компьютер, содержащий сотни процессоров, а под SMP-конфигурацией (symmetric multiprocessor — симметричный мультипроцессор) — единая система, в которой тесно связанные процессоры совместно используют общую память и информационный канал. SMP-процессоры разделяют общие ресурсы и являются объектами управления одной операционной системы. Поскольку эта книга представляет собой введение в параллельное и распределенное программирование, нас будут интересовать небольшие кластеры, состоящие из 8-32 процессоров, и многопроцессорные компьютеры с двумя-четырьмя процессорами. И хотя многие рассматриваемые здесь методы можно использовать в MPP- или больших SMP-средах, мы в основном уделяем внимание системам среднего масштаба.

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

Примечания:

3

) В оригинале написано «On the other hand, the distributed application in Figure 1-1 consists of three separate programs with each program executing on a separate computer». Что можно перевести как «С другой стороны, распределенное приложение на рисунке 1-1 состоит из трех отдельных программ, каждая из которых выполняется на отдельном компьютере» (Примечание пирата)

4

M.J. Flynn. Very high-speed computers. Из сборников объединения IEEE, 54, 1901-1909 (декабрь 1966).

5

MPP- Massively Parallel Processors (процессоры с массовым параллелизмом), SMP- symmetric multi-processor(симметричный мультипроцессор).