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