doc: Add serial to list of ci file reserved words
[charm.git] / examples / pose / LBSim / SchedSIM.C
1 #include "topology.C"
2
3 const int DEBUG=0;
4 int maxObj;
5
6 int myinitialise(QUEUE *queue)
7 {  
8     if ((queue->front = (NODE *)malloc(sizeof(NODE))) == NULL)
9     return 0;    
10     queue->rear = queue->front;
11     queue->front->data=-1;
12     queue->front->next = NULL;
13     return 1;
14 }
15
16 int myenqueue(QUEUE *queue, long int key)
17 {
18     NODE *newnode;
19     if ((newnode=(NODE *)malloc(sizeof(NODE))) == NULL)
20         return 0;
21     newnode->data = key;
22     newnode->next = NULL;
23     /* Add to the queue */
24     queue->rear->next = newnode;
25     queue->rear = newnode;
26     return 1;
27 }
28
29 int mydequeue(QUEUE *queue)
30 {
31     NODE *oldnode;
32     long int key;
33     oldnode = queue->front->next;
34     key = oldnode->data;
35     /* Check if removing the last node from the queue */
36     if (queue->front->next->next == NULL)
37         queue->rear = queue->front;
38     else
39         queue->front->next = queue->front->next->next;
40     delete(oldnode);
41     //printf("Item %d dequeued\n",key);
42     return key;
43 }
44
45 int myisempty(QUEUE *queue)
46 {
47     return (queue->front == queue->rear);
48 }
49
50 int myqlength(QUEUE *queue)
51 {
52     NODE *ptr;
53     int count = 0;
54     ptr=queue->front;
55     while(!(ptr==queue->rear))
56     {
57       count++;
58       ptr=ptr->next;
59     }
60     return count;
61 }
62
63 void printqueue(QUEUE *queue)
64 {
65     NODE *ptr;
66     int count=0;
67     ptr=queue->front;
68     while(!(ptr==queue->rear))
69     {
70       count++;  
71       ptr=ptr->next;
72       printf("%ld:%ld  ",count,ptr->data);
73     }
74     printf("\n");
75 }
76
77     
78 // schedulerObject implementation
79
80 // the non-empty constructor
81
82 schedulerObject::schedulerObject(SchedulerData *m)
83 {
84   int i,avg=0,recvid;
85   srand48(42);
86   maxObjects = m->maxObjects;
87   connectivity = m->connectivity;
88   id = m->id;
89   data=m->data;
90   lbtopolen=m->lbtopolen;
91   lbtopo=new char[lbtopolen];
92   strcpy(lbtopo,m->lbtopo);
93   delete(m);
94   queue= new QUEUE;
95   myinitialise(queue);
96   load=0;
97   WorkTime=0;
98   IdleTime=0;
99   count=0;
100   MinProc=id;
101   MinLoad=0;
102   Mindex=0;
103   prevovt=0;
104   created=0;
105   processed=0;
106   Inactivity_Detected=0;
107   neighborlist=NULL;
108   loadlist=NULL;  
109   maxNeighbors=0;
110   if (!(id)) maxObj=maxObjects;  
111   findneighbors();
112  
113   // Send two messages to objects 
114   if(!(id)){
115
116   for (i=1; i<=2; i++) {
117     computeMsg *m1 = new computeMsg;
118     m1->data=data-i;
119     m1->type=WORK_MSG;
120     m1->sum=0;
121     if(m1->data>-1){
122         ldminavg(avg);
123         if (load<avg) recvid=id;
124         else recvid=MinProc;
125         if (DEBUG) printf("I m in constructor now\n"); 
126         created++;
127         if (DEBUG) printf("Creating on %d , created no. %d, value: %d\n", id,created,m1->data);
128         POSE_invoke(receiveWork(m1), schedulerObject, recvid,0);
129         }
130     else delete(m1);
131    }
132  
133    computeMsg *m2=new computeMsg;
134    m2->data=created;
135    m2->sum=processed;
136    m2->type=2;
137    POSE_invoke(sendData(m2), schedulerObject, (id+1)%maxObjects, 0);
138   }
139   //to begin work on each scheduler poser
140   computeMsg *m2=new computeMsg;
141   m2->data=0;
142   m2->sum=0;
143   m2->type=1;
144   POSE_local_invoke(startWork(m2),0);
145
146   //periodic load balancing 
147   computeMsg *m1 = new computeMsg;
148   m1->type = LDBAL_MSG;
149   m1->data=0;
150   m1->sum=id;
151   POSE_local_invoke(receiveWork(m1), 2);    
152 }
153
154 void schedulerObject::fibonacci(long int key)
155 {
156    int i,avg=0,recvid;
157    if (DEBUG) printf("Calculating fibonacci of %ld\n",key); 
158    if (key>1){
159          for (i=1; i<=2; i++)
160          {
161             computeMsg *m1 = new computeMsg;
162             m1->data=key-i;
163             m1->type=WORK_MSG;
164             if(m1->data>-1){
165                 ldminavg(avg);
166                 if (load<avg) recvid=id;
167                 else recvid=MinProc;
168                 created++;
169                 if (DEBUG) printf("Creating on %d , created no. %d, value: %d\n", id,created,m1->data);
170                 POSE_invoke(receiveWork(m1), schedulerObject, recvid,0);
171             }
172             else delete(m1);
173          }
174    }   
175    //printf("In Fibonacci Id: %d Created: %d Processed: %d\n",id,created,processed);                                                            
176 }
177
178 void schedulerObject::receiveWork(computeMsg *m) {
179   int i,workDone;
180   long int key;
181   // appfn=&fibonacci;
182   srand48(36);
183   if (DEBUG) printf("Recieve Work on poser %d at ovt %d\n",id,ovt); 
184   if (m->type==LDBAL_MSG) {
185      for (i=0; i<maxNeighbors; i++) {
186       //reusing fields of computeMsg for data transfer..define new messagetype later.
187       computeMsg *m1= new computeMsg;
188       m1->type=load;
189       m1->data=i;
190       m1->sum=id;
191       POSE_invoke(recvLoad(m1), schedulerObject, neighborlist[i], maxNeighbors);
192     }
193    }
194   else
195   if(m->data>-1){
196     key=m->data;
197     myenqueue(queue,key);
198     load=myqlength(queue);
199   }
200 }
201
202 void schedulerObject::startWork(computeMsg *m)
203 {
204   int msum,mtype,mtimestamp,workDone,idle=1;
205   long int key=-1;
206   msum=m->sum;
207   mtype=m->type;
208   if (DEBUG) printf("Startwork on object %d at ovt %d\n",id,ovt); 
209   if(!(myisempty(queue)))
210   {
211          key=mydequeue(queue);
212          load=myqlength(queue);
213          mtimestamp=m->timestamp;
214          idle=0;
215          if(key>=0){
216                  //(*appfn)(key);
217                  processed++;
218                  if (DEBUG) printf("Processing on %d , processed no. %d, value: %d\n", id,processed,key);
219                  fibonacci(key);
220                  if (key<=1)
221                     workDone = 25;
222                  else
223                          workDone = 15;
224                  elapse(workDone);
225                  parent->CommitPrintf("%d %d %d\n",id,ovt-workDone,ovt);
226
227                  WorkTime+=workDone;
228          }
229          if (ovt>lastovt+100){
230               float busy;
231               //busy=float(WorkTime*100)/(WorkTime+IdleTime);       
232               //if (ovt-lastovt>200)
233               //{
234                 //ovt
235               //}
236               //{
237               //busy=float(WorkTime*100)/(ovt-lastovt);
238                //parent->CommitPrintf("%d %d %d %d %f\n",id,lastovt,ovt-ovt%100,WorkTime,WorkTime*((double)(ovt-ovt%100-lastovt)/(ovt-lastovt)));
239                //parent->CommitPrintf("%d %d %d %f\n",id,ovt-ovt%100,ovt, WorkTime-WorkTime*((double)(ovt-ovt%100-lastovt)/(ovt-lastovt)));
240                  
241                  //parent->CommitPrintf("%d %d %lf\n",id,lastovt/100+1, WorkTime*((double)(ovt-ovt%100-lastovt)/(ovt-lastovt)));
242                 // parent->CommitPrintf("%d %d %lf\n",id,(ovt-ovt%100)/100+1, WorkTime-WorkTime*((double)(ovt-ovt%100-lastovt)/(ovt-lastovt)));
243
244               //}
245               lastovt=ovt;
246               WorkTime=0;
247               IdleTime=0;            
248           }
249    }
250    if (!Inactivity_Detected)
251         {                                                       
252            computeMsg *m1 = new computeMsg;
253            m1->data = 0;
254            m1->sum = 0;
255            m1->type = WORK_MSG;
256            IdleTime+=idle*5;
257            POSE_local_invoke(startWork(m1),idle*5);
258            if (ovt>prevovt+50){
259               computeMsg *m1 = new computeMsg;
260               m1->type = LDBAL_MSG;
261               POSE_local_invoke(receiveWork(m1), 50);    
262            }
263            prevovt=ovt;
264         }
265    else 
266          CkExit();
267         
268 }
269
270 void schedulerObject::recvLoad(computeMsg *m)
271 {   
272    int mdata,mtype;
273    mdata=m->data;
274    mtype=m->type;
275    loadlist[mdata]=mtype;
276    IdleTime+=maxNeighbors;
277    ldbalance();
278 }
279
280 void schedulerObject::ldminavg(int& k)
281 {
282   int sum=0, i;
283   int mype=id;
284   static int start=-1;
285   if (start == -1)
286     start = CmiMyPe() % (maxNeighbors);
287   MinProc = neighborlist[start];
288   MinLoad = loadlist[start];
289   sum =loadlist[start];
290   Mindex = start;
291   for (i=1; i<maxNeighbors; i++) {
292     start = (start+1) % maxNeighbors;
293     sum += loadlist[start];
294     if (MinLoad >loadlist[start]) {
295       MinLoad = loadlist[start];
296       MinProc = neighborlist[start];
297       Mindex = start;
298     }
299   }
300   start = (start+2) % maxNeighbors;
301   sum += CldLoad();
302   if (CldLoad() < MinLoad) {
303     MinLoad = CldLoad();
304     MinProc = CmiMyPe();
305   }
306   k = (int)(1.0 + (((float)sum) /((float)(maxNeighbors)+1)));  
307 }
308
309 void schedulerObject::ldbalance()
310 {
311   int sum=0, i, j, overload, numToMove=0, avgLoad=0;
312   int totalUnderAvg=0, numUnderAvg=0, maxUnderAvg=0;
313   int mype=id;
314   count=0;
315   ldminavg(avgLoad);
316   overload = CldLoad() - avgLoad;
317   if (overload > MAXOVERLOAD) {
318     for (i=0; i<maxNeighbors; i++)
319       if (loadlist[i] < avgLoad) {
320         totalUnderAvg += avgLoad-loadlist[i];
321         if (avgLoad - loadlist[i] > maxUnderAvg)
322           maxUnderAvg = avgLoad - loadlist[i];
323         numUnderAvg++;
324       }
325     if (numUnderAvg > 0)
326       for (i=0; ((i<maxNeighbors) && (overload>0)); i++) {
327         j = (i+Mindex)%maxNeighbors;
328         if (loadlist[j] < avgLoad) {
329           numToMove = avgLoad - loadlist[j];
330           if (numToMove > overload)
331             numToMove = overload;
332           overload -= numToMove;
333           loadlist[j]+=numToMove;
334           long int key;
335           for (i=0;i<numToMove;i++){
336            if(!(myisempty(queue))){
337                 key=mydequeue(queue);  
338                 computeMsg *m1 = new computeMsg;
339                 m1->data=key;
340                 m1->type=WORK_MSG;
341                 POSE_invoke(receiveWork(m1), schedulerObject, (neighborlist[j]), 0);
342                }
343            }
344           
345         }
346       }
347   }
348 }
349
350
351 //extern "C" void gengraph(int, int, int, int *, int *, int, int);
352
353 void schedulerObject::findneighbors()
354 {
355   LBTopology *topo;
356   LBtopoFn topofn = LBTopoLookup(lbtopo);
357   //printf("lbtopo:%s\n",lbtopo);
358   if (topofn == NULL) {
359     if (id==0) printf("LB> Fatal error: Unknown topology: %s.\n", lbtopo);
360     CkExit();
361   }
362   topo = topofn();
363   maxNeighbors = topo->max_neighbors();
364   neighborlist = new int[maxNeighbors];
365   int nb=0;
366   topo->neighbors(id, neighborlist, nb);
367   maxNeighbors=nb;
368   loadlist = new int[nb];
369   for(int i=0;i<nb;i++)  loadlist[i]=0;
370 }
371
372 void schedulerObject::sendData(computeMsg *m)
373 {
374         if (!(id))
375                 {
376                          if (DEBUG) printf("\nId: %d Created: %d Processed: %d\n",id,m->data,m->sum); 
377                          if (m->data==m->sum) Inactivity_Detected=1;
378                          else   {
379                                  computeMsg *m1 = new computeMsg;
380                                  m1->data = created;
381                                  m1->sum = processed;
382                                  POSE_invoke(sendData(m1), schedulerObject, (id+1)%maxObjects, 0);
383                                 }
384                 }
385         else    
386                 {
387                         computeMsg *m1 = new computeMsg;
388                         m1->data = m->data+created;
389                         m1->sum = m->sum+processed;
390                         POSE_invoke(sendData(m1), schedulerObject, (id+1)%maxObjects, 0);
391                 }
392 }