|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vovanius Uryvaeff 2:5020/175.2 25 Oct 2002 20:03:45
To : Stepan M. Pechkin
Subject : А параллельными алгоритмами тут кто-нибудь балуется?
--------------------------------------------------------------------------------
Sun Oct 20 2002 01:11, Stepan M. Pechkin wrote to All:
SMP> * Crossposted in RU.ALGORITHMS
SMP> * Crossposted in PECHKIN.SPEAKS
SMP> O, All!
SMP> Люди добрые, извините, что к вам обращаюсь, я не лодырь, не бомж, не
SMP> пьяница, просто у нас нагрузки такие, что нет возможности ждать, пока
SMP> все разъяснится, надо загодя все делать, а была только одна лекция.
SMP> Есть полное бинарное дерево процессоров с N листьями. Каждый лист
SMP> может хранить O(lg N) бит. Как сложить таким деревом два N lg N-битные
SMP> числа за O(lg N) шагов?
Это скорей не из области алгоритмов, а из области проектирования цифровых
электрических схем.
Схема быстрого переноса называется.
Так вот. Первое, что сделать должны все процессоры одновременно, это
выработать флаги генерации переноса и распространения переноса.
делается это следующим образом:
пусть каждый процессор обрабатывает число в H (=lgN) бит.
Каждый процессор складывает свои два кусочка числа, и если сумма оказалась
равной 2^H-1 то вырабатывается флаг распространения переноса P, если сумма
оказалась больше 2^H-1, то вырабатывается флаг генерации переноса G.
Далее каждый узел, от которого отходят "листья" должен сгенерировать флаги G и
P для всего своего поддерева. это делается так
P=P0 AND P1; G = G0 AND P1 OR G1 (где P0,P1,G0,G1 - флаги распространения и
генерации переноса для младшей и старшей части поддерева соответственно)
и все передается вышестоящему узлу.
После того, как все дошло до самого верхнего узла, начинается следующий этап:
генерация собственно переносов.
тогда он выполнит следующее:
C0 = Сi, C1 = (Ci AND P0) OR G0, где (C0,C1 - флаги переноса, которые он узел
передаст нижестоящим узлам или листьям, Сi - флаг переноса, поступивший от
вышестоящего узла, для самого верхнего узла равен 0)
И так делаем во всех узлах, начиная с верхнего.
когда дело дойдет до процессоров-листьев, тогда если на процассор поступает
перенос, то к ранее вычисленной сумме еще прибавить 1.
Все.
Все можно изобразить в виде этакого алгоритмика:
ADD(A,B,0,N,Y)
begin
MakePG(0,N);
AddSection(A,B[0..N],0);
end
MakePG(M,N)
begin
if(N-M>1):
K := (M+N)/2
MakePG(A,B[M..K) || MakePG(A,B[K..N])
P[M,N]:=P[M,K] AND P[K,M] || G[M,N]:=(G[M,K] AND P[K,N]) OR G[K,N]
else
P[M,N]:=A[M]+B[M]=2^H-1 || G[M,N]:=A[M]+B[M]==2^H-1
then
end
AddSection(M,N,Ci) \\ Ci - перенос
begin
if(N-M>1):
K:=(N+M)/2
AddSection(A,B[M..K],Ci) || AddSection(A,B[K..N],(Ci AND P[M,K]) OR
G[M,K])
else
Y[M] := A[M]+B[M] + Ci
then
end
SMP> Есть полное бинарное дерево процессоров высотой lg N. В N листьев
SMP> его засаживаются числа, а из корня вынимается отсортированный массив.
SMP> Каждый процессор имеет память в N/lg N ячеек. Размер дерева меняется.
SMP> КАК ЭТО ДОЛЖHО РАБОТАТЬ?
Hаверное это параллельная реализация сортировки слиянием.
Hа самом последнем уровне процессоры сортируют массив из двух элементов
простым сравнением,
а следующие ближе к корню делают из двух маленьких отсортированных массивов
один побольше за вполне линейное время.
Send Email to vovanius2000<yxo>mail. ru
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
А параллельными алгоритмами тут кто-нибудь балуется?