root / src / sim / cheuristic.cc @ a6f5ec85
History  View  Annotate  Download (6.04 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 
EventSet::iterator::iterator(const EventSet::iterator& b) :

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

39 
pdf_t pdf; 
40 
evType_t* type; 
41 
bool isConf;

42  
43 
public:

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

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

59 
} 
60  
61 
void releaseSuccListLock()

62 
{ 
63 
type>releaseSuccListLock(); 
64 
} 
65  
66 
const pdf_t& getProbabilityDistribution()

67 
{ 
68 
return pdf;

69 
} 
70  
71 
bool isConflicting()

72 
{ 
73 
return isConf;

74 
} 
75 
}; 
76  
77 
/**

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

79 
* for a causal violation to occur.

80 
*/

81 
class cTree 
82 
{ 
83 
private:

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

85 
double lowerBound;

86 
double upperBound;

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

88 
nodeSet_t bfsVisitList; 
89  
90 
public:

91 
/**

92 
* Constructor for tree

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

94 
*/

95 
cTree() 
96 
{ 
97 
lowerBound=0;

98 
upperBound=1;

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

104 
#ifdef DEBUG

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

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

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

113 
return res;

114 
} 
115  
116 
/**

117 
* Adding a node into the tree.

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

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

120 
* @param eventType The OMNeT++ message kind

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

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

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

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

125 
* takes place at the same module.

126 
*/

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

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

137 
bool bfs(double threshold, int moduleId) 
138 
{ 
139 
nodeSet_t::iterator it; 
140 
while((it=bfsVisitList.begin()) != bfsVisitList.end())

141 
{ 
142 
std::cout << "bfsVisitList.size()=" << bfsVisitList.size() << std::endl;

143 
cNode* node=*it; 
144 
bfsVisitList.erase(it); 
145 
if(node>isConflicting())

146 
{ 
147 
continue;

148 
} 
149 
else

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

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

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

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

162 
bool isConflicting=moduleId==succModId;

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

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

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

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

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

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

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

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

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

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

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

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

186 
* @param threshold The threshold to compare against.

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

188 
*/

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

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

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

198 
bool isConflicting=pendingEvModId==runningEvModId;

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

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

204 
} 
205 