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

         

Пусть H? есть расписание для


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

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


Содержание  Назад  Вперед







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий