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-indirect.in
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 4516 - (view) (download)

1 : jhr 4501 // forward declarations of strand methoda
2 :     #ifdef DIDEROT_HAS_START_METHOD
3 :     static diderot::strand_status @STRAND@_start (@START_PARAMS@@STRANDTY@ *self);
4 :     #endif // DIDEROT_HAS_START_METHOD
5 :     static diderot::strand_status @STRAND@_update (@UPDATE_PARAMS@@STRANDTY@ *self);
6 :     #ifdef DIDEROT_HAS_STABILIZE_METHOD
7 :     static void @STRAND@_stabilize (@STABILIZE_PARAMS@@STRANDTY@ *self);
8 :     #endif // DIDEROT_HAS_STABILIZE_METHOD
9 :    
10 : jhr 4460 // strand_array for BSP/SINGLE STATE/INDIRECT ACCESS
11 :     //
12 :     struct strand_array {
13 : jhr 4516 typedef @STRANDTY@ strand_t;
14 : jhr 4460 typedef uint32_t index_t;
15 : jhr 4510 typedef char *block_t; // points to array of @STRANDTY@ structs
16 : jhr 4507
17 : jhr 4510 uint8_t *_status; // the array of status information for the strands
18 :     uint32_t *_idx; // array of strand indices for indirect state rep.
19 :     std::vector<block_t> _blocks; // vector of pointers to strand-storage blocks
20 :     uint32_t _nItems; // number of items in the _blocks and _status arrays
21 :     uint32_t _nStable; // stable strands (0.._nStable-1)
22 :     uint32_t _nActive; // active strands (_nStable.._nStable+_nActive)
23 :     uint32_t _nStabilizing; // number of stablizing strands
24 :     uint32_t _nDying; // number of dying strands
25 :     uint32_t _nNew; // number of new strands
26 : jhr 4460
27 : jhr 4510 static const uint32_t LOG_BLKSZ = 12; // 2^12 items per block
28 : jhr 4460 static const uint32_t BLKSZ = (1 << LOG_BLKSZ);
29 : jhr 4510 static const uint32_t BLKMASK = (BLKSZ-1); // mask for block index
30 : jhr 4460
31 :     strand_array () : _status(nullptr), _idx(nullptr), _nItems(0) { }
32 : jhr 4505 ~strand_array ()
33 :     {
34 : jhr 4510 this->dealloc();
35 : jhr 4505 }
36 : jhr 4460
37 : jhr 4516 uint32_t in_state_index () const { return 0; /* dummy */ }
38 :    
39 : jhr 4505 uint32_t num_active () const { return this->_nActive; }
40 :     uint32_t num_stable () const { return this->_nStable; }
41 :     uint32_t num_alive () const { return this->_nActive+this->_nStable; }
42 :    
43 :     // return a strand's status
44 :     diderot::strand_status status (index_t ix) const
45 :     {
46 : jhr 4512 assert (ix < this->_nItems);
47 : jhr 4510 return static_cast<diderot::strand_status>(this->_status[ix]);
48 : jhr 4505 }
49 : jhr 4460 // return a pointer to the given strand
50 :     @STRANDTY@ *strand (index_t ix) const
51 :     {
52 : jhr 4512 assert (ix < this->_nItems);
53 : jhr 4510 uint32_t jx = this->_idx[ix];
54 : jhr 4512 assert (jx < this->_nItems);
55 : jhr 4510 uint32_t blkId = jx >> LOG_BLKSZ;
56 : jhr 4512 uint32_t offset = jx & BLKMASK;
57 : jhr 4510 return reinterpret_cast<@STRANDTY@ *>(this->_blocks[blkId] + offset * sizeof(S_strand));
58 : jhr 4460 }
59 :     // return a pointer to the local state of strand ix
60 :     @STRANDTY@ *local_state (index_t ix) const
61 :     {
62 : jhr 4510 return this->strand(ix);
63 : jhr 4460 }
64 :    
65 :     // deallocate space reserved for strands
66 :     void dealloc ()
67 :     {
68 : jhr 4510 if (this->_status != nullptr) {
69 :     std::free (this->_status);
70 :     this->_status = nullptr;
71 :     }
72 :     if (this->_idx != nullptr) {
73 :     std::free (this->_idx);
74 :     this->_idx = nullptr;
75 :     }
76 :     for (uint32_t i = 0; i < this->_blocks.size(); i++) {
77 :     if (this->_blocks[i] != nullptr) {
78 :     std::free (this->_blocks[i]);
79 :     this->_blocks[i] = nullptr;
80 :     }
81 :     else {
82 :     break;
83 :     }
84 :     }
85 : jhr 4460 }
86 :    
87 :     // allocate space for at least nItems
88 :     bool alloc (uint32_t nItems)
89 :     {
90 : jhr 4510 nItems = (nItems + BLKSZ - 1) & ~BLKMASK;
91 :     uint32_t nBlks = nItems >> LOG_BLKSZ;
92 : jhr 4512 assert (nItems == nBlks*BLKSZ);
93 : jhr 4460 // allocate block vector
94 : jhr 4510 this->_blocks.resize(nBlks, nullptr);
95 : jhr 4460 // allocate blocks
96 : jhr 4510 for (int i = 0; i < nBlks; i++) {
97 :     this->_blocks[i] = static_cast<char *>(std::malloc (BLKSZ * sizeof(@STRANDTY@)));
98 :     if (this->_blocks[i] == nullptr) {
99 :     // unable to allocate memory
100 :     this->dealloc();
101 :     return true;
102 :     }
103 :     }
104 : jhr 4460 // allocate _status array
105 : jhr 4510 this->_status = static_cast<uint8_t *>(std::malloc (nItems * sizeof(uint8_t)));
106 :     if (this->_status == nullptr) {
107 :     this->dealloc();
108 :     return true;
109 :     }
110 : jhr 4460 // allocate _idx array
111 : jhr 4510 this->_idx = static_cast<uint32_t *>(std::malloc (nItems * sizeof(uint32_t)));
112 :     if (this->_idx == nullptr) {
113 :     this->dealloc();
114 :     return true;
115 :     }
116 : jhr 4512 // initialize arrays
117 :     for (index_t ix = 0; ix < nItems; ix++) {
118 :     this->_status[ix] = diderot::kDead;
119 :     this->_idx[ix] = ix;
120 :     }
121 : jhr 4510 this->_nItems = nItems;
122 :     this->_nActive = 0;
123 :     this->_nStable = 0;
124 :     this->_nStabilizing = 0;
125 :     this->_nNew = 0;
126 :     this->_nDying = 0;
127 :     return false;
128 : jhr 4460 }
129 :    
130 :     // initialize the first nStrands locations as new active strands
131 :     void create_strands (uint32_t nStrands)
132 :     {
133 : jhr 4510 assert (this->_nActive == 0);
134 :     assert (this->_nItems >= nStrands);
135 : jhr 4460
136 : jhr 4512 for (index_t ix = 0; ix < nStrands; ix++) {
137 :     new (this->strand(ix)) @STRANDTY@;
138 :     }
139 : jhr 4460
140 : jhr 4510 this->_nActive = nStrands;
141 : jhr 4460 }
142 :    
143 : jhr 4489 // swap in and out states (NOP for this version)
144 :     void swap () { }
145 :    
146 : jhr 4501 #ifdef DIDEROT_HAS_START_METHOD
147 :     // invoke strand's start method
148 :     diderot::strand_status strand_start (@START_PARAMS@index_t ix)
149 :     {
150 : jhr 4510 return @STRAND@_start(@START_ARGS@this->strand(ix));
151 : jhr 4501 }
152 :     #endif // DIDEROT_HAS_START_METHOD
153 :    
154 :     // invoke strand's update method
155 :     diderot::strand_status strand_update (@UPDATE_PARAMS@index_t ix)
156 :     {
157 : jhr 4510 return @STRAND@_update(@UPDATE_ARGS@this->strand(ix));
158 : jhr 4501 }
159 :    
160 :     // invoke strand's stabilize method
161 :     void strand_stabilize (@STABILIZE_PARAMS@index_t ix)
162 :     {
163 :     #ifdef DIDEROT_HAS_STABILIZE_METHOD
164 :     @STRAND@_stabilize (@STABILIZE_ARGS@this->strand(ix));
165 :     #endif // DIDEROT_HAS_STABILIZE_METHOD
166 : jhr 4507 // we swap the strand-indices at ix and _nStable + this->_nStabilizing
167 : jhr 4510 uint32_t jx = this->_nStable + this->_nStabilizing;
168 :     std::swap (this->_idx[ix], this->_idx[jx]);
169 :     this->_nStabilizing++;
170 : jhr 4501 }
171 :    
172 : jhr 4507 // record that the specified strand is dying
173 : jhr 4460 void kill (index_t ix)
174 :     {
175 : jhr 4510 assert (this->_nStable <= ix);
176 :     assert (ix < this->num_alive());
177 :     this->_nDying++;
178 :     uint32_t jx = this->num_alive() - this->_nDying;
179 :     std::swap (this->_idx[ix], this->_idx[jx]);
180 : jhr 4460 }
181 :    
182 : jhr 4512 // allocate a new strand
183 :     index_t new_strand ()
184 :     {
185 :     index_t ix = this->num_alive() + this->_nNew;
186 :     if (this->_nItems <= ix) {
187 :     if (this->grow ()) {
188 :     std::cerr << "Fatal error: unable to allocate space for new strands" << std::endl;
189 :     exit (1);
190 :     }
191 :     }
192 :     this->_status[ix] = diderot::kNew;
193 :     new (this->strand(ix)) @STRANDTY@;
194 :     this->_nNew++;
195 :     return ix;
196 :     }
197 :    
198 : jhr 4507 // finish a step by updating the strand statuses and the various counters
199 :     void finish_step ()
200 :     {
201 :     /*
202 :     std::cout << "finish_step: "
203 :     << this->_nStable << " stable, "
204 :     << this->_nActive << " active, "
205 :     << this->_nStabilizing << " stabilizing, "
206 :     << this->_nDying << " dying, "
207 :     << this->_nNew << " new\n";
208 :     */
209 : jhr 4510 index_t next = this->_nStable;
210 :     for (index_t ix = 0; ix < this->_nStabilizing; ix++, next++) {
211 :     this->_status[next] = diderot::kStable;
212 :     }
213 :     if (this->_nDying == 0) {
214 :     // no need to swap strands
215 :     index_t next = this->num_alive();
216 :     for (auto ix = 0; ix < this->_nNew; ix++, next++) {
217 :     this->_status[next] = diderot::kActive;
218 :     }
219 :     }
220 :     else {
221 :     // first handle the dying
222 :     next = this->num_alive() - this->_nDying;
223 :     for (index_t ix = 0; ix < this->_nDying; ix++, next++) {
224 :     this->_status[next] = diderot::kDead;
225 :     // invoke the dead strand's destructors
226 :     reinterpret_cast<@STRANDTY@ *>(this->strand(next))->~@STRANDTY@();
227 :     }
228 :     // move the new strands down over the dying strands
229 : jhr 4514 index_t src = this->num_alive();
230 :     index_t dst = src - this->_nDying;
231 : jhr 4510 for (auto ix = 0; ix < this->_nNew; ix++, dst++, src++) {
232 :     this->_status[dst] = diderot::kActive;
233 :     this->_status[src] = diderot::kDead;
234 :     std::swap (this->_idx[src], this->_idx[dst]);
235 :     }
236 :     }
237 : jhr 4507
238 :     // update counts
239 : jhr 4510 this->_nStable += this->_nStabilizing;
240 :     this->_nActive -= this->_nStabilizing + this->_nDying;
241 :     this->_nActive += this->_nNew;
242 :     this->_nStabilizing = 0;
243 :     this->_nNew = 0;
244 :     this->_nDying = 0;
245 : jhr 4507 }
246 :    
247 : jhr 4512 // iterator over stable strands
248 :     index_t begin_stable () const { return 0; }
249 :     index_t end_stable () const { return this->_nStable; }
250 :     index_t next_stable (index_t &ix) { return ++ix; }
251 : jhr 4460
252 : jhr 4512 // iterator over active strands; we assume that _nStabilizing is 0
253 :     index_t begin_active () const { return this->_nStable; }
254 :     index_t end_active () const { return this->_nStable+this->_nActive; }
255 :     index_t next_active (index_t &ix) { return ++ix; }
256 :    
257 :     // iterator over alive (active+stable) strands; we assume that _nStabilizing and _nNew are 0
258 :     index_t begin_alive () const { return 0; }
259 :     index_t end_alive () const { return this->num_alive(); }
260 :     index_t next_alive (index_t &ix) { return ++ix; }
261 :    
262 : jhr 4460 // allocate more space for strand state
263 :     bool grow ()
264 :     {
265 : jhr 4510 size_t nItems = static_cast<size_t>(this->_nItems) + BLKSZ;
266 :     if (nItems >= UINT32_MAX) {
267 :     // cannot have more than UINT32_MAX elements
268 :     return true;
269 :     }
270 : jhr 4460
271 :     // allocate a new block at the end of the _blocks array
272 : jhr 4510 char *blk = static_cast<char *>(std::malloc (BLKSZ * sizeof(@STRANDTY@)));
273 :     if (blk == nullptr) {
274 :     return true;
275 :     }
276 :     this->_blocks.push_back (blk);
277 : jhr 4460
278 :     // grow the _status and _idx arrays
279 : jhr 4510 uint8_t *status = static_cast<uint8_t *>(std::malloc (nItems * sizeof(uint8_t)));
280 :     uint32_t *idx = static_cast<uint32_t *>(std::malloc (nItems * sizeof(uint32_t)));
281 :     if ((status == nullptr) || (idx == nullptr)) {
282 :     return true;
283 :     }
284 :     std::memcpy (status, this->_status, this->_nItems * sizeof(uint8_t));
285 :     std::memcpy (idx, this->_idx, this->_nItems * sizeof(uint32_t));
286 : jhr 4460
287 :     // initialize the new storage
288 : jhr 4510 @STRANDTY@ *p = reinterpret_cast<@STRANDTY@ *>(blk);
289 :     for (uint32_t ix = this->_nItems; ix < nItems; ix++) {
290 :     status[ix] = diderot::kDead;
291 :     idx[ix] = ix;
292 :     }
293 : jhr 4460
294 :     // free the old storage
295 : jhr 4510 std::free (this->_status);
296 :     std::free (this->_idx);
297 : jhr 4460
298 :     // update pointers
299 : jhr 4510 this->_status = status;
300 :     this->_idx = idx;
301 :     this->_nItems = nItems;
302 : jhr 4460
303 : jhr 4505 return false;
304 : jhr 4460 }
305 :    
306 :     }; // struct strand_array

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