Statistics
| Branch: | Revision:

root / src / sim / cheuristic.cc @ 35f4da42

History | View | Annotate | Download (6.02 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 1000000
31

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

    
38
class cNode
39
{
40
        private:
41
                pdf_t pdf;
42
                evType_t* type;
43
                bool isConf;
44

    
45
        public:
46
                cNode(evType_t* const evType,bool isConflicting,pdf_t probabilityDistribution) :
47
                        pdf(probabilityDistribution),
48
                        isConf(isConflicting)
49
                {
50
                        type=evType;
51
                }
52

    
53
                double getProbability()
54
                {
55
                        return pdf.getProbability(0);
56
                }
57

    
58
                succList_t getSuccessors()
59
                {
60
                        return type->getSuccessors();
61
                }
62

    
63
                void releaseSuccListLock()
64
                {
65
                        type->releaseSuccListLock();
66
                }
67

    
68
                const pdf_t& getProbabilityDistribution()
69
                {
70
                        return pdf;
71
                }
72

    
73
                bool isConflicting()
74
                {
75
                        return isConf;
76
                }
77
};
78

    
79
/**
80
 * A tree to perform a BFS and predict the probability
81
 * for a causal violation to occur.
82
 */
83
class cTree
84
{
85
        private:
86
                // Lower and upper bounds for the causal violation probability:
87
                double lowerBound;
88
                double upperBound;
89
                typedef std::list<cNode*> nodeSet_t;
90
                nodeSet_t bfsVisitList;
91

    
92
        public:
93
                /**
94
                 * Constructor for tree
95
                 * The probability for a causal violation resides (obviously) in the interval [0;1].
96
                 */
97
                cTree()
98
                {
99
                        lowerBound=0;
100
                        upperBound=1;
101
                }
102

    
103
                bool leafSetContainsParent(cNode* parent) const
104
                {
105
                        bool res=*bfsVisitList.begin()==parent;
106
#ifdef DEBUG
107
                        std::cout << "Is parent really always at beginning of list?" << std::endl;
108
                        bool checkedRes=false;
109
                        for(nodeSet_t::iterator it=bfsVisitList.begin();it!=bfsVisitList.end();it++)
110
                        {
111
                                if(*it==parent) checkedRes=true;
112
                        }
113
                        assert(res==checkedRes);
114
#endif
115
                        return res;
116
                }
117

    
118
                /**
119
                 * Adding a node into the tree.
120
                 * @param parent The parent node in the tree. If parent==NULL, the new node will
121
                 *               be inserted as one of the roots of the tree (forest)
122
                 * @param eventType The OMNeT++ message kind
123
                 * @param moduleId The module the event takes place at
124
                 * @param probabilityDistribution The PDF to be stored inside the node
125
                 * @param isConflicting Whether this node is a conflicting node, i.e. an event on this
126
                 *                      node would conflict with the pending event since the pending event
127
                 *                      takes place at the same module.
128
                 */
129
                void addNode(cNode* parent, evType_t* const evType,pdf_t probabilityDistribution, bool isConflicting)
130
                {
131
                        cNode* newNode=new cNode(evType,isConflicting,probabilityDistribution);
132
                        const double dangerProb=newNode->getProbability();
133
                        upperBound=1-(1-upperBound)*(1-dangerProb);
134
                        if(isConflicting) lowerBound=1-(1-lowerBound)*(1-dangerProb);
135
                        bfsVisitList.push_back(newNode);
136
                }
137

    
138
                // Performing BFS and spanning the tree:
139
                bool bfs(double threshold, int moduleId)
140
                {
141
                        nodeSet_t::iterator it;
142
                        for(int i=0; i<MAX_IT && (it=bfsVisitList.begin()) != bfsVisitList.end(); i++)
143
                        {
144
                                cNode* node=*it;
145
                                bfsVisitList.erase(it);
146
                                if(node->isConflicting())
147
                                {
148
                                        continue;
149
                                }
150
                                else
151
                                {
152
                                        upperBound=1-(1-upperBound)/(1-node->getProbability());
153
                                }
154
                                succList_t succs=node->getSuccessors();
155
                                for(succList_t::iterator succ=succs.begin();succ!=succs.end();++succ)
156
                                {
157
                                        // We need to convolve the PDF of the (previous) leaf node with the PDF of its successors:
158
                                        //pdf_t convolvedPdf=node->getProbabilityDistribution()+succ->getProbabilityDistribution();
159
                                        pdf_t convolvedPdf=succ->getProbabilityDistributionCopy();
160
                                        convolvedPdf+=node->getProbabilityDistribution();
161
                                        evType_t* succEvType=succ->getEvType();
162
                                        int succModId=succ->getEvType()->getModId();
163
                                        bool isConflicting=moduleId==succModId;
164
                                        // We add the new node as a child of the leaf into the tree:
165
                                        addNode(node,succEvType,convolvedPdf,isConflicting);
166
                                        // If both bounds for the probability are below (above) the threshold,
167
                                        // the probability itself is also below (above) the threshold,
168
                                        // i.e. we can yield the decision without further inspecting the BFS tree.
169
                                        if(lowerBound<=threshold && upperBound<=threshold) return true;
170
                                        if(lowerBound>=threshold && upperBound>=threshold) return false;
171
                                }
172
                                node->releaseSuccListLock();
173
                        }
174
                        if(lowerBound<=threshold && upperBound<=threshold) return true;
175
                        return false; // be pessimistic
176
                }
177
};
178

    
179
/**
180
 * This function will be executed whenever the event scheduler encounters
181
 * an event that cannot be executed conservatively at that moment. In this
182
 * case the heuristic computes a probability for a causal violation to occur /
183
 * to not occur, and returns a recommendation whether to execute the event
184
 * speculatively (return value=true) or not (return value=false).
185
 * @param pendingEv The pending event (message in OMNeT++).
186
 * @param setO The set $O$ of currently executed events.
187
 * @param threshold The threshold to compare against.
188
 * @return true iff recommendation for speculative execution is positive.
189
 */
190
bool cHeuristic::askHeuristic(const cMessage* const pendingEv,eventSet_t setO,double threshold)
191
{
192
        cTree bfsTree;
193
        int pendingEvModId=pendingEv->getArrivalModuleId();
194

    
195
        for (eventSet_t::iterator it=setO.begin();it!=setO.end();++it)
196
        {
197
                evType_t* runningEvType=it->getEvType();
198
                int runningEvModId=it->getEvModId();
199
                bool isConflicting=pendingEvModId==runningEvModId;
200
                pdf_t pdf(it->getArrivalTime()-pendingEv->getArrivalTime());
201
                bfsTree.addNode(NULL,runningEvType,pdf,isConflicting);
202
        }
203

    
204
        return bfsTree.bfs(threshold,pendingEvModId);
205
}
206