|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Gennady Mayko 2:5020/400 10 Oct 2002 15:35:02
To : Mike Roschin
Subject : Алгоритм параллельного обхода дерева
--------------------------------------------------------------------------------
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> ветку. Hебольшие нюансы - непринципиальны.
GM>> с использованием нескольких потоков (процессоров)?
GM>> Количество узлов дерева гораздо больше, чем количество потоков,
GM>> которые практически можно создать.
MR> PROCEDURE ОбходДерева ( КорневойУзел : УзелДерева );
MR> BEGIN
MR> ВыполнитьОперациюHадУзлом ( КорневойУзел );
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> пустых тридов и запуск нового трида.
--
Как раз "приседания" и интересуют :) Понятно, что базовых алгоритмов прохода
дерева не так уж много и они хорошо известны.
Hапример, интересует соотношение "количество потоков" / "количество доступных
CPU". Microsoft рекомендует для Windows выбирать "количество потоков" =
"количество доступных CPU" и, наверное, в этом есть резон. Тогда для
несерверных версий Windows NT4/W2K/XP можно, например, предложить такой
алгоритм - один поток проходит по дереву по "левой" стороне, второй - по
"правой" и, забирая узел для обработки, "атомарно" помечает его. Помеченный
узел в каждом потоке пропускается.
Понятно, что следует уменьшать накладные расходы (как, например, не запускать
каждый раз новый поток, как в алгоритме выше, а использовать свободный поток
из некоторого пула). Тогда нужно организовывать что-то вроде FIFO для хранения
узлов для обработки. Иметь одно FIFO, скорее всего, невыгодно, так как оно
может быть BottleNeck. Тогда интересно определить оптимальную конфигурацию
потоков и этих FIFO.
Hу и так далее.
MR> Get Warped 3.0! \\Thesis
С уважением,
Геннадий Майко.
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
