doc: Add serial to list of ci file reserved words
[charm.git] / src / ck-ldb / ScotchRefineLB.C
1 /** \file ScotchRefineLB.C
2  *
3  */
4
5 /**
6  *  \addtogroup CkLdb
7  */
8
9 /*@{*/
10
11 #include "ScotchRefineLB.h"
12 #include "ckgraph.h"
13 #include "scotch.h"
14
15 CreateLBFunc_Def(ScotchRefineLB, "Load balancing using the Scotch graph partitioning library")
16
17 ScotchRefineLB::ScotchRefineLB(const CkLBOptions &opt) : CentralLB(opt) {
18   lbname = "ScotchRefineLB";
19   if(CkMyPe() == 0)
20     CkPrintf("ScotchRefineLB created\n");
21 }
22
23 CmiBool ScotchRefineLB::QueryBalanceNow(int _step) {
24   return CmiTrue;
25 }
26
27 void ScotchRefineLB::work(LDStats *stats) {
28   /** ========================== INITIALIZATION ============================= */
29   ProcArray *parr = new ProcArray(stats);
30   ObjGraph *ogr = new ObjGraph(stats);
31   int cost_array[10] = {64, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536};
32
33   /** ============================= STRATEGY ================================ */
34   // convert ObjGraph to the Scotch graph
35   SCOTCH_Num baseval = 0;                       // starting index of vertices
36   SCOTCH_Num vertnbr = ogr->vertices.size();    // number of vertices
37   SCOTCH_Num edgenbr = 0;                       // number of edges
38
39   SCOTCH_Num *oldpemap = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * vertnbr);
40
41   double maxLoad = 0.0;
42   double minLoad = 0.0;
43   if (vertnbr > 0) {
44     minLoad = ogr->vertices[baseval].getVertexLoad();
45   }
46
47   long maxBytes = 1;
48   int i, j, k, vert;
49   
50
51   /** remove duplicate edges from recvFrom */
52   for(i = baseval; i < vertnbr; i++) {
53     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
54       vert = ogr->vertices[i].sendToList[j].getNeighborId();
55       for(k = 0; k < ogr->vertices[i].recvFromList.size(); k++) {
56         if(ogr->vertices[i].recvFromList[k].getNeighborId() == vert) {
57           ogr->vertices[i].sendToList[j].setNumBytes(ogr->vertices[i].sendToList[j].getNumBytes() + ogr->vertices[i].recvFromList[k].getNumBytes());
58           ogr->vertices[i].recvFromList.erase(ogr->vertices[i].recvFromList.begin() + k);
59         }
60       }
61     }
62   }
63
64   /** the object load is normalized to an integer between 0 and 256 */
65   for(i = baseval; i < vertnbr; i++) {
66     if(ogr->vertices[i].getVertexLoad() > maxLoad)
67       maxLoad = ogr->vertices[i].getVertexLoad();
68
69     if (ogr->vertices[i].getVertexLoad() < minLoad) {
70       minLoad = ogr->vertices[i].getVertexLoad();
71     }
72     edgenbr += ogr->vertices[i].sendToList.size() + ogr->vertices[i].recvFromList.size();
73     oldpemap[i] = ogr->vertices[i].getCurrentPe();
74   }
75
76   for(i = baseval; i < vertnbr; i++) {
77     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
78       if (ogr->vertices[i].sendToList[j].getNumBytes() > maxBytes) {
79         maxBytes = ogr->vertices[i].sendToList[j].getNumBytes();
80       }
81     }
82     for(j = 0; j < ogr->vertices[i].recvFromList.size(); j++) {
83       if (ogr->vertices[i].recvFromList[j].getNumBytes() > maxBytes) {
84         maxBytes = ogr->vertices[i].recvFromList[j].getNumBytes();
85       }
86     }
87   }
88
89   /* adjacency list */
90   SCOTCH_Num *verttab = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * (vertnbr+1));
91   /* loads of vertices */
92   SCOTCH_Num *velotab = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * vertnbr);
93   /* id of the neighbors */
94   SCOTCH_Num *edgetab = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * edgenbr);
95   /* number of bytes exchanged */
96   SCOTCH_Num *edlotab = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * edgenbr);
97
98   int edgeNum = 0;
99   double ratio = 256.0/maxLoad;
100   double byteRatio = 1024.0/maxBytes;
101   
102   for(i = baseval; i < vertnbr; i++) {
103     verttab[i] = edgeNum;
104     velotab[i] = (int)ceil(ogr->vertices[i].getVertexLoad() * ratio);
105     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
106       edgetab[edgeNum] = ogr->vertices[i].sendToList[j].getNeighborId();
107       edlotab[edgeNum] = (int) ceil(ogr->vertices[i].sendToList[j].getNumBytes()
108           * byteRatio);
109       edgeNum++;
110     }
111     for(j = 0; j < ogr->vertices[i].recvFromList.size(); j++) {
112       edgetab[edgeNum] = ogr->vertices[i].recvFromList[j].getNeighborId();
113       edlotab[edgeNum] = (int)
114           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   double migration_cost = 1024.0;
132
133     if (step() == 0) {
134       SCOTCH_stratGraphMapBuild (&strat, SCOTCH_STRATBALANCE, parr->procs.size (), 0.01);
135     } else {
136       SCOTCH_stratGraphMapBuild (&strat, SCOTCH_STRATBALANCE | SCOTCH_STRATREMAP, parr->procs.size (), 0.01);
137     }
138
139   SCOTCH_Num *pemap = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * vertnbr);
140
141   // Takes as input the graph, arch graph, strategy, migration cost in
142   // double, old mapping and new mapping
143
144   if (step() == 0) {
145     SCOTCH_graphPart(&graph, parr->procs.size(), &strat, pemap);
146   } else {
147     SCOTCH_graphRepart(&graph, parr->procs.size(), oldpemap, migration_cost, NULL, &strat, pemap);
148   }
149   
150   SCOTCH_graphExit (&graph);
151   SCOTCH_stratExit (&strat);
152
153   free(verttab);
154   free(velotab);
155   free(edgetab);
156   free(edlotab);
157
158   for(i = baseval; i < vertnbr; i++) {
159     if(pemap[i] != ogr->vertices[i].getCurrentPe())
160       ogr->vertices[i].setNewPe(pemap[i]);
161   }
162
163   free(pemap);
164   free(oldpemap);
165   /** ============================== CLEANUP ================================ */
166   ogr->convertDecisions(stats);
167   delete parr;
168   delete ogr;
169 }
170
171 #include "ScotchRefineLB.def.h"
172
173 /*@}*/