Цено-оптимальные (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), не является цено-оптимальным.

left up right [Назад] [Оглавление] [Вперед]
Последнее обновление 21.10.2001 WebMaster