Project

General

Profile

Statistics
| Branch: | Revision:

root / src / sim / cheuristic.cc @ 8b911557

History | View | Annotate | Download (8.55 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
#define MAX_IT 100
31
#define EPSILON 1e-6
32

    
33
EventSet::iterator::iterator(const EventSet::iterator& b) :
34
        index(index),
35
        s(s)
36
{
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

    
124
class cNode
125
{
126
        private:
127
                pdf_t pdf;
128
                evType_t* type;
129
                bool isConf;
130

    
131
        public:
132
                cNode(evType_t* const evType,bool isConflicting,pdf_t probabilityDistribution) :
133
                        pdf(probabilityDistribution),
134
                        isConf(isConflicting)
135
                {
136
                        type=evType;
137
                }
138

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

    
148
                succList_t getSuccessors()
149
                {
150
                        return type->getSuccessors();
151
                }
152

    
153
                void releaseSuccListLock()
154
                {
155
                        type->releaseSuccListLock();
156
                }
157

    
158
                const pdf_t& getProbabilityDistribution()
159
                {
160
                        return pdf;
161
                }
162

    
163
                bool isConflicting()
164
                {
165
                        return isConf;
166
                }
167
};
168

    
169
/**
170
 * A tree to perform a BFS and predict the probability
171
 * for a causal violation to occur.
172
 */
173
class cTree
174
{
175
        private:
176
                // Lower and upper bounds for the causal violation probability:
177
                Probability lowerBound;
178
                Probability upperBound;
179
                typedef std::list<cNode*> nodeSet_t;
180
                nodeSet_t bfsVisitList;
181

    
182
        public:
183
                /**
184
                 * Constructor for tree
185
                 * The probability for a causal violation resides (obviously) in the interval [0;1].
186
                 */
187
                cTree()
188
                {
189
                }
190

    
191
                ~cTree()
192
                {
193
                        for(nodeSet_t::iterator it=bfsVisitList.begin();it!=bfsVisitList.end();it++)
194
                        {
195
                                delete *it;
196
                        }
197
                }
198

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

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

    
209
                /**
210
                 * Adding a node into the tree.
211
                 * @param parent The parent node in the tree. If parent==NULL, the new node will
212
                 *               be inserted as one of the roots of the tree (forest)
213
                 * @param eventType The OMNeT++ message kind
214
                 * @param moduleId The module the event takes place at
215
                 * @param probabilityDistribution The PDF to be stored inside the node
216
                 * @param isConflicting Whether this node is a conflicting node, i.e. an event on this
217
                 *                      node would conflict with the pending event since the pending event
218
                 *                      takes place at the same module.
219
                 */
220
                void addNode(cNode* parent, evType_t* const evType,pdf_t probabilityDistribution, bool isConflicting)
221
                {
222
                        cNode* newNode=new cNode(evType,isConflicting,probabilityDistribution);
223
                        const double dangerProb=newNode->getProbability();
224
                        upperBound.addFactor(dangerProb);
225
                        if(isConflicting) lowerBound.addFactor(dangerProb);
226
                        bfsVisitList.push_back(newNode);
227
                }
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

    
254
                // Performing BFS and spanning the tree:
255
                bool bfs(double threshold, int moduleId)
256
                {
257
                        nodeSet_t::iterator it;
258
                        for(int i=0; i<MAX_IT && (it=bfsVisitList.begin()) != bfsVisitList.end(); i++)
259
                        {
260
                                cNode* node=*it;
261
                                bfsVisitList.erase(it);
262
                                if(node->isConflicting())
263
                                {
264
                                        delete node;
265
                                        continue;
266
                                }
267
                                else
268
                                {
269
                                        upperBound.removeFactor(node->getProbability());
270
                                }
271
                                succList_t succs=node->getSuccessors();
272
                                for(succList_t::iterator succ=succs.begin();succ!=succs.end();++succ)
273
                                {
274
                                        // We need to convolve the PDF of the (previous) leaf node with the PDF of its successors:
275
                                        //pdf_t convolvedPdf=node->getProbabilityDistribution()+succ->getProbabilityDistribution();
276
                                        pdf_t convolvedPdf=succ->getProbabilityDistributionCopy();
277
                                        convolvedPdf+=node->getProbabilityDistribution();
278
                                        evType_t* succEvType=succ->getEvType();
279
                                        int succModId=succ->getEvType()->getModId();
280
                                        bool isConflicting=moduleId==succModId;
281
                                        // We add the new node as a child of the leaf into the tree:
282
                                        addNode(node,succEvType,convolvedPdf,isConflicting);
283
                                        // If both bounds for the probability are below (above) the threshold,
284
                                        // the probability itself is also below (above) the threshold,
285
                                        // i.e. we can yield the decision without further inspecting the BFS tree.
286
                                        assert(checkBounds());
287
                                        if(lowerBound<=threshold && upperBound<=threshold) {node->releaseSuccListLock(); delete node; return true;}
288
                                        if(lowerBound>=threshold && upperBound>=threshold) {node->releaseSuccListLock(); delete node; return false;}
289
                                }
290
                                node->releaseSuccListLock();
291
                                delete node;
292
                        }
293
                        assert(checkBounds());
294
                        if(lowerBound<=threshold && upperBound<=threshold) return true;
295
                        return false; // be pessimistic
296
                }
297
};
298

    
299
/**
300
 * This function will be executed whenever the event scheduler encounters
301
 * an event that cannot be executed conservatively at that moment. In this
302
 * case the heuristic computes a probability for a causal violation to occur /
303
 * to not occur, and returns a recommendation whether to execute the event
304
 * speculatively (return value=true) or not (return value=false).
305
 * @param pendingEv The pending event (message in OMNeT++).
306
 * @param setO The set $O$ of currently executed events.
307
 * @param threshold The threshold to compare against.
308
 * @return true iff recommendation for speculative execution is positive.
309
 */
310
bool cHeuristic::askHeuristic(const cMessage* const pendingEv,eventSet_t setO,double threshold)
311
{
312
        cTree bfsTree;
313
        int pendingEvModId=pendingEv->getArrivalModuleId();
314

    
315
        for (eventSet_t::iterator it=setO.begin();it!=setO.end();++it)
316
        {
317
                evType_t* runningEvType=it->getEvType();
318
                int runningEvModId=it->getEvModId();
319
                bool isConflicting=pendingEvModId==runningEvModId;
320
                pdf_t pdf(it->getArrivalTime()-pendingEv->getArrivalTime(),1);
321
                bfsTree.addNode(NULL,runningEvType,pdf,isConflicting);
322
        }
323

    
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;
328
}
329