Декомпозиция

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

Связь

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

Синхронизация

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

Базовые уровни программного параллелизма

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

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

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

• объектов;

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

Параллелизм на уровне инструкций

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

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

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

Параллелизм на уровне подпрограмм

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

Параллелизм на уровне объектов

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

Параллелизм на уровне приложений

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