ck-ldb: fix comm graph and leaks in ScotchLB
[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].sendToList[j].setNumBytes(ogr->vertices[i].sendToList[j].getNumBytes() + ogr->vertices[i].recvFromList[k].getNumBytes());
51           ogr->vertices[i].recvFromList.erase(ogr->vertices[i].recvFromList.begin() + k);
52         }
53       }
54     }
55   }
56
57   /** the object load is normalized to an integer between 0 and 256 */
58   for(i = baseval; i < vertnbr; i++) {
59     if(ogr->vertices[i].getVertexLoad() > maxLoad)
60       maxLoad = ogr->vertices[i].getVertexLoad();
61     edgenbr += ogr->vertices[i].sendToList.size() + ogr->vertices[i].recvFromList.size();
62   }
63
64   /* adjacency list */
65   SCOTCH_Num *verttab = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * (vertnbr+1));
66   /* loads of vertices */
67   SCOTCH_Num *velotab = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * vertnbr);
68   /* id of the neighbors */
69   SCOTCH_Num *edgetab = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * edgenbr);
70   /* number of bytes exchanged */
71   SCOTCH_Num *edlotab = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * edgenbr);
72
73   int edgeNum = 0;
74   double ratio = 256.0/maxLoad;
75
76   for(i = baseval; i < vertnbr; i++) {
77     verttab[i] = edgeNum;
78     velotab[i] = (int)ceil(ogr->vertices[i].getVertexLoad() * ratio);
79     for(j = 0; j < ogr->vertices[i].sendToList.size(); j++) {
80       edgetab[edgeNum] = ogr->vertices[i].sendToList[j].getNeighborId();
81       edlotab[edgeNum] = ogr->vertices[i].sendToList[j].getNumBytes();
82       edgeNum++;
83     }
84     for(j = 0; j < ogr->vertices[i].recvFromList.size(); j++) {
85       edgetab[edgeNum] = ogr->vertices[i].recvFromList[j].getNeighborId();
86       edlotab[edgeNum] = ogr->vertices[i].recvFromList[j].getNumBytes();
87       edgeNum++;
88     }
89   }
90   verttab[i] = edgeNum;
91   CkAssert(edgeNum == edgenbr);
92
93   SCOTCH_Graph graph;           // Graph to partition
94   SCOTCH_Strat strat;           // Strategy to achieve partitioning
95
96   /* Initialize data structures */
97   SCOTCH_graphInit (&graph);
98   SCOTCH_stratInit (&strat);
99
100   SCOTCH_graphBuild (&graph, baseval, vertnbr, verttab, NULL, velotab, NULL, edgenbr, edgetab, edlotab); 
101   SCOTCH_graphCheck (&graph);
102
103   // 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}}");
104
105   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}}})}");
106
107   SCOTCH_Num *pemap = (SCOTCH_Num *)malloc(sizeof(SCOTCH_Num) * vertnbr);
108
109   SCOTCH_graphPart(&graph, parr->procs.size(), &strat, pemap);
110
111   SCOTCH_graphExit (&graph);
112   SCOTCH_stratExit (&strat);
113  
114   free(verttab);
115   free(velotab);
116   free(edgetab);
117   free(edlotab);
118
119   for(i = baseval; i < vertnbr; i++) {
120     if(pemap[i] != ogr->vertices[i].getCurrentPe())
121       ogr->vertices[i].setNewPe(pemap[i]);
122   }
123
124   free(pemap);
125   /** ============================== CLEANUP ================================ */
126   ogr->convertDecisions(stats);
127 }
128
129 #include "ScotchLB.def.h"
130
131 /*@}*/