doc: Add serial to list of ci file reserved words
[charm.git] / src / ck-ldb / ScotchTopoLB.C
1 /** \file ScotchTopoLB.C
2  *  Authors: Abhinav S Bhatele (bhatele@illinois.edu)
3  *           Sebastien Fourestier (fouresti@labri.fr)
4  *  Date Created: November 25th, 2010
5  *
6  */
7
8 /**
9  *  \addtogroup CkLdb
10  */
11
12 /*@{*/
13
14 #include "ScotchTopoLB.h"
15 #include "TopoManager.h"
16 #include "ckgraph.h"
17 #include "scotch.h"
18
19 CreateLBFunc_Def(ScotchTopoLB, "Load balancing using the Scotch graph partitioning library")
20
21 ScotchTopoLB::ScotchTopoLB(const CkLBOptions &opt) : CentralLB(opt) {
22   lbname = "ScotchTopoLB";
23   if(CkMyPe() == 0)
24     CkPrintf("ScotchTopoLB created\n");
25 }
26
27 CmiBool ScotchTopoLB::QueryBalanceNow(int _step) {
28   return CmiTrue;
29 }
30
31 void ScotchTopoLB::work(LDStats *stats) {
32   /** ========================== INITIALIZATION ============================= */
33   ProcArray *parr = new ProcArray(stats);
34   ObjGraph *ogr = new ObjGraph(stats);
35   TopoManager tmgr;
36   double start_time = CmiWallTimer();
37
38   /** ============================= STRATEGY ================================ */
39   // convert ObjGraph to the Scotch graph
40   SCOTCH_Num baseval = 0;                       // starting index of vertices
41   SCOTCH_Num vertnbr = ogr->vertices.size();    // number of vertices
42   SCOTCH_Num edgenbr = 0;                       // number of edges
43
44   double maxLoad = 0.0;
45   double minLoad = 0.0;
46   if (vertnbr > 0) {
47     minLoad = ogr->vertices[baseval].getVertexLoad();
48   }
49
50   long maxBytes = 1;
51   int i, j, k, vert;
52
53
54   /** remove duplicate edges from recvFrom */
55   for(i = baseval; i < vertnbr; i++) {
56     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
57       vert = ogr->vertices[i].sendToList[j].getNeighborId();
58       for(k = 0; k < ogr->vertices[i].recvFromList.size(); k++) {
59         if(ogr->vertices[i].recvFromList[k].getNeighborId() == vert) {
60           ogr->vertices[i].sendToList[j].setNumBytes(ogr->vertices[i].sendToList[j].getNumBytes() + ogr->vertices[i].recvFromList[k].getNumBytes());
61           ogr->vertices[i].recvFromList.erase(ogr->vertices[i].recvFromList.begin() + k);
62         }
63       }
64     }
65   }
66   /** the object load is normalized to an integer between 0 and 256 */
67   for(i = baseval; i < vertnbr; i++) {
68     if(ogr->vertices[i].getVertexLoad() > maxLoad)
69       maxLoad = ogr->vertices[i].getVertexLoad();
70
71     if (ogr->vertices[i].getVertexLoad() < minLoad) {
72       minLoad = ogr->vertices[i].getVertexLoad();
73     }
74     edgenbr += ogr->vertices[i].sendToList.size() + ogr->vertices[i].recvFromList.size();
75   }
76
77   for(i = baseval; i < vertnbr; i++) {
78     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
79       if (ogr->vertices[i].sendToList[j].getNumBytes() > maxBytes) {
80         maxBytes = ogr->vertices[i].sendToList[j].getNumBytes();
81       }
82     }
83     for(j = 0; j < ogr->vertices[i].recvFromList.size(); j++) {
84       if (ogr->vertices[i].recvFromList[j].getNumBytes() > maxBytes) {
85         maxBytes = ogr->vertices[i].recvFromList[j].getNumBytes();
86       }
87     }
88   }
89
90
91   /* adjacency list */
92   SCOTCH_Num *verttab = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * (vertnbr+1));
93   /* loads of vertices */
94   SCOTCH_Num *velotab = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * vertnbr);
95   /* id of the neighbors */
96   SCOTCH_Num *edgetab = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * edgenbr);
97   /* number of bytes exchanged */
98   SCOTCH_Num *edlotab = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * edgenbr);
99
100   int edgeNum = 0;
101   double ratio = 256.0/maxLoad;
102   double byteRatio = 1024.0/maxBytes;
103
104   for(i = baseval; i < vertnbr; i++) {
105     verttab[i] = edgeNum;
106     velotab[i] = (SCOTCH_Num) ceil(ogr->vertices[i].getVertexLoad() * ratio);
107     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
108       edgetab[edgeNum] = ogr->vertices[i].sendToList[j].getNeighborId();
109       edlotab[edgeNum] = (int) ceil(ogr->vertices[i].sendToList[j].getNumBytes() * byteRatio);
110       edgeNum++;
111     }
112     for(j = 0; j < ogr->vertices[i].recvFromList.size(); j++) {
113       edgetab[edgeNum] = ogr->vertices[i].recvFromList[j].getNeighborId();
114       edlotab[edgeNum] = (int) ceil(ogr->vertices[i].recvFromList[j].getNumBytes() * byteRatio);
115       edgeNum++;
116     }
117   }
118   verttab[i] = edgeNum;
119   CkAssert(edgeNum == edgenbr);
120
121   SCOTCH_Graph graph;           // Graph to partition
122   SCOTCH_Arch  arch;            // Target architecture
123   SCOTCH_Strat strat;           // Strategy to achieve partitioning
124
125   /* Initialize data structures */
126   SCOTCH_graphInit (&graph);
127   SCOTCH_stratInit (&strat);
128
129   SCOTCH_graphBuild (&graph, baseval, vertnbr, verttab, NULL, velotab, NULL, edgenbr, edgetab, edlotab); 
130   SCOTCH_graphCheck (&graph);
131
132
133   SCOTCH_stratGraphMapBuild (&strat, SCOTCH_STRATBALANCE, parr->procs.size (), 0.01);
134
135   SCOTCH_Num *pemap = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * vertnbr);
136   SCOTCH_archInit (&arch);
137   SCOTCH_archTorus3 (&arch, tmgr.getDimNX(), tmgr.getDimNY(), tmgr.getDimNZ());
138
139   SCOTCH_graphMap (&graph, &arch, &strat, pemap);
140
141   SCOTCH_graphExit (&graph);
142   SCOTCH_archExit  (&arch);
143   SCOTCH_stratExit (&strat);
144
145   free(verttab);
146   free(velotab);
147   free(edgetab);
148   free(edlotab);
149   for(i = baseval; i < vertnbr; i++) {
150     if(pemap[i] != ogr->vertices[i].getCurrentPe()) {
151       ogr->vertices[i].setNewPe(pemap[i]);
152     }
153   }
154
155   free(pemap);
156   /** ============================== CLEANUP ================================ */
157   ogr->convertDecisions(stats);
158   delete ogr;
159 }
160
161 #include "ScotchTopoLB.def.h"
162
163 /*@}*/