Теоретическое время коммуникаций
Будем считать время в единицах выполненных операций.
Для того, чтобы научиться оценивать производительность параллельного
вычисления, рассмотрим простейший пример:
Мы хотим сложить n чисел на двух компьютерах, причем каждый компьютер
складывает n/2 чисел, и все числа изначально содержались на двух
компьютерах. Второй компьютер предоставляет результат первому для сложения
двух частей суммы вместе. То есть задача разбивается на следующие фазы:
- Компьютер "1" посылает n/2 чисел компьютеру "2".
- Оба компьютера одновременно складывают n/2 чисел.
- Компьютер "2" посылает частичную сумму назад компьютеру "1".
- Компьютер "1" складывает частичные суммы для получения конечного результата.
Вычисления: (для шагов 2 и 4):
tcomm=n/2+1
Коммуникации: (для шагов 1 и 3):
t_comm=(tstartup+(n/2)tdata)+
(tstartup+tdata)=2tstartup+((n/2)+1)tdata
Отсюда оценим время вычислений как O(n), время коммуникаций -
также как O(n). Итого, общее время будет оцениваться как O(n).
[Назад]
[Оглавление]
[Вперед]
Последнее обновление 21.10.2001 WebMaster