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