Теория и практика параллельных вычислений


Определение времени выполнения параллельного алгоритма - часть 3


Доказательство теоремы 4. Пусть H? есть расписание для достижения минимально возможного времени выполнения T?. Для каждой итерации ?, 0<?<T?, выполнения расписания H? обозначим через n? количество операций, выполняемых в ходе итерации ?. Расписание выполнения алгоритма с использованием p процессоров может быть построено следующим образом. Выполнение алгоритма разделим на T? шагов; на каждом шаге ? следует выполнить все n? операций, которые выполнялись на итерации ? расписания H?. Эти операции могут быть выполнены не более чем за ?n?/p? итераций при использовании p процессоров. Как результат, время выполнения алгоритма Tp может быть оценено следующим образом

Доказательство теоремы дает практический способ построения расписания параллельного алгоритма. Первоначально может быть построено расписание без учета ограниченности числа используемых процессоров (расписание для паракомпьютера). Затем, согласно схеме вывода теоремы, может быть построено расписание для конкретного количества процессоров.




Начало  Назад  Вперед



Книжный магазин