root / src / sim / cheuristic.cc @ 92cc8482
History  View  Annotate  Download (9.54 KB)
1 
//=========================================================================


2 
// CHEURISTIC.CC  part of

3 
//

4 
// OMNeT++/OMNEST

5 
// Discrete System Simulation in C++

6 
//

7 
//

8 
// Member functions of

9 
// cSpinningThreadPool : heuristic for probablistic synchronization

10 
//

11 
// Author: Mirko Stoffers

12 
//

13 
//=========================================================================

14  
15 
/**

16 
Copyright (C) 2013 Mirko Stoffers

17 

18 
This file is distributed WITHOUT ANY WARRANTY. See the file

19 
`license' for details on this and other legal matters.

20 
**/

21 
#include <string.h> 
22  
23 
#include "cmessage.h" 
24 
#include "cheuristic.h" 
25  
26 
// TODO:

27  
28 
// eventSet_t

29 
// eventSet_t::begin()

30 
// eventSet_t::end()

31 
// eventSet_t::iterator

32 
// eventSet_t::iterator::++operator

33 
// eventSet_t::iterator::operator!=(eventSet_t::iterator)

34 
// eventSet_t::iterator::operator=

35 
// abstractEvent_t eventSet_t::iterator::operator>

36  
37 
typedef std::list<evType_t> succList_t;

38 
typedef class Pdf pdf_t; 
39 
typedef class AbstractEvent abstractEvent_t; 
40 
typedef class EventType evType_t; 
41  
42 
class EventType 
43 
{ 
44 
private:

45 
succList_t succs; 
46  
47 
public:

48 
const succList_t& getSuccessors() const 
49 
{ 
50 
return succs;

51 
} 
52 
}; 
53  
54 
class AbstractEvent 
55 
{ 
56 
private:

57 
evType_t type; 
58 
int modId;

59 
pdf_t pdf; 
60 
public:

61 
evType_t getEvType() 
62 
{ 
63 
return type;

64 
} 
65  
66 
int getEvModId()

67 
{ 
68 
return modId;

69 
} 
70  
71 
pdf_t getProbabilityDistribution() 
72 
{ 
73 
return pdf;

74 
} 
75 
}; 
76  
77 
class Pdf 
78 
{ 
79 
private:

80 
struct Bucket

81 
{ 
82 
public:

83 
simtime_t rightBorder; 
84 
size_t bin; 
85  
86 
Bucket() {} 
87  
88 
Bucket(const Bucket& b)

89 
{ 
90 
set(b); 
91 
} 
92  
93 
bool operator<(const Bucket& b) 
94 
{ 
95 
return this>rightBorder<b.rightBorder; 
96 
} 
97  
98 
bool operator<=(const Bucket& b) 
99 
{ 
100 
return this>rightBorder<=b.rightBorder; 
101 
} 
102  
103 
bool operator>(const Bucket& b) 
104 
{ 
105 
return this>rightBorder>b.rightBorder; 
106 
} 
107  
108 
bool operator>=(const Bucket& b) 
109 
{ 
110 
return this>rightBorder>=b.rightBorder; 
111 
} 
112  
113 
void set(const Bucket& b) 
114 
{ 
115 
memcpy(this,&b,sizeof(*this)); 
116 
} 
117 
} bucket_t; 
118  
119 
static const size_t size=9; // MUST BE (2^n)+1 for some integer n (like 3,5,9,17,...) 
120 
size_t[size] bins; 
121 
simtime_t[size] leftBorders; 
122 
simtime_t* rightBorders; 
123 
size_t count; 
124 
bool isDet;

125 
simtime_t detVal; 
126  
127 
Pdf& convolveInPlaceDetDet(const Pdf& b)

128 
{ 
129 
this>detVal+=b.detVal;

130 
return *this; 
131 
} 
132  
133 
Pdf& convolveInPlaceDetBin(const Pdf& b)

134 
{ 
135 
memcpy(this>bins,b.bins,sizeof(bins)); 
136 
memcpy(this>leftBorders,b.leftBorders,sizeof(leftBorders)); 
137 
rightBorders=&(leftBorders[1]);

138 
this>count=b.count;

139 
this>isDet=false; 
140 
for(size_t i=1;i<size;i++) 
141 
leftBorders[i]+=this>detVal;

142 
return *this; 
143 
} 
144  
145 
Pdf& convolveInPlaceBinDet(const Pdf& b)

146 
{ 
147 
for(size_t i=1;i<size;i++) 
148 
leftBorders[i]+=b.detVal; 
149 
return *this; 
150 
} 
151  
152 
Pdf& convolveInPlaceBinBin(const Pdf& b)

153 
{ 
154 
const size_t s1=size1; 
155 
size_t from=1;

156 
size_t to=0;

157 
bucket_t matrix[s1*s1][s1][2];

158 
bucket_t b1,b2; 
159 
size_t total=0;

160  
161 
for(size_t i=0;i<s1;i++) 
162 
{ 
163 
for(size_t j=0;j<s1;j++) 
164 
{ 
165 
matrix[i][j][to].rightBorder=this>rightBorders[i]+b.rightBorders[j];

166 
matrix[i][j][to].bin=this>bins[i]+b.bins[j];

167 
total+=matrix[i][j][to].bin; 
168 
} 
169 
} 
170  
171 
for(size_t m=1;m<s1;m*=2) 
172 
{ 
173 
from=1from;

174 
to=1to;

175 
for(size_t i=0;i<s1/m;i+=2) 
176 
{ 
177 
size_t k=0;

178 
size_t l=0;

179 
for(size_t j=0;j<m*2*s1;j++) 
180 
{ 
181 
if(k<m*s1) b1.set(matrix[i][k][from]);

182 
else b1.rightBorder=MAXTIME;

183 
if(l<m*s1) b2.set(matrix[i+1][l][from]); 
184 
else b2.rightBorder=MAXTIME;

185 
if(b1<=b2)

186 
{ 
187 
matrix[i/2][j][to].set(b1);

188 
k++; 
189 
} 
190 
else

191 
{ 
192 
matrix[i/2][j][to].set(b2);

193 
l++; 
194 
} 
195 
} 
196 
} 
197 
} 
198 
assert(m==s1); 
199  
200 
// now we have the sorted borders in borderMatrix[0][x][to]

201  
202 
for(size_t i=0;i<s1;i++) 
203 
{ 
204 
this>bins[i]=0; 
205 
for(size_t j=0;j<s1;j++) 
206 
{ 
207 
this>bins[i]+=matrix[0][j+i*s1][to].bin; 
208 
} 
209 
this>rightBorder[i]=matrix[0][s11+i*s1][to].rightBorder; 
210 
} 
211 
this>bins[s1]*=b.bins[s1];

212 
this>count*=b.count;

213 
} 
214  
215 
public:

216 
Pdf(simtime_t delay) 
217 
{ 
218 
isDet=true;

219 
detVal=delay; 
220 
} 
221  
222 
Pdf& operator+=(const Pdf& b) 
223 
{ 
224 
if( this>isDet && b.isDet) 
225 
return convolveInPlaceDetDet(b);

226 
if( this>isDet && !b.isDet) 
227 
return convolveInPlaceDetBin(b);

228 
if(!this>isDet && b.isDet) 
229 
return convolveInPlaceBinDet(b);

230 
if(!this>isDet && !b.isDet) 
231 
return convolveInPlaceBinBin(b);

232 
assert(false);

233 
return *this; 
234 
} 
235  
236 
double getProbability(simtime_t val)

237 
{ 
238 
if(isDet && detVal< val) return 1; 
239 
if(isDet && detVal>=val) return 0; 
240  
241 
size_t sum=0;

242 
for(size_t i=0;i<size;i++) 
243 
{ 
244 
if(leftBorders[i]<val) sum+=bins[i];

245 
else return sum; 
246 
} 
247 
} 
248  
249 
/* Pdf operator+(const Pdf& a,const Pdf& b) const

250 
{

251 
if( a.isDet && b.isDet)

252 
return convolveDetDet(a,b);

253 
if( a.isDet && !b.isDet)

254 
return convolveDetBin(a,b);

255 
if(!a.isDet && b.isDet)

256 
return convolveDetBin(b,a);

257 
if(!a.isDet && !b.isDet)

258 
return convolveBinBin(a,b);

259 
assert(false);

260 
return Pdf(1337);

261 
}*/

262 
}; 
263  
264 
class cNode 
265 
{ 
266 
private:

267 
pdf_t pdf; 
268 
evType_t type; 
269 
int modId;

270  
271 
public:

272 
cNode(evType_t evType,int moduleId,pdf_t probabilityDistribution)

273 
{ 
274 
pdf=probabilityDistribution; 
275 
type=evType; 
276 
modId=moduleId; 
277 
} 
278  
279 
double getProbability()

280 
{ 
281 
return pdf.getProbability(0); 
282 
} 
283  
284 
succList_t getSuccessors() 
285 
{ 
286 
return type>getSuccessors();

287 
} 
288  
289 
const pdf_t& getProbabilityDistribution()

290 
{ 
291 
return pdf;

292 
} 
293  
294 
pdf_t getProbabilityDistributionCopy() 
295 
{ 
296 
return pdf;

297 
} 
298 
}; 
299  
300 
/**

301 
* A tree to perform a BFS and predict the probability

302 
* for a causal violation to occur.

303 
*/

304 
class cTree 
305 
{ 
306 
private:

307 
// Lower and upper bounds for the causal violation probability:

308 
double lowerBound;

309 
double upperBound;

310 
std::list<cNode> leaves; 
311  
312 
public:

313 
/**

314 
* Constructor for tree

315 
* The probability for a causal violation resides (obviously) in the interval [0;1].

316 
*/

317 
cTree() 
318 
{ 
319 
lowerBound=0;

320 
upperBound=1;

321 
} 
322  
323 
/**

324 
* Adding a node into the tree.

325 
* @param parent The parent node in the tree. If parent==NULL, the new node will

326 
* be inserted as one of the roots of the tree (forest)

327 
* @param eventType The OMNeT++ message kind

328 
* @param moduleId The module the event takes place at

329 
* @param probabilityDistribution The PDF to be stored inside the node

330 
* @param isConflicting Whether this node is a conflicting node, i.e. an event on this

331 
* node would conflict with the pending event since the pending event

332 
* takes place at the same module.

333 
*/

334 
void addNode(cNode* parent, evType_t evType, int moduleId, pdf_t probabilityDistribution, bool isConflicting) 
335 
{ 
336 
cNode newNode(evType,moduleId,probabilityDistribution); 
337 
double dangerProb=newNode>getProbability()

338 
upperBound=1(1upperBound)*(1dangerProb); 
339 
if(isConflicting) lowerBound=1(1lowerBound)*(1dangerProb); 
340 
if(parent && leaves.contains(parent))

341 
{ 
342 
upperBound=1(1upperBound)/(1parent>getProbability()); 
343 
leaves.remove(parent); 
344 
} 
345 
leaves.push_back(newNode); 
346 
} 
347  
348 
// Performing BFS and spanning the tree:

349 
bool bfs(double threshold, int moduleId) 
350 
{ 
351 
for(nodeSet_t::iterator leaf=leaves.begin();leaf!=leaves.end();++leaf)

352 
{ 
353 
if(leaf>isConflicting())

354 
{ 
355 
continue;

356 
} 
357 
succList_t succs=leaf>getSuccessors(); 
358 
for(succList_t::iterator succ=succs.begin();succ!=succs.end();++succ)

359 
{ 
360 
// We need to convolve the PDF of the (previous) leaf node with the PDF of its successors:

361 
//pdf_t convolvedPdf=leaf>getProbabilityDistribution()+succ>getProbabilityDistribution();

362 
pdf_t convolvedPdf=succ>getProbabilityDistributionCopy(); 
363 
convolvedPdf+=leaf>getProbabilityDistribution(); 
364 
evType_t succEvType=succ>getEvType(); 
365 
int succModId=succ>getEvModId();

366 
bool isConflicting=moduleId==succModId;

367 
// We add the new node as a child of the leaf into the tree:

368 
addNode(leaf,succEvType,convolvedPdf,isConflicting); 
369 
// If both bounds for the probability are below (above) the threshold,

370 
// the probability itself is also below (above) the threshold,

371 
// i.e. we can yield the decision without further inspecting the BFS tree.

372 
if(lowerBound<=threshold && upperBound<=threshold) return true; 
373 
if(lowerBound>=threshold && upperBound>=threshold) return false; 
374 
} 
375 
} 
376 
} 
377 
}; 
378  
379 
/**

380 
* This function will be executed whenever the event scheduler encounters

381 
* an event that cannot be executed conservatively at that moment. In this

382 
* case the heuristic computes a probability for a causal violation to occur /

383 
* to not occur, and returns a recommendation whether to execute the event

384 
* speculatively (return value=true) or not (return value=false).

385 
* @param pendingEv The pending event (message in OMNeT++).

386 
* @param setO The set $O$ of currently executed events.

387 
* @param threshold The threshold to compare against.

388 
* @return true iff recommendation for speculative execution is positive.

389 
*/

390 
bool cHeuristic::askHeuristic(cMessage* pendingEv,eventSet_t setO,double threshold) 
391 
{ 
392 
cTree bfsTree; 
393 
int pendingEvModId=pendingEv>getArrivalModuleId();

394  
395 
for (eventSet_t::iterator it=setO>begin();it!=setO>end();++it)

396 
{ 
397 
evType_t runningEvType=it>getEvType(); 
398 
int runningEvModId=it>getEvModId();

399 
bool isConflicting=pendingEvModId==runningEvModId;

400 
pdf_t pdf(eventInO>arrivalTime()pendingEvent>arrivalTime()); 
401 
bfsTree.addNode(NULL,runningEvType,pdf,isConflicting);

402 
} 
403  
404 
return bfsTree.bfs(threshold,pendingEvModId);

405 
} 
406 