Project

General

Profile

Revision 8b911557

ID8b91155720a5cfcd26b44d6e52b64f4de49d345d
Parent 0d3d896c
Child e702d896

Added by Mirko Stoffers about 7 years ago

Various fixes for heuristic

View differences:

src/sim/cheuristic.cc
27 27
#include "cheuristic.h"
28 28
#include "eventset.h"
29 29

  
30
#define MAX_IT 1000000
30
#define MAX_IT 100
31
#define EPSILON 1e-6
31 32

  
32 33
EventSet::iterator::iterator(const EventSet::iterator& b) :
33 34
	index(index),
......
35 36
{
36 37
}
37 38

  
39
class Probability
40
{
41
	private:
42
		double invProb;
43
		int ones;
44
#ifdef DEBUG
45
		std::list<double> factors;
46
#endif
47

  
48
	public:
49
		Probability()
50
		{
51
			invProb=1;
52
			ones=0;
53
		}
54

  
55
		operator double() const
56
		{
57
			if(ones>0)
58
			{
59
				return 1;
60
			}
61
			else
62
			{
63
				std::cout << invProb << std::endl;
64
				assert(!isnan(invProb));
65
				assert(invProb>=0 && invProb<=1+EPSILON);
66
				return 1-invProb;
67
			}
68
		}
69

  
70
		void addFactor(const double factor)
71
		{
72
#ifdef DEBUG
73
			assert(!isnan(factor));
74
			assert(factor>=0 && factor <=1);
75
			factors.push_back(factor);
76
			//std::cout << this << "adding " << factor << std::endl;
77
#endif
78
			if(factor==1)
79
			{
80
				ones++;
81
			}
82
			else
83
			{
84
				assert(invProb>=0);
85
				double ips=invProb;
86
				invProb*=(1-factor);
87
				if(invProb<0) std::cout << ips << "*" << (1-factor) << "=" << invProb << std::endl;
88
				assert(invProb>=0);
89
			}
90
		}
91

  
92
		void removeFactor(const double factor)
93
		{
94
#ifdef DEBUG
95
			assert(!isnan(factor) && factor>=0 && factor <=1);
96
			bool existed=false;
97
			for(std::list<double>::iterator it=factors.begin();it!=factors.end();++it)
98
			{
99
				if(*it==factor)
100
				{
101
					factors.erase(it);
102
					existed=true;
103
					break;
104
				}
105
			}
106
			assert(existed);
107
			//std::cout << this << ":removing " << factor << std::endl;
108
#endif
109
			if(factor==1)
110
			{
111
				ones--;
112
				assert(ones>=0);
113
			}
114
			else
115
			{
116
				double ips=invProb;
117
				invProb/=(1-factor);
118
				if(invProb<0) std::cout << ips << "/" << (1-factor) << "=" << invProb << std::endl;
119
				assert(invProb>=0);
120
			}
121
		}
122
};
123

  
38 124
class cNode
39 125
{
40 126
	private:
......
52 138

  
53 139
		double getProbability()
54 140
		{
55
			return pdf.getProbability(0);
141
			double prob=pdf.getProbability(0);
142
			assert(!isnan(prob));
143
			assert(prob>=0);
144
			assert(prob<=1);
145
			return prob;
56 146
		}
57 147

  
58 148
		succList_t getSuccessors()
......
84 174
{
85 175
	private:
86 176
		// Lower and upper bounds for the causal violation probability:
87
		double lowerBound;
88
		double upperBound;
177
		Probability lowerBound;
178
		Probability upperBound;
89 179
		typedef std::list<cNode*> nodeSet_t;
90 180
		nodeSet_t bfsVisitList;
91 181

  
......
96 186
		 */
97 187
		cTree()
98 188
		{
99
			lowerBound=0;
100
			upperBound=1;
101 189
		}
102 190

  
103 191
		~cTree()
......
108 196
			}
109 197
		}
110 198

  
199
		double getLowerBound() const
200
		{
201
			return lowerBound;
202
		}
203

  
204
		double getUpperBound() const
205
		{
206
			return upperBound;
207
		}
208

  
111 209
		/**
112 210
		 * Adding a node into the tree.
113 211
		 * @param parent The parent node in the tree. If parent==NULL, the new node will
......
123 221
		{
124 222
			cNode* newNode=new cNode(evType,isConflicting,probabilityDistribution);
125 223
			const double dangerProb=newNode->getProbability();
126
			upperBound=1-(1-upperBound)*(1-dangerProb);
127
			if(isConflicting) lowerBound=1-(1-lowerBound)*(1-dangerProb);
224
			upperBound.addFactor(dangerProb);
225
			if(isConflicting) lowerBound.addFactor(dangerProb);
128 226
			bfsVisitList.push_back(newNode);
129 227
		}
130 228

  
229
		bool checkBounds() const
230
		{
231
			if(isnan(lowerBound) || isnan(upperBound))
232
			{
233
				std::cout << "a bound is not a number! lower bound: " << lowerBound << ", upper bound: " << upperBound << std::endl;
234
				return false;
235
			}
236
			if(lowerBound<-EPSILON || lowerBound>1)
237
			{
238
				std::cout << "lower bound out of bounds! lower bound: " << lowerBound << ", upper bound: " << upperBound << std::endl;
239
				return false;
240
			}
241
			if(upperBound<-EPSILON || upperBound>1)
242
			{
243
				std::cout << "upper bound out of bounds! lower bound: " << lowerBound << ", upper bound: " << upperBound << std::endl;
244
				return false;
245
			}
246
			if(lowerBound-EPSILON>upperBound+EPSILON)
247
			{
248
				std::cout << "lower bound greater then upper bound! lower bound: " << lowerBound << ", upper bound: " << upperBound << std::endl;
249
				return false;
250
			}
251
			return true;
252
		}
253

  
131 254
		// Performing BFS and spanning the tree:
132 255
		bool bfs(double threshold, int moduleId)
133 256
		{
......
143 266
				}
144 267
				else
145 268
				{
146
					upperBound=1-(1-upperBound)/(1-node->getProbability());
269
					upperBound.removeFactor(node->getProbability());
147 270
				}
148 271
				succList_t succs=node->getSuccessors();
149 272
				for(succList_t::iterator succ=succs.begin();succ!=succs.end();++succ)
......
160 283
					// If both bounds for the probability are below (above) the threshold,
161 284
					// the probability itself is also below (above) the threshold,
162 285
					// i.e. we can yield the decision without further inspecting the BFS tree.
286
					assert(checkBounds());
163 287
					if(lowerBound<=threshold && upperBound<=threshold) {node->releaseSuccListLock(); delete node; return true;}
164 288
					if(lowerBound>=threshold && upperBound>=threshold) {node->releaseSuccListLock(); delete node; return false;}
165 289
				}
166 290
				node->releaseSuccListLock();
167 291
				delete node;
168 292
			}
293
			assert(checkBounds());
169 294
			if(lowerBound<=threshold && upperBound<=threshold) return true;
170 295
			return false; // be pessimistic
171 296
		}
......
192 317
		evType_t* runningEvType=it->getEvType();
193 318
		int runningEvModId=it->getEvModId();
194 319
		bool isConflicting=pendingEvModId==runningEvModId;
195
		pdf_t pdf(it->getArrivalTime()-pendingEv->getArrivalTime());
320
		pdf_t pdf(it->getArrivalTime()-pendingEv->getArrivalTime(),1);
196 321
		bfsTree.addNode(NULL,runningEvType,pdf,isConflicting);
197 322
	}
198 323

  
199
	return bfsTree.bfs(threshold,pendingEvModId);
324
	bool res=bfsTree.bfs(threshold,pendingEvModId);
325
//	std::cout << "lower bound: " << bfsTree.getLowerBound() << std::endl;
326
//	std::cout << "upper bound: " << bfsTree.getUpperBound() << std::endl;
327
	return res;
200 328
}
201 329

  

Also available in: Unified diff