Алгоритм параллельного обхода дерева

From

Gennady Mayko ()

To

Mike Roschin

Date

2002-10-10T15:35:02Z

Area

RU.ALGORITHMS

From: "Gennady Mayko" <gennady.mayko@broadcom.com>

Sat Oct 05 2002 22:54, Mike Roschin wrote to Gennady Mayko:

 MR> Reply to msg from Gennady Mayko(2:5020/400)
 MR> To All written 01.Oct.2002, 11:27
 MR> Ave Gennady Mayko!

 GM>> Есть некоторое дерево, точная структура его не известна. Какие есть
 GM>> алгоритмы полного обхода дерева 

 MR> ВОзможно, что я чего-то не понимаю, но IMHO есть один-единствный способ
 MR> обхода дерева: взался за корешок -> обошел левую ветку -> обошел правую
 MR> ветку. Небольшие нюансы - непринципиальны.

 GM>> с использованием нескольких потоков (процессоров)? 
 GM>> Количество узлов дерева гораздо больше, чем количество потоков,
 GM>> которые практически можно создать.

 MR> PROCEDURE ОбходДерева ( КорневойУзел : УзелДерева );
 MR>   BEGIN
 MR>     ВыполнитьОперациюНадУзлом ( КорневойУзел );

 MR>     IF ЕстьСвободныйПроцесс THEN    
 MR>       ЗапуститьПроцесс ( ОбходДерева ( КорневойУзел->Левое ) );
 MR>     ELSE
 MR>       ОбходДерева ( КорневойУзел->Левое );
 MR>     END;

 MR>     IF ЕстьСвободныйПроцесс THEN    
 MR>       ЗапуститьПроцесс ( ОбходДерева ( КорневойУзел->Правое ) );
 MR>     ELSE
 MR>       ОбходДерева ( КорневойУзел->Правое );
 MR>     END;

 MR>   END ОбходДерева;

 MR> Примерно так. В рельности придется добавить массу приседаний для
 MR> взаимоувязывания процессов, как то: обеспечить реентерабельность процедур
 MR> обработки, локнуть обращение к разделяемым ресурсам, в зависимости от
 MR> организации мультитридовой надстройки согласовать проверку наличных
 MR> пустых тридов и запуск нового трида.
--
Как раз "приседания" и интересуют :) Понятно, что базовых алгоритмов прохода
дерева не так уж много и они хорошо известны.

Например, интересует соотношение "количество потоков" / "количество доступных
CPU". Microsoft рекомендует для Windows выбирать "количество потоков" =
"количество доступных CPU" и, наверное, в этом есть резон. Тогда для
несерверных версий Windows NT4/W2K/XP можно, например, предложить такой
алгоритм - один поток проходит по дереву по "левой" стороне, второй - по
"правой" и, забирая узел для обработки, "атомарно" помечает его. Помеченный
узел в каждом потоке пропускается.

Понятно, что следует уменьшать накладные расходы (как, например, не запускать
каждый раз новый поток, как в алгоритме выше, а использовать свободный поток
из некоторого пула). Тогда нужно организовывать что-то вроде FIFO для хранения
узлов для обработки. Иметь одно FIFO, скорее всего, невыгодно, так как оно
может быть BottleNeck. Тогда интересно определить оптимальную конфигурацию
потоков и этих FIFO.

Ну и так далее.

 MR> Get Warped 3.0!  \\Thesis 

С уважением,
Геннадий Майко.

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)