e6256e2b6bb082f2217541dfc8be6f41994eee04
[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
35   /** ============================= STRATEGY ================================ */
36   // convert ObjGraph to the Scotch graph
37   SCOTCH_Num baseval = 0;                       // starting index of vertices
38   SCOTCH_Num vertnbr = ogr->vertices.size();    // number of vertices
39   SCOTCH_Num edgenbr = 0;                       // number of edges
40
41   double maxLoad = 0.0;
42   int i, j, k, vert;
43
44   /** remove duplicate edges from recvFrom */
45   for(i = baseval; i < vertnbr; i++) {
46     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
47       vert = ogr->vertices[i].sendToList[j].getNeighborId();
48       for(k = 0; k < ogr->vertices[i].recvFromList.size(); k++) {
49         if(ogr->vertices[i].recvFromList[k].getNeighborId() == vert)
50           ogr->vertices[i].recvFromList.erase(ogr->vertices[i].recvFromList.begin() + k);
51       }
52     }
53   }
54
55   /** the object load is normalized to an integer between 0 and 256 */
56   for(i = baseval; i < vertnbr; i++) {
57     if(ogr->vertices[i].getVertexLoad() > maxLoad)
58       maxLoad = ogr->vertices[i].getVertexLoad();
59     edgenbr += ogr->vertices[i].sendToList.size() + ogr->vertices[i].recvFromList.size();
60   }
61
62   /* adjacency list */
63   SCOTCH_Num *verttab = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * (vertnbr+1));
64   /* loads of vertices */
65   SCOTCH_Num *velotab = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * vertnbr);
66   /* id of the neighbors */
67   SCOTCH_Num *edgetab = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * edgenbr);
68   /* number of bytes exchanged */
69   SCOTCH_Num *edlotab = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * edgenbr);
70
71   int edgeNum = 0;
72   double ratio = 256.0/maxLoad;
73
74   for(i = baseval; i < vertnbr; i++) {
75     verttab[i] = edgeNum;
76     velotab[i] = (int)ceil(ogr->vertices[i].getVertexLoad() * ratio);
77     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
78       edgetab[edgeNum] = ogr->vertices[i].sendToList[j].getNeighborId();
79       edlotab[edgeNum] = ogr->vertices[i].sendToList[j].getNumBytes();
80       edgeNum++;
81     }
82     for(j = 0; j < ogr->vertices[i].recvFromList.size(); j++) {
83       edgetab[edgeNum] = ogr->vertices[i].recvFromList[j].getNeighborId();
84       edlotab[edgeNum] = ogr->vertices[i].recvFromList[j].getNumBytes();
85       edgeNum++;
86     }
87   }
88   verttab[i] = edgeNum;
89   CkAssert(edgeNum == edgenbr);
90
91   SCOTCH_Graph graph;           // Graph to partition
92   SCOTCH_Strat strat;           // Strategy to achieve partitioning
93
94   /* Initialize data structures */
95   SCOTCH_graphInit (&graph);
96   SCOTCH_stratInit (&strat);
97
98   SCOTCH_graphBuild (&graph, baseval, vertnbr, verttab, NULL, velotab, NULL, edgenbr, edgetab, edlotab); 
99   SCOTCH_graphCheck (&graph);
100
101   // SCOTCH_stratGraphMap (&strat, "m{type=h,vert=80,low=r{job=t,map=t,poli=S,sep=h{pass=10}},asc=b{bnd=d{dif=1,rem=1,pass=40},org=}f{bal=0.01,move=80}}");
102
103   SCOTCH_stratGraphMap (&strat, "r{job=t,map=t,poli=S,sep=(m{type=h,vert=80,low=h{pass=10}f{bal=0.001,move=80},asc=b{bnd=f{bal=0.001,move=80},org=f{bal=0.001,move=80}}}|m{type=h,vert=80,low=h{pass=10}f{bal=0.001,move=80},asc=b{bnd=f{bal=0.001,move=80},org=f{bal=0.001,move=80}}})}");
104
105   SCOTCH_Num *pemap = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * vertnbr);
106
107   SCOTCH_graphPart(&graph, parr->procs.size(), &strat, pemap);
108
109   SCOTCH_graphExit (&graph);
110   SCOTCH_stratExit (&strat);
111
112   for(i = baseval; i < vertnbr; i++) {
113     if(pemap[i] != ogr->vertices[i].getCurrentPe())
114       ogr->vertices[i].setNewPe(pemap[i]);
115   }
116
117   /** ============================== CLEANUP ================================ */
118   ogr->convertDecisions(stats);
119 }
120
121 #include "ScotchLB.def.h"
122
123 /*@}*/