Цено-оптимальные (cost-optimal) алгоритмы
Величина Cost
указывает число связей в сети процессоров.
Определение:
Цено-оптимальный (связе-оптимальный), или работа-эффективный
(work-efficient), или оптимальный по процессорному времени (processor-time
optimality) алгоритм - это такой алгоритм, в котором величина цены
cost для решения проблемы пропорциональна времени выполнения на одном
процессоре системы (используя наиболее быстрый последовательный алгоритм):
Cost=tp*n=k*ts , где
k является константой.
Пример: Предположим, что наилучший
последовательный алгоритм для решения некой проблемы имеет общее время (time
complexity), равное O(n log(n)). Параллельный алгоритм для
решения той же проблемы с использованием n процессоров и имеющий "общее" время
O(log n) является ценооптимальным, тогда как параллельный
алгоритм, использующий n2 процессоров и имеющий "общее"
время O(1), не является цено-оптимальным.
[Назад] [Оглавление] [Вперед]
Последнее обновление 21.10.2001 WebMaster