Project

General

Profile

Statistics
| Branch: | Revision:

root / src / sim / cheuristic.cc @ 92cc8482

History | View | Annotate | Download (9.54 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
#include "cheuristic.h"
25

    
26
// TODO:
27

    
28
// eventSet_t
29
// eventSet_t::begin()
30
// eventSet_t::end()
31
// eventSet_t::iterator
32
// eventSet_t::iterator::++operator
33
// eventSet_t::iterator::operator!=(eventSet_t::iterator)
34
// eventSet_t::iterator::operator=
35
// abstractEvent_t eventSet_t::iterator::operator->
36

    
37
typedef std::list<evType_t> succList_t;
38
typedef class Pdf pdf_t;
39
typedef class AbstractEvent abstractEvent_t;
40
typedef class EventType evType_t;
41

    
42
class EventType
43
{
44
        private:
45
                succList_t succs;
46

    
47
        public:
48
                const succList_t& getSuccessors() const
49
                {
50
                        return succs;
51
                }
52
};
53

    
54
class AbstractEvent
55
{
56
        private:
57
                evType_t type;
58
                int modId;
59
                pdf_t pdf;
60
        public:
61
                evType_t getEvType()
62
                {
63
                        return type;
64
                }
65

    
66
                int getEvModId()
67
                {
68
                        return modId;
69
                }
70

    
71
                pdf_t getProbabilityDistribution()
72
                {
73
                        return pdf;
74
                }
75
};
76

    
77
class Pdf
78
{
79
        private:
80
                struct Bucket
81
                {
82
                        public:
83
                                simtime_t rightBorder;
84
                                size_t bin;
85

    
86
                                Bucket() {}
87

    
88
                                Bucket(const Bucket& b)
89
                                {
90
                                        set(b);
91
                                }
92

    
93
                                bool operator<(const Bucket& b)
94
                                {
95
                                        return this->rightBorder<b.rightBorder;
96
                                }
97

    
98
                                bool operator<=(const Bucket& b)
99
                                {
100
                                        return this->rightBorder<=b.rightBorder;
101
                                }
102

    
103
                                bool operator>(const Bucket& b)
104
                                {
105
                                        return this->rightBorder>b.rightBorder;
106
                                }
107

    
108
                                bool operator>=(const Bucket& b)
109
                                {
110
                                        return this->rightBorder>=b.rightBorder;
111
                                }
112

    
113
                                void set(const Bucket& b)
114
                                {
115
                                        memcpy(this,&b,sizeof(*this));
116
                                }
117
                } bucket_t;
118

    
119
                static const size_t size=9; // MUST BE (2^n)+1 for some integer n (like 3,5,9,17,...)
120
                size_t[size] bins;
121
                simtime_t[size] leftBorders;
122
                simtime_t* rightBorders;
123
                size_t count;
124
                bool isDet;
125
                simtime_t detVal;
126

    
127
                Pdf& convolveInPlaceDetDet(const Pdf& b)
128
                {
129
                        this->detVal+=b.detVal;
130
                        return *this;
131
                }
132

    
133
                Pdf& convolveInPlaceDetBin(const Pdf& b)
134
                {
135
                        memcpy(this->bins,b.bins,sizeof(bins));
136
                        memcpy(this->leftBorders,b.leftBorders,sizeof(leftBorders));
137
                        rightBorders=&(leftBorders[1]);
138
                        this->count=b.count;
139
                        this->isDet=false;
140
                        for(size_t i=1;i<size;i++)
141
                                leftBorders[i]+=this->detVal;
142
                        return *this;
143
                }
144

    
145
                Pdf& convolveInPlaceBinDet(const Pdf& b)
146
                {
147
                        for(size_t i=1;i<size;i++)
148
                                leftBorders[i]+=b.detVal;
149
                        return *this;
150
                }
151

    
152
                Pdf& convolveInPlaceBinBin(const Pdf& b)
153
                {
154
                        const size_t s1=size-1;
155
                        size_t from=1;
156
                        size_t to=0;
157
                        bucket_t matrix[s1*s1][s1][2];
158
                        bucket_t b1,b2;
159
                        size_t total=0;
160

    
161
                        for(size_t i=0;i<s1;i++)
162
                        {
163
                                for(size_t j=0;j<s1;j++)
164
                                {
165
                                        matrix[i][j][to].rightBorder=this->rightBorders[i]+b.rightBorders[j];
166
                                        matrix[i][j][to].bin=this->bins[i]+b.bins[j];
167
                                        total+=matrix[i][j][to].bin;
168
                                }
169
                        }
170

    
171
                        for(size_t m=1;m<s1;m*=2)
172
                        {
173
                                from=1-from;
174
                                to=1-to;
175
                                for(size_t i=0;i<s1/m;i+=2)
176
                                {
177
                                        size_t k=0;
178
                                        size_t l=0;
179
                                        for(size_t j=0;j<m*2*s1;j++)
180
                                        {
181
                                                if(k<m*s1) b1.set(matrix[i][k][from]);
182
                                                else b1.rightBorder=MAXTIME;
183
                                                if(l<m*s1) b2.set(matrix[i+1][l][from]);
184
                                                else b2.rightBorder=MAXTIME;
185
                                                if(b1<=b2)
186
                                                {
187
                                                        matrix[i/2][j][to].set(b1);
188
                                                        k++;
189
                                                }
190
                                                else
191
                                                {
192
                                                        matrix[i/2][j][to].set(b2);
193
                                                        l++;
194
                                                }
195
                                        }
196
                                }
197
                        }
198
                        assert(m==s1);
199

    
200
                        // now we have the sorted borders in borderMatrix[0][x][to]
201

    
202
                        for(size_t i=0;i<s1;i++)
203
                        {
204
                                this->bins[i]=0;
205
                                for(size_t j=0;j<s1;j++)
206
                                {
207
                                        this->bins[i]+=matrix[0][j+i*s1][to].bin;
208
                                }
209
                                this->rightBorder[i]=matrix[0][s1-1+i*s1][to].rightBorder;
210
                        }
211
                        this->bins[s1]*=b.bins[s1];
212
                        this->count*=b.count;
213
                }
214

    
215
        public:
216
                Pdf(simtime_t delay)
217
                {
218
                        isDet=true;
219
                        detVal=delay;
220
                }
221

    
222
                Pdf& operator+=(const Pdf& b)
223
                {
224
                        if( this->isDet &&  b.isDet)
225
                                return convolveInPlaceDetDet(b);
226
                        if( this->isDet && !b.isDet)
227
                                return convolveInPlaceDetBin(b);
228
                        if(!this->isDet &&  b.isDet)
229
                                return convolveInPlaceBinDet(b);
230
                        if(!this->isDet && !b.isDet)
231
                                return convolveInPlaceBinBin(b);
232
                        assert(false);
233
                        return *this;
234
                }
235

    
236
                double getProbability(simtime_t val)
237
                {
238
                        if(isDet && detVal< val) return 1;
239
                        if(isDet && detVal>=val) return 0;
240

    
241
                        size_t sum=0;
242
                        for(size_t i=0;i<size;i++)
243
                        {
244
                                if(leftBorders[i]<val) sum+=bins[i];
245
                                else return sum;
246
                        }
247
                }
248

    
249
/*                Pdf operator+(const Pdf& a,const Pdf& b) const
250
                {
251
                        if( a.isDet &&  b.isDet)
252
                                return convolveDetDet(a,b);
253
                        if( a.isDet && !b.isDet)
254
                                return convolveDetBin(a,b);
255
                        if(!a.isDet &&  b.isDet)
256
                                return convolveDetBin(b,a);
257
                        if(!a.isDet && !b.isDet)
258
                                return convolveBinBin(a,b);
259
                        assert(false);
260
                        return Pdf(1337);
261
                }*/
262
};
263

    
264
class cNode
265
{
266
        private:
267
                pdf_t pdf;
268
                evType_t type;
269
                int modId;
270

    
271
        public:
272
                cNode(evType_t evType,int moduleId,pdf_t probabilityDistribution)
273
                {
274
                        pdf=probabilityDistribution;
275
                        type=evType;
276
                        modId=moduleId;
277
                }
278

    
279
                double getProbability()
280
                {
281
                        return pdf.getProbability(0);
282
                }
283

    
284
                succList_t getSuccessors()
285
                {
286
                        return type->getSuccessors();
287
                }
288

    
289
                const pdf_t& getProbabilityDistribution()
290
                {
291
                        return pdf;
292
                }
293

    
294
                pdf_t getProbabilityDistributionCopy()
295
                {
296
                        return pdf;
297
                }
298
};
299

    
300
/**
301
 * A tree to perform a BFS and predict the probability
302
 * for a causal violation to occur.
303
 */
304
class cTree
305
{
306
        private:
307
                // Lower and upper bounds for the causal violation probability:
308
                double lowerBound;
309
                double upperBound;
310
                std::list<cNode> leaves;
311

    
312
        public:
313
                /**
314
                 * Constructor for tree
315
                 * The probability for a causal violation resides (obviously) in the interval [0;1].
316
                 */
317
                cTree()
318
                {
319
                        lowerBound=0;
320
                        upperBound=1;
321
                }
322

    
323
                /**
324
                 * Adding a node into the tree.
325
                 * @param parent The parent node in the tree. If parent==NULL, the new node will
326
                 *               be inserted as one of the roots of the tree (forest)
327
                 * @param eventType The OMNeT++ message kind
328
                 * @param moduleId The module the event takes place at
329
                 * @param probabilityDistribution The PDF to be stored inside the node
330
                 * @param isConflicting Whether this node is a conflicting node, i.e. an event on this
331
                 *                      node would conflict with the pending event since the pending event
332
                 *                      takes place at the same module.
333
                 */
334
                void addNode(cNode* parent, evType_t evType, int moduleId, pdf_t probabilityDistribution, bool isConflicting)
335
                {
336
                        cNode newNode(evType,moduleId,probabilityDistribution);
337
                        double dangerProb=newNode->getProbability()
338
                        upperBound=1-(1-upperBound)*(1-dangerProb);
339
                        if(isConflicting) lowerBound=1-(1-lowerBound)*(1-dangerProb);
340
                        if(parent && leaves.contains(parent))
341
                        {
342
                                upperBound=1-(1-upperBound)/(1-parent->getProbability());
343
                                leaves.remove(parent);
344
                        }
345
                        leaves.push_back(newNode);
346
                }
347

    
348
                // Performing BFS and spanning the tree:
349
                bool bfs(double threshold, int moduleId)
350
                {
351
                        for(nodeSet_t::iterator leaf=leaves.begin();leaf!=leaves.end();++leaf)
352
                        {
353
                                if(leaf->isConflicting())
354
                                {
355
                                        continue;
356
                                }
357
                                succList_t succs=leaf->getSuccessors();
358
                                for(succList_t::iterator succ=succs.begin();succ!=succs.end();++succ)
359
                                {
360
                                        // We need to convolve the PDF of the (previous) leaf node with the PDF of its successors:
361
                                        //pdf_t convolvedPdf=leaf->getProbabilityDistribution()+succ->getProbabilityDistribution();
362
                                        pdf_t convolvedPdf=succ->getProbabilityDistributionCopy();
363
                                        convolvedPdf+=leaf->getProbabilityDistribution();
364
                                        evType_t succEvType=succ->getEvType();
365
                                        int succModId=succ->getEvModId();
366
                                        bool isConflicting=moduleId==succModId;
367
                                        // We add the new node as a child of the leaf into the tree:
368
                                        addNode(leaf,succEvType,convolvedPdf,isConflicting);
369
                                        // If both bounds for the probability are below (above) the threshold,
370
                                        // the probability itself is also below (above) the threshold,
371
                                        // i.e. we can yield the decision without further inspecting the BFS tree.
372
                                        if(lowerBound<=threshold && upperBound<=threshold) return true;
373
                                        if(lowerBound>=threshold && upperBound>=threshold) return false;
374
                                }
375
                        }
376
                }
377
};
378

    
379
/**
380
 * This function will be executed whenever the event scheduler encounters
381
 * an event that cannot be executed conservatively at that moment. In this
382
 * case the heuristic computes a probability for a causal violation to occur /
383
 * to not occur, and returns a recommendation whether to execute the event
384
 * speculatively (return value=true) or not (return value=false).
385
 * @param pendingEv The pending event (message in OMNeT++).
386
 * @param setO The set $O$ of currently executed events.
387
 * @param threshold The threshold to compare against.
388
 * @return true iff recommendation for speculative execution is positive.
389
 */
390
bool cHeuristic::askHeuristic(cMessage* pendingEv,eventSet_t setO,double threshold)
391
{
392
        cTree bfsTree;
393
        int pendingEvModId=pendingEv->getArrivalModuleId();
394

    
395
        for (eventSet_t::iterator it=setO->begin();it!=setO->end();++it)
396
        {
397
                evType_t runningEvType=it->getEvType();
398
                int runningEvModId=it->getEvModId();
399
                bool isConflicting=pendingEvModId==runningEvModId;
400
                pdf_t pdf(eventInO->arrivalTime()-pendingEvent->arrivalTime());
401
                bfsTree.addNode(NULL,runningEvType,pdf,isConflicting);
402
        }
403

    
404
        return bfsTree.bfs(threshold,pendingEvModId);
405
}
406