next up previous contents
Next: Широковещательные посылки Up: Коллективные коммуникации Previous: Коллективные коммуникации   Contents

Коммуникации в виде дерева

Равномерное распределение загрузки по процессорам предполагает определенную организацию передач данных в рамках некоторой структуры. Например, при рассылке входных данных между процессами программы вычисления интеграла хороший результат может дать организация дерева процессов, корнем которого является процесс 0 (рис. 2).

На первой стадии распределения данных процесс 0 посылает данные процессу 4. В течение следующей стадии, процесс 0 посылает данные процессу 2, в то время как процесс 4 посылает те же данные процессу 6. В ходе последней стадии, процесс 0 посылает данные процессу 1, в то время как процесс 2 посылает данные процессу 3, процесс 4 посылает данные процессу 5, и наконец, процесс 6 посылает данные процессу 7. При этом цикл распределения данных уменьшился с 7 этапов до 3. Если существует $p$ процессов, эта процедура позволяет распределять входные данные в $\left\lceil log_{2}(p)\right\rceil $ этапов, вместо $p-1$ этапов, что при достаточно большом $p$ существенно ускоряет процесс.

\includegraphics[scale = 0.7]{fig1.eps}

Рис. 2. Организация процессов в виде дерева

Чтобы модифицировать функцию Get_data() для использования схемы распределения в виде дерева, необходимо ввести цикл из $\left\lceil log_{2}(p)\right\rceil $ итераций. Каждый процесс при этом определяет на каждой стадии:

Отметим, что порядок выполнения передач и организация процессов в виде дерева могут осуществляться разными способами. Поэтому иногда следует использовать другие возможности для эффективной организации передач. Например, в приведенной схеме передача идет в последовательности:

  1. 0 передает в 4;
  2. 0 передает в 2, 4 передает в 6;
  3. 0 передает в 1, 2 передает в 3, 4 передает в 5, 6 передает в 7.
Можно использовать другой вариант, например:

  1. 0 передает в 1;
  2. 0 передает в 2, 1 передает в 3;
  3. 0 передает в 4, 1 передает в 5, 2 передает в 6, 3 передает в 7.


2004-06-22