Project

General

Profile

Revision 8b911557

ID8b91155720a5cfcd26b44d6e52b64f4de49d345d
Parent 0d3d896c
Child e702d896

Added by Mirko Stoffers about 7 years ago

Various fixes for heuristic

View differences:

include/eventtype.h
30 30
		pdf_t pdf;
31 31

  
32 32
	public:
33
		SuccessorEvent(EventType* const type, simtime_t firstSample) : pdf(firstSample)
33
		SuccessorEvent(EventType* const type, simtime_t firstSample, size_t callCount) : pdf(firstSample, callCount)
34 34
		{
35 35
			this->type=type;
36 36
		}
37 37

  
38
		SuccessorEvent(const cMessage* const msg, simtime_t firstSample) : pdf(firstSample)
39
		{
40
			cModule* mod=msg->getArrivalModule();
41
			type=mod->getEventType(msg);
42
		}
43 38

  
44 39
		bool operator==(const EventType& type) const
45 40
		{
......
67 62
		{
68 63
			pdf.sample(delay);
69 64
		}
65

  
66
		void setBaseLine(size_t newBaseLine)
67
		{
68
			pdf.setBaseLine(newBaseLine);
69
		}
70 70
};
71 71

  
72 72
class EventType
......
77 77
		int kind;
78 78
		int sender;
79 79
		cTTASLock succListLock;
80
		size_t callCount;
80 81

  
81 82
	public:
82 83
		EventType(const cMessage* const msg)
......
84 85
			modId=msg->getArrivalModuleId();
85 86
			kind=msg->getKind();
86 87
			sender=msg->getSenderModuleId();
88
			callCount=0;
87 89
		}
88 90

  
89 91
		bool operator==(const cMessage& msg)
......
129 131
			// If event type does not exist, create it:
130 132
			if(succ==NULL)
131 133
			{
132
				succs.emplace_back(t,delay);
134
				succs.emplace_back(t,delay,callCount);
133 135
				succ=&succs.back();
134 136
			}
135

  
136
			succ->sample(delay);
137
			else
138
			{
139
				succ->sample(delay);
140
			}
137 141
			succListLock.unlock();
138 142
		}
143

  
144
		void isCalled()
145
		{
146
			callCount++;
147
			for(succList_t::iterator it=succs.begin();it!=succs.end();++it)
148
			{
149
				it->setBaseLine(callCount);
150
			}
151
			// XXX: Don't like that. Must iterate over all the list :(
152
		}
139 153
};
140 154

  
include/pdf.h
27 27
				simtime_t rightBorder;
28 28
				size_t bin;
29 29

  
30
				Bin() {}
31

  
32
				Bin(const Bin& b)
33
				{
34
					set(b);
35
				}
36

  
37 30
				bool operator<(const Bin& b)
38 31
				{
39 32
					return this->rightBorder<b.rightBorder;
......
53 46
				{
54 47
					return this->rightBorder>=b.rightBorder;
55 48
				}
56

  
57
				void set(const Bin& b)
58
				{
59
					memcpy(this,&b,sizeof(*this));
60
				}
61 49
		} bin_t;
62 50

  
63 51
		static const size_t size=9; // MUST BE (2^n)+1 for some integer n (like 3,5,9,17,...)
......
65 53
		simtime_t leftBorders[size+1];
66 54
		simtime_t* rightBorders;
67 55
		size_t count;
56
		size_t baseLine;
68 57
		bool isDet;
69 58
		simtime_t detVal;
70 59

  
71 60
		Pdf& convolveInPlaceDetDet(const Pdf& b)
72 61
		{
73 62
			this->detVal+=b.detVal;
63
			this->count*=b.count;
64
			this->baseLine*=b.baseLine;
74 65
			return *this;
75 66
		}
76 67

  
......
79 70
			memcpy(this->bins,b.bins,sizeof(bins));
80 71
			memcpy(this->leftBorders,b.leftBorders,sizeof(leftBorders));
81 72
			rightBorders=&(leftBorders[1]);
82
			this->count=b.count;
73
			this->baseLine*=b.baseLine;
83 74
			this->isDet=false;
75
			bins[0]*=this->count;
84 76
			for(size_t i=1;i<size;i++)
77
			{
85 78
				leftBorders[i]+=this->detVal;
79
				bins[i]*=this->count;
80
			}
86 81
			return *this;
87 82
		}
88 83

  
89 84
		Pdf& convolveInPlaceBinDet(const Pdf& b)
90 85
		{
86
			this->baseLine*=b.baseLine;
87
			bins[0]*=b.count;
91 88
			for(size_t i=1;i<size;i++)
89
			{
92 90
				leftBorders[i]+=b.detVal;
91
				bins[i]*=b.count;
92
			}
93 93
			return *this;
94 94
		}
95 95

  
......
98 98
			const size_t s1=size-1;
99 99
			size_t from=1;
100 100
			size_t to=0;
101
			bin_t matrix[s1*s1][s1][2];
101
			bin_t matrix[size][s1*s1][2];
102 102
			bin_t b1,b2;
103
			size_t total=0;
104 103

  
105 104
			for(size_t i=0;i<s1;i++)
106 105
			{
107 106
				for(size_t j=0;j<s1;j++)
108 107
				{
109 108
					matrix[i][j][to].rightBorder=this->rightBorders[i]+b.rightBorders[j];
110
					matrix[i][j][to].bin=this->bins[i]+b.bins[j];
111
					total+=matrix[i][j][to].bin;
109
					matrix[i][j][to].bin=this->bins[i]*b.bins[j];
112 110
				}
113 111
			}
114 112

  
......
123 121
					size_t l=0;
124 122
					for(size_t j=0;j<m*2*s1;j++)
125 123
					{
126
						if(k<m*s1) b1.set(matrix[i][k][from]);
127
						else b1.rightBorder=MAXTIME;
128
						if(l<m*s1) b2.set(matrix[i+1][l][from]);
129
						else b2.rightBorder=MAXTIME;
124
						if(k<m*s1) b1=matrix[i][k][from];
125
						else
126
						{
127
							b1.bin=(size_t)-1;
128
							b1.rightBorder=MAXTIME;
129
						}
130
						if(l<m*s1) b2=matrix[i+1][l][from];
131
						else
132
						{
133
							b2.bin=(size_t)-1;
134
							b2.rightBorder=MAXTIME;
135
						}
130 136
						if(b1<=b2)
131 137
						{
132
							matrix[i/2][j][to].set(b1);
138
							matrix[i/2][j][to]=b1;
133 139
							k++;
134 140
						}
135 141
						else
136 142
						{
137
							matrix[i/2][j][to].set(b2);
143
							matrix[i/2][j][to]=b2;
138 144
							l++;
139 145
						}
140 146
					}
......
154 160
				this->rightBorders[i]=matrix[0][s1-1+i*s1][to].rightBorder;
155 161
			}
156 162
			this->bins[s1]*=b.bins[s1];
157
			this->count*=b.count;
163
			this->baseLine*=b.baseLine;
158 164
			return *this;
159 165
		}
160 166

  
......
195 201
			simtime_t b=max/2;
196 202
			simtime_t step=(b-a)/(size-1);
197 203
			leftBorders[0]=MINTIME;
204
			bins[0]=0;
198 205
			simtime_t next=a;
199 206
			for(size_t i=1;i<size;i++)
200 207
			{
208
				bins[i]=0;
201 209
				leftBorders[i]=next;
202 210
				next+=step;
203 211
			}
204 212
			rightBorders[size-1]=MAXTIME;
213
			isDet=false;
205 214
			insert(detVal,count);
206 215
			insert(delay);
216
			assert(isValidPdf());
207 217
		}
208 218

  
209 219
	public:
210
		Pdf(simtime_t delay)
220
		Pdf(simtime_t delay,size_t baseLine)
211 221
		{
212 222
			isDet=true;
213 223
			detVal=delay;
214 224
			count=1;
225
			this->baseLine=baseLine;
226
			assert(isValidPdf());
227
		}
228

  
229
		Pdf(const Pdf& other)
230
		{
231
			memcpy(this,&other,sizeof(*this));
232
			rightBorders=&(leftBorders[1]);
215 233
		}
216 234

  
217 235
		Pdf& operator+=(const Pdf& b)
218 236
		{
219 237
			if( this->isDet &&  b.isDet)
220
				return convolveInPlaceDetDet(b);
221
			if( this->isDet && !b.isDet)
222
				return convolveInPlaceDetBin(b);
223
			if(!this->isDet &&  b.isDet)
224
				return convolveInPlaceBinDet(b);
225
			if(!this->isDet && !b.isDet)
226
				return convolveInPlaceBinBin(b);
227
			assert(false);
238
				convolveInPlaceDetDet(b);
239
			else if( this->isDet && !b.isDet)
240
				convolveInPlaceDetBin(b);
241
			else if(!this->isDet &&  b.isDet)
242
				convolveInPlaceBinDet(b);
243
			else if(!this->isDet && !b.isDet)
244
				convolveInPlaceBinBin(b);
245
			else
246
				assert(false);
247
			//print();
248
			assert(isValidPdf());
228 249
			return *this;
229 250
		}
230 251

  
231
		double getProbability(simtime_t val)
252
		double getProbability(simtime_t val) const
232 253
		{
233 254
			if(isDet && detVal< val) return 1;
234 255
			if(isDet && detVal>=val) return 0;
......
237 258
			for(size_t i=0;i<size;i++)
238 259
			{
239 260
				if(leftBorders[i]<val) sum+=bins[i];
240
				else return sum;
261
				else return (double)sum/baseLine;
241 262
			}
242
			return sum;
263
			return (double)sum/baseLine;
243 264
		}
244 265

  
245 266
		void sample(simtime_t delay)
......
253 274
			{
254 275
				insert(delay);
255 276
			}
277
			assert(isValidPdf());
278
		}
279

  
280
		void print() const
281
		{
282
			std::cout << "printing " << this << std::endl;
283
			std::cout << "base line: " << baseLine << std::endl;
284
			if(isDet)
285
			{
286
				std::cout << "Deterministic, value: " << detVal << std::endl;
287
			}
288
			else
289
			{
290
				std::cout << "=======" << std::endl;
291
				std::cout << leftBorders << "," << &(leftBorders[1]) << "," << rightBorders << std::endl;
292
				assert(rightBorders==&(leftBorders[1]));
293
				for(size_t i=0;i<size;i++)
294
					std::cout << "[" << leftBorders[i] << ";" << rightBorders[i] << "]: " << bins[i] << std::endl;
295
				std::cout << "=======" << std::endl;
296
			}
297
		}
298

  
299
		bool isValidPdf() const
300
		{
301
			if(isDet)
302
			{
303
				return count!=0 && count <= baseLine;
304
			}
305
			else
306
			{
307
				size_t sum=0;
308
				for(size_t i=0;i<size;i++)
309
				{
310
					if(leftBorders[i]>rightBorders[i]) return false;
311
					sum+=bins[i];
312
				}
313
				if(sum>baseLine) return false;
314
				else return true;
315
			}
316
		}
317

  
318
		void setBaseLine(size_t newBaseLine)
319
		{
320
			baseLine=newBaseLine;
256 321
		}
257 322
};
258 323

  
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

  
src/sim/csimplemodule.cc
198 198
    // which must always be called
199 199
    timeoutmsg = NULL;
200 200

  
201
	currentEventType = NULL;
202

  
203 201
    if (usesActivity())
204 202
    {
205 203
       // setup coroutine, allocate stack for it
......
836 834
    executionOrderId = msg->getExecutionOrderId();
837 835

  
838 836
	currentEventType=getEventType(msg);
837
	currentEventType->isCalled();
839 838

  
840 839
}
841 840

  

Also available in: Unified diff