Параллельное и распределенное программирование на С++
Шрифт:
Преимущества параллельного программирования
Программы, надлежащее качество проектирования которых позволяет воспользоваться преимуществами параллелизма, могут выполняться быстрее, чем их последовательные эквиваленты, что повышает их рыночную стоимость. Иногда скорость может спасти жизнь. В таких случаях быстрее означает лучше. Иногда решение некоторых проблем представляется естественнее в виде коллекции одновременно выполняемых задач. Это характерно для таких областей, как научное программирование, математическое и программирование искусственного интеллекта. Это означает, что в некоторых ситуациях технологии параллельного программирования снижают трудозатраты разработчика ПО, позволяя ему напрямую реализовать структуры данных, алгоритмы и эвристические методы, разрабатываемые учеными. При этом используется специализированное оборудование. Например, в мультимедийной программе с широкими функциональными возможностями с целью получения более высокой производительности ее логика может быть распределена между такими специализированными процессорами, как микросхемы компьютерной графики, цифровые звуковые процессоры и математические спецпроцессоры. К таким процессорам обычно обеспечивается одновременный доступ. МРР-компьютеры (Massively Parallel Processors — процессоры с массовым параллелизмом) имеют сотни, а иногда и тысячи процессоров, что позволяет их использовать для решения проблем, которые просто не реально решить последовательными методами. Однако при использовании МРР-компьютеров (т.е. при объединении скорости и «грубой силы») невозможное становится возможным. К категории
Простейшая модель параллельного программирования (PRAM)
В качестве простейшей модели, отражающей базовые концепции параллельного программирования, рассмотрим модель 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. Разработка ПО — это процесс перевода принципов, идей, шаблонов, правил, алгоритмов или формул в набор инструкций, которые выполняются, и данных, которые обрабатываются компьютером. Это, в основном, и составляет процесс моделирования. Программные модели — это воспроизведение в виде ПО некоторой реальной задачи, процесса или идеала. Цель модели— сымитировать или скопировать поведение и характеристики некоторой реальной сущности в конкретной предметной области. Процесс моделирования вскрывает естественную декомпозицию работ программного решения. Чем лучше модель понята и разработана, тем более естественной будет декомпозиция работ. Наша цель — обнаружить параллелизм и распределение с помощью моделирования. Если естественный параллелизм не наблюдается, не стоит его навязывать насильно. На вопрос, как разбить приложение на параллельно выполняемые части, необходимо найти ответ в период проектирования, и правильность этого ответа должна стать очевидной в модели решения. Если модель задачи и решения не предполагает параллелизма и распределения, следует попытаться найти последовательное решение. Если последовательное решение оказывается неудачным, эта неудача может дать ключ к нужному параллельному решению.
Связь
После декомпозиции программного решения на ряд параллельно выполняемых частей обычно возникает вопрос о связи этих частей между собой. Как же реализовать связь, если эти части разнесены по различным процессам или различным компьютерам? Должны ли различные части ПО совместно использовать общую область памяти? Каким образом одна часть ПО узнает о том, что другая справилась со своей задачей? Какая часть должна первой приступить к работе? Откуда один компонент узнает об отказе другого компонента? На эти и многие другие вопросы необходимо найти ответы при проектировании параллельных и распределенных систем. Если отдельным частям ПО не нужно связываться между собой, значит, они в действительности не образуют единое приложение.