Add a flag to provide timer for the case of no objs in Meta-Balancer
[charm.git] / src / ck-core / sdag.h
1 #ifndef _sdag_H_
2 #define _sdag_H_
3
4 #include "charm++.h"
5 #include <vector>
6
7 class CMsgBuffer {
8   public:
9     int entry;
10     void *msg;
11     void *bgLog1; 
12     void *bgLog2; 
13     int refnum;
14     CMsgBuffer *next;
15
16     CMsgBuffer(int e, void *m, void* l1, int r) : entry(e), msg(m), bgLog1(l1), bgLog2(NULL),refnum(r), next(NULL) {}
17     CMsgBuffer(int e, void *m, int r) : entry(e), msg(m), bgLog1(NULL), bgLog2(NULL),refnum(r), next(NULL) {}
18     CMsgBuffer(): bgLog1(NULL), bgLog2(NULL), next(NULL) {}
19     void pup(PUP::er& p) {
20       p|entry;
21       CkPupMessage(p, &msg);
22       p|refnum;
23       if (p.isUnpacking()) {
24         bgLog1 = bgLog2 = NULL;
25       }
26     }
27 };
28
29 #define MAXARG 8
30 #define MAXANY 8
31 #define MAXREF 8
32
33 class CWhenTrigger {
34   public:
35     int whenID, nArgs;
36     size_t args[MAXARG];
37     int nAnyEntries;
38     int anyEntries[MAXANY];
39     int nEntries;
40     int entries[MAXREF];
41     int refnums[MAXREF];
42     int speculationIndex;
43
44     CWhenTrigger *next;
45     CWhenTrigger(int id, int na, int ne, int nae) :
46       whenID(id), nArgs(na), nAnyEntries(nae), nEntries(ne), next(NULL), speculationIndex(-1) {}
47     CWhenTrigger(): next(NULL) {}
48     void pup(PUP::er& p) {
49       p|whenID;
50       p|nArgs;
51       p(args, MAXARG);
52       p|nAnyEntries;
53       p(anyEntries, MAXANY);
54       p|nEntries;
55       p(entries, MAXREF);
56       p(refnums, MAXREF);
57       // since CCounter is not pup'ed
58       // don't expect Overlap works with load balancer 
59       // as well as checkpointing
60       p(args, MAXARG);
61       //if (p.isUnpacking()) args[0]=0;            // HACK for load balancer
62       p|speculationIndex;
63     }
64 };
65
66 // Quick and dirty List for small numbers of items.
67 // It should ideally be a template, but in order to have portability,
68 // we would make it two lists
69
70 class TListCWhenTrigger
71 {
72   private:
73
74     CWhenTrigger *first, *last;
75     CWhenTrigger *current;
76
77   public:
78
79     TListCWhenTrigger(void) : first(0), last(0) {;}
80
81     void pup(PUP::er& p) {
82       int nEntries=0;
83       int cur=-1;
84       if (!p.isUnpacking()) { 
85         for (CWhenTrigger *tmp = first; tmp; tmp=tmp->next, nEntries++)
86           if (current == tmp) cur = nEntries;
87       }
88       p|nEntries;
89       p|cur;
90       if (p.isUnpacking()) { 
91         first = last = current = NULL;
92         if (nEntries) {
93           CWhenTrigger** unpackArray = new CWhenTrigger*[nEntries]; 
94           for (int i=0; i<nEntries; i++)  {
95             unpackArray[i] = new CWhenTrigger;
96             if (i!=0) unpackArray[i-1]->next=unpackArray[i];
97           }
98           first = unpackArray[0];
99           last = unpackArray[nEntries-1];
100           last->next = NULL;
101           current = cur==-1?NULL:unpackArray[cur];
102           delete [] unpackArray;
103         }
104       }
105       for (CWhenTrigger *tmp = first; tmp; tmp=tmp->next) tmp->pup(p);
106     }
107
108     int empty(void) { return ! first; }
109     
110     CWhenTrigger *begin(void) {
111       return (current = first);
112     }
113
114     int end(void) {
115       return (current == 0);
116     }
117
118     CWhenTrigger *next (void) {
119       return (current = current->next);
120     }
121
122     CWhenTrigger *front(void)
123     {
124       return first;
125     }
126
127     CWhenTrigger* remove(CWhenTrigger *data)
128     {
129       // case 1: empty list
130       if (first == 0)
131         return 0;
132       // case 2: first element to be removed
133       if(first == data) {
134         first = first->next;
135         if(first==0) last=0;
136         return first;
137       }
138       // case 3: middle or last element to be removed
139       CWhenTrigger *nn;
140       CWhenTrigger *prev = first;
141       for(nn=first->next; nn; nn = nn->next) {
142         if (nn == data) {
143           prev->next = nn->next;
144           if(nn==last)
145             last=prev;
146           return prev;
147         }
148         prev = nn;
149       }
150     }
151
152     void append(CWhenTrigger *data)
153     {
154       data->next = 0;
155       if(first == 0) {
156         last = first = data;
157       } else {
158         last->next = data;
159         last = last->next;
160       }
161     }
162 };
163
164 class TListCMsgBuffer
165 {
166   private:
167
168     CMsgBuffer *first, *last;
169     CMsgBuffer *current;
170
171   public:
172
173     TListCMsgBuffer(void) : first(0), last(0) {}
174
175     void pup(PUP::er& p) {
176       int nEntries=0;
177       int cur=0;
178       if (!p.isUnpacking()) { 
179         for (CMsgBuffer *tmp = first; tmp; tmp=tmp->next, nEntries++) {
180           if (current == tmp) cur = nEntries;
181         }
182       }
183       p|nEntries;
184       p|cur;
185       if (p.isUnpacking()) { 
186         first = last = current = NULL;
187         if (nEntries) {
188           CMsgBuffer** unpackArray = new CMsgBuffer*[nEntries]; 
189           for (int i=0; i<nEntries; i++)  {
190             unpackArray[i] = new CMsgBuffer;
191             if (i!=0) unpackArray[i-1]->next=unpackArray[i];
192           }
193           first = unpackArray[0];
194           last = unpackArray[nEntries-1];
195           current = unpackArray[cur];
196           delete [] unpackArray;
197         }
198       }
199       for (CMsgBuffer *tmp = first; tmp; tmp=tmp->next) tmp->pup(p);
200     }
201
202     int empty(void) { return ! first; }
203     
204     CMsgBuffer *begin(void) {
205       return (current = first);
206     }
207
208     int end(void) {
209       return (current == 0);
210     }
211
212     CMsgBuffer *next (void) {
213       return (current = current->next);
214     }
215
216     CMsgBuffer *front(void)
217     {
218       return first;
219     }
220
221     void remove(CMsgBuffer *data)
222     {
223       // case 1: empty list
224       if (first == 0)
225         return;
226       // case 2: first element to be removed
227       if(first == data) {
228         first = first->next;
229         if(first==0) last=0;
230         return;
231       }
232       // case 3: middle or last element to be removed
233       CMsgBuffer *nn;
234       CMsgBuffer *prev = first;
235       for(nn=first->next; nn; nn = nn->next) {
236         if (nn == data) {
237           prev->next = nn->next;
238           if(nn==last)
239             last=prev;
240           return;
241         }
242         prev = nn;
243       }
244     }
245
246     void append(CMsgBuffer *data)
247     {
248       data->next = 0;
249       if(first == 0) {
250         last = first = data;
251       } else {
252         last->next = data;
253         last = last->next;
254       }
255     }
256 };
257
258
259 /**
260  This class hides all the details of dependencies between
261  when blocks and entries. It also contains the entry buffers
262  and when triggers.
263 */
264
265 class CDep {
266    int numEntries, numWhens;
267    TListCWhenTrigger **whens;
268    TListCMsgBuffer **buffers;
269    int *numWhenDepends;
270    int *numEntryDepends;
271    TListCMsgBuffer ***whenDepends;
272    TListCWhenTrigger ***entryDepends;
273    int curSpeculationIndex;
274
275  public:
276    void pup(PUP::er& p) {
277      /* 
278         no need for initMem() because __sdag_pup() will take care of 
279         allocating of CDep and call addDepends(), so we don't pup whenDepends
280         and entryDepends here.
281      */ 
282      int i;
283
284      for (i=0; i<numWhens; i++)    whens[i]->pup(p);
285      for (i=0; i<numEntries; i++)  buffers[i]->pup(p);
286
287      p(numWhenDepends, numWhens);
288      p(numEntryDepends, numEntries);
289
290      p | curSpeculationIndex;
291 /*
292      // don't actually pack this info because it gets created once 
293      // the addDepends() in the initialization scheme are called for this class
294      for (i=0; i<numWhens; i++)
295        for (j=0; j<numWhenDepends[i]; j++) {
296          int which;
297          if (p.isPacking())  which = whenDepends[i][j] - buffers[0];
298          p|which;
299          if (p.isUnpacking()) whenDepends[i][j] = buffers[which];
300        }
301
302      for (i=0; i<numEntries; i++)
303        for (j=0; j<numEntryDepends[i]; j++) {
304          int which;
305          if (p.isPacking())  which = entryDepends[i][j] - whens[0];
306          p|which;
307          if (p.isUnpacking()) entryDepends[i][j] = whens[which];
308      }
309 */
310    }
311
312    CDep(int ne, int nw) : numEntries(ne), numWhens(nw), curSpeculationIndex(0) { initMem(); }
313
314    ~CDep() {
315      int i;
316      delete [] numWhenDepends;
317      delete [] numEntryDepends;
318      for(i=0;i<numWhens;i++) {
319        delete whens[i];
320        delete [] whenDepends[i];
321      }
322      for(i=0;i<numEntries;i++) {
323        delete buffers[i];
324        delete [] entryDepends[i];
325      }
326      delete [] whens;
327      delete [] buffers;
328      delete [] whenDepends;
329      delete [] entryDepends;
330    }
331
332  private:
333    void initMem() {
334      // initialize the internal data structures here
335      whens = new TListCWhenTrigger *[numWhens];
336      buffers = new TListCMsgBuffer *[numEntries];
337      numWhenDepends = new int[numWhens];
338      numEntryDepends = new int[numEntries];
339      whenDepends = new TListCMsgBuffer **[numWhens];
340      entryDepends = new TListCWhenTrigger **[numEntries];
341      int i;
342      for(i=0;i<numWhens;i++) {
343        whens[i] = new TListCWhenTrigger();
344        whenDepends[i] = new TListCMsgBuffer *[numEntries];
345        numWhenDepends[i] = 0;
346      }
347      for(i=0;i<numEntries;i++) {
348        buffers[i] = new TListCMsgBuffer();
349        entryDepends[i] = new TListCWhenTrigger *[numWhens];
350        numEntryDepends[i] = 0;
351      }
352    }
353
354  public:
355    // adds a dependency of whenID upon Entry
356    // done only at initialization.
357    void addDepends(int whenID, int entry) {
358      whenDepends[whenID][numWhenDepends[whenID]++] = buffers[entry];
359      entryDepends[entry][numEntryDepends[entry]++] = whens[whenID];
360    }
361
362    // register a trigger to be called with
363    // with <nEntries> specified
364    // in <entries> with corresponding <refnums>
365    void Register(CWhenTrigger *trigger)
366    {
367      whens[trigger->whenID]->append(trigger);
368    }
369
370    // deregister trigger from all
371    // the entries it is registered for
372    CWhenTrigger* deRegister(CWhenTrigger *trigger) {
373      return whens[trigger->whenID]->remove(trigger);
374    }
375
376    // buffer a message for a specific entry point with a specified
377    // reference number
378    CMsgBuffer* bufferMessage(int entry, void *msg, void* log , int refnum)
379    {
380      CMsgBuffer *buf = new CMsgBuffer(entry, msg, log,refnum);
381      buffers[entry]->append(buf);
382      return buf;
383    }
384
385    // For a specified entry number and reference number,
386    // get the registered trigger which satisfies dependency. 
387    // If no trigger exists
388    // for the given reference number, get the trigger registered for
389    // ANY ref num. If that also doesnt exist, Return NULL
390    CWhenTrigger *getTrigger(int entry, int refnum)
391    {
392      for(int i=0;i<numEntryDepends[entry];i++) {
393        TListCWhenTrigger *wlist = entryDepends[entry][i];
394        for(CWhenTrigger *elem=wlist->begin(); 
395            !wlist->end(); 
396            elem=wlist->next()) {
397          if(elem==0)
398            break;
399          if(depSatisfied(elem)){
400             deRegister(elem);
401             return elem;
402          }
403        }
404      }
405      return 0;
406    }
407
408
409    // given the entry number and reference number,
410    // get the buffered message, without removing it from
411    // the list, NULL if no such message exists
412    CMsgBuffer *getMessage(int entry, int refnum)
413    {
414      TListCMsgBuffer *list = buffers[entry];
415      for(CMsgBuffer *elem=list->begin(); !list->end(); elem=list->next()) {
416        if(elem==0)
417          return 0;
418        if(elem->refnum == refnum)
419          return elem;
420      }
421      return 0;
422    }
423
424    // given the entry number,
425    // get the buffered message, without removing it from
426    // the list, NULL if no such message exists
427    // note that this is the ANY case
428    CMsgBuffer *getMessage(int entry)
429    {
430      return buffers[entry]->front();
431    }
432
433    // remove the given message from buffer
434    void removeMessage(CMsgBuffer *msg)
435    {
436      TListCMsgBuffer *list = buffers[msg->entry];
437      list->remove(msg);
438    }
439
440    // return 1 if all the dependeces for trigger are satisfied
441    // return 0 otherwise
442    int depSatisfied(CWhenTrigger *trigger)
443    {
444      int i;
445      for(i=0;i<trigger->nEntries;i++) {
446        if(!getMessage(trigger->entries[i], trigger->refnums[i]))
447          return 0;
448      }
449      for(i=0;i<trigger->nAnyEntries;i++) {
450        if(!getMessage(trigger->anyEntries[i]))
451          return 0;
452      }
453      return 1;
454    }
455
456    int getAndIncrementSpeculationIndex() {
457      return curSpeculationIndex++;
458    }
459
460    void removeAllSpeculationIndex(int speculationIndex) {
461      for (int i = 0; i < numWhens; i++) {
462        TListCWhenTrigger *wlist = whens[i];
463        for (CWhenTrigger *elem = wlist->begin(); !wlist->end(); elem = wlist->next()) {
464          if (elem == 0) break;
465          if (elem->speculationIndex == speculationIndex) {
466            elem = deRegister(elem);
467          }
468        }
469      }
470    }
471
472 };
473
474
475 /** 
476  This class hides all of the details of dependencies between
477  overlap blocks and when blocks. 
478  */
479
480 class COverDep {
481
482    int numOverlaps, numWhens;
483    TListCWhenTrigger **whens;
484    int *numOverlapDepends;
485    TListCWhenTrigger ***overlapDepends;
486    
487   public:
488      void pup(PUP::er& p) {
489         /*
490           no need for initMem() because __sdag_pup() will take care of
491           allocating of COverDep and call addOverlapDepends(), so we don't pup overlapsDepends here
492         */
493         int i; // , j;
494         for (i=0; i<numWhens; i++)    whens[i]->pup(p);
495
496         p(numOverlapDepends, numOverlaps);
497      }
498
499      COverDep(int no, int nw) : numOverlaps(no), numWhens(nw) { initMem(); }
500
501      ~COverDep() {
502         int i;
503         delete [] numOverlapDepends;
504         for(i=0;i<numWhens;i++) {
505             delete whens[i];
506         }
507         for(i=0;i<numOverlaps;i++) {
508             delete [] overlapDepends[i];
509
510         }
511         delete [] whens;
512         delete [] overlapDepends;
513      }
514      
515    private:
516      void initMem() {
517        // initialize the internal data structures here
518        whens = new TListCWhenTrigger *[numWhens];
519        numOverlapDepends = new int[numOverlaps];
520        overlapDepends = new TListCWhenTrigger **[numOverlaps];
521        int i;
522        for(i=0;i<numWhens;i++) {
523          whens[i] = new TListCWhenTrigger();
524        }
525        for(i=0;i<numOverlaps;i++) {
526          overlapDepends[i] = new TListCWhenTrigger *[numWhens];
527          numOverlapDepends[i] = 0;
528        }
529      }
530
531    public:
532      //adds a dependency of the whenID for each Overlap
533      // done only at initialization
534      void addOverlapDepends(int whenID, int overlap) {
535        overlapDepends[overlap][whenID] = whens[whenID];
536        //overlapDepends[overlap][numOverlapDepends[overlap]++] = whens[whenID];
537      }
538      
539      // register a trigger to be called with
540      // with <nEntries> specified
541      // in <entries> with corresponding <refnums>
542      void Register(CWhenTrigger *trigger)
543      {
544        whens[trigger->whenID]->append(trigger);
545      }
546      
547      // deregister trigger from all
548      // the entries it is registered for
549      void deRegister(CWhenTrigger *trigger)
550      {
551         whens[trigger->whenID]->remove(trigger);
552      }
553      
554      
555      // For a specified entry number and reference number,
556      // get the registered trigger which satisfies dependency.
557      // If no trigger exists
558      // for the given reference number, get the trigger registered for
559      // ANY ref num. If that also doesnt exist, Return NULL
560      CWhenTrigger *getTrigger(int overlapID, int whenID)
561      {
562         TListCWhenTrigger *wlist = overlapDepends[overlapID][whenID];
563         CWhenTrigger *elem=wlist->begin(); 
564         if (elem == 0)
565           return 0;       
566         else {
567           deRegister(elem);
568           return elem;
569         }
570      }
571 };
572
573 class CCounter {
574   private:
575     unsigned int count;
576   public:
577     CCounter(int c) : count(c) { }
578     CCounter(int first, int last, int stride) {
579       count = ((last-first)/stride)+1;
580     }
581     void decrement(void) {count--;}
582     int isDone(void) {return (count==0);}
583 };
584
585 struct CSpeculator {
586   int speculationIndex;
587   CSpeculator(int speculationIndex_)
588     : speculationIndex(speculationIndex_) { }
589 };
590
591 #endif