Задача о широковещательной передаче данных "от одного всем"
Распараллеливание этой задачи необходимо для решения проблемы увеличения скорости централизованного
распространения файлов, изображений, репликаций баз данных, зеркалирования серверов, видео и аудиовещания, для дистанционного
образования и телемедицины и т.д.
Рассмотрим задачу о широковещательной передаче данных из одного узла по сети трехмерного
гиперкуба. Имеются 8 узлов: 000, 001, 010, 011, 100, 101, 110 и 111.
Из узла 000 нужно передать одно и то же сообщение во все остальные узлы,
при этом все узлы могут обмениваться сообщениями.
Эффективный алгоритм таков:
- 1 шаг:
- 2 шаг:
- Узел 000 ---- узел 010
- Узел 001 ---- узел 011
- 3 шаг:
- Узел 000 ---- узел 100
- Узел 000 ---- узел 101
- Узел 010 ---- узел 110
- Узел 011 ---- узел 111
Общее время (time complexity) для этого алгоритма будет оцениваться
как O(log n) и этот алгоритм оптимален. Удобно изображать графически
алгоритмы распределения задачи по процессорам в виде деревьев. Данная задача
может быть представлена следующим образом:
[Назад]
[Оглавление]
[Вперед]
Последнее обновление 21.11.2001 WebMaster