3c47638453054e30d4871e3e53b0a5f90183cc83
[charm.git] / src / libs / ck-libs / multiphaseSharedArrays / msa-distArray.h
1 // emacs mode line -*- mode: c++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*-
2 #ifndef MSA_DISTARRAY_H
3 #define MSA_DISTARRAY_H
4
5 #include <utility>
6 #include <algorithm>
7 #include "msa-DistPageMgr.h"
8
9
10 struct MSA_InvalidHandle { };
11
12 template <typename ENTRY>
13 class Writable
14 {
15     ENTRY &e;
16     
17 public:
18     Writable(ENTRY &e_) : e(e_) {}
19     inline const ENTRY& operator= (const ENTRY& rhs) { e = rhs; return rhs; }
20 };
21
22 template <typename ENTRY, class ENTRY_OPS_CLASS>
23 class Accumulable
24 {
25     ENTRY &e;
26     
27 public:
28     Accumulable(ENTRY &e_) : e(e_) {}
29     void operator+=(const ENTRY &rhs_)
30         { ENTRY_OPS_CLASS::accumulate(e, rhs_); }
31     template<typename T>
32     void accumulate(const T& rhs)
33         {
34             ENTRY_OPS_CLASS::accumulate(e, rhs);
35         }
36 };
37
38
39 /**
40    The MSA1D class is a handle to a distributed shared array of items
41    of data type ENTRY. There are nEntries total numer of ENTRY's, with
42    ENTRIES_PER_PAGE data items per "page".  It is implemented as a
43    Chare Array of pages, and a Group representing the local cache.
44
45    The requirements for the templates are:
46      ENTRY: User data class stored in the array, with at least:
47         - A default constructor and destructor
48         - A working assignment operator
49         - A working pup routine
50      ENTRY_OPS_CLASS: Used to combine values for "accumulate":
51         - A method named "getIdentity", taking no arguments and
52           returning an ENTRY to use before any accumulation.
53         - A method named "accumulate", taking a source/dest ENTRY by reference
54           and an ENTRY to add to it by value or const reference.
55      ENTRIES_PER_PAGE: Optional integer number of ENTRY objects
56         to store and communicate at once.  For good performance,
57         make sure this value is a power of two.
58  */
59 template<class ENTRY, class ENTRY_OPS_CLASS, unsigned int ENTRIES_PER_PAGE=MSA_DEFAULT_ENTRIES_PER_PAGE>
60 class MSA1D
61 {
62 public:
63     typedef MSA_CacheGroup<ENTRY, ENTRY_OPS_CLASS, ENTRIES_PER_PAGE> CacheGroup_t;
64     typedef CProxy_MSA_CacheGroup<ENTRY, ENTRY_OPS_CLASS, ENTRIES_PER_PAGE> CProxy_CacheGroup_t;
65     typedef CProxy_MSA_PageArray<ENTRY, ENTRY_OPS_CLASS, ENTRIES_PER_PAGE> CProxy_PageArray_t;
66
67     // Sun's C++ compiler doesn't understand that nested classes are
68     // members for the sake of access to private data. (2008-10-23)
69     class Read; class Write; class Accum;
70     friend class Read; friend class Write; friend class Accum;
71
72         class Handle
73         {
74     public:
75         inline unsigned int length() const { return msa.length(); }
76
77         protected:
78         MSA1D &msa;
79         bool valid;
80
81         friend class MSA1D;
82
83         void inline checkInvalidate(MSA1D *m) 
84         {
85             if (m != &msa || !valid)
86                 throw MSA_InvalidHandle();
87             valid = false;
88         }
89
90         Handle(MSA1D &msa_) 
91             : msa(msa_), valid(true) 
92         { }
93         void checkValid()
94         {
95             if (!valid)
96                 throw MSA_InvalidHandle();
97         }
98
99     private:
100         // Disallow copy construction
101         Handle(Handle &);
102     };
103
104     class Read : public Handle
105     {
106     protected:
107         friend class MSA1D;
108         Read(MSA1D &msa_)
109             :  Handle(msa_) { }
110         using Handle::checkValid;
111         using Handle::checkInvalidate;
112
113     public:
114         inline const ENTRY& get(unsigned int idx)
115         {
116             checkValid();
117             return Handle::msa.get(idx); 
118         }
119         inline const ENTRY& operator[](unsigned int idx) { return get(idx); }
120         inline const ENTRY& operator()(unsigned int idx) { return get(idx); }
121         inline const ENTRY& get2(unsigned int idx)
122         {
123             checkValid();
124             return Handle::msa.get2(idx);
125         }
126     };
127
128     class Write : public Handle
129     {
130     protected:
131         friend class MSA1D;
132         Write(MSA1D &msa_)
133             : Handle(msa_) { }
134
135     public:
136         inline Writable<ENTRY> set(unsigned int idx)
137         {
138             Handle::checkValid();
139             return Writable<ENTRY>(Handle::msa.set(idx));
140         }
141         inline Writable<ENTRY> operator()(unsigned int idx)
142             { return set(idx); }
143     };
144
145     class Accum : public Handle
146     {
147     protected:
148         friend class MSA1D;
149         Accum(MSA1D &msa_)
150             : Handle(msa_) { }
151         using Handle::checkInvalidate;
152     public:
153         inline Accumulable<ENTRY, ENTRY_OPS_CLASS> accumulate(unsigned int idx)
154         { 
155             Handle::checkValid();
156             return Accumulable<ENTRY, ENTRY_OPS_CLASS>(Handle::msa.accumulate(idx));
157         }
158         inline void accumulate(unsigned int idx, const ENTRY& ent)
159         {
160             Handle::checkValid();
161             Handle::msa.accumulate(idx, ent);
162         }
163
164         void contribute(unsigned int idx, const ENTRY *begin, const ENTRY *end)
165         {
166             Handle::checkValid();
167             for (const ENTRY *e = begin; e != end; ++e, ++idx)
168                 {
169                     Handle::msa.accumulate(idx, *e);
170                 }
171         }
172
173         inline Accumulable<ENTRY, ENTRY_OPS_CLASS> operator() (unsigned int idx)
174             { return accumulate(idx); }
175     };
176
177 protected:
178     /// Total number of ENTRY's in the whole array.
179     unsigned int nEntries;
180     bool initHandleGiven;
181
182     /// Handle to owner of cache.
183     CacheGroup_t* cache;
184     CProxy_CacheGroup_t cg;
185
186     inline const ENTRY* readablePage(unsigned int page)
187     {
188         return (const ENTRY*)(cache->readablePage(page));
189     }
190
191     // known local page.
192     inline const ENTRY* readablePage2(unsigned int page)
193     {
194         return (const ENTRY*)(cache->readablePage2(page));
195     }
196
197     // Returns a pointer to the start of the local copy in the cache of the writeable page.
198     // @@ what if begin - end span across two or more pages?
199     inline ENTRY* writeablePage(unsigned int page, unsigned int offset)
200     {
201         return (ENTRY*)(cache->writeablePage(page, offset));
202     }
203
204 public:
205     // @@ Needed for Jade
206     inline MSA1D() 
207         :initHandleGiven(false) 
208     {}
209
210     virtual void pup(PUP::er &p){
211         p|nEntries;
212         p|cg;
213         if (p.isUnpacking()) cache=cg.ckLocalBranch();
214     }
215
216     /**
217       Create a completely new MSA array.  This call creates the
218       corresponding groups, so only call it once per array.
219     */
220     inline MSA1D(unsigned int nEntries_, unsigned int num_wrkrs, 
221                  unsigned int maxBytes=MSA_DEFAULT_MAX_BYTES) 
222         : nEntries(nEntries_), initHandleGiven(false)
223     {
224         // first create the Page Array and the Page Group
225         unsigned int nPages = (nEntries + ENTRIES_PER_PAGE - 1)/ENTRIES_PER_PAGE;
226         CProxy_PageArray_t pageArray = CProxy_PageArray_t::ckNew(nPages);
227         cg = CProxy_CacheGroup_t::ckNew(nPages, pageArray, maxBytes, nEntries, num_wrkrs);
228         pageArray.setCacheProxy(cg);
229         pageArray.ckSetReductionClient(new CkCallback(CkIndex_MSA_CacheGroup<ENTRY, ENTRY_OPS_CLASS, ENTRIES_PER_PAGE>::SyncDone(NULL), cg));
230         cache = cg.ckLocalBranch();
231     }
232
233     // Deprecated API for accessing CacheGroup directly.
234     inline MSA1D(CProxy_CacheGroup_t cg_) : cg(cg_), initHandleGiven(false)
235     {
236         cache = cg.ckLocalBranch();
237         nEntries = cache->getNumEntries();
238     }
239
240     inline ~MSA1D()
241     {
242         // TODO: how to get rid of the cache group and the page array
243         //(cache->getArray()).destroy();
244         //cg.destroy();
245         // TODO: calling FreeMem does not seem to work. Need to debug it.
246                                 cache->unroll();
247  //       cache->FreeMem();
248     }
249
250     /**
251      * this function is supposed to be called when the thread/object using this array
252      * migrates to another PE.
253      */
254     inline void changePE()
255     {
256         cache = cg.ckLocalBranch();
257
258         /* don't need to update the number of entries, as that does not change */
259     }
260
261     // ================ Accessor/Utility functions ================
262     /// Get the total length of the array, across all processors.
263     inline unsigned int length() const { return nEntries; }
264
265     inline const CProxy_CacheGroup_t &getCacheGroup() const { return cg; }
266
267     // Avoid using the term "page size" because it is confusing: does
268     // it mean in bytes or number of entries?
269     inline unsigned int getNumEntriesPerPage() const { return ENTRIES_PER_PAGE; }
270
271     /// Return the page this entry is stored at.
272     inline unsigned int getPageIndex(unsigned int idx)
273     {
274         return idx / ENTRIES_PER_PAGE;
275     }
276
277     /// Return the offset, in entries, that this entry is stored at within a page.
278     inline unsigned int getOffsetWithinPage(unsigned int idx)
279     {
280         return idx % ENTRIES_PER_PAGE;
281     }
282
283     // ================ MSA API ================
284
285     // We need to know the total number of workers across all
286     // processors, and we also calculate the number of worker threads
287     // running on this processor.
288     //
289     // Blocking method, basically does a barrier until all workers
290     // enroll.
291     inline void enroll(int num_workers)
292     {
293         // @@ This is a hack to identify the number of MSA1D
294         // threads on this processor.  This number is needed for sync.
295         //
296         // @@ What if a MSA1D thread migrates?
297         cache->enroll(num_workers);
298     }
299
300     // idx is the element to be read/written
301     //
302     // This function returns a reference to the first element on the
303     // page that contains idx.
304     inline ENTRY& getPageBottom(unsigned int idx, MSA_Page_Fault_t accessMode)
305     {
306         if (accessMode==Read_Fault) {
307             unsigned int page = idx / ENTRIES_PER_PAGE;
308             return const_cast<ENTRY&>(readablePage(page)[0]);
309         } else {
310             CkAssert(accessMode==Write_Fault || accessMode==Accumulate_Fault);
311             unsigned int page = idx / ENTRIES_PER_PAGE;
312             unsigned int offset = idx % ENTRIES_PER_PAGE;
313             ENTRY* e=writeablePage(page, offset);
314             return e[0];
315         }
316     }
317
318     inline void FreeMem()
319     {
320         cache->FreeMem();
321     }
322
323     /// Non-blocking prefetch of entries from start to end, inclusive.
324     /// Prefetch'd pages are locked into the cache, so you must call
325     ///   unlock afterwards.
326     inline void Prefetch(unsigned int start, unsigned int end)
327     {
328         unsigned int page1 = start / ENTRIES_PER_PAGE;
329         unsigned int page2 = end / ENTRIES_PER_PAGE;
330         cache->Prefetch(page1, page2);
331     }
332
333     /// Block until all prefetched pages arrive.
334     inline int WaitAll()    { return cache->WaitAll(); }
335
336     /// Unlock all locked pages
337     inline void Unlock()    { return cache->UnlockPages(); }
338
339     /// start and end are element indexes.
340     /// Unlocks completely spanned pages given a range of elements
341     /// index'd from "start" to "end", inclusive.  If start/end does not span a
342     /// page completely, i.e. start/end is in the middle of a page,
343     /// the entire page is still unlocked--in particular, this means
344     /// you should not have several adjacent ranges locked.
345     inline void Unlock(unsigned int start, unsigned int end)
346     {
347         unsigned int page1 = start / ENTRIES_PER_PAGE;
348         unsigned int page2 = end / ENTRIES_PER_PAGE;
349         cache->UnlockPages(page1, page2);
350     }
351
352     static const int DEFAULT_SYNC_SINGLE = 0;
353
354     inline Read &syncToRead(Handle &m, int single = DEFAULT_SYNC_SINGLE)
355     {
356         m.checkInvalidate(this);
357         delete &m;
358         sync(single);
359         return *(new Read(*this));
360     }
361
362     inline Write &syncToWrite(Handle &m, int single = DEFAULT_SYNC_SINGLE)
363     {
364         m.checkInvalidate(this);
365         delete &m;
366         sync(single);
367         return *(new Write(*this));
368     }
369
370     inline Accum &syncToAccum(Handle &m, int single = DEFAULT_SYNC_SINGLE)
371     {
372         m.checkInvalidate(this);
373         delete &m;
374         sync(single);
375         return *(new Accum(*this));
376     }
377
378     inline Write &getInitialWrite()
379     {
380         if (initHandleGiven)
381             throw MSA_InvalidHandle();
382
383         Write *w = new Write(*this);
384         sync();
385         initHandleGiven = true;
386         return *w;
387     }
388
389     inline Accum &getInitialAccum()
390     {
391         if (initHandleGiven)
392             throw MSA_InvalidHandle();
393
394         Accum *a = new Accum(*this);
395         sync();
396         initHandleGiven = true;
397         return *a;
398     }
399
400   // These are the meat of the MSA API, but they are only accessible
401   // through appropriate handles (defined in the public section above).
402 protected:
403     /// Return a read-only copy of the element at idx.
404     ///   May block if the element is not already in the cache.
405     inline const ENTRY& get(unsigned int idx)
406     {
407         unsigned int page = idx / ENTRIES_PER_PAGE;
408         unsigned int offset = idx % ENTRIES_PER_PAGE;
409         return readablePage(page)[offset];
410     }
411
412     inline const ENTRY& operator[](unsigned int idx)
413     {
414         return get(idx);
415     }
416
417     /// Return a read-only copy of the element at idx;
418     ///   ONLY WORKS WHEN ELEMENT IS ALREADY IN THE CACHE--
419     ///   WILL SEGFAULT IF ELEMENT NOT ALREADY PRESENT.
420     ///    Never blocks; may crash if element not already present.
421     inline const ENTRY& get2(unsigned int idx)
422     {
423         unsigned int page = idx / ENTRIES_PER_PAGE;
424         unsigned int offset = idx % ENTRIES_PER_PAGE;
425         return readablePage2(page)[offset];
426     }
427
428     /// Return a writeable copy of the element at idx.
429     ///    Never blocks; will create a new blank element if none exists locally.
430     ///    UNDEFINED if two threads set the same element.
431     inline ENTRY& set(unsigned int idx)
432     {
433         unsigned int page = idx / ENTRIES_PER_PAGE;
434         unsigned int offset = idx % ENTRIES_PER_PAGE;
435         ENTRY* e=writeablePage(page, offset);
436         return e[offset];
437     }
438
439     /// Fetch the ENTRY at idx to be accumulated.
440     ///   You must perform the accumulation on 
441     ///     the return value before calling "sync".
442     ///   Never blocks.
443     inline ENTRY& accumulate(unsigned int idx)
444     {
445         unsigned int page = idx / ENTRIES_PER_PAGE;
446         unsigned int offset = idx % ENTRIES_PER_PAGE;
447         return cache->accumulate(page, offset);
448     }
449     
450     /// Add ent to the element at idx.
451     ///   Never blocks.
452     ///   Merges together accumulates from different threads.
453     inline void accumulate(unsigned int idx, const ENTRY& ent)
454     {
455         ENTRY_OPS_CLASS::accumulate(accumulate(idx),ent);
456     }
457
458     /// Synchronize reads and writes across the entire array.
459     inline void sync(int single=0)
460     {
461         cache->SyncReq(single); 
462     }
463 };
464
465
466 // define a 2d distributed array based on the 1D array, support row major and column
467 // major arrangement of data
468 template<class ENTRY, class ENTRY_OPS_CLASS, unsigned int ENTRIES_PER_PAGE=MSA_DEFAULT_ENTRIES_PER_PAGE, MSA_Array_Layout_t ARRAY_LAYOUT=MSA_ROW_MAJOR>
469 class MSA2D : public MSA1D<ENTRY, ENTRY_OPS_CLASS, ENTRIES_PER_PAGE>
470 {
471 public:
472     typedef CProxy_MSA_CacheGroup<ENTRY, ENTRY_OPS_CLASS, ENTRIES_PER_PAGE> CProxy_CacheGroup_t;
473     typedef MSA1D<ENTRY, ENTRY_OPS_CLASS, ENTRIES_PER_PAGE> super;
474
475 protected:
476     unsigned int rows, cols;
477
478 public:
479     // @@ Needed for Jade
480     inline MSA2D() : super() {}
481     virtual void pup(PUP::er &p) {
482        super::pup(p);
483        p|rows; p|cols;
484     };
485
486         class Handle
487         {
488         protected:
489         MSA2D &msa;
490         bool valid;
491
492         friend class MSA2D;
493
494         inline void checkInvalidate(MSA2D *m)
495         {
496             if (&msa != m || !valid)
497                 throw MSA_InvalidHandle();
498             valid = false;
499         }
500
501         Handle(MSA2D &msa_) 
502             : msa(msa_), valid(true) 
503         { }
504         inline void checkValid()
505         {
506             if (!valid)
507                 throw MSA_InvalidHandle();
508         }
509     private:
510         // Disallow copy construction
511         Handle(Handle &);
512     };
513
514     class Read : public Handle
515     {
516     private:
517         friend class MSA2D;
518         Read(MSA2D &msa_)
519             :  Handle(msa_) { }
520
521     public: 
522         inline const ENTRY& get(unsigned int row, unsigned int col)
523         {
524             Handle::checkValid();
525             return Handle::msa.get(row, col);
526         }
527         inline const ENTRY& get2(unsigned int row, unsigned int col)
528         {
529             Handle::checkValid();
530             return Handle::msa.get2(row, col);
531         }
532
533         inline const ENTRY& operator() (unsigned int row, unsigned int col)
534             {
535                 return get(row,col);
536             }
537
538     };
539
540     class Write : public Handle
541     {
542     private:
543         friend class MSA2D;
544         Write(MSA2D &msa_)
545             :  Handle(msa_) { }
546
547     public: 
548         inline Writable<ENTRY> set(unsigned int row, unsigned int col)
549         {
550             Handle::checkValid();
551             return Writable<ENTRY>(Handle::msa.set(row, col));
552         }
553     };
554
555     class Accum : public Handle
556     {
557     protected:
558         friend class MSA2D;
559         Accum(MSA2D &msa_)
560             : Handle(msa_) { }
561         using Handle::checkInvalidate;
562     public:
563         inline Accumulable<ENTRY, ENTRY_OPS_CLASS> accumulate(unsigned int idx)
564         {
565             Handle::checkValid();
566             return Accumulable<ENTRY, ENTRY_OPS_CLASS>(Handle::msa.accumulate(idx));
567         }
568         inline void accumulate(unsigned int idx, const ENTRY& ent)
569         {
570             Handle::checkValid();
571             Handle::msa.accumulate(idx, ent);
572         }
573
574         void contribute(unsigned int idx, const ENTRY *begin, const ENTRY *end)
575         {
576             Handle::checkValid();
577             for (const ENTRY *e = begin; e != end; ++e, ++idx)
578                 {
579                     Handle::msa.accumulate(idx, *e);
580                 }
581         }
582
583         inline Accumulable<ENTRY, ENTRY_OPS_CLASS> operator() (unsigned int idx)
584             { return accumulate(idx); }
585     };
586
587     inline MSA2D(unsigned int rows_, unsigned int cols_, unsigned int numwrkrs,
588                  unsigned int maxBytes=MSA_DEFAULT_MAX_BYTES)
589         :super(rows_*cols_, numwrkrs, maxBytes)
590     {
591         rows = rows_; cols = cols_;
592     }
593
594     inline MSA2D(unsigned int rows_, unsigned int cols_, CProxy_CacheGroup_t cg_)
595         : rows(rows_), cols(cols_), super(cg_)
596     {}
597
598     // get the 1D index of the given entry as per the row major/column major format
599     inline unsigned int getIndex(unsigned int row, unsigned int col)
600     {
601         unsigned int index;
602
603         if(ARRAY_LAYOUT==MSA_ROW_MAJOR)
604             index = row*cols + col;
605         else
606             index = col*rows + row;
607
608         return index;
609     }
610
611     // Which page is (row, col) on?
612     inline unsigned int getPageIndex(unsigned int row, unsigned int col)
613     {
614         return getIndex(row, col)/ENTRIES_PER_PAGE;
615     }
616
617     inline unsigned int getOffsetWithinPage(unsigned int row, unsigned int col)
618     {
619         return getIndex(row, col)%ENTRIES_PER_PAGE;
620     }
621
622     inline unsigned int getRows(void) const {return rows;}
623     inline unsigned int getCols(void) const {return cols;}
624     inline unsigned int getColumns(void) const {return cols;}
625     inline MSA_Array_Layout_t getArrayLayout() const {return ARRAY_LAYOUT;}
626
627     inline void Prefetch(unsigned int start, unsigned int end)
628     {
629         // prefetch the start ... end rows/columns into the cache
630         if(start > end)
631         {
632             unsigned int temp = start;
633             start = end;
634             end = temp;
635         }
636
637         unsigned int index1 = (ARRAY_LAYOUT==MSA_ROW_MAJOR) ? getIndex(start, 0) : getIndex(0, start);
638         unsigned int index2 = (ARRAY_LAYOUT==MSA_ROW_MAJOR) ? getIndex(end, cols-1) : getIndex(rows-1, end);
639
640         MSA1D<ENTRY, ENTRY_OPS_CLASS, ENTRIES_PER_PAGE>::Prefetch(index1, index2);
641     }
642
643     // Unlocks pages starting from row "start" through row "end", inclusive
644     inline void UnlockPages(unsigned int start, unsigned int end)
645     {
646         if(start > end)
647         {
648             unsigned int temp = start;
649             start = end;
650             end = temp;
651         }
652
653         unsigned int index1 = (ARRAY_LAYOUT==MSA_ROW_MAJOR) ? getIndex(start, 0) : getIndex(0, start);
654         unsigned int index2 = (ARRAY_LAYOUT==MSA_ROW_MAJOR) ? getIndex(end, cols-1) : getIndex(rows-1, end);
655
656         MSA1D<ENTRY, ENTRY_OPS_CLASS, ENTRIES_PER_PAGE>::Unlock(index1, index2);
657     }
658
659     inline Read& syncToRead(Handle &m, int single = super::DEFAULT_SYNC_SINGLE)
660     {
661         m.checkInvalidate(this);
662         delete &m;
663         super::sync(single);
664         return *(new Read(*this));
665     }
666
667     inline Write& syncToWrite(Handle &m, int single = super::DEFAULT_SYNC_SINGLE)
668     {
669         m.checkInvalidate(this);
670         delete &m;
671         super::sync(single);
672         return *(new Write(*this));
673     }
674
675     inline Accum& syncToAccum(Handle &m, int single = super::DEFAULT_SYNC_SINGLE)
676     {
677         m.checkInvalidate(this);
678         delete &m;
679         super::sync(single);
680         return *(new Accum(*this));
681     }
682
683     inline Write& getInitialWrite()
684     {
685         if (super::initHandleGiven)
686             throw MSA_InvalidHandle();
687
688         Write *w = new Write(*this);
689         super::initHandleGiven = true;
690         return *w;
691     }
692
693     inline Accum &getInitialAccum()
694     {
695         if (super::initHandleGiven)
696             throw MSA_InvalidHandle();
697
698         Accum *a = new Accum(*this);
699         sync();
700         super::initHandleGiven = true;
701         return *a;
702     }
703
704
705 protected:
706     inline const ENTRY& get(unsigned int row, unsigned int col)
707     {
708         return super::get(getIndex(row, col));
709     }
710
711     // known local
712     inline const ENTRY& get2(unsigned int row, unsigned int col)
713     {
714         return super::get2(getIndex(row, col));
715     }
716
717     // MSA2D::
718     inline ENTRY& set(unsigned int row, unsigned int col)
719     {
720         return super::set(getIndex(row, col));
721     }
722 };
723
724 namespace MSA
725 {
726     using std::min;
727     using std::max;
728
729
730 /**
731    The MSA3D class is a handle to a distributed shared array of items
732    of data type ENTRY. There are nEntries total numer of ENTRY's, with
733    ENTRIES_PER_PAGE data items per "page".  It is implemented as a
734    Chare Array of pages, and a Group representing the local cache.
735
736    The requirements for the templates are:
737      ENTRY: User data class stored in the array, with at least:
738         - A default constructor and destructor
739         - A working assignment operator
740         - A working pup routine
741      ENTRY_OPS_CLASS: Used to combine values for "accumulate":
742         - A method named "getIdentity", taking no arguments and
743           returning an ENTRY to use before any accumulation.
744         - A method named "accumulate", taking a source/dest ENTRY by reference
745           and an ENTRY to add to it by value or const reference.
746      ENTRIES_PER_PAGE: Optional integer number of ENTRY objects
747         to store and communicate at once.  For good performance,
748         make sure this value is a power of two.
749  */
750 template<class ENTRY, class ENTRY_OPS_CLASS, unsigned int ENTRIES_PER_PAGE>
751 class MSA3D
752 {
753     unsigned dim_x, dim_y, dim_z;
754
755
756 public:
757     typedef MSA_CacheGroup<ENTRY, ENTRY_OPS_CLASS, ENTRIES_PER_PAGE> CacheGroup_t;
758     typedef CProxy_MSA_CacheGroup<ENTRY, ENTRY_OPS_CLASS, ENTRIES_PER_PAGE> CProxy_CacheGroup_t;
759     typedef CProxy_MSA_PageArray<ENTRY, ENTRY_OPS_CLASS, ENTRIES_PER_PAGE> CProxy_PageArray_t;
760
761     // Sun's C++ compiler doesn't understand that nested classes are
762     // members for the sake of access to private data. (2008-10-23)
763     class Read; class Write; class Accum;
764     friend class Read; friend class Write; friend class Accum;
765
766         class Handle
767         {
768         protected:
769         MSA3D *msa;
770         bool valid;
771
772         friend class MSA3D;
773
774         void inline checkInvalidate() 
775         {
776             if (!valid)
777                 throw MSA_InvalidHandle();
778             valid = false;
779         }
780
781         Handle(MSA3D *msa_) 
782             : msa(msa_), valid(true) 
783         { }
784         void checkValid()
785         {
786             if (!valid)
787                 throw MSA_InvalidHandle();
788         }
789         
790     public:
791         inline void syncRelease()
792             {
793                 checkInvalidate();
794                 if (msa->active)
795                     msa->cache->SyncRelease();
796                 else
797                     CmiAbort("sync from an inactive thread!\n");
798                 msa->active = false;
799             }
800
801         inline void syncDone()
802             {
803                 checkInvalidate();
804                 msa->sync(DEFAULT_SYNC_SINGLE);
805             }
806
807         inline Read syncToRead()
808             {
809                 checkInvalidate();
810                 msa->sync(DEFAULT_SYNC_SINGLE);
811                 return Read(msa);
812             }
813
814         inline Write syncToWrite()
815             {
816                 checkInvalidate();
817                 msa->sync(DEFAULT_SYNC_SINGLE);
818                 return Write(msa);
819             }
820
821         inline Accum syncToAccum()
822             {
823                 checkInvalidate();
824                 msa->sync(DEFAULT_SYNC_SINGLE);
825                 return Accum(msa);
826             }
827
828         void pup(PUP::er &p)
829             {
830                 p|valid;
831                 if (valid)
832                 {
833                     if (p.isUnpacking())
834                         msa = new MSA3D;
835                     p|(*msa);
836                 }
837                 else if (p.isUnpacking())
838                     msa = NULL;
839             }
840
841         Handle() : msa(NULL), valid(false) {}
842     };
843
844     class Read : public Handle
845     {
846     protected:
847         friend class MSA3D;
848         Read(MSA3D *msa_)
849             :  Handle(msa_) { }
850         using Handle::checkValid;
851         using Handle::checkInvalidate;
852
853     public:
854         Read() {}
855
856         inline const ENTRY& get(unsigned x, unsigned y, unsigned z)
857         {
858             checkValid();
859             return Handle::msa->get(x, y, z); 
860         }
861         inline const ENTRY& operator()(unsigned x, unsigned y, unsigned z) { return get(x, y, z); }
862         inline const ENTRY& get2(unsigned x, unsigned y, unsigned z)
863         {
864             checkValid();
865             return Handle::msa->get2(x, y, z);
866         }
867
868         // Reads the specified range into the provided buffer in row-major order
869         void read(ENTRY *buf, unsigned x1, unsigned y1, unsigned z1, unsigned x2, unsigned y2, unsigned z2)
870         {
871             checkValid();
872
873             CkAssert(x1 <= x2);
874             CkAssert(y1 <= y2);
875             CkAssert(z1 <= z2);
876
877             CkAssert(x1 >= 0);
878             CkAssert(y1 >= 0);
879             CkAssert(z1 >= 0);
880
881             CkAssert(x2 < Handle::msa->dim_x);
882             CkAssert(y2 < Handle::msa->dim_y);
883             CkAssert(z2 < Handle::msa->dim_z);
884
885             unsigned i = 0;
886
887             for (unsigned ix = x1; ix <= x2; ++ix)
888                 for (unsigned iy = y1; iy <= y2; ++iy)
889                     for (unsigned iz = z1; iz <= z2; ++iz)
890                         buf[i++] = Handle::msa->get(ix, iy, iz);
891         }
892     };
893
894     class Write : public Handle
895     {
896     protected:
897         friend class MSA3D;
898         Write(MSA3D *msa_)
899             : Handle(msa_) { }
900
901     public:
902         Write() {}
903
904         inline Writable<ENTRY> set(unsigned x, unsigned y, unsigned z)
905         {
906             Handle::checkValid();
907             return Writable<ENTRY>(Handle::msa->set(x,y,z));
908         }
909         inline Writable<ENTRY> operator()(unsigned x, unsigned y, unsigned z)
910         {
911             return set(x,y,z);
912         }
913
914         void write(unsigned x1, unsigned y1, unsigned z1, unsigned x2, unsigned y2, unsigned z2, const ENTRY *buf)
915         {
916             Handle::checkValid();
917
918             CkAssert(x1 <= x2);
919             CkAssert(y1 <= y2);
920             CkAssert(z1 <= z2);
921
922             CkAssert(x1 >= 0);
923             CkAssert(y1 >= 0);
924             CkAssert(z1 >= 0);
925
926             CkAssert(x2 < Handle::msa->dim_x);
927             CkAssert(y2 < Handle::msa->dim_y);
928             CkAssert(z2 < Handle::msa->dim_z);
929
930             unsigned i = 0;
931
932             for (unsigned ix = x1; ix <= x2; ++ix)
933                 for (unsigned iy = y1; iy <= y2; ++iy)
934                     for (unsigned iz = z1; iz <= z2; ++iz)
935                     {
936                         if (isnan(buf[i]))
937                             CmiAbort("Tried to write a NaN!");
938                         Handle::msa->set(ix, iy, iz) = buf[i++];
939                     }
940         }
941 #if 0
942     private:
943         Write(Write &);
944 #endif
945     };
946
947     class Accum : public Handle
948     {
949     protected:
950         friend class MSA3D;
951         Accum(MSA3D *msa_)
952             : Handle(msa_) { }
953         using Handle::checkInvalidate;
954     public:
955         Accum() {}
956
957         inline Accumulable<ENTRY, ENTRY_OPS_CLASS> accumulate(unsigned int x, unsigned int y, unsigned int z)
958         {
959             Handle::checkValid();
960             return Accumulable<ENTRY, ENTRY_OPS_CLASS>(Handle::msa->accumulate(x,y,z));
961         }
962         inline void accumulate(unsigned int x, unsigned int y, unsigned int z, const ENTRY& ent)
963         {
964             Handle::checkValid();
965             Handle::msa->accumulate(x,y,z, ent);
966         }
967
968         void accumulate(unsigned x1, unsigned y1, unsigned z1, unsigned x2, unsigned y2, unsigned z2, const ENTRY *buf)
969         {
970             Handle::checkValid();
971             CkAssert(x1 <= x2);
972             CkAssert(y1 <= y2);
973             CkAssert(z1 <= z2);
974
975             CkAssert(x1 >= 0);
976             CkAssert(y1 >= 0);
977             CkAssert(z1 >= 0);
978
979             CkAssert(x2 < Handle::msa->dim_x);
980             CkAssert(y2 < Handle::msa->dim_y);
981             CkAssert(z2 < Handle::msa->dim_z);
982
983             unsigned i = 0;
984
985             for (unsigned ix = x1; ix <= x2; ++ix)
986                 for (unsigned iy = y1; iy <= y2; ++iy)
987                     for (unsigned iz = z1; iz <= z2; ++iz)
988                         Handle::msa->accumulate(ix, iy, iz, buf[i++]);
989         }
990
991         inline Accumulable<ENTRY, ENTRY_OPS_CLASS> operator() (unsigned int x, unsigned int y, unsigned int z)
992             { return accumulate(x,y,z); }
993     };
994
995 protected:
996     /// Total number of ENTRY's in the whole array.
997     unsigned int nEntries;
998     bool initHandleGiven;
999
1000     /// Handle to owner of cache.
1001     CacheGroup_t* cache;
1002     CProxy_CacheGroup_t cg;
1003
1004     inline const ENTRY* readablePage(unsigned int page)
1005     {
1006         return (const ENTRY*)(cache->readablePage(page));
1007     }
1008
1009     // known local page.
1010     inline const ENTRY* readablePage2(unsigned int page)
1011     {
1012         return (const ENTRY*)(cache->readablePage2(page));
1013     }
1014
1015     // Returns a pointer to the start of the local copy in the cache of the writeable page.
1016     // @@ what if begin - end span across two or more pages?
1017     inline ENTRY* writeablePage(unsigned int page, unsigned int offset)
1018     {
1019         return (ENTRY*)(cache->writeablePage(page, offset));
1020     }
1021
1022 public:
1023     // @@ Needed for Jade
1024     inline MSA3D() 
1025         :initHandleGiven(false) 
1026     {}
1027
1028     virtual void pup(PUP::er &p){
1029         p|dim_x;
1030         p|dim_y;
1031         p|dim_z;
1032         p|nEntries;
1033         p|cg;
1034         if (p.isUnpacking()) cache=cg.ckLocalBranch();
1035     }
1036
1037     /**
1038       Create a completely new MSA array.  This call creates the
1039       corresponding groups, so only call it once per array.
1040     */
1041     inline MSA3D(unsigned x, unsigned y, unsigned z, unsigned int num_wrkrs, 
1042                  unsigned int maxBytes=MSA_DEFAULT_MAX_BYTES)
1043         : dim_x(x), dim_y(y), dim_z(z), initHandleGiven(false)
1044     {
1045         unsigned nEntries = x*y*z;
1046         unsigned int nPages = (nEntries + ENTRIES_PER_PAGE - 1)/ENTRIES_PER_PAGE;
1047         CProxy_PageArray_t pageArray = CProxy_PageArray_t::ckNew(nPages);
1048         cg = CProxy_CacheGroup_t::ckNew(nPages, pageArray, maxBytes, nEntries, num_wrkrs);
1049         pageArray.setCacheProxy(cg);
1050         //pageArray.ckSetReductionClient(new CkCallback(CkIndex_MSA_CacheGroup<ENTRY, ENTRY_OPS_CLASS, ENTRIES_PER_PAGE>::SyncDone(NULL), cg));
1051         cache = cg.ckLocalBranch();
1052     }
1053
1054     inline ~MSA3D()
1055     {
1056         // TODO: how to get rid of the cache group and the page array
1057         //(cache->getArray()).destroy();
1058         //cg.destroy();
1059         // TODO: calling FreeMem does not seem to work. Need to debug it.
1060         //cache->unroll();
1061         //cache->FreeMem();
1062     }
1063
1064     /**
1065      * this function is supposed to be called when the thread/object using this array
1066      * migrates to another PE.
1067      */
1068     inline void changePE()
1069     {
1070         cache = cg.ckLocalBranch();
1071
1072         /* don't need to update the number of entries, as that does not change */
1073     }
1074
1075     // ================ Accessor/Utility functions ================
1076
1077     inline const CProxy_CacheGroup_t &getCacheGroup() const { return cg; }
1078
1079     // Avoid using the term "page size" because it is confusing: does
1080     // it mean in bytes or number of entries?
1081     inline unsigned int getNumEntriesPerPage() const { return ENTRIES_PER_PAGE; }
1082
1083     inline unsigned int index(unsigned x, unsigned y, unsigned z)
1084     {
1085         CkAssert(x < dim_x);
1086         CkAssert(y < dim_y);
1087         CkAssert(z < dim_z);
1088         return ((x*dim_y) + y) * dim_z + z;
1089     }
1090     
1091     /// Return the page this entry is stored at.
1092     inline unsigned int getPageIndex(unsigned int idx)
1093     {
1094         return idx / ENTRIES_PER_PAGE;
1095     }
1096
1097     /// Return the offset, in entries, that this entry is stored at within a page.
1098     inline unsigned int getOffsetWithinPage(unsigned int idx)
1099     {
1100         return idx % ENTRIES_PER_PAGE;
1101     }
1102
1103     // ================ MSA API ================
1104
1105     // We need to know the total number of workers across all
1106     // processors, and we also calculate the number of worker threads
1107     // running on this processor.
1108     //
1109     // Blocking method, basically does a barrier until all workers
1110     // enroll.
1111     inline void enroll(int num_workers)
1112     {
1113         // @@ This is a hack to identify the number of MSA3D
1114         // threads on this processor.  This number is needed for sync.
1115         //
1116         // @@ What if a MSA3D thread migrates?
1117         cache->enroll(num_workers);
1118     }
1119
1120     // idx is the element to be read/written
1121     //
1122     // This function returns a reference to the first element on the
1123     // page that contains idx.
1124     inline ENTRY& getPageBottom(unsigned int idx, MSA_Page_Fault_t accessMode)
1125     {
1126         if (accessMode==Read_Fault) {
1127             unsigned int page = idx / ENTRIES_PER_PAGE;
1128             return const_cast<ENTRY&>(readablePage(page)[0]);
1129         } else {
1130             CkAssert(accessMode==Write_Fault || accessMode==Accumulate_Fault);
1131             unsigned int page = idx / ENTRIES_PER_PAGE;
1132             unsigned int offset = idx % ENTRIES_PER_PAGE;
1133             ENTRY* e=writeablePage(page, offset);
1134             return e[0];
1135         }
1136     }
1137
1138     inline void FreeMem()
1139     {
1140         cache->FreeMem();
1141     }
1142
1143     /// Non-blocking prefetch of entries from start to end, inclusive.
1144     /// Prefetch'd pages are locked into the cache, so you must call
1145     ///   unlock afterwards.
1146     inline void Prefetch(unsigned int start, unsigned int end)
1147     {
1148         unsigned int page1 = start / ENTRIES_PER_PAGE;
1149         unsigned int page2 = end / ENTRIES_PER_PAGE;
1150         cache->Prefetch(page1, page2);
1151     }
1152
1153     /// Block until all prefetched pages arrive.
1154     inline int WaitAll()    { return cache->WaitAll(); }
1155
1156     /// Unlock all locked pages
1157     inline void Unlock()    { return cache->UnlockPages(); }
1158
1159     /// start and end are element indexes.
1160     /// Unlocks completely spanned pages given a range of elements
1161     /// index'd from "start" to "end", inclusive.  If start/end does not span a
1162     /// page completely, i.e. start/end is in the middle of a page,
1163     /// the entire page is still unlocked--in particular, this means
1164     /// you should not have several adjacent ranges locked.
1165     inline void Unlock(unsigned int start, unsigned int end)
1166     {
1167         unsigned int page1 = start / ENTRIES_PER_PAGE;
1168         unsigned int page2 = end / ENTRIES_PER_PAGE;
1169         cache->UnlockPages(page1, page2);
1170     }
1171
1172     static const int DEFAULT_SYNC_SINGLE = 0;
1173
1174     inline Write getInitialWrite()
1175     {
1176         if (initHandleGiven)
1177             CmiAbort("Trying to get an MSA's initial handle a second time");
1178
1179         //Write *w = new Write(*this);
1180         //sync();
1181         initHandleGiven = true;
1182         return Write(this);
1183     }
1184
1185     inline Accum getInitialAccum()
1186     {
1187         if (initHandleGiven)
1188             CmiAbort("Trying to get an MSA's initial handle a second time");
1189
1190         //Accum *a = new Accum(*this);
1191         //sync();
1192         initHandleGiven = true;
1193         return Accum(this);
1194     }
1195
1196   // These are the meat of the MSA API, but they are only accessible
1197   // through appropriate handles (defined in the public section above).
1198 protected:
1199     /// Return a read-only copy of the element at idx.
1200     ///   May block if the element is not already in the cache.
1201     inline const ENTRY& get(unsigned x, unsigned y, unsigned z)
1202     {
1203         unsigned int idx = index(x,y,z);
1204         unsigned int page = idx / ENTRIES_PER_PAGE;
1205         unsigned int offset = idx % ENTRIES_PER_PAGE;
1206         return readablePage(page)[offset];
1207     }
1208
1209     /// Return a read-only copy of the element at idx;
1210     ///   ONLY WORKS WHEN ELEMENT IS ALREADY IN THE CACHE--
1211     ///   WILL SEGFAULT IF ELEMENT NOT ALREADY PRESENT.
1212     ///    Never blocks; may crash if element not already present.
1213     inline const ENTRY& get2(unsigned x, unsigned y, unsigned z)
1214     {
1215         unsigned int idx = index(x,y,z);
1216         unsigned int page = idx / ENTRIES_PER_PAGE;
1217         unsigned int offset = idx % ENTRIES_PER_PAGE;
1218         return readablePage2(page)[offset];
1219     }
1220
1221     /// Return a writeable copy of the element at idx.
1222     ///    Never blocks; will create a new blank element if none exists locally.
1223     ///    UNDEFINED if two threads set the same element.
1224     inline ENTRY& set(unsigned x, unsigned y, unsigned z)
1225     {
1226         unsigned int idx = index(x,y,z);
1227         unsigned int page = idx / ENTRIES_PER_PAGE;
1228         unsigned int offset = idx % ENTRIES_PER_PAGE;
1229         ENTRY* e=writeablePage(page, offset);
1230         return e[offset];
1231     }
1232
1233     /// Fetch the ENTRY at idx to be accumulated.
1234     ///   You must perform the accumulation on 
1235     ///     the return value before calling "sync".
1236     ///   Never blocks.
1237     inline ENTRY& accumulate(unsigned x, unsigned y, unsigned z)
1238     {
1239         unsigned int idx = index(x,y,z);
1240         unsigned int page = idx / ENTRIES_PER_PAGE;
1241         unsigned int offset = idx % ENTRIES_PER_PAGE;
1242         return cache->accumulate(page, offset);
1243     }
1244     
1245     /// Add ent to the element at idx.
1246     ///   Never blocks.
1247     ///   Merges together accumulates from different threads.
1248     inline void accumulate(unsigned x, unsigned y, unsigned z, const ENTRY& ent)
1249     {
1250         ENTRY_OPS_CLASS::accumulate(accumulate(x,y,z),ent);
1251     }
1252
1253     /// Synchronize reads and writes across the entire array.
1254     inline void sync(int single=0)
1255     {
1256         cache->SyncReq(single); 
1257     }
1258 };
1259
1260 }
1261 #endif