Loading [MathJax]/extensions/tex2jax.js
The Gaudi Framework  v31r0 (aeb156f0)
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
PRGraphVisitors.cpp
Go to the documentation of this file.
1 #include "PRGraphVisitors.h"
2 #include "AlgsExecutionStates.h"
3 
5 #include "GaudiKernel/ICondSvc.h"
6 
7 #include <queue>
8 
9 namespace concurrency {
11 
12  //--------------------------------------------------------------------------
14 
15  if ( AState::CONTROLREADY != m_slot->algsStates[node.getAlgoIndex()] ) return false;
16 
17  return true;
18  }
19 
20  //--------------------------------------------------------------------------
22 
23  bool result = true; // return true if this algorithm has no data inputs
24 
25  for ( auto dataNode : node.getInputDataNodes() ) {
26 
27  result = dataNode->accept( *this );
28 
29  // With ConditionNodes, one may decide NOT to break here so that associated
30  // ConditionAlgorithms are scheduled ASAP. This behavior can be made configurable
31  if ( !result ) break; // skip checking other inputs if this input was not produced yet
32  }
33 
34  if ( result ) {
35  m_slot->algsStates.set( node.getAlgoIndex(), AState::DATAREADY ).ignore();
36 
37  if ( m_trace ) {
38  auto sourceNode = ( m_cause.m_source == Cause::source::Task )
40  : nullptr;
41  node.m_graph->addEdgeToPrecTrace( sourceNode, &node );
42  }
43  }
44 
45  // return true only if an algorithm is promoted to DR
46  return result;
47  }
48 
49  //--------------------------------------------------------------------------
50  bool DataReadyPromoter::visitEnter( DataNode& ) const { return true; }
51 
52  //--------------------------------------------------------------------------
54  /* Implements 'observer' strategy, i.e., only check if producer of this DataNode
55  * has been already executed or not */
56 
57  auto const& producers = node.getProducers();
58  for ( auto algoNode : producers ) {
59  const auto& state = m_slot->algsStates[algoNode->getAlgoIndex()];
60  if ( AState::EVTACCEPTED == state || AState::EVTREJECTED == state ) {
61  return true; // skip checking other producers if one was found to be executed
62  }
63  }
64 
65  // Check parent slot if necessary
66  if ( m_slot->parentSlot ) {
67  for ( auto algoNode : producers ) {
68  const auto& state = m_slot->parentSlot->algsStates[algoNode->getAlgoIndex()];
69  if ( AState::EVTACCEPTED == state || AState::EVTREJECTED == state ) {
70  return true; // skip checking other producers if one was found to be executed
71  }
72  }
73  }
74 
75  // return true only if this DataNode is produced
76  return false;
77  }
78 
79  //--------------------------------------------------------------------------
81 
82  if ( node.m_condSvc->isValidID( *( m_slot->eventContext ), node.getPath() ) )
83  return false; // do not enter this ConditionNode if the condition has bee already loaded
84 
85  return true;
86  }
87 
88  //--------------------------------------------------------------------------
90  /* Implements 'requester' strategy, i.e., requests this ConditionNode to be loaded
91  * by its associated ConditionAlgorithm */
92 
93  auto promoter = Supervisor( *m_slot, m_cause, m_trace );
94 
95  for ( auto condAlg : node.getProducers() ) condAlg->accept( promoter );
96 
97  // this method is called if, and only if, this ConditionNode is not yet produced.
98  // thus, by definition, this ConditionNode is not yet available at this moment
99  return false;
100  }
101 
102  //--------------------------------------------------------------------------
104 
105  auto& states = m_slot->algsStates;
106  const AState& state = states[node.getAlgoIndex()];
107  int decision = -1;
108 
109  if ( true == node.isOptimist() )
110  decision = 1;
111  else if ( AState::EVTACCEPTED == state )
112  decision = !node.isLiar();
113  else if ( AState::EVTREJECTED == state )
114  decision = node.isLiar();
115 
116  if ( -1 != decision ) {
117 
118  m_slot->controlFlowState[node.getNodeIndex()] = decision;
119 
120  auto promoter = DataReadyPromoter( *m_slot, m_cause, m_trace );
121  for ( const auto& output : node.getOutputDataNodes() )
122  for ( auto& consumer : output->getConsumers() ) consumer->accept( promoter );
123 
125  for ( auto& p : node.getParentDecisionHubs() ) p->accept( vis );
126 
127  return true; // return true only if the algorithm produced a decision
128  }
129 
130  return false;
131  }
132 
133  //---------------------------------------------------------------------------
134  bool Supervisor::visitEnter( DecisionNode& node ) const {
135  // Protect against graph traversal escaping from sub-slots
136  if ( m_slot->parentSlot ) {
137  // Examine the ancestry of this node, looking for sub-slot entry point
138  bool canFindExit = false;
139  std::queue<DecisionNode*> allAncestors;
140  allAncestors.push( &node );
141  while ( allAncestors.size() ) {
142 
143  DecisionNode* thisAncestor = allAncestors.front();
144  allAncestors.pop();
145 
146  if ( thisAncestor->getNodeName() == m_slot->entryPoint ) {
147 
148  // This ancestor is the sub-slot exit
149  canFindExit = true;
150  break;
151 
152  } else {
153 
154  // Go further up the node ancestry
155  for ( auto& evenOlder : thisAncestor->m_parents ) { allAncestors.push( evenOlder ); }
156  }
157  }
158 
159  // If the sub-slot entry point is not in this node's ancestry, don't visit the node
160  if ( !canFindExit ) return false;
161  }
162 
163  if ( m_slot->controlFlowState[node.getNodeIndex()] != -1 ) return false;
164  return true;
165  }
166 
167  //---------------------------------------------------------------------------
169 
170  bool foundNonResolvedChild = false;
171  bool foundNegativeChild = false;
172  bool foundPositiveChild = false;
173  int decision = -1;
174 
175  // Leave a sub-slot if this is the exit node
176  EventSlot* oldSlot = nullptr;
177  if ( m_slot->parentSlot && m_slot->entryPoint == node.getNodeName() ) {
178  oldSlot = m_slot;
180  }
181 
182  // If children are in sub-slots, loop over all
183  auto searchResult = m_slot->subSlotsByNode.find( node.getNodeName() );
184  if ( searchResult != m_slot->subSlotsByNode.end() ) {
185  bool breakout = false;
186  for ( unsigned int slotIndex : searchResult->second ) {
187 
188  // Enter the sub-slot
189  m_slot = &( m_slot->allSubSlots[slotIndex] );
190 
191  for ( auto child : node.getDaughters() ) {
192 
193  int& childDecision = m_slot->controlFlowState[child->getNodeIndex()];
194 
195  if ( childDecision == -1 )
196  foundNonResolvedChild = true;
197  else if ( childDecision == 1 )
198  foundPositiveChild = true;
199  else
200  foundNegativeChild = true;
201 
202  if ( node.m_modePromptDecision ) {
203  if ( node.m_modeOR && foundPositiveChild ) {
204  decision = 1;
205  breakout = true;
206  break;
207  } else if ( !node.m_modeOR && foundNegativeChild ) {
208  decision = 0;
209  breakout = true;
210  break;
211  }
212  } else {
213  if ( foundNonResolvedChild ) {
214  breakout = true;
215  break;
216  }
217  }
218  }
219 
220  // Leave the sub-slot
222  if ( breakout ) break;
223  }
224  } else {
225  for ( auto child : node.getDaughters() ) {
226  int& childDecision = m_slot->controlFlowState[child->getNodeIndex()];
227 
228  if ( childDecision == -1 )
229  foundNonResolvedChild = true;
230  else if ( childDecision == 1 )
231  foundPositiveChild = true;
232  else
233  foundNegativeChild = true;
234 
235  if ( node.m_modePromptDecision ) {
236  if ( node.m_modeOR && foundPositiveChild ) {
237  decision = 1;
238  break;
239  } else if ( !node.m_modeOR && foundNegativeChild ) {
240  decision = 0;
241  break;
242  }
243  } else {
244  if ( foundNonResolvedChild ) break;
245  }
246  }
247  } // end monitoring children
248 
249  if ( !foundNonResolvedChild && decision == -1 ) {
250  if ( node.m_modeOR ) { // OR
251  if ( foundPositiveChild )
252  decision = 1;
253  else
254  decision = 0;
255  } else { // AND
256  if ( foundNegativeChild )
257  decision = 0;
258  else
259  decision = 1;
260  }
261  }
262 
263  if ( node.m_inverted && decision == 1 )
264  decision = 0;
265  else if ( node.m_inverted && decision == 0 )
266  decision = 1;
267 
268  if ( node.m_allPass && !foundNonResolvedChild ) decision = 1;
269 
270  if ( decision != -1 ) {
271  m_slot->controlFlowState[node.getNodeIndex()] = decision;
272 
273  // if a decision was made for this node, propagate the result upwards
274  for ( auto parent : node.m_parents ) { parent->accept( *this ); }
275 
276  if ( oldSlot ) m_slot = oldSlot;
277  return true;
278  }
279 
280  // if no decision can be made yet, request further information downwards
281  // Enter subslots for children if needed
282  if ( searchResult != m_slot->subSlotsByNode.end() ) {
283  for ( unsigned int slotIndex : searchResult->second ) {
284 
285  // Enter sub-slot
286  m_slot = &( m_slot->allSubSlots[slotIndex] );
287 
288  for ( auto child : node.getDaughters() ) {
289  bool result = child->accept( *this );
290  if ( !node.m_modeConcurrent )
291  if ( result ) break; // stop on first unresolved child if its decision hub is sequential
292  }
293 
294  // Leave sub-slot
296  }
297  } else {
298  for ( auto child : node.getDaughters() ) {
299  bool result = child->accept( *this );
300  if ( !node.m_modeConcurrent )
301  if ( result ) break; // stop on first unresolved child if its decision hub is sequential
302  }
303  }
304 
305  if ( oldSlot ) m_slot = oldSlot;
306  return false;
307  }
308 
309  //---------------------------------------------------------------------------
310  bool Supervisor::visitEnter( AlgorithmNode& node ) const {
311 
312  if ( m_slot->controlFlowState[node.getNodeIndex()] != -1 ) return false;
313  return true;
314  }
315 
316  //--------------------------------------------------------------------------
318 
319  bool result = false;
320 
321  auto& states = m_slot->algsStates;
322  auto& state = states[node.getAlgoIndex()];
323 
324  // Promote with INITIAL->CR
325  if ( AState::INITIAL == state ) states.set( node.getAlgoIndex(), AState::CONTROLREADY ).ignore();
326 
327  // Try to promote with CR->DR
328  if ( AState::CONTROLREADY == state ) {
329  auto promoter = DataReadyPromoter( *m_slot, m_cause, m_trace );
330  result = promoter.visit( node );
331  } else {
332  result = true;
333  }
334 
335  // return true only when an algorithm is not lower than DR in its FSM
336  // i.e., the visitor has done everything it could with this algorithm
337  return result;
338  }
339 
340  //--------------------------------------------------------------------------
342 
343  auto& products = node.getOutputDataNodes();
344  float rank = 0;
345 
346  for ( auto p : products ) rank += p->getConsumers().size();
347 
348  node.setRank( rank );
349  /*std::stringstream s;
350  s << node.getNodeName() << ", " << rank << "\n";
351  std::ofstream myfile;
352  myfile.open("AlgoRank.csv", std::ios::app);
353  myfile << s.str();
354  myfile.close();*/
355 
356  return true;
357  }
358 
359  //--------------------------------------------------------------------------
361 
362  std::ifstream myfile;
363  myfile.open( "InputExecutionPlan.graphml", std::ios::in );
364 
365  precedence::PrecTrace execPlan;
366 
367  using boost::get;
369 
370  boost::dynamic_properties dp;
371  dp.property( "name", get( &AlgoTraceProps::m_name, execPlan ) );
372  dp.property( "index", get( &AlgoTraceProps::m_index, execPlan ) );
373  dp.property( "dataRank", get( &AlgoTraceProps::m_rank, execPlan ) );
374  dp.property( "runtime", get( &AlgoTraceProps::m_runtime, execPlan ) );
375 
376  boost::read_graphml( myfile, execPlan, dp );
377 
378  typedef boost::graph_traits<precedence::PrecTrace>::vertex_iterator itV;
380 
381  for ( vp = boost::vertices( execPlan ); vp.first != vp.second; ++vp.first ) {
382  precedence::AlgoTraceVertex v = *vp.first;
383  auto index = get( &AlgoTraceProps::m_name, execPlan );
384  if ( index[v] == node.getNodeName() ) {
385  runThroughAdjacents( v, execPlan );
386  float rank = m_nodesSucceeded;
387  node.setRank( rank );
388  reset();
389  // std::cout << "Rank of " << index[v] << " is " << rank << std::endl;
390  }
391  }
392 
393  return true;
394  }
395 
396  //--------------------------------------------------------------------------
398  boost::graph_traits<precedence::PrecTrace>::vertex_descriptor vertex, precedence::PrecTrace graph ) {
399  typename boost::graph_traits<precedence::PrecTrace>::adjacency_iterator itVB;
400  typename boost::graph_traits<precedence::PrecTrace>::adjacency_iterator itVE;
401 
402  for ( boost::tie( itVB, itVE ) = adjacent_vertices( vertex, graph ); itVB != itVE; ++itVB ) {
403  m_nodesSucceeded += 1;
404  runThroughAdjacents( *itVB, graph );
405  }
406  }
407 
408  //--------------------------------------------------------------------------
410 
411  std::ifstream myfile;
412  myfile.open( "InputExecutionPlan.graphml", std::ios::in );
413 
414  precedence::PrecTrace execPlan;
415  using boost::get;
417 
418  boost::dynamic_properties dp;
419  dp.property( "name", get( &AlgoTraceProps::m_name, execPlan ) );
420  dp.property( "index", get( &AlgoTraceProps::m_index, execPlan ) );
421  dp.property( "dataRank", get( &AlgoTraceProps::m_rank, execPlan ) );
422  dp.property( "runtime", get( &AlgoTraceProps::m_runtime, execPlan ) );
423 
424  boost::read_graphml( myfile, execPlan, dp );
425 
426  typedef boost::graph_traits<precedence::PrecTrace>::vertex_iterator itV;
428 
429  for ( vp = boost::vertices( execPlan ); vp.first != vp.second; ++vp.first ) {
430  precedence::AlgoTraceVertex v = *vp.first;
431  auto index = get( &AlgoTraceProps::m_name, execPlan );
432  if ( index[v] == node.getNodeName() ) {
433  auto index_runtime = get( &AlgoTraceProps::m_runtime, execPlan );
434  float rank = index_runtime[v];
435  node.setRank( rank );
436  // std::cout << "Rank of " << index[v] << " is " << rank << std::endl;
437  }
438  }
439  return true;
440  }
441 
442  //--------------------------------------------------------------------------
444 
445  std::ifstream myfile;
446  myfile.open( "Eccentricity.graphml", std::ios::in );
447 
448  precedence::PrecTrace execPlan;
449 
450  boost::dynamic_properties dp;
451  using boost::get;
452 
453  dp.property( "name", get( &precedence::AlgoTraceProps::m_name, execPlan ) );
454  dp.property( "Eccentricity", get( &precedence::AlgoTraceProps::m_eccentricity, execPlan ) );
455 
456  boost::read_graphml( myfile, execPlan, dp );
457 
458  typedef boost::graph_traits<precedence::PrecTrace>::vertex_iterator itV;
460 
461  for ( vp = boost::vertices( execPlan ); vp.first != vp.second; ++vp.first ) {
462  precedence::AlgoTraceVertex v = *vp.first;
463  auto index = get( &precedence::AlgoTraceProps::m_name, execPlan );
464  if ( index[v] == node.getNodeName() ) {
465  auto index_eccentricity = get( &precedence::AlgoTraceProps::m_eccentricity, execPlan );
466  float rank = index_eccentricity[v];
467  node.setRank( rank );
468  // std::cout << "Rank of " << index[v] << " is " << rank << std::endl;
469  }
470  }
471  return true;
472  }
473 
474  //--------------------------------------------------------------------------
476 
477  // Find eccentricity of the node (only within the data realm of the execution flow graph)
478  recursiveVisit( node );
479 
480  float rank = m_maxKnownDepth;
481  node.setRank( rank );
482 
483  // Reset visitor for next nodes, if any
484  reset();
485 
486  return true;
487  }
488 
489  //--------------------------------------------------------------------------
491 
492  m_currentDepth += 1;
493 
494  auto& products = node.getOutputDataNodes();
495 
496  if ( products.empty() )
497  if ( ( m_currentDepth - 1 ) > m_maxKnownDepth ) m_maxKnownDepth = m_currentDepth - 1;
498 
499  for ( auto p : products )
500  for ( auto algoNode : p->getConsumers() ) recursiveVisit( *algoNode );
501 
502  m_currentDepth -= 1;
503  }
504 
505  //---------------------------------------------------------------------------
507 
508  if ( m_slot->controlFlowState[node.getNodeIndex()] != 1 ) return true;
509  return false;
510  }
511 
512  //---------------------------------------------------------------------------
514 
515  bool allChildDecisionsResolved = true;
516 
517  for ( const auto& child : node.getDaughters() ) {
518 
519  child->accept( *this );
520 
521  int childDecision = m_slot->controlFlowState[child->getNodeIndex()];
522  if ( childDecision == -1 ) allChildDecisionsResolved = false;
523 
524  // process children sequentially if their decision hub is sequential
525  if ( !node.m_modeConcurrent && childDecision == -1 ) return false;
526 
527  if ( childDecision == 1 && node.m_modeOR && node.m_modePromptDecision ) {
528  m_slot->controlFlowState[node.getNodeIndex()] = 1;
529 
530  // if a decision was made for this node, propagate the result upwards
531  for ( auto parent : node.m_parents ) { parent->accept( *this ); }
532  return true;
533  }
534  }
535 
536  if ( allChildDecisionsResolved ) {
537  m_slot->controlFlowState[node.getNodeIndex()] = 1;
538 
539  // if a decision was made for this node, propagate the result upwards
540  for ( auto parent : node.m_parents ) { parent->accept( *this ); }
541  }
542 
543  return allChildDecisionsResolved;
544  }
545 
546  //---------------------------------------------------------------------------
548 
549  if ( m_slot->controlFlowState[node.getNodeIndex()] != 1 ) return true;
550  return false;
551  }
552 
553  //--------------------------------------------------------------------------
555 
556  auto& states = m_slot->algsStates;
557  int& decision = m_slot->controlFlowState[node.getNodeIndex()];
558 
559  auto dataPromoter = DataReadyPromoter( *m_slot, m_cause );
560 
561  if ( AState::INITIAL == states[node.getAlgoIndex()] ) {
562  states.set( node.getAlgoIndex(), AState::CONTROLREADY );
563  if ( dataPromoter.visit( node ) ) {
564  states.set( node.getAlgoIndex(), AState::SCHEDULED );
565  states.set( node.getAlgoIndex(), AState::EVTACCEPTED );
566  decision = 1;
567  ++m_nodesSucceeded;
568  // std::cout << "Algorithm decided: " << node.getNodeName() << std::endl;
569  return true;
570  }
571  } else if ( AState::CONTROLREADY == states[node.getAlgoIndex()] && dataPromoter.visit( node ) ) {
572  states.set( node.getAlgoIndex(), AState::SCHEDULED );
573  states.set( node.getAlgoIndex(), AState::EVTACCEPTED );
574  decision = 1;
575  ++m_nodesSucceeded;
576  // std::cout << "Algorithm decided: " << node.getNodeName() << std::endl;
577  return true;
578  }
579 
580  return false;
581  }
582 } // namespace concurrency
const unsigned int & getAlgoIndex() const
Get algorithm index.
std::string entryPoint
Event Views bookkeeping (TODO: optimize view bookkeeping)
Definition: EventSlot.h:84
Class representing an event slot.
Definition: EventSlot.h:14
std::vector< DecisionNode * > m_parents
Direct parent nodes.
T open(T...args)
bool visit(AlgorithmNode &) override
boost::graph_traits< PrecTrace >::vertex_descriptor AlgoTraceVertex
const std::vector< DataNode * > & getInputDataNodes() const
Get all consumer nodes.
bool isOptimist() const
Check if positive control flow decision is enforced.
T front(T...args)
void setRank(float &rank)
Set Algorithm rank.
T pop(T...args)
bool visit(AlgorithmNode &) override
void recursiveVisit(AlgorithmNode &)
Depth-first node parser to calculate node eccentricity (only within the data realm of the precedence ...
const std::vector< DataNode * > & getOutputDataNodes() const
Get all supplier nodes.
std::vector< int > controlFlowState
State of the control flow.
Definition: EventSlot.h:77
std::vector< EventSlot > allSubSlots
Actual sub-slot instances.
Definition: EventSlot.h:90
bool m_allPass
Whether always passing regardless of daughter results.
const std::vector< DecisionNode * > & getParentDecisionHubs() const
Get all parent decision hubs.
T push(T...args)
bool visit(DecisionNode &) override
bool visitEnter(AlgorithmNode &) const override
bool visit(AlgorithmNode &) override
bool visitEnter(DecisionNode &) const override
bool m_modeOR
Whether acting as "and" (false) or "or" node (true)
bool visit(AlgorithmNode &) override
PrecedenceRulesGraph * m_graph
bool visitEnter(DecisionNode &) const override
DataReadyPromoter(EventSlot &slot, const Cause &cause, bool ifTrace=false)
Constructor.
const DataObjID & getPath()
const std::vector< ControlFlowNode * > & getDaughters() const
Get children nodes.
StatusCode set(unsigned int iAlgo, State newState)
bool visit(AlgorithmNode &) override
void runThroughAdjacents(boost::graph_traits< precedence::PrecTrace >::vertex_descriptor, precedence::PrecTrace)
boost::adjacency_list< boost::vecS, boost::vecS, boost::bidirectionalS, AlgoTraceProps > PrecTrace
virtual bool isValidID(const EventContext &ctx, const DataObjID &id) const =0
check to see if a specific condition object ID is valid for this event
State
Execution states of the algorithms.
bool m_modePromptDecision
Whether to evaluate the hub decision ASA its child decisions allow to do that.
void addEdgeToPrecTrace(const AlgorithmNode *u, const AlgorithmNode *v)
set cause-effect connection between two algorithms in the precedence trace
bool visit(DecisionNode &) override
T find(T...args)
T size(T...args)
STL class.
bool m_modeConcurrent
Whether all daughters will be evaluated concurrently or sequentially.
EventSlot * parentSlot
Pointer to parent slot (null for top level)
Definition: EventSlot.h:86
bool visit(AlgorithmNode &) override
bool m_inverted
Whether the selection result is negated or not.
bool isLiar() const
Check if control flow logic is always inverted.
bool visit(AlgorithmNode &) override
const std::string & getNodeName() const
Get node name.
const unsigned int & getNodeIndex() const
Get node index.
std::unordered_map< std::string, std::vector< unsigned int > > subSlotsByNode
Listing of sub-slots by the node (name) they are attached to.
Definition: EventSlot.h:88
AlgorithmNode * getAlgorithmNode(const std::string &algoName) const
Get the AlgorithmNode from by algorithm name using graph index.
STL class.
std::unique_ptr< EventContext > eventContext
Cache for the eventContext.
Definition: EventSlot.h:73
std::string m_sourceName
const std::vector< AlgorithmNode * > & getProducers() const
Get all data object producers.
AlgsExecutionStates algsStates
Vector of algorithms states.
Definition: EventSlot.h:75