Рекурсивная декомпозиция
Рекурсивная декомпозиция: вид декомпозиции, предполагающий рекурсивное разделение действий общей задачи на подзадачи с нарастающей подробностью (мелкостью).
Рекурсивный процесс выделения задач останавливается на элементарных (неделимых) задачах. Результат декомпозиции — математическое дерево, в котором вершины-листья обозначают элементарные задачи, а прочие вершины обозначают те задачи, результат работы которых составляется из результатов работы задач, выделенных в их составе. Окончательный результат расчёта получается в корневой вершине дерева. Рёбра (ветви) дерева обозначают зависимости между задачами.
Так как все вершины-листья взаимно независимы, максимальным уровнем параллелизма является число листьев в дереве.
Подобные структуры для решения задачи по частям выстраиваются во многих программах и алгоритмах, как, например, в mergesort[1]. В параллельных вычислениях рекурсивную декомпозицию применяют, например, в реализации алгоритма сортировки quicksort.
Бывает, что можно так реструктурировать расчёт, что он становится пригоден к параллелизации через рекурсивную декомпозицию, хотя исходный (последовательный) алгоритм этого расчёта не основывается на решении по частям. Пример: задача нахождения минимального элемента в неупорядоченной последовательности элементов.
— Ю.Т.
- Ссылки и примечания
- ↑ Cormen et al. [42].
Источники
- Introduction to parallel computing / 2nd ed. ...
