Statistics
| Branch: | Revision:

root / src / sim / cheuristic.cc @ a6f5ec85

History | View | Annotate | Download (6.04 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
EventSet::iterator::iterator(const EventSet::iterator& b) :
31
        index(index),
32
        s(s)
33
{
34
}
35

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

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

    
51
                double getProbability()
52
                {
53
                        return pdf.getProbability(0);
54
                }
55

    
56
                succList_t getSuccessors()
57
                {
58
                        return type->getSuccessors();
59
                }
60

    
61
                void releaseSuccListLock()
62
                {
63
                        type->releaseSuccListLock();
64
                }
65

    
66
                const pdf_t& getProbabilityDistribution()
67
                {
68
                        return pdf;
69
                }
70

    
71
                bool isConflicting()
72
                {
73
                        return isConf;
74
                }
75
};
76

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

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

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

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

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

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

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

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