Project

General

Profile

Statistics
| Branch: | Revision:

root / src / sim / cheuristic.cc @ f8c033b6

History | View | Annotate | Download (5.21 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
// cNode
29
// cNode::cNode
30
// cNode::getProbability()
31
// cNode::getSuccessors()
32
// cNode::getProbabilityDistribution()
33

    
34
// eventSet_t
35
// eventSet_t::begin()
36
// eventSet_t::end()
37
// eventSet_t::iterator
38
// eventSet_t::iterator::++operator
39
// eventSet_t::iterator::operator!=(eventSet_t::iterator)
40
// eventSet_t::iterator::operator=
41

    
42
// evType_t
43

    
44
// abstractEvent_t
45
// abstractEvent_t eventSet_t::iterator::operator->
46
// evType_t abstractEvent_t::getEvType()
47
// int abstractEvent_t::getEvModId()
48
// pdf_t abstractEvent_t::getProbabilityDistribution()
49

    
50
// pdf_t
51
// pdf_t::pdf_t(simtime_t)
52
// pdf_t::operator+ (=convolution)
53

    
54
typedef std::list<abstractEvent_t> succList_t;
55

    
56
/**
57
 * A tree to perform a BFS and predict the probability
58
 * for a causal violation to occur.
59
 */
60
class cTree
61
{
62
        private:
63
                // Lower and upper bounds for the causal violation probability:
64
                double lowerBound;
65
                double upperBound;
66
                std::list<cNode> leaves;
67

    
68
        public:
69
                /**
70
                 * Constructor for tree
71
                 * The probability for a causal violation resides (obviously) in the interval [0;1].
72
                 */
73
                cTree()
74
                {
75
                        lowerBound=0;
76
                        upperBound=1;
77
                }
78

    
79
                /**
80
                 * Adding a node into the tree.
81
                 * @param parent The parent node in the tree. If parent==NULL, the new node will
82
                 *               be inserted as one of the roots of the tree (forest)
83
                 * @param eventType The OMNeT++ message kind
84
                 * @param moduleId The module the event takes place at
85
                 * @param probabilityDistribution The PDF to be stored inside the node
86
                 * @param isConflicting Whether this node is a conflicting node, i.e. an event on this
87
                 *                      node would conflict with the pending event since the pending event
88
                 *                      takes place at the same module.
89
                 */
90
                void addNode(cNode* parent, evType_t evType, int moduleId, pdf_t probabilityDistribution, bool isConflicting)
91
                {
92
                        cNode newNode(evType,moduleId,probabilityDistribution);
93
                        double dangerProb=newNode->getProbability()
94
                        upperBound=1-(1-upperBound)*(1-dangerProb);
95
                        if(isConflicting) lowerBound=1-(1-lowerBound)*(1-dangerProb);
96
                        if(parent && leaves.contains(parent))
97
                        {
98
                                upperBound=1-(1-upperBound)/(1-parent->getProbability());
99
                                leaves.remove(parent);
100
                        }
101
                        leaves.push_back(newNode);
102
                }
103

    
104
                // Performing BFS and spanning the tree:
105
                bool bfs(double threshold, int moduleId)
106
                {
107
                        for(nodeSet_t::iterator leaf=leaves.begin();leaf!=leaves.end();++leaf)
108
                        {
109
                                if(leaf->isConflicting())
110
                                {
111
                                        continue;
112
                                }
113
                                succList_t succs=leaf->getSuccessors();
114
                                for(succList_t::iterator succ=succs.begin();succ!=succs.end();++succ)
115
                                {
116
                                        // We need to convolve the PDF of the (previous) leaf node with the PDF of its successors:
117
                                        pdf_t convolvedPdf=leaf->getProbabilityDistribution()+succ->getProbabilityDistribution();
118
                                        evType_t succEvType=succ->getEvType();
119
                                        int succModId=succ->getEvModId();
120
                                        bool isConflicting=moduleId==succModId;
121
                                        // We add the new node as a child of the leaf into the tree:
122
                                        addNode(leaf,succEvType,convolvedPdf,isConflicting);
123
                                        // If both bounds for the probability are below (above) the threshold,
124
                                        // the probability itself is also below (above) the threshold,
125
                                        // i.e. we can yield the decision without further inspecting the BFS tree.
126
                                        if(lowerBound<=threshold && upperBound<=threshold) return true;
127
                                        if(lowerBound>=threshold && upperBound>=threshold) return false;
128
                                }
129
                        }
130
                }
131
};
132

    
133
/**
134
 * This function will be executed whenever the event scheduler encounters
135
 * an event that cannot be executed conservatively at that moment. In this
136
 * case the heuristic computes a probability for a causal violation to occur /
137
 * to not occur, and returns a recommendation whether to execute the event
138
 * speculatively (return value=true) or not (return value=false).
139
 * @param pendingEv The pending event (message in OMNeT++).
140
 * @param setO The set $O$ of currently executed events.
141
 * @param threshold The threshold to compare against.
142
 * @return true iff recommendation for speculative execution is positive.
143
 */
144
bool cHeuristic::askHeuristic(cMessage* pendingEv,eventSet_t setO,double threshold)
145
{
146
        cTree bfsTree;
147
        int pendingEvModId=pendingEv->getArrivalModuleId();
148

    
149
        for (eventSet_t::iterator it=setO->begin();it!=setO->end();++it)
150
        {
151
                evType_t runningEvType=it->getEvType();
152
                int runningEvModId=it->getEvModId();
153
                bool isConflicting=pendingEvModId==runningEvModId;
154
                pdf_t pdf(eventInO->arrivalTime()-pendingEvent->arrivalTime());
155
                bfsTree.addNode(NULL,runningEvType,pdf,isConflicting);
156
        }
157

    
158
        return bfsTree.bfs(threshold,pendingEvModId);
159
}
160