ScaLAPACK 2.1  2.1 ScaLAPACK: Scalable Linear Algebra PACKage
BI_TreeComb.c
Go to the documentation of this file.
1 #include "Bdef.h"
2
3 /*
4  * This topology supports trees with arbitrary numbers of branches at
5  * each step. The following pictures show the tree that should be visualized
6  * when examining the algorithm.
7  *
8  * TREE GLOBAL OP, NBRANCHES = 2 * TREE GLOBAL OP, NBRANCHES = 3
9  * *
10  * i=4 &______________ *
11  * | \ *
12  * i=2 &______ &______ * i=3 &______________________
13  * | \ | \ * | \ \
14  * i=1 &__ &__ &__ &__ * i=1 &______ &______ &__
15  * | \ | \ | \ | \ * | \ \ | \ \ | \
16  * 0 1 2 3 4 5 6 7 * 0 1 2 3 4 5 6 7
17  */
18
19 void BI_TreeComb(BLACSCONTEXT *ctxt, BLACBUFF *bp, BLACBUFF *bp2,
20  int N, VVFUNPTR Xvvop, int dest, int nbranches)
21 /*
22  * -- V1.1ALPHA (test version) BLACS routine --
23  * University of Tennessee, October 1, 1995
24  * Written by Clint Whaley.
25  *
26  * Purpose
27  * =======
28  * Perform a element-by-element combine on vectors.
29  * If rdest1 = -1, the answer will be left on all participating processes.
30  * Otherwise, only the process at grid coordinates {rdest1, cdest1} will
31  * have the final answer. Other Processes will have intermediate (useless)
32  * values.
33  *
34  * Arguments
35  * =========
36  * CTXT (input) pointer to BLACSCONTEXT
37  * The BLACS context where operation is taking place.
38  *
39  * BP (input/output) pointer to BLACBUFF.
40  * BLACBUFF is a special data type used by the BLACS to control
41  * buffers and the asynchronous operations coming out of them.
42  * This BLACBUFF should have a buffer who's first N elements
43  * contain the data to be combined. Additional space may be
44  * required, depending upon what combine is being performed.
45  *
46  * BP2 (workspace) pointer to BLACBUFF.
47  * This BLACBUFF is used to receive information for combining with
48  * this process's information.
49  *
50  * DEST (input) int
53  *
54  * N (input) int
55  * The number of elements in the vector. N >= 0.
56  *
57  * Xvvop (input) pointer to typed operation function
58  * Points to a typed function which performs the required operation
59  * (e.g. summation) on the two N-element vectors.
60  *
61  * NBRANCHES (input) int
62  * Indicates the degree of the tree to use (see picture above).
63  *
64  * ------------------------------------------------------------------------
65  */
66 {
67  void BI_UpdateBuffs(BLACBUFF *);
68  BLACBUFF *BI_GetBuff(int);
69  int BI_BuffIsFree(BLACBUFF *, int);
70  void BI_Ssend(BLACSCONTEXT *, int, int, BLACBUFF *);
71  void BI_Srecv(BLACSCONTEXT *, int, int, BLACBUFF *);
72  void BI_Rsend(BLACSCONTEXT *, int, int, BLACBUFF *);
73  void BI_Arecv(BLACSCONTEXT *, int, int, BLACBUFF *);
74
75  int Np, Iam, msgid, Rmsgid, i, j;
76  int nrcvs=0; /* Number of ReCeiVeS to do */
77  int REBS; /* should info be RE-BroadcaSt? */
78  int rightedge; /* right-most receiving node */
79  int mydist; /* my distance from destination node */
80  int dist;
81  int src; /* Used if we must force repeatability */
82
83  Np = ctxt->scp->Np;
84  if (Np < 2) return;
85  Iam = ctxt->scp->Iam;
86  msgid = Mscopeid(ctxt);
87  Rmsgid = Mscopeid(ctxt);
88  if (REBS = (dest == -1)) dest = 0;
89
90  mydist = (Np + Iam - dest) % Np;
91  if (REBS)
92  {
93  dist = mydist;
94  if (mydist != 0) BI_Arecv(ctxt, BANYNODE, Rmsgid, bp);
95  }
96
97  if (nbranches == FULLCON) nbranches = Np;
98  rightedge = Np - 1 - (Np-1)%nbranches;
99
100  for (i=1; (i < Np); i *= nbranches)
101  {
102  if (mydist%nbranches) /* nodes that send to other nodes */
103  {
104  BI_Ssend(ctxt, (dest + (mydist-mydist%nbranches)*i)%Np, msgid, bp);
105  break; /* I'm done */
106  }
107  else
108  {
109  if (mydist != rightedge) nrcvs = nbranches - 1;
110  else nrcvs = (Np + i - 1) / i - rightedge - 1;
111  mydist /= nbranches;
112  rightedge /= nbranches;
113  rightedge -= (rightedge % nbranches);
114
115  if (!ctxt->TopsRepeat)
116  {
117  for (j=nrcvs; j; j--)
118  {
119  BI_Srecv(ctxt, BANYNODE, msgid, bp2);
120  Xvvop(N, bp->Buff, bp2->Buff);
121  }
122  }
123  else
124  {
125  src = (Iam + i) % Np;
126  for (j=nrcvs; j; j--)
127  {
128  BI_Srecv(ctxt, src, msgid, bp2);
129  Xvvop(N, bp->Buff, bp2->Buff);
130  src = (src + i) % Np;
131  }
132  }
133  }
134  }
135
136 /*
138  */
139  if (REBS)
140  {
141  mydist = dist;
142  for (i=2; i < Np; i <<= 1);
143  if (mydist > 0) BI_BuffIsFree(bp, 1);
144
145  while (i > 1)
146  {
147  if ( !(mydist%i) )
148  {
149  i >>= 1;
150  dist = mydist + i;
151  if (dist < Np) BI_Rsend(ctxt, dist, Rmsgid, bp);
152  }
153  else i >>= 1;
154  }
155  }
156 } /* end BI_TreeComb */
bLaCsCoNtExT::TopsRepeat
int TopsRepeat
Definition: Bdef.h:27
BI_GetBuff
BLACBUFF * BI_GetBuff(int length)
Definition: BI_GetBuff.c:36
bLaCbUfF::Buff
char * Buff
Definition: Bdef.h:56
FULLCON
#define FULLCON
Definition: Bdef.h:100
BI_Ssend
void BI_Ssend(BLACSCONTEXT *ctxt, int dest, int msgid, BLACBUFF *bp)
Definition: BI_Ssend.c:3
bLaCbUfF
Definition: Bdef.h:54
VVFUNPTR
void(* VVFUNPTR)(int, char *, char *)
Definition: Bdef.h:68
bLaCsScOpE::Iam
int Iam
Definition: Bdef.h:17
Mscopeid
#define Mscopeid(ctxt)
Definition: Bdef.h:179
bLaCsCoNtExT
Definition: Bdef.h:23
BI_TreeComb
void BI_TreeComb(BLACSCONTEXT *ctxt, BLACBUFF *bp, BLACBUFF *bp2, int N, VVFUNPTR Xvvop, int dest, int nbranches)
Definition: BI_TreeComb.c:19
BI_Rsend
void BI_Rsend(BLACSCONTEXT *ctxt, int dest, int msgid, BLACBUFF *bp)
Definition: BI_Rsend.c:4
bLaCsCoNtExT::scp
BLACSSCOPE * scp
Definition: Bdef.h:26
Bdef.h
BI_Arecv
void BI_Arecv(BLACSCONTEXT *ctxt, int src, int msgid, BLACBUFF *bp)
Definition: BI_Arecv.c:3
BI_Srecv
void BI_Srecv(BLACSCONTEXT *ctxt, int src, int msgid, BLACBUFF *bp)
Definition: BI_Srecv.c:3
bLaCsScOpE::Np
int Np
Definition: Bdef.h:17
BANYNODE
#define BANYNODE
Definition: Bdef.h:76
BI_UpdateBuffs
void BI_UpdateBuffs(BLACBUFF *Newbp)
Definition: BI_UpdateBuffs.c:3
BI_BuffIsFree
int BI_BuffIsFree(BLACBUFF *bp, int Wait)
Definition: BI_BuffIsFree.c:3