important changes:
[charm.git] / src / ck-ldb / ObjGraph.C
1 /*****************************************************************************
2  * $Source$
3  * $Author$
4  * $Date$
5  * $Revision$
6  *****************************************************************************/
7
8 /**
9  * \addtogroup CkLdb
10 */
11 /*@{*/
12
13 #include "ObjGraph.h"
14
15 static const double alpha = 30.e-6;
16 static const double beta = 3.e-9;
17
18 ObjGraph::ObjGraph(int count, CentralLB::LDStats* _stats)
19 {
20   stats = _stats;
21   // First, we need to make a linked list of objects.
22   // Also, we'll construct a little hash table to improve
23   // efficiency in finding the objects to build the edge lists
24
25   // Initialize the linked list
26   for(int i=0; i < hash_max; i++)
27     node_table[i] = 0;
28   
29   nodelist = 0;
30   // Count up the edges and the nodes, and allocate storage for
31   // them all at once.
32   n_objs = stats->n_objs;
33   n_edges = 0;
34     // initialize node array
35   int index;
36   for(index = 0; index < stats->n_comm; index++) {
37       const LDCommData newedgedata = stats->commData[index];
38
39       // If this isn't an object-to-object message, ignore it
40       if (!newedgedata.from_proc() && newedgedata.recv_type() == LD_OBJ_MSG)
41         n_edges++;
42     }
43   nodelist = new Node[n_objs];
44   edgelist = new Edge[n_edges];
45
46   // Now initialize the node and the edge arrays
47   int cur_node = 0;
48   int cur_edge = 0;
49   // initialize node array
50   for(index = 0; index < stats->n_objs; index++) {
51       LDObjData &odata = stats->objData[index];
52       if(cur_node >= n_objs)
53         CkPrintf("Error %d %d\n",cur_node,n_objs);
54       Node* thisnode = nodelist + cur_node;
55       thisnode->node_index = cur_node;
56       thisnode->proc = stats->from_proc[index];
57       thisnode->index = index;
58       thisnode->n_out = 0;
59       thisnode->outEdge = 0;
60       thisnode->n_in = 0;
61       thisnode->inEdge = 0;
62       cur_node++;
63       const int hashval = calc_hashval(odata.omID(),
64                                        odata.objID());
65       thisnode->nxt_hash = node_table[hashval];
66       node_table[hashval] = thisnode;
67   }
68
69     // initialize edge array
70     for(index=0; index < stats->n_comm; index++) {
71       LDCommData &newedgedata = stats->commData[index];
72
73       // If this isn't an object-to-object message, ignore it
74       if (newedgedata.from_proc() || newedgedata.recv_type()!=LD_OBJ_MSG)
75         continue;
76
77       if(cur_edge >= n_edges)
78         CkPrintf("Error %d %d\n",cur_edge,n_edges);
79
80       Edge* thisedge = edgelist + cur_edge;
81       thisedge->edge_index = cur_edge;
82       thisedge->index = index;
83       thisedge->from_node = -1;
84       thisedge->to_node = -1;
85       thisedge->nxt_out = 0;
86       thisedge->nxt_in = 0;
87       cur_edge++;
88   }
89   if(cur_node != n_objs)
90       CkPrintf("did not fill table %d %d\n",cur_node,n_objs);
91
92   if(cur_edge != n_edges)
93     CkPrintf("did not fill edge table %d %d\n",cur_edge,n_edges);
94
95   // Now go through the comm lists
96   for(cur_edge = 0; cur_edge < n_edges; cur_edge++) {
97     Edge* newedge = edgelist + cur_edge;
98     int index = newedge->index;
99     const LDCommData newedgedata = stats->commData[index];
100
101     Node* from_node = find_node(newedgedata.sender);
102     if (from_node == 0) {
103       if (!lb_ignoreBgLoad) 
104         CkPrintf("ObjGraph::find_node: Didn't locate from node match!\n");
105       continue;
106     }
107
108     Node* to_node = find_node(newedgedata.receiver.get_destObj());
109     if (to_node == 0) {
110       if (!lb_ignoreBgLoad) 
111         CkPrintf("ObjGraph::find_node: Didn't locate to node match!\n");
112       continue;
113     }
114
115     // Store the edge data in correct outgoing and incoming lists.
116     newedge->from_node = from_node->node_index;
117     newedge->to_node = to_node->node_index;
118     newedge->nxt_out = from_node->outEdge;
119     from_node->outEdge = newedge;
120     from_node->n_out++;
121     newedge->nxt_in = to_node->inEdge;
122     to_node->inEdge = newedge;
123     to_node->n_in++;
124   }
125 }
126
127 ObjGraph::~ObjGraph()
128 {
129   delete [] nodelist;
130   delete [] edgelist;
131 }
132
133 double ObjGraph::EdgeWeight(Edge* e) {
134   LDCommData commData = stats->commData[e->index];
135   return commData.messages * alpha + commData.bytes * beta;
136 }
137
138 int ObjGraph::calc_hashval(LDOMid omid, LDObjid id)
139 {
140   int hashval = omid.id.idx;
141   for(int i=0; i < OBJ_ID_SZ; i++)
142     hashval +=  id.id[i];
143   hashval %= hash_max;
144   return hashval;
145 }
146
147 ObjGraph::Node* ObjGraph::find_node(const LDObjKey &edge_key)
148 {
149   const LDOMid &edge_omid = edge_key.omID();
150   const LDObjid &edge_id = edge_key.objID();
151   const int from_hashval = calc_hashval(edge_omid,edge_id);
152   //  CkPrintf("From = %d\n",from_hashval);
153   Node* from_node = node_table[from_hashval];
154
155   while (from_node != 0) {
156     const LDOMid omid =
157       stats->objData[from_node->index].omID();
158     const LDObjid objid =
159       stats->objData[from_node->index].objID();
160     //    CkPrintf("Comparing %d to %d\n",objid.id[0],edge_id.id[0]);
161     if (LDOMidEqual(omid,edge_omid) && LDObjIDEqual(objid,edge_id) )
162       break;
163     from_node = from_node->nxt_hash;
164   }
165
166   return from_node;
167 }
168
169
170
171
172
173 /*@}*/