Project

General

Profile

Revision f8c033b6

IDf8c033b687c88b817e6cd70f6b32c7fcb44a7add
Parent c9eb5668
Child 423dece2

Added by Mirko Stoffers over 7 years ago

Added some code to askHeuristic function

View differences:

src/sim/cheuristic.cc
20 20
 *--------------------------------------------------------------*/
21 21
#include <string.h>
22 22

  
23
#include "cmessage.h"
23 24
#include "cheuristic.h"
24 25

  
25
bool cHeuristic::askHeuristic()
26
// TODO:
27

  
28
// cNode
29
// cNode::cNode
30
// cNode::getProbability()
31
// cNode::getSuccessors()
32
// cNode::getProbabilityDistribution()
33

  
34
// eventSet_t
35
// eventSet_t::begin()
36
// eventSet_t::end()
37
// eventSet_t::iterator
38
// eventSet_t::iterator::++operator
39
// eventSet_t::iterator::operator!=(eventSet_t::iterator)
40
// eventSet_t::iterator::operator=
41

  
42
// evType_t
43

  
44
// abstractEvent_t
45
// abstractEvent_t eventSet_t::iterator::operator->
46
// evType_t abstractEvent_t::getEvType()
47
// int abstractEvent_t::getEvModId()
48
// pdf_t abstractEvent_t::getProbabilityDistribution()
49

  
50
// pdf_t
51
// pdf_t::pdf_t(simtime_t)
52
// pdf_t::operator+ (=convolution)
53

  
54
typedef std::list<abstractEvent_t> succList_t;
55

  
56
/**
57
 * A tree to perform a BFS and predict the probability
58
 * for a causal violation to occur.
59
 */
60
class cTree
26 61
{
62
	private:
63
		// Lower and upper bounds for the causal violation probability:
64
		double lowerBound;
65
		double upperBound;
66
		std::list<cNode> leaves;
67

  
68
	public:
69
		/**
70
		 * Constructor for tree
71
		 * The probability for a causal violation resides (obviously) in the interval [0;1].
72
		 */
73
		cTree()
74
		{
75
			lowerBound=0;
76
			upperBound=1;
77
		}
78

  
79
		/**
80
		 * Adding a node into the tree.
81
		 * @param parent The parent node in the tree. If parent==NULL, the new node will
82
		 *               be inserted as one of the roots of the tree (forest)
83
		 * @param eventType The OMNeT++ message kind
84
		 * @param moduleId The module the event takes place at
85
		 * @param probabilityDistribution The PDF to be stored inside the node
86
		 * @param isConflicting Whether this node is a conflicting node, i.e. an event on this
87
		 *                      node would conflict with the pending event since the pending event
88
		 *                      takes place at the same module.
89
		 */
90
		void addNode(cNode* parent, evType_t evType, int moduleId, pdf_t probabilityDistribution, bool isConflicting)
91
		{
92
			cNode newNode(evType,moduleId,probabilityDistribution);
93
			double dangerProb=newNode->getProbability()
94
			upperBound=1-(1-upperBound)*(1-dangerProb);
95
			if(isConflicting) lowerBound=1-(1-lowerBound)*(1-dangerProb);
96
			if(parent && leaves.contains(parent))
97
			{
98
				upperBound=1-(1-upperBound)/(1-parent->getProbability());
99
				leaves.remove(parent);
100
			}
101
			leaves.push_back(newNode);
102
		}
103

  
104
		// Performing BFS and spanning the tree:
105
		bool bfs(double threshold, int moduleId)
106
		{
107
			for(nodeSet_t::iterator leaf=leaves.begin();leaf!=leaves.end();++leaf)
108
			{
109
				if(leaf->isConflicting())
110
				{
111
					continue;
112
				}
113
				succList_t succs=leaf->getSuccessors();
114
				for(succList_t::iterator succ=succs.begin();succ!=succs.end();++succ)
115
				{
116
					// We need to convolve the PDF of the (previous) leaf node with the PDF of its successors:
117
					pdf_t convolvedPdf=leaf->getProbabilityDistribution()+succ->getProbabilityDistribution();
118
					evType_t succEvType=succ->getEvType();
119
					int succModId=succ->getEvModId();
120
					bool isConflicting=moduleId==succModId;
121
					// We add the new node as a child of the leaf into the tree:
122
					addNode(leaf,succEvType,convolvedPdf,isConflicting);
123
					// If both bounds for the probability are below (above) the threshold,
124
					// the probability itself is also below (above) the threshold,
125
					// i.e. we can yield the decision without further inspecting the BFS tree.
126
					if(lowerBound<=threshold && upperBound<=threshold) return true;
127
					if(lowerBound>=threshold && upperBound>=threshold) return false;
128
				}
129
			}
130
		}
131
};
132

  
133
/**
134
 * This function will be executed whenever the event scheduler encounters
135
 * an event that cannot be executed conservatively at that moment. In this
136
 * case the heuristic computes a probability for a causal violation to occur /
137
 * to not occur, and returns a recommendation whether to execute the event
138
 * speculatively (return value=true) or not (return value=false).
139
 * @param pendingEv The pending event (message in OMNeT++).
140
 * @param setO The set $O$ of currently executed events.
141
 * @param threshold The threshold to compare against.
142
 * @return true iff recommendation for speculative execution is positive.
143
 */
144
bool cHeuristic::askHeuristic(cMessage* pendingEv,eventSet_t setO,double threshold)
145
{
146
	cTree bfsTree;
147
	int pendingEvModId=pendingEv->getArrivalModuleId();
148

  
149
	for (eventSet_t::iterator it=setO->begin();it!=setO->end();++it)
150
	{
151
		evType_t runningEvType=it->getEvType();
152
		int runningEvModId=it->getEvModId();
153
		bool isConflicting=pendingEvModId==runningEvModId;
154
		pdf_t pdf(eventInO->arrivalTime()-pendingEvent->arrivalTime());
155
		bfsTree.addNode(NULL,runningEvType,pdf,isConflicting);
156
	}
27 157

  
158
	return bfsTree.bfs(threshold,pendingEvModId);
28 159
}
29 160

  

Also available in: Unified diff