ScaLAPACK 2.1  2.1 ScaLAPACK: Scalable Linear Algebra PACKage
BI_TreeBS.c
Go to the documentation of this file.
1 #include "Bdef.h"
2
3 /*
4  * Tree_bs/br is a algorithm that does a broadcast send/recv such that the
5  * communication pattern is a tree with an arbitrary number of branches.
6  * The following two pairs of graphs give different ways of viewing the same
7  * algorithm. The first pair shows the trees as they should be visualized
8  * when examining the algorithm. The second pair are isomorphic graphs of
9  * of the first, which show the actual pattern of data movement.
10
11  * Note that a tree broadcast with NBRANCHES = 2 is isomorphic with a
12  * hypercube broadcast (however, it does not require the nodes be a
13  * power of two to work).
14  *
15  * TREE BROADCAST, NBRANCHES = 2 * TREE BROADCAST, NBRANCHES = 3
16  * *
17  * i=4 &______________ *
18  * | \ *
19  * i=2 &______ &______ * i=3 &______________________
20  * | \ | \ * | \ \
21  * i=1 &__ &__ &__ &__ * i=1 &______ &______ &__
22  * | \ | \ | \ | \ * | \ \ | \ \ | \
23  * 0 1 2 3 4 5 6 7 * 0 1 2 3 4 5 6 7
24  *
25  *
26  * ISOMORPHIC GRAPHS OF ABOVE, SHOWN IN MORE FAMILIAR TERMS:
27  *
28  * 0 0
29  * _________|_________ ___________|____________
30  * / | \ / | | \
31  * 4 2 1 6 3 2 1
32  * / \ | | / \
33  * 6 5 3 7 4 5
34  * |
35  * 7
36  */
37 void BI_TreeBS(BLACSCONTEXT *ctxt, BLACBUFF *bp, SDRVPTR send, int nbranches)
38 {
39  int Np, Iam, msgid, i, j;
40  int destdist; /* the distance of the destination node */
41
42  Np = ctxt->scp->Np;
43  if (Np < 2) return;
44  Iam = ctxt->scp->Iam;
45  msgid = Mscopeid(ctxt);
46
47  for (i=nbranches; i < Np; i*=nbranches);
48  for (i /= nbranches; i > 0; i /= nbranches)
49  {
50  j = 1;
51  do
52  {
53  destdist = i*j;
54  if (destdist < Np)
55  send(ctxt, (destdist+Iam)%Np, msgid, bp);
56  }
57  while(++j < nbranches);
58  }
59 } /* end BI_TreeBS */
bLaCbUfF
Definition: Bdef.h:54
bLaCsScOpE::Iam
int Iam
Definition: Bdef.h:17
Mscopeid
#define Mscopeid(ctxt)
Definition: Bdef.h:179
bLaCsCoNtExT
Definition: Bdef.h:23
SDRVPTR
void(* SDRVPTR)(BLACSCONTEXT *, int, int, BLACBUFF *)
Definition: Bdef.h:69
bLaCsCoNtExT::scp
BLACSSCOPE * scp
Definition: Bdef.h:26
Bdef.h
BI_TreeBS
void BI_TreeBS(BLACSCONTEXT *ctxt, BLACBUFF *bp, SDRVPTR send, int nbranches)
Definition: BI_TreeBS.c:37
bLaCsScOpE::Np
int Np
Definition: Bdef.h:17