А параллельными алгоритмами тут кто-нибудь балуется?

From

Vovanius Uryvaeff (2:5020/175.2)

To

Stepan M. Pechkin

Date

2002-10-25T20:03:45Z

Area

RU.ALGORITHMS

From: "Vovanius Uryvaeff" <micro-s@vniiofi.ru>

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> КАК ЭТО ДОЛЖНО РАБОТАТЬ?

Наверное это параллельная реализация сортировки слиянием.
На самом последнем уровне процессоры сортируют массив из двух элементов
простым сравнением,
а следующие ближе к корню делают из двух маленьких отсортированных массивов
один побольше за вполне линейное время.

Send Email to vovanius2000<yxo>mail. ru

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