doc: Add serial to list of ci file reserved words
[charm.git] / src / ck-ldb / ScotchLB.C
1 /** \file ScotchLB.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 "ScotchLB.h"
15 #include "ckgraph.h"
16 #include "scotch.h"
17
18 CreateLBFunc_Def(ScotchLB, "Load balancing using the Scotch graph partitioning library")
19
20 ScotchLB::ScotchLB(const CkLBOptions &opt) : CentralLB(opt) {
21   lbname = "ScotchLB";
22   if(CkMyPe() == 0)
23     CkPrintf("ScotchLB created\n");
24 }
25
26 CmiBool ScotchLB::QueryBalanceNow(int _step) {
27   return CmiTrue;
28 }
29
30 void ScotchLB::work(LDStats *stats) {
31   /** ========================== INITIALIZATION ============================= */
32   ProcArray *parr = new ProcArray(stats);
33   ObjGraph *ogr = new ObjGraph(stats);
34   double start_time = CmiWallTimer();
35
36   /** ============================= STRATEGY ================================ */
37   // convert ObjGraph to the Scotch graph
38   SCOTCH_Num baseval = 0;                       // starting index of vertices
39   SCOTCH_Num vertnbr = ogr->vertices.size();    // number of vertices
40   SCOTCH_Num edgenbr = 0;                       // number of edges
41
42   double maxLoad = 0.0;
43   double minLoad = 0.0;
44   if (vertnbr > 0) {
45     minLoad = ogr->vertices[baseval].getVertexLoad();
46   }
47
48   long maxBytes = 1;
49   int i, j, k, vert;
50
51
52   /** remove duplicate edges from recvFrom */
53   for(i = baseval; i < vertnbr; i++) {
54     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
55       vert = ogr->vertices[i].sendToList[j].getNeighborId();
56       for(k = 0; k < ogr->vertices[i].recvFromList.size(); k++) {
57         if(ogr->vertices[i].recvFromList[k].getNeighborId() == vert) {
58           ogr->vertices[i].sendToList[j].setNumBytes(
59               ogr->vertices[i].sendToList[j].getNumBytes() +
60               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_Strat strat;           // Strategy to achieve partitioning
123
124   /* Initialize data structures */
125   SCOTCH_graphInit (&graph);
126   SCOTCH_stratInit (&strat);
127
128   SCOTCH_graphBuild (&graph, baseval, vertnbr, verttab, NULL, velotab, NULL, edgenbr, edgetab, edlotab); 
129   SCOTCH_graphCheck (&graph);
130
131   SCOTCH_stratGraphMapBuild (&strat, SCOTCH_STRATBALANCE, parr->procs.size (), 0.01);
132   SCOTCH_Num *pemap = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * vertnbr);
133
134   SCOTCH_graphPart(&graph, parr->procs.size(), &strat, pemap);
135
136
137   SCOTCH_graphExit (&graph);
138   SCOTCH_stratExit (&strat);
139
140   free(verttab);
141   free(velotab);
142   free(edgetab);
143   free(edlotab);
144   for(i = baseval; i < vertnbr; i++) {
145     if(pemap[i] != ogr->vertices[i].getCurrentPe()) {
146       ogr->vertices[i].setNewPe(pemap[i]);
147     }
148   }
149
150   free(pemap);
151   /** ============================== CLEANUP ================================ */
152   ogr->convertDecisions(stats);
153   delete parr;
154   delete ogr;
155 }
156
157 #include "ScotchLB.def.h"
158
159 /*@}*/