Основными этапами разработки параллельных приложений являются:
Функциональная декомпозиция разбивает работу приложения на подзадачи таким образом, чтобы каждая подзадача была связана с отдельной функцией. Но не все операции могут выполняться параллельно. Например, сохранение документа и отправка документа выполняются только после завершения всех предыдущих этапов. Форматирование и сбор статистики могут выполняться параллельно, но только после завершения проверки орфографии и пунктуации.
При декомпозиции по данным каждая подзадача работает со своим фрагментом данных, выполняя весть перечень действий. В рассматриваемом примере декомпозиция по данным может применяться к задачам, допускающим работу с фрагментом документа. Таким образом, функции CheckSpelling, CheckPuncto, CalcStat, Format объединяются в одну подзадачу, но создается несколько экземпляров этой подзадачи, которые параллельно работают с разными фрагментами документа. Функции SaveChanges и SendDoc составляют отдельные подзадачи, так как не могут работать с частью документа.
Два основных принципа разделения данных между подзадачами – статический и динамический. При статической декомпозиции фрагменты данных назначаются потокам до начала обработки и, как правило, содержат одинаковое число элементов для каждого потока. Например, разделение массива элементов может осуществляться по равным диапазонам индекса между потоками (range partition).
Основным достоинством статического разделения является независимость работы
потоков (нет проблемы гонки данных) и, как следствие, нет необходимости в средствах
синхронизации для доступа к элементам. Эффективность статической декомпозиции
снижается при разной вычислительной сложности обработки элементов данных.
Например, вычислительная нагрузка обработки i-элемента может зависеть от
индекса элемента.
Разделение по диапазону приводит к несбалансированности нагрузки разных
потоков. Несбалансированность нагрузки снижает эффективность распараллеливания. В
некоторых случаях декомпозиция может быть улучшена и при статическом разбиении,
когда заранее известно какие элементы обладают большей вычислительной
трудоемкостью, а какие меньшей. Например, в случае зависимости вычислительной
трудоемкости от индекса элемента, применение круговой декомпозиции выравнивает
загруженность потоков. Первый поток обрабатывает все четные элементы, второй поток
обрабатывает все нечетные.
В общем случае, когда вычислительная сложность обработки элементов заранее не
известна, сбалансированность загрузки потоков обеспечивает динамическая
декомпозиция.
При динамической декомпозиции каждый поток, участвующий в обработке, обращается за блоком данных (порцией). После обработки блока данных поток обращается за следующей порцией. Динамическая декомпозиция требует синхронизации доступа потоков к структуре данных. Размер блока определяет частоту обращений потоков к структуре. Некоторые алгоритмы динамической декомпозиции увеличивают размер блока в процессе обработки. Если поток быстро обрабатывает элементы, то размер блока для него увеличивается.
- декомпозиция,
- выявление информационных зависимостей между подзадачами,
- масштабирование подзадач
- и балансировка нагрузки для каждого процессора.
Декомпозиция
Под декомпозицией понимается разбиение задачи на относительно независимые части (подзадачи). Декомпозиция задачи может быть проведена несколькими способами:
- по заданиям,
- по данным,
- по информационным потокам.
Декомпозиция по заданиям
(Функциональная декомпозиция) предполагает присвоение разным потокам разных функций. Например, приложение выполняющее правку документа включает следующие функции: проверка орфографии CheckSpelling, проверка пунктуации CheckPuncto, форматирование текста в соответствие с выбранными стилями Format, подсчет статистики по документу CalcStat, сохранение изменений в файле SaveChanges и отправка документа по электронной почте SendDoc.Функциональная декомпозиция разбивает работу приложения на подзадачи таким образом, чтобы каждая подзадача была связана с отдельной функцией. Но не все операции могут выполняться параллельно. Например, сохранение документа и отправка документа выполняются только после завершения всех предыдущих этапов. Форматирование и сбор статистики могут выполняться параллельно, но только после завершения проверки орфографии и пунктуации.
Декомпозиция по информационным потокам
Выделяет подзадачи, работающие с одним типом данных. В рассматриваемом примере могут быть выделены следующие подзадачи:- Работа с черновым документом (орфография и пунктуация):
- Работа с исправленным документом (форматирование и сбор статистики);
- Работа с готовым документом (сохранение и отправка);
При декомпозиции по данным каждая подзадача работает со своим фрагментом данных, выполняя весть перечень действий. В рассматриваемом примере декомпозиция по данным может применяться к задачам, допускающим работу с фрагментом документа. Таким образом, функции CheckSpelling, CheckPuncto, CalcStat, Format объединяются в одну подзадачу, но создается несколько экземпляров этой подзадачи, которые параллельно работают с разными фрагментами документа. Функции SaveChanges и SendDoc составляют отдельные подзадачи, так как не могут работать с частью документа.
Декомпозиция по данным
При декомпозиции по данным каждая подзадача выполняет одни и те же действия, но с разными данными. Во многих задачах, параллельных по данным, существует несколько способов разделения данных. Например, задача матричного умножения допускает разделение по строчкам – каждый поток обрабатывает одну или несколько строчек матрицы, по столбцам – каждый поток обрабатывает один или несколько столбцов, а также по блокам заданного размера.Два основных принципа разделения данных между подзадачами – статический и динамический. При статической декомпозиции фрагменты данных назначаются потокам до начала обработки и, как правило, содержат одинаковое число элементов для каждого потока. Например, разделение массива элементов может осуществляться по равным диапазонам индекса между потоками (range partition).
Основным достоинством статического разделения является независимость работы
потоков (нет проблемы гонки данных) и, как следствие, нет необходимости в средствах
синхронизации для доступа к элементам. Эффективность статической декомпозиции
снижается при разной вычислительной сложности обработки элементов данных.
Например, вычислительная нагрузка обработки i-элемента может зависеть от
индекса элемента.
Разделение по диапазону приводит к несбалансированности нагрузки разных
потоков. Несбалансированность нагрузки снижает эффективность распараллеливания. В
некоторых случаях декомпозиция может быть улучшена и при статическом разбиении,
когда заранее известно какие элементы обладают большей вычислительной
трудоемкостью, а какие меньшей. Например, в случае зависимости вычислительной
трудоемкости от индекса элемента, применение круговой декомпозиции выравнивает
загруженность потоков. Первый поток обрабатывает все четные элементы, второй поток
обрабатывает все нечетные.
В общем случае, когда вычислительная сложность обработки элементов заранее не
известна, сбалансированность загрузки потоков обеспечивает динамическая
декомпозиция.
При динамической декомпозиции каждый поток, участвующий в обработке, обращается за блоком данных (порцией). После обработки блока данных поток обращается за следующей порцией. Динамическая декомпозиция требует синхронизации доступа потоков к структуре данных. Размер блока определяет частоту обращений потоков к структуре. Некоторые алгоритмы динамической декомпозиции увеличивают размер блока в процессе обработки. Если поток быстро обрабатывает элементы, то размер блока для него увеличивается.
