doc: Add serial to list of ci file reserved words
[charm.git] / src / ck-ldb / TeamLB.C
1 /** \file TeamLB.C
2  *  Written by Esteban Meneses, 2010-11-24
3  *  Updated by Abhinav Bhatele, 2010-12-09 to use ckgraph
4  */
5
6 /**
7  * \addtogroup CkLdb
8 */
9 /*@{*/
10
11 #include "TeamLB.h"
12 #include "ckgraph.h"
13 #include "metis.h"
14
15 CreateLBFunc_Def(TeamLB, "Use Metis(tm) to partition object graph at two levels: team level and processor level")
16
17 TeamLB::TeamLB(const CkLBOptions &opt): CentralLB(opt)
18 {
19   lbname = "TeamLB";
20   if (CkMyPe() == 0)
21     CkPrintf("[%d] TeamLB created\n",CkMyPe());
22
23   // setting number of teams and team size
24   teamSize = _lb_args.teamSize();
25   numberTeams = CkNumPes() / teamSize;
26 }
27
28 /**
29  * @brief METIS function that performs a balanced k-way partitioning of the
30  * graph, considering the communication volume (hence the "V" in the name of
31  * the function).
32
33    extern "C" void METIS_PartGraphRecursive(int*, int*, int*, int*, int*, int*,
34                               int*, int*, int*, int*, int*);
35  */
36
37
38 /**
39  * @brief Load balancing function. It uses METIS in a two step approach. The
40  * first step consists in splitting the objects into teams. METIS is able to
41  * minimize the communication volume across the teams while balancing the load
42  * among the different teams. The second step goes deep in each team to balance
43  * the load in the processors belonging to that particular team.
44  */
45 void TeamLB::work(LDStats* stats)
46 {
47   /** ========================== INITIALIZATION ============================= */
48   ProcArray *parr = new ProcArray(stats);
49   ObjGraph *ogr = new ObjGraph(stats);
50
51   /** ============================= STRATEGY ================================ */
52   if (_lb_args.debug() >= 2) {
53     CkPrintf("[%d] In TeamLB Strategy...\n", CkMyPe());
54   }
55
56   // convert ObjGraph to the adjacency structure
57   int numVertices = ogr->vertices.size();       // number of vertices
58   int numEdges = 0;                             // number of edges
59
60   double maxLoad = 0.0;
61   int maxBytes = 0, i, j, k;
62
63   /** both object load and number of bytes exchanged are normalized to an
64    *  integer between 0 and 256 */
65   for(i = 0; i < numVertices; i++) {
66     if(ogr->vertices[i].getVertexLoad() > maxLoad)
67       maxLoad = ogr->vertices[i].getVertexLoad();
68     numEdges += ogr->vertices[i].sendToList.size();
69     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
70       if(ogr->vertices[i].sendToList[j].getNumBytes() > maxBytes)
71         maxBytes = ogr->vertices[i].sendToList[j].getNumBytes();
72     }
73   }
74
75   /* adjacency list */
76   idxtype *xadj = new idxtype[numVertices + 1];
77   /* id of the neighbors */
78   idxtype *adjncy = new idxtype[numEdges];
79   /* weights of the vertices */
80   idxtype *vwgt = new idxtype[numVertices];
81   /* weights of the edges */
82   idxtype *adjwgt = new idxtype[numEdges];
83
84   int edgeNum = 0;
85
86   for(i = 0; i < numVertices; i++) {
87     xadj[i] = edgeNum;
88     vwgt[i] = (int)( (ogr->vertices[i].getVertexLoad() * 128) /maxLoad );
89     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
90       adjncy[edgeNum] = ogr->vertices[i].sendToList[j].getNeighborId();
91       adjwgt[edgeNum] = (int)( (ogr->vertices[i].sendToList[j].getNumBytes() * 128) / maxBytes );
92       edgeNum++;
93     }
94   }
95   xadj[i] = edgeNum;
96   CkAssert(edgeNum == numEdges);
97
98   int wgtflag = 3;      // weights both on vertices and edges
99   int numflag = 0;      // C Style numbering
100   int options[5];
101   options[0] = 0;       // use default values
102   int edgecut;          // number of edges cut by the partitioning
103   idxtype *pemap = new idxtype[numVertices];
104
105   if (_lb_args.debug() >= 1)
106   CkPrintf("[%d] calling METIS_PartGraphRecursive.\n", CkMyPe());
107
108   METIS_PartGraphRecursive(&numVertices, xadj, adjncy, vwgt, adjwgt,
109             &wgtflag, &numflag, &numberTeams, options, &edgecut, pemap);
110
111   int *global_pemap = new int[numVertices];
112
113   // partitioning each team
114   if(teamSize > 1) {
115     idxtype *team_xadj = new idxtype[numVertices + 1];
116     idxtype *team_adjncy = new idxtype[numEdges];
117     idxtype *team_vwgt = new idxtype[numVertices];
118     idxtype *team_adjwgt = new idxtype[numEdges];
119     idxtype *team_pemap = new idxtype[numVertices];
120
121     int teamEdgecut, node;
122     int *mapping = new int[numVertices];
123     int *invMapping = new int[numVertices];
124
125     // traversing the list of teams and load balancing each one
126     for(i=0; i<numberTeams; i++) {
127       int teamMembers = 0;      // number of vertices in a team
128
129       // collecting all the elements of a particular team
130       // mapping stores the association of local to global index
131       // invMapping stores the inverse association
132       for(j = 0; j < numVertices; j++) {
133         if(pemap[j] == i) {
134           mapping[teamMembers] = j;
135           invMapping[j] = teamMembers;
136           team_vwgt[teamMembers] = vwgt[j];
137           teamMembers++;
138         }
139       }
140
141       // building up the adjacency data structures
142       int teamIndex = 0;
143       for(j = 0; j < teamMembers; j++) {
144         team_xadj[j] = teamIndex;
145         for(k = xadj[mapping[j]]; k < xadj[mapping[j]+1]; k++) {
146           node = adjncy[k];
147           if(pemap[node] == i) {
148             team_adjncy[teamIndex] = invMapping[node];
149             team_adjwgt[teamIndex] = adjwgt[k];
150             teamIndex++;
151           }
152         }
153       }
154       team_xadj[teamMembers] = teamIndex;
155
156       // calling METIS library
157       METIS_PartGraphRecursive(&teamMembers, team_xadj, team_adjncy, team_vwgt,
158                   team_adjwgt, &wgtflag, &numflag, &teamSize, options,
159                   &teamEdgecut, team_pemap);
160
161       // converting local mapping into global mapping
162       for(j = 0; j < teamMembers; j++) {
163         global_pemap[mapping[j]] = i*teamSize + team_pemap[j];
164       }
165                         
166     } // end for
167
168     delete[] team_xadj;
169     delete[] team_adjncy;
170     delete[] team_vwgt;
171     delete[] team_adjwgt;
172     delete[] team_pemap;
173
174     delete[] mapping;
175     delete[] invMapping;
176   } else {
177     delete[] global_pemap;
178     global_pemap = pemap;
179   }
180
181   delete[] xadj;
182   delete[] adjncy;
183   delete[] vwgt;
184   delete[] adjwgt;
185
186   if (_lb_args.debug() >= 1) {
187    CkPrintf("[%d] TeamLB done! \n", CkMyPe());
188   }
189
190   for(i = 0; i < numVertices; i++) {
191     if(pemap[i] != ogr->vertices[i].getCurrentPe())
192       ogr->vertices[i].setNewPe(pemap[i]);
193   }
194
195   delete[] pemap;
196
197   /** ============================== CLEANUP ================================ */
198   ogr->convertDecisions(stats);
199 }
200
201 #include "TeamLB.def.h"
202
203 /*@}*/