MSA: Add fuller range of functionality to 2D's handles
[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         inline Writable<ENTRY> operator()(unsigned int row, unsigned int col)
555             { return set(row, col); }
556     };
557
558     class Accum : public Handle
559     {
560     protected:
561         friend class MSA2D;
562         Accum(MSA2D &msa_)
563             : Handle(msa_) { }
564         using Handle::checkInvalidate;
565     public:
566         inline Accumulable<ENTRY, ENTRY_OPS_CLASS> accumulate(unsigned int idx)
567         {
568             Handle::checkValid();
569             return Accumulable<ENTRY, ENTRY_OPS_CLASS>(Handle::msa.accumulate(idx));
570         }
571         inline Accumulable<ENTRY, ENTRY_OPS_CLASS> accumulate(unsigned int x, unsigned int y)
572         {
573             Handle::checkValid();
574             return Accumulable<ENTRY, ENTRY_OPS_CLASS>(Handle::msa.accumulate(Handle::msa.getIndex(x, y)));
575         }
576         inline void accumulate(unsigned int idx, const ENTRY& ent)
577         {
578             Handle::checkValid();
579             Handle::msa.accumulate(idx, ent);
580         }
581
582         void contribute(unsigned int idx, const ENTRY *begin, const ENTRY *end)
583         {
584             Handle::checkValid();
585             for (const ENTRY *e = begin; e != end; ++e, ++idx)
586                 {
587                     Handle::msa.accumulate(idx, *e);
588                 }
589         }
590
591         inline Accumulable<ENTRY, ENTRY_OPS_CLASS> operator() (unsigned int idx)
592             { return accumulate(idx); }
593         inline Accumulable<ENTRY, ENTRY_OPS_CLASS> operator() (unsigned int x, unsigned int y)
594             { return accumulate(x, y); }
595     };
596
597     inline MSA2D(unsigned int rows_, unsigned int cols_, unsigned int numwrkrs,
598                  unsigned int maxBytes=MSA_DEFAULT_MAX_BYTES)
599         :super(rows_*cols_, numwrkrs, maxBytes)
600     {
601         rows = rows_; cols = cols_;
602     }
603
604     inline MSA2D(unsigned int rows_, unsigned int cols_, CProxy_CacheGroup_t cg_)
605         : rows(rows_), cols(cols_), super(cg_)
606     {}
607
608     // get the 1D index of the given entry as per the row major/column major format
609     inline unsigned int getIndex(unsigned int row, unsigned int col)
610     {
611         unsigned int index;
612
613         if(ARRAY_LAYOUT==MSA_ROW_MAJOR)
614             index = row*cols + col;
615         else
616             index = col*rows + row;
617
618         return index;
619     }
620
621     // Which page is (row, col) on?
622     inline unsigned int getPageIndex(unsigned int row, unsigned int col)
623     {
624         return getIndex(row, col)/ENTRIES_PER_PAGE;
625     }
626
627     inline unsigned int getOffsetWithinPage(unsigned int row, unsigned int col)
628     {
629         return getIndex(row, col)%ENTRIES_PER_PAGE;
630     }
631
632     inline unsigned int getRows(void) const {return rows;}
633     inline unsigned int getCols(void) const {return cols;}
634     inline unsigned int getColumns(void) const {return cols;}
635     inline MSA_Array_Layout_t getArrayLayout() const {return ARRAY_LAYOUT;}
636
637     inline void Prefetch(unsigned int start, unsigned int end)
638     {
639         // prefetch the start ... end rows/columns into the cache
640         if(start > end)
641         {
642             unsigned int temp = start;
643             start = end;
644             end = temp;
645         }
646
647         unsigned int index1 = (ARRAY_LAYOUT==MSA_ROW_MAJOR) ? getIndex(start, 0) : getIndex(0, start);
648         unsigned int index2 = (ARRAY_LAYOUT==MSA_ROW_MAJOR) ? getIndex(end, cols-1) : getIndex(rows-1, end);
649
650         MSA1D<ENTRY, ENTRY_OPS_CLASS, ENTRIES_PER_PAGE>::Prefetch(index1, index2);
651     }
652
653     // Unlocks pages starting from row "start" through row "end", inclusive
654     inline void UnlockPages(unsigned int start, unsigned int end)
655     {
656         if(start > end)
657         {
658             unsigned int temp = start;
659             start = end;
660             end = temp;
661         }
662
663         unsigned int index1 = (ARRAY_LAYOUT==MSA_ROW_MAJOR) ? getIndex(start, 0) : getIndex(0, start);
664         unsigned int index2 = (ARRAY_LAYOUT==MSA_ROW_MAJOR) ? getIndex(end, cols-1) : getIndex(rows-1, end);
665
666         MSA1D<ENTRY, ENTRY_OPS_CLASS, ENTRIES_PER_PAGE>::Unlock(index1, index2);
667     }
668
669     inline Read& syncToRead(Handle &m, int single = super::DEFAULT_SYNC_SINGLE)
670     {
671         m.checkInvalidate(this);
672         delete &m;
673         super::sync(single);
674         return *(new Read(*this));
675     }
676
677     inline Write& syncToWrite(Handle &m, int single = super::DEFAULT_SYNC_SINGLE)
678     {
679         m.checkInvalidate(this);
680         delete &m;
681         super::sync(single);
682         return *(new Write(*this));
683     }
684
685     inline Accum& syncToAccum(Handle &m, int single = super::DEFAULT_SYNC_SINGLE)
686     {
687         m.checkInvalidate(this);
688         delete &m;
689         super::sync(single);
690         return *(new Accum(*this));
691     }
692
693     inline Write& getInitialWrite()
694     {
695         if (super::initHandleGiven)
696             throw MSA_InvalidHandle();
697
698         Write *w = new Write(*this);
699         super::initHandleGiven = true;
700         return *w;
701     }
702
703     inline Accum &getInitialAccum()
704     {
705         if (super::initHandleGiven)
706             throw MSA_InvalidHandle();
707
708         Accum *a = new Accum(*this);
709         sync();
710         super::initHandleGiven = true;
711         return *a;
712     }
713
714
715 protected:
716     inline const ENTRY& get(unsigned int row, unsigned int col)
717     {
718         return super::get(getIndex(row, col));
719     }
720
721     // known local
722     inline const ENTRY& get2(unsigned int row, unsigned int col)
723     {
724         return super::get2(getIndex(row, col));
725     }
726
727     // MSA2D::
728     inline ENTRY& set(unsigned int row, unsigned int col)
729     {
730         return super::set(getIndex(row, col));
731     }
732 };
733
734 namespace MSA
735 {
736     using std::min;
737     using std::max;
738
739
740 /**
741    The MSA3D class is a handle to a distributed shared array of items
742    of data type ENTRY. There are nEntries total numer of ENTRY's, with
743    ENTRIES_PER_PAGE data items per "page".  It is implemented as a
744    Chare Array of pages, and a Group representing the local cache.
745
746    The requirements for the templates are:
747      ENTRY: User data class stored in the array, with at least:
748         - A default constructor and destructor
749         - A working assignment operator
750         - A working pup routine
751      ENTRY_OPS_CLASS: Used to combine values for "accumulate":
752         - A method named "getIdentity", taking no arguments and
753           returning an ENTRY to use before any accumulation.
754         - A method named "accumulate", taking a source/dest ENTRY by reference
755           and an ENTRY to add to it by value or const reference.
756      ENTRIES_PER_PAGE: Optional integer number of ENTRY objects
757         to store and communicate at once.  For good performance,
758         make sure this value is a power of two.
759  */
760 template<class ENTRY, class ENTRY_OPS_CLASS, unsigned int ENTRIES_PER_PAGE>
761 class MSA3D
762 {
763     unsigned dim_x, dim_y, dim_z;
764
765
766 public:
767     typedef MSA_CacheGroup<ENTRY, ENTRY_OPS_CLASS, ENTRIES_PER_PAGE> CacheGroup_t;
768     typedef CProxy_MSA_CacheGroup<ENTRY, ENTRY_OPS_CLASS, ENTRIES_PER_PAGE> CProxy_CacheGroup_t;
769     typedef CProxy_MSA_PageArray<ENTRY, ENTRY_OPS_CLASS, ENTRIES_PER_PAGE> CProxy_PageArray_t;
770
771     // Sun's C++ compiler doesn't understand that nested classes are
772     // members for the sake of access to private data. (2008-10-23)
773     class Read; class Write; class Accum;
774     friend class Read; friend class Write; friend class Accum;
775
776         class Handle
777         {
778         protected:
779         MSA3D *msa;
780         bool valid;
781
782         friend class MSA3D;
783
784         void inline checkInvalidate() 
785         {
786             if (!valid)
787                 throw MSA_InvalidHandle();
788             valid = false;
789         }
790
791         Handle(MSA3D *msa_) 
792             : msa(msa_), valid(true) 
793         { }
794         void checkValid()
795         {
796             if (!valid)
797                 throw MSA_InvalidHandle();
798         }
799         
800     public:
801         inline void syncRelease()
802             {
803                 checkInvalidate();
804                 if (msa->active)
805                     msa->cache->SyncRelease();
806                 else
807                     CmiAbort("sync from an inactive thread!\n");
808                 msa->active = false;
809             }
810
811         inline void syncDone()
812             {
813                 checkInvalidate();
814                 msa->sync(DEFAULT_SYNC_SINGLE);
815             }
816
817         inline Read syncToRead()
818             {
819                 checkInvalidate();
820                 msa->sync(DEFAULT_SYNC_SINGLE);
821                 return Read(msa);
822             }
823
824         inline Write syncToWrite()
825             {
826                 checkInvalidate();
827                 msa->sync(DEFAULT_SYNC_SINGLE);
828                 return Write(msa);
829             }
830
831         inline Accum syncToAccum()
832             {
833                 checkInvalidate();
834                 msa->sync(DEFAULT_SYNC_SINGLE);
835                 return Accum(msa);
836             }
837
838         void pup(PUP::er &p)
839             {
840                 p|valid;
841                 if (valid)
842                 {
843                     if (p.isUnpacking())
844                         msa = new MSA3D;
845                     p|(*msa);
846                 }
847                 else if (p.isUnpacking())
848                     msa = NULL;
849             }
850
851         Handle() : msa(NULL), valid(false) {}
852     };
853
854     class Read : public Handle
855     {
856     protected:
857         friend class MSA3D;
858         Read(MSA3D *msa_)
859             :  Handle(msa_) { }
860         using Handle::checkValid;
861         using Handle::checkInvalidate;
862
863     public:
864         Read() {}
865
866         inline const ENTRY& get(unsigned x, unsigned y, unsigned z)
867         {
868             checkValid();
869             return Handle::msa->get(x, y, z); 
870         }
871         inline const ENTRY& operator()(unsigned x, unsigned y, unsigned z) { return get(x, y, z); }
872         inline const ENTRY& get2(unsigned x, unsigned y, unsigned z)
873         {
874             checkValid();
875             return Handle::msa->get2(x, y, z);
876         }
877
878         // Reads the specified range into the provided buffer in row-major order
879         void read(ENTRY *buf, unsigned x1, unsigned y1, unsigned z1, unsigned x2, unsigned y2, unsigned z2)
880         {
881             checkValid();
882
883             CkAssert(x1 <= x2);
884             CkAssert(y1 <= y2);
885             CkAssert(z1 <= z2);
886
887             CkAssert(x1 >= 0);
888             CkAssert(y1 >= 0);
889             CkAssert(z1 >= 0);
890
891             CkAssert(x2 < Handle::msa->dim_x);
892             CkAssert(y2 < Handle::msa->dim_y);
893             CkAssert(z2 < Handle::msa->dim_z);
894
895             unsigned i = 0;
896
897             for (unsigned ix = x1; ix <= x2; ++ix)
898                 for (unsigned iy = y1; iy <= y2; ++iy)
899                     for (unsigned iz = z1; iz <= z2; ++iz)
900                         buf[i++] = Handle::msa->get(ix, iy, iz);
901         }
902     };
903
904     class Write : public Handle
905     {
906     protected:
907         friend class MSA3D;
908         Write(MSA3D *msa_)
909             : Handle(msa_) { }
910
911     public:
912         Write() {}
913
914         inline Writable<ENTRY> set(unsigned x, unsigned y, unsigned z)
915         {
916             Handle::checkValid();
917             return Writable<ENTRY>(Handle::msa->set(x,y,z));
918         }
919         inline Writable<ENTRY> operator()(unsigned x, unsigned y, unsigned z)
920         {
921             return set(x,y,z);
922         }
923
924         void write(unsigned x1, unsigned y1, unsigned z1, unsigned x2, unsigned y2, unsigned z2, const ENTRY *buf)
925         {
926             Handle::checkValid();
927
928             CkAssert(x1 <= x2);
929             CkAssert(y1 <= y2);
930             CkAssert(z1 <= z2);
931
932             CkAssert(x1 >= 0);
933             CkAssert(y1 >= 0);
934             CkAssert(z1 >= 0);
935
936             CkAssert(x2 < Handle::msa->dim_x);
937             CkAssert(y2 < Handle::msa->dim_y);
938             CkAssert(z2 < Handle::msa->dim_z);
939
940             unsigned i = 0;
941
942             for (unsigned ix = x1; ix <= x2; ++ix)
943                 for (unsigned iy = y1; iy <= y2; ++iy)
944                     for (unsigned iz = z1; iz <= z2; ++iz)
945                     {
946                         if (isnan(buf[i]))
947                             CmiAbort("Tried to write a NaN!");
948                         Handle::msa->set(ix, iy, iz) = buf[i++];
949                     }
950         }
951 #if 0
952     private:
953         Write(Write &);
954 #endif
955     };
956
957     class Accum : public Handle
958     {
959     protected:
960         friend class MSA3D;
961         Accum(MSA3D *msa_)
962             : Handle(msa_) { }
963         using Handle::checkInvalidate;
964     public:
965         Accum() {}
966
967         inline Accumulable<ENTRY, ENTRY_OPS_CLASS> accumulate(unsigned int x, unsigned int y, unsigned int z)
968         {
969             Handle::checkValid();
970             return Accumulable<ENTRY, ENTRY_OPS_CLASS>(Handle::msa->accumulate(x,y,z));
971         }
972         inline void accumulate(unsigned int x, unsigned int y, unsigned int z, const ENTRY& ent)
973         {
974             Handle::checkValid();
975             Handle::msa->accumulate(x,y,z, ent);
976         }
977
978         void accumulate(unsigned x1, unsigned y1, unsigned z1, unsigned x2, unsigned y2, unsigned z2, const ENTRY *buf)
979         {
980             Handle::checkValid();
981             CkAssert(x1 <= x2);
982             CkAssert(y1 <= y2);
983             CkAssert(z1 <= z2);
984
985             CkAssert(x1 >= 0);
986             CkAssert(y1 >= 0);
987             CkAssert(z1 >= 0);
988
989             CkAssert(x2 < Handle::msa->dim_x);
990             CkAssert(y2 < Handle::msa->dim_y);
991             CkAssert(z2 < Handle::msa->dim_z);
992
993             unsigned i = 0;
994
995             for (unsigned ix = x1; ix <= x2; ++ix)
996                 for (unsigned iy = y1; iy <= y2; ++iy)
997                     for (unsigned iz = z1; iz <= z2; ++iz)
998                         Handle::msa->accumulate(ix, iy, iz, buf[i++]);
999         }
1000
1001         inline Accumulable<ENTRY, ENTRY_OPS_CLASS> operator() (unsigned int x, unsigned int y, unsigned int z)
1002             { return accumulate(x,y,z); }
1003     };
1004
1005 protected:
1006     /// Total number of ENTRY's in the whole array.
1007     unsigned int nEntries;
1008     bool initHandleGiven;
1009
1010     /// Handle to owner of cache.
1011     CacheGroup_t* cache;
1012     CProxy_CacheGroup_t cg;
1013
1014     inline const ENTRY* readablePage(unsigned int page)
1015     {
1016         return (const ENTRY*)(cache->readablePage(page));
1017     }
1018
1019     // known local page.
1020     inline const ENTRY* readablePage2(unsigned int page)
1021     {
1022         return (const ENTRY*)(cache->readablePage2(page));
1023     }
1024
1025     // Returns a pointer to the start of the local copy in the cache of the writeable page.
1026     // @@ what if begin - end span across two or more pages?
1027     inline ENTRY* writeablePage(unsigned int page, unsigned int offset)
1028     {
1029         return (ENTRY*)(cache->writeablePage(page, offset));
1030     }
1031
1032 public:
1033     // @@ Needed for Jade
1034     inline MSA3D() 
1035         :initHandleGiven(false) 
1036     {}
1037
1038     virtual void pup(PUP::er &p){
1039         p|dim_x;
1040         p|dim_y;
1041         p|dim_z;
1042         p|nEntries;
1043         p|cg;
1044         if (p.isUnpacking()) cache=cg.ckLocalBranch();
1045     }
1046
1047     /**
1048       Create a completely new MSA array.  This call creates the
1049       corresponding groups, so only call it once per array.
1050     */
1051     inline MSA3D(unsigned x, unsigned y, unsigned z, unsigned int num_wrkrs, 
1052                  unsigned int maxBytes=MSA_DEFAULT_MAX_BYTES)
1053         : dim_x(x), dim_y(y), dim_z(z), initHandleGiven(false)
1054     {
1055         unsigned nEntries = x*y*z;
1056         unsigned int nPages = (nEntries + ENTRIES_PER_PAGE - 1)/ENTRIES_PER_PAGE;
1057         CProxy_PageArray_t pageArray = CProxy_PageArray_t::ckNew(nPages);
1058         cg = CProxy_CacheGroup_t::ckNew(nPages, pageArray, maxBytes, nEntries, num_wrkrs);
1059         pageArray.setCacheProxy(cg);
1060         //pageArray.ckSetReductionClient(new CkCallback(CkIndex_MSA_CacheGroup<ENTRY, ENTRY_OPS_CLASS, ENTRIES_PER_PAGE>::SyncDone(NULL), cg));
1061         cache = cg.ckLocalBranch();
1062     }
1063
1064     inline ~MSA3D()
1065     {
1066         // TODO: how to get rid of the cache group and the page array
1067         //(cache->getArray()).destroy();
1068         //cg.destroy();
1069         // TODO: calling FreeMem does not seem to work. Need to debug it.
1070         //cache->unroll();
1071         //cache->FreeMem();
1072     }
1073
1074     /**
1075      * this function is supposed to be called when the thread/object using this array
1076      * migrates to another PE.
1077      */
1078     inline void changePE()
1079     {
1080         cache = cg.ckLocalBranch();
1081
1082         /* don't need to update the number of entries, as that does not change */
1083     }
1084
1085     // ================ Accessor/Utility functions ================
1086
1087     inline const CProxy_CacheGroup_t &getCacheGroup() const { return cg; }
1088
1089     // Avoid using the term "page size" because it is confusing: does
1090     // it mean in bytes or number of entries?
1091     inline unsigned int getNumEntriesPerPage() const { return ENTRIES_PER_PAGE; }
1092
1093     inline unsigned int index(unsigned x, unsigned y, unsigned z)
1094     {
1095         CkAssert(x < dim_x);
1096         CkAssert(y < dim_y);
1097         CkAssert(z < dim_z);
1098         return ((x*dim_y) + y) * dim_z + z;
1099     }
1100     
1101     /// Return the page this entry is stored at.
1102     inline unsigned int getPageIndex(unsigned int idx)
1103     {
1104         return idx / ENTRIES_PER_PAGE;
1105     }
1106
1107     /// Return the offset, in entries, that this entry is stored at within a page.
1108     inline unsigned int getOffsetWithinPage(unsigned int idx)
1109     {
1110         return idx % ENTRIES_PER_PAGE;
1111     }
1112
1113     // ================ MSA API ================
1114
1115     // We need to know the total number of workers across all
1116     // processors, and we also calculate the number of worker threads
1117     // running on this processor.
1118     //
1119     // Blocking method, basically does a barrier until all workers
1120     // enroll.
1121     inline void enroll(int num_workers)
1122     {
1123         // @@ This is a hack to identify the number of MSA3D
1124         // threads on this processor.  This number is needed for sync.
1125         //
1126         // @@ What if a MSA3D thread migrates?
1127         cache->enroll(num_workers);
1128     }
1129
1130     // idx is the element to be read/written
1131     //
1132     // This function returns a reference to the first element on the
1133     // page that contains idx.
1134     inline ENTRY& getPageBottom(unsigned int idx, MSA_Page_Fault_t accessMode)
1135     {
1136         if (accessMode==Read_Fault) {
1137             unsigned int page = idx / ENTRIES_PER_PAGE;
1138             return const_cast<ENTRY&>(readablePage(page)[0]);
1139         } else {
1140             CkAssert(accessMode==Write_Fault || accessMode==Accumulate_Fault);
1141             unsigned int page = idx / ENTRIES_PER_PAGE;
1142             unsigned int offset = idx % ENTRIES_PER_PAGE;
1143             ENTRY* e=writeablePage(page, offset);
1144             return e[0];
1145         }
1146     }
1147
1148     inline void FreeMem()
1149     {
1150         cache->FreeMem();
1151     }
1152
1153     /// Non-blocking prefetch of entries from start to end, inclusive.
1154     /// Prefetch'd pages are locked into the cache, so you must call
1155     ///   unlock afterwards.
1156     inline void Prefetch(unsigned int start, unsigned int end)
1157     {
1158         unsigned int page1 = start / ENTRIES_PER_PAGE;
1159         unsigned int page2 = end / ENTRIES_PER_PAGE;
1160         cache->Prefetch(page1, page2);
1161     }
1162
1163     /// Block until all prefetched pages arrive.
1164     inline int WaitAll()    { return cache->WaitAll(); }
1165
1166     /// Unlock all locked pages
1167     inline void Unlock()    { return cache->UnlockPages(); }
1168
1169     /// start and end are element indexes.
1170     /// Unlocks completely spanned pages given a range of elements
1171     /// index'd from "start" to "end", inclusive.  If start/end does not span a
1172     /// page completely, i.e. start/end is in the middle of a page,
1173     /// the entire page is still unlocked--in particular, this means
1174     /// you should not have several adjacent ranges locked.
1175     inline void Unlock(unsigned int start, unsigned int end)
1176     {
1177         unsigned int page1 = start / ENTRIES_PER_PAGE;
1178         unsigned int page2 = end / ENTRIES_PER_PAGE;
1179         cache->UnlockPages(page1, page2);
1180     }
1181
1182     static const int DEFAULT_SYNC_SINGLE = 0;
1183
1184     inline Write getInitialWrite()
1185     {
1186         if (initHandleGiven)
1187             CmiAbort("Trying to get an MSA's initial handle a second time");
1188
1189         //Write *w = new Write(*this);
1190         //sync();
1191         initHandleGiven = true;
1192         return Write(this);
1193     }
1194
1195     inline Accum getInitialAccum()
1196     {
1197         if (initHandleGiven)
1198             CmiAbort("Trying to get an MSA's initial handle a second time");
1199
1200         //Accum *a = new Accum(*this);
1201         //sync();
1202         initHandleGiven = true;
1203         return Accum(this);
1204     }
1205
1206   // These are the meat of the MSA API, but they are only accessible
1207   // through appropriate handles (defined in the public section above).
1208 protected:
1209     /// Return a read-only copy of the element at idx.
1210     ///   May block if the element is not already in the cache.
1211     inline const ENTRY& get(unsigned x, unsigned y, unsigned z)
1212     {
1213         unsigned int idx = index(x,y,z);
1214         unsigned int page = idx / ENTRIES_PER_PAGE;
1215         unsigned int offset = idx % ENTRIES_PER_PAGE;
1216         return readablePage(page)[offset];
1217     }
1218
1219     /// Return a read-only copy of the element at idx;
1220     ///   ONLY WORKS WHEN ELEMENT IS ALREADY IN THE CACHE--
1221     ///   WILL SEGFAULT IF ELEMENT NOT ALREADY PRESENT.
1222     ///    Never blocks; may crash if element not already present.
1223     inline const ENTRY& get2(unsigned x, unsigned y, unsigned z)
1224     {
1225         unsigned int idx = index(x,y,z);
1226         unsigned int page = idx / ENTRIES_PER_PAGE;
1227         unsigned int offset = idx % ENTRIES_PER_PAGE;
1228         return readablePage2(page)[offset];
1229     }
1230
1231     /// Return a writeable copy of the element at idx.
1232     ///    Never blocks; will create a new blank element if none exists locally.
1233     ///    UNDEFINED if two threads set the same element.
1234     inline ENTRY& set(unsigned x, unsigned y, unsigned z)
1235     {
1236         unsigned int idx = index(x,y,z);
1237         unsigned int page = idx / ENTRIES_PER_PAGE;
1238         unsigned int offset = idx % ENTRIES_PER_PAGE;
1239         ENTRY* e=writeablePage(page, offset);
1240         return e[offset];
1241     }
1242
1243     /// Fetch the ENTRY at idx to be accumulated.
1244     ///   You must perform the accumulation on 
1245     ///     the return value before calling "sync".
1246     ///   Never blocks.
1247     inline ENTRY& accumulate(unsigned x, unsigned y, unsigned z)
1248     {
1249         unsigned int idx = index(x,y,z);
1250         unsigned int page = idx / ENTRIES_PER_PAGE;
1251         unsigned int offset = idx % ENTRIES_PER_PAGE;
1252         return cache->accumulate(page, offset);
1253     }
1254     
1255     /// Add ent to the element at idx.
1256     ///   Never blocks.
1257     ///   Merges together accumulates from different threads.
1258     inline void accumulate(unsigned x, unsigned y, unsigned z, const ENTRY& ent)
1259     {
1260         ENTRY_OPS_CLASS::accumulate(accumulate(x,y,z),ent);
1261     }
1262
1263     /// Synchronize reads and writes across the entire array.
1264     inline void sync(int single=0)
1265     {
1266         cache->SyncReq(single); 
1267     }
1268 };
1269
1270 }
1271 #endif