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