Home My Page Projects Code Snippets Project Openings diderot
Summary Activity Tracker Tasks SCM

SCM Repository

[diderot] Annotation of /branches/vis15/src/compiler/target-cpu/fragments/seq-sarr-dual-indirect.in
ViewVC logotype

Annotation of /branches/vis15/src/compiler/target-cpu/fragments/seq-sarr-dual-indirect.in

Parent Directory Parent Directory | Revision Log Revision Log


Revision 5061 - (view) (download)

1 : jhr 4631 // forward declarations of strand methods
2 : jhr 4501 #ifdef DIDEROT_HAS_START_METHOD
3 :     static diderot::strand_status @STRAND@_start (@START_PARAMS@
4 :     @STRAND@_local *selfLocal, @STRAND@_shared *selfIn, @STRAND@_shared *selfOut);
5 :     #endif // DIDEROT_HAS_START_METHOD
6 :     static diderot::strand_status @STRAND@_update (@UPDATE_PARAMS@
7 :     @STRAND@_local *selfLocal, @STRAND@_shared *selfIn, @STRAND@_shared *selfOut);
8 :     #ifdef DIDEROT_HAS_STABILIZE_METHOD
9 :     static void @STRAND@_stabilize (@STABILIZE_PARAMS@
10 :     @STRAND@_local *selfLocal, @STRAND@_shared *selfIn, @STRAND@_shared *selfOut);
11 :     #endif // DIDEROT_HAS_STABILIZE_METHOD
12 :    
13 : jhr 4460 // strand_array for BSP/DUAL STATE/INDIRECT ACCESS
14 :     //
15 :     struct strand_array {
16 : jhr 4516 typedef @STRANDTY@ strand_t;
17 : jhr 4591 typedef uint32_t index_t; // strand index (index into _idx and _status arrays)
18 :     typedef uint32_t sid_t; // strand ID (index into strand-state storage)
19 : jhr 4510 typedef char *block_t; // points to array of @STRANDTY@ structs
20 : jhr 4460
21 : jhr 4510 uint8_t *_status; // the array of status information for the strands
22 :     uint32_t *_idx; // array of strand indices for indirect state rep.
23 :     std::vector<block_t> _blocks; // vector of pointers to strand-storage blocks
24 :     uint32_t _inIdx; // index of shared input state (either 0 or 1)
25 :     uint32_t _nItems; // number of items in the _blocks and _status arrays
26 :     uint32_t _nStable; // stable strands (in locations 0.._nStable-1)
27 :     uint32_t _nActive; // active strands (in locations _nStable.._nStable+_nActive-1)
28 :     uint32_t _nStabilizing; // number of stablizing strands
29 :     uint32_t _nDying; // number of dying strands
30 :     uint32_t _nNew; // number of new strands
31 : jhr 4753 uint32_t _nFresh; // number of fresh strands (new strands from previous step)
32 : jhr 4460
33 : jhr 4510 static const uint32_t LOG_BLKSZ = 12; // 2^12 items per block
34 : jhr 4460 static const uint32_t BLKSZ = (1 << LOG_BLKSZ);
35 : jhr 4510 static const uint32_t BLKMASK = (BLKSZ-1); // mask for block index
36 : jhr 4460
37 :     strand_array () : _status(nullptr), _idx(nullptr), _nItems(0) { }
38 : jhr 4551 ~strand_array ();
39 : jhr 4460
40 : jhr 4516 uint32_t in_state_index () const { return this->_inIdx; }
41 :    
42 : jhr 4609 uint32_t num_active () const { return this->_nActive; }
43 : jhr 4510 uint32_t num_stable () const { return this->_nStable; }
44 :     uint32_t num_alive () const { return this->_nActive+this->_nStable; }
45 : jhr 4753 uint32_t num_fresh () const { return this->_nFresh; }
46 : jhr 4510
47 : jhr 4590 // return the ID of a strand, which is the value of the _idx array
48 :     sid_t id (index_t ix) const
49 :     {
50 : jhr 4591 assert (ix < this->_nItems);
51 :     return this->_idx[ix];
52 : jhr 4590 }
53 :     // return a pointer to the strand with the given ID
54 :     @STRANDTY@ *id_to_strand (sid_t id) const
55 :     {
56 : jhr 4591 assert (id < this->_nItems);
57 : jhr 4590 uint32_t blkId = id >> LOG_BLKSZ;
58 :     uint32_t offset = id & BLKMASK;
59 :     return reinterpret_cast<@STRANDTY@ *>(this->_blocks[blkId] + offset * sizeof(@STRANDTY@));
60 :     }
61 :    
62 : jhr 4510 // return a strand's status
63 :     diderot::strand_status status (index_t ix) const
64 :     {
65 : jhr 4582 assert (ix < this->_nItems);
66 : jhr 4510 return static_cast<diderot::strand_status>(this->_status[ix]);
67 :     }
68 : jhr 4460 // return a pointer to the given strand
69 :     @STRANDTY@ *strand (index_t ix) const
70 :     {
71 : jhr 4591 return this->id_to_strand(this->id(ix));
72 : jhr 4460 }
73 : jhr 4582
74 : jhr 4460 // return a pointer to the local state of strand ix
75 : jhr 4489 @STRAND@_local *local_state (index_t ix) const
76 : jhr 4460 {
77 : jhr 4547 return &(this->strand(ix)->_local);
78 : jhr 4460 }
79 : jhr 4590 // return a pointer to the local state of strand with the given ID
80 :     @STRAND@_local *id_to_local_state (sid_t id) const
81 :     {
82 :     return &(this->id_to_strand(id)->_local);
83 :     }
84 : jhr 4460 // return a pointer to the in-state of strand ix
85 :     const @STRAND@_shared *in_state (index_t ix) const
86 :     {
87 : jhr 4547 return &(this->strand(ix)->_shared[this->_inIdx]);
88 : jhr 4460 }
89 : jhr 4590 // return a pointer to the in-state of the strand with the given ID
90 :     const @STRAND@_shared *id_to_in_state (sid_t id) const
91 :     {
92 :     return &(this->id_to_strand(id)->_shared[this->_inIdx]);
93 :     }
94 : jhr 4460 // return a pointer to the out-state of strand ix
95 :     @STRAND@_shared *out_state (index_t ix) const
96 :     {
97 : jhr 4547 return &(this->strand(ix)->_shared[this->_inIdx ^ 1]);
98 : jhr 4460 }
99 :    
100 : jhr 4934 // wrappers for accessing the state of newly created strands
101 : jhr 4948 @STRAND@_local *new_local_state (index_t ix) const
102 : jhr 4934 {
103 :     return this->local_state(ix);
104 :     }
105 :     @STRAND@_shared *new_out_state (index_t ix) const
106 :     {
107 :     return this->out_state(ix);
108 :     }
109 :    
110 : jhr 5015 // is an index valid for the strand array?
111 :     bool validIndex (index_t ix) const { return (ix < this->_nItems); }
112 :    
113 :     // is a given strand alive?
114 :     bool isAlive (index_t ix) const
115 :     {
116 :     #ifdef DIDEROT_HAS_STRAND_DIE
117 : jhr 5061 return aliveSts(this->status(ix));
118 : jhr 5015 #else
119 :     return true;
120 :     #endif
121 :     }
122 :    
123 : jhr 4460 // deallocate space reserved for strands
124 : jhr 4551 void dealloc ();
125 : jhr 4460
126 :     // allocate space for at least nItems
127 :     bool alloc (uint32_t nItems)
128 :     {
129 : jhr 4510 nItems = (nItems + BLKSZ - 1) & ~BLKMASK;
130 :     uint32_t nBlks = nItems >> LOG_BLKSZ;
131 : jhr 4460 // allocate block vector
132 : jhr 4510 this->_blocks.resize(nBlks, nullptr);
133 : jhr 4460 // allocate blocks
134 : jhr 4510 for (int i = 0; i < nBlks; i++) {
135 :     this->_blocks[i] = static_cast<char *>(std::malloc (BLKSZ * sizeof(@STRANDTY@)));
136 :     if (this->_blocks[i] == nullptr) {
137 :     // unable to allocate memory
138 :     this->dealloc();
139 :     return true;
140 :     }
141 :     }
142 : jhr 4460 // allocate _status array
143 : jhr 4510 this->_status = static_cast<uint8_t *>(std::malloc (nItems * sizeof(uint8_t)));
144 :     if (this->_status == nullptr) {
145 : jhr 4547 this->dealloc();
146 : jhr 4510 return true;
147 :     }
148 : jhr 4460 // allocate _idx array
149 : jhr 4510 this->_idx = static_cast<uint32_t *>(std::malloc (nItems * sizeof(uint32_t)));
150 :     if (this->_idx == nullptr) {
151 : jhr 4547 this->dealloc();
152 : jhr 4510 return true;
153 :     }
154 : jhr 4512 // initialize arrays
155 : jhr 4582 for (index_t ix = 0; ix < nItems; ix++) {
156 :     this->_status[ix] = diderot::kDead;
157 :     this->_idx[ix] = ix;
158 :     }
159 :     this->_inIdx = 0;
160 : jhr 4510 this->_nItems = nItems;
161 :     this->_nActive = 0;
162 :     this->_nStable = 0;
163 : jhr 4580 this->_nStabilizing = 0;
164 :     this->_nNew = 0;
165 :     this->_nDying = 0;
166 : jhr 4753 this->_nFresh = 0;
167 : jhr 4510 return false;
168 : jhr 4460 }
169 :    
170 :     // initialize the first nStrands locations as new active strands
171 :     void create_strands (uint32_t nStrands)
172 :     {
173 : jhr 4510 assert (this->_nActive == 0);
174 :     assert (this->_nItems >= nStrands);
175 : jhr 4582 for (index_t ix = 0; ix < nStrands; ix++) {
176 : jhr 4580 this->_status[ix] = diderot::kActive;
177 : jhr 4512 new (this->strand(ix)) @STRANDTY@;
178 : jhr 4582 }
179 : jhr 4510 this->_nActive = nStrands;
180 : jhr 4753 this->_nFresh = nStrands;
181 : jhr 4460 }
182 :    
183 : jhr 4510 // swap in and out states
184 :     void swap ()
185 :     {
186 : jhr 4547 this->_inIdx ^= 1;
187 : jhr 4510 }
188 :    
189 : jhr 4501 #ifdef DIDEROT_HAS_START_METHOD
190 :     // invoke strand's start method
191 :     diderot::strand_status strand_start (@START_PARAMS@index_t ix)
192 :     {
193 : jhr 4510 @STRANDTY@ *self = this->strand(ix);
194 :     return @STRAND@_start (@START_ARGS@
195 :     &self->_local,
196 :     &self->_shared[this->_inIdx],
197 :     &self->_shared[this->_inIdx^1]);
198 : jhr 4501 }
199 :     #endif // DIDEROT_HAS_START_METHOD
200 :    
201 :     // invoke strand's update method
202 :     diderot::strand_status strand_update (@UPDATE_PARAMS@index_t ix)
203 :     {
204 : jhr 4510 @STRANDTY@ *self = this->strand(ix);
205 :     return @STRAND@_update (@UPDATE_ARGS@
206 :     &self->_local,
207 :     &self->_shared[this->_inIdx],
208 :     &self->_shared[this->_inIdx^1]);
209 : jhr 4501 }
210 :    
211 :     // invoke strand's stabilize method
212 : jhr 4580 index_t strand_stabilize (@STABILIZE_PARAMS@index_t ix)
213 : jhr 4501 {
214 : jhr 4582 @STRANDTY@ *self = this->strand(ix);
215 :     @STRAND@_shared *selfIn = &self->_shared[this->_inIdx];
216 :     @STRAND@_shared *selfOut = &self->_shared[this->_inIdx^1];
217 : jhr 4501 #ifdef DIDEROT_HAS_STABILIZE_METHOD
218 : jhr 4582 // note that we swap out and in here because out holds the current state
219 :     @STRAND@_stabilize (@STABILIZE_ARGS@&self->_local, selfOut, selfIn);
220 :     std::memcpy (selfOut, selfIn, sizeof(@STRAND@_shared));
221 :     #else
222 :     std::memcpy (selfIn, selfOut, sizeof(@STRAND@_shared));
223 : jhr 4501 #endif // DIDEROT_HAS_STABILIZE_METHOD
224 : jhr 4510 // we swap the strand-indices at ix and _nStable + this->_nStabilizing
225 :     uint32_t jx = this->_nStable + this->_nStabilizing;
226 : jhr 4582 this->_status[jx] = diderot::kStabilize;
227 : jhr 4510 std::swap (this->_idx[ix], this->_idx[jx]);
228 :     this->_nStabilizing++;
229 : jhr 4582 return ix+1;
230 : jhr 4501 }
231 :    
232 : jhr 4580 // record that the specified strand is dying
233 :     index_t kill (index_t ix)
234 : jhr 4460 {
235 : jhr 4510 assert (this->_nStable <= ix);
236 :     assert (ix < this->num_alive());
237 :     this->_nDying++;
238 :     uint32_t jx = this->num_alive() - this->_nDying;
239 : jhr 4582 this->_status[jx] = diderot::kDie;
240 : jhr 4510 std::swap (this->_idx[ix], this->_idx[jx]);
241 : jhr 4582 return ix; // don't advance, since ix is an active strand after the swap
242 : jhr 4460 }
243 :    
244 : jhr 4512 // allocate a new strand
245 :     index_t new_strand ()
246 :     {
247 :     index_t ix = this->num_alive() + this->_nNew;
248 :     if (this->_nItems <= ix) {
249 :     if (this->grow ()) {
250 :     std::cerr << "Fatal error: unable to allocate space for new strands" << std::endl;
251 :     exit (1);
252 :     }
253 :     }
254 :     this->_status[ix] = diderot::kNew;
255 : jhr 4591 new (this->strand(ix)) @STRANDTY@;
256 : jhr 4512 this->_nNew++;
257 :     return ix;
258 :     }
259 :    
260 : jhr 4510 // finish a step by updating the strand statuses and the various counters
261 : jhr 5050 bool finish_step ()
262 : jhr 4510 {
263 : jhr 5050 bool anyNewDie = ((this->_nDying + this->_nNew) > 0);
264 : jhr 4510 index_t next = this->_nStable;
265 :     for (index_t ix = 0; ix < this->_nStabilizing; ix++, next++) {
266 :     this->_status[next] = diderot::kStable;
267 :     }
268 :     if (this->_nDying == 0) {
269 :     // no need to swap strands
270 :     index_t next = this->num_alive();
271 :     for (auto ix = 0; ix < this->_nNew; ix++, next++) {
272 :     this->_status[next] = diderot::kActive;
273 :     }
274 :     }
275 :     else {
276 : jhr 4582 // first handle the dying strands
277 : jhr 4510 next = this->num_alive() - this->_nDying;
278 :     for (index_t ix = 0; ix < this->_nDying; ix++, next++) {
279 :     this->_status[next] = diderot::kDead;
280 :     // invoke the dead strand's destructors
281 :     reinterpret_cast<@STRANDTY@ *>(this->strand(next))->~@STRANDTY@();
282 :     }
283 :     // move the new strands down over the dying strands
284 : jhr 4580 index_t src = this->num_alive();
285 :     index_t dst = src - this->_nDying;
286 : jhr 4510 for (auto ix = 0; ix < this->_nNew; ix++, dst++, src++) {
287 :     this->_status[dst] = diderot::kActive;
288 :     this->_status[src] = diderot::kDead;
289 :     std::swap (this->_idx[src], this->_idx[dst]);
290 :     }
291 :     }
292 :    
293 :     // update counts
294 : jhr 5015 this->_nFresh = this->_nNew;
295 : jhr 4510 this->_nStable += this->_nStabilizing;
296 :     this->_nActive -= this->_nStabilizing + this->_nDying;
297 :     this->_nActive += this->_nNew;
298 :     this->_nStabilizing = 0;
299 :     this->_nNew = 0;
300 :     this->_nDying = 0;
301 : jhr 5050
302 :     return anyNewDie;
303 : jhr 4510 }
304 :    
305 : jhr 4753 // finish a kill_all operation
306 :     void finish_kill_all ()
307 :     {
308 :     this->_nActive -= this->_nDying;
309 :     this->_nDying = 0;
310 :     }
311 :    
312 :     // finish a stabilize_all operation
313 :     void finish_stabilize_all ()
314 :     {
315 :     this->_nStable += this->_nStabilizing;
316 :     this->_nActive -= this->_nStabilizing;
317 :     this->_nStabilizing = 0;
318 :     }
319 :    
320 : jhr 4510 // iterator over stable strands
321 :     index_t begin_stable () const { return 0; }
322 :     index_t end_stable () const { return this->_nStable; }
323 : jhr 4518 index_t next_stable (index_t &ix) const { return ++ix; }
324 : jhr 4510
325 : jhr 4580 // iterator over active strands
326 :     index_t begin_active () const { return this->_nStable+this->_nStabilizing; }
327 :     index_t end_active () const { return this->_nStable+this->_nActive-this->_nDying; }
328 : jhr 4518 index_t next_active (index_t &ix) const { return ++ix; }
329 : jhr 4510
330 :     // iterator over alive (active+stable) strands; we assume that _nStabilizing and _nNew are 0
331 :     index_t begin_alive () const { return 0; }
332 :     index_t end_alive () const { return this->num_alive(); }
333 : jhr 4518 index_t next_alive (index_t &ix) const { return ++ix; }
334 : jhr 4510
335 : jhr 4753 // iterator over fresh strands
336 :     index_t begin_fresh () const { return this->num_alive() - this->_nFresh; }
337 :     index_t end_fresh () const { return this->num_alive(); }
338 :     index_t next_fresh (index_t &ix) const { return ++ix; }
339 :    
340 : jhr 4547 // allocate more space for strand state; return true on error
341 : jhr 4460 bool grow ()
342 :     {
343 : jhr 4510 size_t nItems = static_cast<size_t>(this->_nItems) + BLKSZ;
344 :     if (nItems >= UINT32_MAX) {
345 :     // cannot have more than UINT32_MAX elements
346 :     return true;
347 :     }
348 : jhr 4460
349 :     // allocate a new block at the end of the _blocks array
350 : jhr 4510 char *blk = static_cast<char *>(std::malloc (BLKSZ * sizeof(@STRANDTY@)));
351 :     if (blk == nullptr) {
352 :     return true;
353 :     }
354 :     this->_blocks.push_back (blk);
355 : jhr 4460
356 :     // grow the _status and _idx arrays
357 : jhr 4510 uint8_t *status = static_cast<uint8_t *>(std::malloc (nItems * sizeof(uint8_t)));
358 :     uint32_t *idx = static_cast<uint32_t *>(std::malloc (nItems * sizeof(uint32_t)));
359 :     if ((status == nullptr) || (idx == nullptr)) {
360 :     return true;
361 :     }
362 :     std::memcpy (status, this->_status, this->_nItems * sizeof(uint8_t));
363 :     std::memcpy (idx, this->_idx, this->_nItems * sizeof(uint32_t));
364 : jhr 4460
365 :     // initialize the new storage
366 : jhr 4510 @STRANDTY@ *p = reinterpret_cast<@STRANDTY@ *>(blk);
367 :     for (uint32_t ix = this->_nItems; ix < nItems; ix++) {
368 :     status[ix] = diderot::kDead;
369 :     idx[ix] = ix;
370 :     }
371 : jhr 4460
372 :     // free the old storage
373 : jhr 4510 std::free (this->_status);
374 :     std::free (this->_idx);
375 : jhr 4460
376 :     // update pointers
377 : jhr 4510 this->_status = status;
378 :     this->_idx = idx;
379 :     this->_nItems = nItems;
380 : jhr 4460
381 : jhr 4580 return false;
382 : jhr 4460 }
383 :    
384 :     }; // struct strand_array
385 : jhr 4551
386 :     strand_array::~strand_array ()
387 :     {
388 :     // run destructors to reclaim any dynamic memory attached to the strand state
389 :     for (auto ix = this->begin_alive(); ix != this->end_alive(); ix = this->next_alive(ix)) {
390 : jhr 4582 this->strand(ix)->~@STRANDTY@();
391 : jhr 4551 }
392 :     this->dealloc();
393 :     }
394 :    
395 :     void strand_array::dealloc ()
396 :     {
397 :     if (this->_status != nullptr) {
398 : jhr 4582 std::free (this->_status);
399 :     this->_status = nullptr;
400 : jhr 4551 }
401 :     if (this->_idx != nullptr) {
402 : jhr 4582 std::free (this->_idx);
403 :     this->_idx = nullptr;
404 : jhr 4551 }
405 :     for (uint32_t i = 0; i < this->_blocks.size(); i++) {
406 : jhr 4582 if (this->_blocks[i] != nullptr) {
407 :     std::free (this->_blocks[i]);
408 :     this->_blocks[i] = nullptr;
409 :     }
410 :     else {
411 :     break;
412 :     }
413 : jhr 4551 }
414 :     }

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0