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

Каталог документации / Раздел "Программирование в Linux" / Оглавление документа

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

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

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

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

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

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

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

принимает ли он данные, и если да, то каков источник данных;
передает ли он данные, и если да, то каков приемник данных.

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

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

Можно использовать другой вариант, например:

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

2004-06-22

Партнёры:

Хостинг:

Закладки на сайте
Проследить за страницей

Created 1996-2024 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру