Составители:
Рубрика:
12
3.
Укрупнение
.
Подзадачи
объединяются
в
более
крупные
блоки
,
если
это
позволяет
повысить
эффективность
алгоритма
и
снизить
трудоемкость
разработки
.
4.
Планирование
вычислений
.
Распределение
подзадач
между
процессорами
.
Основной
критерий
выбора
способа
размещения
подзадач
эффективное
использование
процессоров
с
минимальными
затратами
времени
на
обмены
данными
.
Рассмотрим
эти
этапы
подробнее
.
Декомпозиция (сегментирование, расщепление)
Существуют
разные
методы
декомпозиции
.
Рассмотрим
основные
подходы
.
Декомпозиция по данным
Вначале
сегментируются
данные
,
затем
алгоритм
их
обработки
.
Данные
разбиваются
на
фрагменты
приблизительно
одинакового
размера
.
С
фрагментами
данных
связываются
операции
их
обработки
,
из
которых
и
формируются
подзадачи
.
Затем
определяются
необходимые
пересылки
данных
.
Пересечение
частей
,
на
которые
разбивается
задача
,
должно
быть
сведено
к
минимуму
,
что
позволяет
избежать
дублирования
вычислений
.
Схема
разбиения
в
дальнейшем
может
уточняться
.
Если
необходимо
для
уменьшения
числа
обменов
,
допускается
увеличение
степени
перекрытия
подзадач
.
Сначала
анализируются
структуры
данных
наибольшего
размера
,
либо
те
,
обращение
к
которым
происходит
чаще
всего
.
На
разных
стадиях
расчета
могут
использоваться
разные
структуры
данных
,
поэтому
могут
использоваться
как
статические
,
так
и
динамические
схемы
декомпозиции
этих
структур
.
Рекурсивная дихотомия
Используется
для
разбиения
области
на
подобласти
,
которым
соответствует
примерно
одинаковая
трудоемкость
вычислений
,
а
коммуникации
сведены
к
минимуму
.
Область
сначала
разбивается
на
две
части
вдоль
одного
измерения
.
Разбиение
повторяется
рекурсивно
в
каждой
новой
подобласти
столько
раз
,
сколько
потребуется
для
получения
необходимого
числа
подзадач
.
Рекурсивная координатная дихотомия
Может
применяться
к
нерегулярным
сеткам
.
Деление
выполняется
на
каждом
шаге
вдоль
того
измерения
,
по
которому
сетка
имеет
наибольшую
протяженность
.
Метод рекурсивной дихотомии графа
Используется
для
нерегулярных
сеток
.
В
нем
с
помощью
информации
о
топологии
решетки
минимизируется
количество
ребер
,
пересекающих
границы
подобластей
.
Это
позволяет
снизить
количество
коммуникаций
.
Функциональная декомпозиция
Вначале
сегментируется
вычислительный
алгоритм
,
а
затем
уже
под
эту
схему
подгоняется
схема
декомпозиции
данных
.
Метод
функциональной
декомпозиции
может
оказаться
полезным
в
ситуации
,
где
нет
структур
данных
,
которые
очевидно
могли
бы
быть
распараллелены
.
Эффективность
декомпозиции
обеспечивается
выполнением
следующих
рекомендаций
:
•
количество
подзадач
после
декомпозиции
должно
примерно
на
порядок
превосходить
количество
процессоров
;
•
следует
избегать
лишних
вычислений
и
пересылок
данных
;
Страницы
- « первая
- ‹ предыдущая
- …
- 10
- 11
- 12
- 13
- 14
- …
- следующая ›
- последняя »
