root / src / sim / cheuristic.cc @ 35f4da42
History  View  Annotate  Download (6.02 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  
25 
#include "cspinningthreadpool.h" 
26  
27 
#include "cheuristic.h" 
28 
#include "eventset.h" 
29  
30 
#define MAX_IT 1000000 
31  
32 
EventSet::iterator::iterator(const EventSet::iterator& b) :

33 
index(index), 
34 
s(s) 
35 
{ 
36 
} 
37  
38 
class cNode 
39 
{ 
40 
private:

41 
pdf_t pdf; 
42 
evType_t* type; 
43 
bool isConf;

44  
45 
public:

46 
cNode(evType_t* const evType,bool isConflicting,pdf_t probabilityDistribution) : 
47 
pdf(probabilityDistribution), 
48 
isConf(isConflicting) 
49 
{ 
50 
type=evType; 
51 
} 
52  
53 
double getProbability()

54 
{ 
55 
return pdf.getProbability(0); 
56 
} 
57  
58 
succList_t getSuccessors() 
59 
{ 
60 
return type>getSuccessors();

61 
} 
62  
63 
void releaseSuccListLock()

64 
{ 
65 
type>releaseSuccListLock(); 
66 
} 
67  
68 
const pdf_t& getProbabilityDistribution()

69 
{ 
70 
return pdf;

71 
} 
72  
73 
bool isConflicting()

74 
{ 
75 
return isConf;

76 
} 
77 
}; 
78  
79 
/**

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

81 
* for a causal violation to occur.

82 
*/

83 
class cTree 
84 
{ 
85 
private:

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

87 
double lowerBound;

88 
double upperBound;

89 
typedef std::list<cNode*> nodeSet_t;

90 
nodeSet_t bfsVisitList; 
91  
92 
public:

93 
/**

94 
* Constructor for tree

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

96 
*/

97 
cTree() 
98 
{ 
99 
lowerBound=0;

100 
upperBound=1;

101 
} 
102  
103 
bool leafSetContainsParent(cNode* parent) const 
104 
{ 
105 
bool res=*bfsVisitList.begin()==parent;

106 
#ifdef DEBUG

107 
std::cout << "Is parent really always at beginning of list?" << std::endl;

108 
bool checkedRes=false; 
109 
for(nodeSet_t::iterator it=bfsVisitList.begin();it!=bfsVisitList.end();it++)

110 
{ 
111 
if(*it==parent) checkedRes=true; 
112 
} 
113 
assert(res==checkedRes); 
114 
#endif

115 
return res;

116 
} 
117  
118 
/**

119 
* Adding a node into the tree.

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

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

122 
* @param eventType The OMNeT++ message kind

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

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

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

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

127 
* takes place at the same module.

128 
*/

129 
void addNode(cNode* parent, evType_t* const evType,pdf_t probabilityDistribution, bool isConflicting) 
130 
{ 
131 
cNode* newNode=new cNode(evType,isConflicting,probabilityDistribution);

132 
const double dangerProb=newNode>getProbability(); 
133 
upperBound=1(1upperBound)*(1dangerProb); 
134 
if(isConflicting) lowerBound=1(1lowerBound)*(1dangerProb); 
135 
bfsVisitList.push_back(newNode); 
136 
} 
137  
138 
// Performing BFS and spanning the tree:

139 
bool bfs(double threshold, int moduleId) 
140 
{ 
141 
nodeSet_t::iterator it; 
142 
for(int i=0; i<MAX_IT && (it=bfsVisitList.begin()) != bfsVisitList.end(); i++) 
143 
{ 
144 
cNode* node=*it; 
145 
bfsVisitList.erase(it); 
146 
if(node>isConflicting())

147 
{ 
148 
continue;

149 
} 
150 
else

151 
{ 
152 
upperBound=1(1upperBound)/(1node>getProbability()); 
153 
} 
154 
succList_t succs=node>getSuccessors(); 
155 
for(succList_t::iterator succ=succs.begin();succ!=succs.end();++succ)

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

158 
//pdf_t convolvedPdf=node>getProbabilityDistribution()+succ>getProbabilityDistribution();

159 
pdf_t convolvedPdf=succ>getProbabilityDistributionCopy(); 
160 
convolvedPdf+=node>getProbabilityDistribution(); 
161 
evType_t* succEvType=succ>getEvType(); 
162 
int succModId=succ>getEvType()>getModId();

163 
bool isConflicting=moduleId==succModId;

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

165 
addNode(node,succEvType,convolvedPdf,isConflicting); 
166 
// If both bounds for the probability are below (above) the threshold,

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

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

169 
if(lowerBound<=threshold && upperBound<=threshold) return true; 
170 
if(lowerBound>=threshold && upperBound>=threshold) return false; 
171 
} 
172 
node>releaseSuccListLock(); 
173 
} 
174 
if(lowerBound<=threshold && upperBound<=threshold) return true; 
175 
return false; // be pessimistic 
176 
} 
177 
}; 
178  
179 
/**

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

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

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

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

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

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

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

187 
* @param threshold The threshold to compare against.

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

189 
*/

190 
bool cHeuristic::askHeuristic(const cMessage* const pendingEv,eventSet_t setO,double threshold) 
191 
{ 
192 
cTree bfsTree; 
193 
int pendingEvModId=pendingEv>getArrivalModuleId();

194  
195 
for (eventSet_t::iterator it=setO.begin();it!=setO.end();++it)

196 
{ 
197 
evType_t* runningEvType=it>getEvType(); 
198 
int runningEvModId=it>getEvModId();

199 
bool isConflicting=pendingEvModId==runningEvModId;

200 
pdf_t pdf(it>getArrivalTime()pendingEv>getArrivalTime()); 
201 
bfsTree.addNode(NULL,runningEvType,pdf,isConflicting);

202 
} 
203  
204 
return bfsTree.bfs(threshold,pendingEvModId);

205 
} 
206 