Line data    Source code

       1             : #ifndef SPSECTTASKGROUP_HPP
       2             : #define SPSECTTASKGROUP_HPP
       3             : 
       4             : #include <vector>
       5             : #include <set>
       6             : #include <queue>
       7             : #include <algorithm>
       8             : #include <cassert>
       9             : 
      10             : #include "Task/SpAbstractTask.hpp"
      11             : #include "Speculation/SpSpeculativeModel.hpp"
      12             : #include "Utils/small_vector.hpp"
      13             : 
      14             : template <SpSpeculativeModel SpecModel>
      15             : class SpGeneralSpecGroup{
      16             : protected:
      17             :     enum class States{
      18             :         UNDEFINED,
      19             :         DO_NOT_SPEC,
      20             :         DO_SPEC
      21             :     };
      22             : 
      23             :     enum class SpecResult{
      24             :         UNDEFINED,
      25             :         SPECULATION_FAILED,
      26             :         SPECULATION_SUCCED
      27             :     };
      28             : 
      29             :     //////////////////////////////////////////////////////////////
      30             : 
      31             :     small_vector<SpGeneralSpecGroup*> parentGroups;
      32             : 
      33             :     int counterParentResults;
      34             :     SpecResult parentSpeculationResults;
      35             :     SpecResult selfSpeculationResults;
      36             : 
      37             :     small_vector<SpGeneralSpecGroup*> subGroups;
      38             : 
      39             :     std::atomic<States> state;
      40             : 
      41             :     small_vector<SpAbstractTask*> copyTasks;
      42             :     SpAbstractTask* mainTask;
      43             :     SpAbstractTask* specTask;
      44             :     small_vector<SpAbstractTask*> selectTasks;
      45             : 
      46             :     SpProbability selfProbability;
      47             : 
      48             :     bool isSpeculatif;
      49             :     
      50             :     std::shared_ptr<std::atomic<size_t>> numberOfSpeculativeSiblingSpecGroupsCounter;
      51             : 
      52             :     //////////////////////////////////////////////////////////////////
      53             : 
      54         672 :     static void EnableAllTasks(const small_vector_base<SpAbstractTask*>& inTasks){
      55         672 :         for(auto* ptr : inTasks){
      56           0 :             ptr->setEnabled(SpTaskActivation::ENABLE);
      57             :         }
      58         672 :     }
      59             : 
      60          46 :     static void DisableAllTasks(const small_vector_base<SpAbstractTask*>& inTasks){
      61          99 :         for(auto* ptr : inTasks){
      62          53 :             ptr->setEnabled(SpTaskActivation::DISABLE);
      63             :         }
      64          46 :     }
      65             :     
      66          35 :     static void DisableTasksDelegate(const small_vector_base<SpAbstractTask*>& inTasks){
      67          92 :         for(auto* ptr : inTasks){
      68          57 :             ptr->setEnabledDelegate(SpTaskActivation::DISABLE);
      69             :         }
      70          35 :     }
      71             : 
      72             :     static void DisableIfPossibleAllTasks(const small_vector_base<SpAbstractTask*>& inTasks){
      73             :         for(auto* ptr : inTasks){
      74             :             ptr->setDisabledIfNotOver();
      75             :         }
      76             :     }
      77             : 
      78             :     //////////////////////////////////////////////////////////////////
      79             : 
      80             : public:
      81         336 :     SpGeneralSpecGroup(const bool inIsSpeculatif, std::shared_ptr<std::atomic<size_t>>& inNumberOfSpeculativeSiblingSpecGroupsCounter) :
      82             :         counterParentResults(0),
      83             :         parentSpeculationResults(SpecResult::UNDEFINED),
      84             :         selfSpeculationResults(SpecResult::UNDEFINED),
      85             :         state(States::UNDEFINED),
      86             :         mainTask(nullptr), specTask(nullptr),
      87             :         isSpeculatif(inIsSpeculatif),
      88         336 :         numberOfSpeculativeSiblingSpecGroupsCounter(inNumberOfSpeculativeSiblingSpecGroupsCounter){
      89         336 :     }
      90             :     
      91         672 :     virtual ~SpGeneralSpecGroup(){
      92         336 :         assert(isSpeculationDisable() || (didParentSpeculationSucceed() && counterParentResults == int(parentGroups.size())) 
      93             :                 || !didParentSpeculationSucceed());
      94        1008 :     }
      95             : 
      96             :     /////////////////////////////////////////////////////////////////////////
      97             : 
      98         183 :     void setProbability(const SpProbability& inSelfProbability){
      99         183 :         selfProbability = inSelfProbability;
     100         183 :     }
     101             : 
     102           0 :     SpProbability getAllProbability(){
     103           0 :         SpProbability proba;
     104             : 
     105           0 :         std::set<SpGeneralSpecGroup*> groupsIncluded;
     106           0 :         std::queue<SpGeneralSpecGroup*> toProceed;
     107             : 
     108           0 :         toProceed.push(this);
     109           0 :         groupsIncluded.insert(this);
     110             : 
     111           0 :         while(toProceed.size()){
     112           0 :             SpGeneralSpecGroup* currentGroup = toProceed.front();
     113           0 :             toProceed.pop();
     114             : 
     115           0 :             proba.append(currentGroup->selfProbability);
     116             : 
     117           0 :             for(auto* parent : parentGroups){
     118           0 :                 if(groupsIncluded.find(parent) == groupsIncluded.end()){
     119           0 :                     toProceed.push(parent);
     120           0 :                     groupsIncluded.insert(parent);
     121             :                 }
     122             :             }
     123           0 :             for(auto* child : subGroups){
     124           0 :                 if(groupsIncluded.find(child) == groupsIncluded.end()){
     125           0 :                     toProceed.push(child);
     126           0 :                     groupsIncluded.insert(child);
     127             :                 }
     128             :             }
     129             :         }
     130             : 
     131           0 :         return proba;
     132             :     }
     133             : 
     134             :     /////////////////////////////////////////////////////////////////////////
     135             : 
     136         336 :     void setSpeculationActivationCore(const bool inIsSpeculationEnable){
     137         336 :         assert(isSpeculationEnableOrDisable() == false);
     138             :         
     139         336 :         if(inIsSpeculationEnable){
     140         336 :             state = States::DO_SPEC;
     141         336 :             if(isSpeculationResultUndefined()) {
     142         336 :                 if(mainTask){
     143           0 :                     assert(mainTask->isOver() == false);
     144           0 :                     if(isSpeculatif){
     145           0 :                         mainTask->setEnabled(SpTaskActivation::DISABLE);
     146             :                     }
     147             :                     else{
     148           0 :                         mainTask->setEnabled(SpTaskActivation::ENABLE);
     149             :                     }
     150             :                 }
     151             : 
     152         336 :                 if(specTask){
     153           0 :                     assert(isSpeculatif);
     154           0 :                     assert(specTask->isOver() == false);
     155           0 :                     specTask->setEnabled(SpTaskActivation::ENABLE);
     156             :                 }
     157             : 
     158         336 :                 EnableAllTasks(copyTasks);
     159         336 :                 EnableAllTasks(selectTasks);
     160             :             }
     161             :         } else {
     162           0 :             state = States::DO_NOT_SPEC;
     163             :         }
     164         336 :     }
     165             : 
     166         227 :     void setSpeculationActivation(const bool inIsSpeculationEnable){
     167         227 :         assert(isSpeculationEnableOrDisable() == false);
     168             : 
     169         454 :         std::set<SpGeneralSpecGroup*> groupsIncluded;
     170         454 :         std::queue<SpGeneralSpecGroup*> toProceed;
     171             : 
     172         227 :         toProceed.push(this);
     173         227 :         groupsIncluded.insert(this);
     174             : 
     175         454 :         while(toProceed.size()){
     176         227 :             SpGeneralSpecGroup* currentGroup = toProceed.front();
     177         227 :             toProceed.pop();
     178             : 
     179         227 :             assert(currentGroup->isSpeculationEnableOrDisable() == false);
     180         227 :             currentGroup->setSpeculationActivationCore(inIsSpeculationEnable);
     181         227 :             assert(currentGroup->isSpeculationEnableOrDisable() == true);
     182             : 
     183         227 :             for(auto* parent : currentGroup->parentGroups){
     184           0 :                 if(groupsIncluded.find(parent) == groupsIncluded.end()
     185           0 :                         && parent->isSpeculationEnableOrDisable() == false){
     186           0 :                     toProceed.push(parent);
     187           0 :                     groupsIncluded.insert(parent);
     188             :                 }
     189             :             }
     190         227 :             for(auto* child : currentGroup->subGroups){
     191           0 :                 if(groupsIncluded.find(child) == groupsIncluded.end()
     192           0 :                         && child->isSpeculationEnableOrDisable() == false){
     193           0 :                     toProceed.push(child);
     194           0 :                     groupsIncluded.insert(child);
     195             :                 }
     196             :             }
     197             :         }
     198         227 :     }
     199             : 
     200             :     /////////////////////////////////////////////////////////////////////////
     201             : 
     202        1988 :     bool isSpeculationEnableOrDisable() const {
     203        1988 :         return state != States::UNDEFINED;
     204             :     }
     205             : 
     206         971 :     bool isSpeculationNotSet() const {
     207         971 :         return isSpeculationEnableOrDisable() == false;
     208             :     }
     209             : 
     210        1186 :     bool isSpeculationEnable() const {
     211        1186 :         return state == States::DO_SPEC;
     212             :     }
     213             : 
     214         698 :     bool isSpeculationDisable() const {
     215         698 :         return state == States::DO_NOT_SPEC;
     216             :     }
     217             : 
     218             :     /////////////////////////////////////////////////////////////////////////
     219             : 
     220         177 :     void addSubGroup(SpGeneralSpecGroup* inGroup){
     221         177 :         assert(std::find(subGroups.begin(), subGroups.end(), inGroup) ==  subGroups.end());
     222         177 :         assert(didSpeculationFailed() == false);
     223         177 :         subGroups.push_back(inGroup);
     224         177 :     }
     225             : 
     226         109 :     void addParents(small_vector_base<SpGeneralSpecGroup*> &inParents){
     227         109 :         assert(parentGroups.empty());
     228         109 :         assert(isParentSpeculationResultUndefined());
     229         109 :         assert(isSpeculationResultUndefined());
     230             : 
     231             :         // Put parents into current group's parent list
     232         109 :         parentGroups = std::move(inParents);
     233             : 
     234             :         // Check if one parent has already speculation activated
     235         109 :         bool oneGroupSpecEnable = false;
     236         109 :         for(SpGeneralSpecGroup* gp : parentGroups){
     237         109 :             assert(gp->isSpeculationDisable() == false);
     238         109 :             if(gp->isSpeculationEnable()){
     239         109 :                 oneGroupSpecEnable = true;
     240         109 :                 break;
     241             :             }
     242             :         }
     243             :         // Yes, so activate all parents
     244         109 :         if(oneGroupSpecEnable){
     245         286 :             for(SpGeneralSpecGroup* gp : parentGroups){
     246         177 :                 assert(gp->didSpeculationFailed() == false);
     247         177 :                 assert(gp->didParentSpeculationFailed() == false);
     248             : 
     249         177 :                 if(gp->isSpeculationNotSet()){
     250           0 :                     assert(gp->isSpeculationResultUndefined() == true);
     251           0 :                     assert(gp->isParentSpeculationResultUndefined() == true);
     252             : 
     253           0 :                     gp->setSpeculationActivation(true);
     254             :                 }
     255         177 :                 else if(gp->didAllSpeculationSucceed()){
     256           0 :                     counterParentResults += 1;
     257             :                 }
     258             :             }
     259             : 
     260         109 :             setSpeculationActivationCore(true);
     261             : 
     262             :             // All results from parents are known
     263         109 :             if(counterParentResults == int(parentGroups.size())){
     264           0 :                 parentSpeculationResults = SpecResult::SPECULATION_SUCCED;
     265             :             }
     266             :         }
     267             : 
     268             :         // Put current group into parents' subGroup lists
     269         286 :         for(auto* ptr : parentGroups){
     270         177 :             ptr->addSubGroup(this);
     271             :         }
     272             : 
     273             :         // Simple check
     274         109 :         if(oneGroupSpecEnable){
     275         286 :             for([[maybe_unused]] SpGeneralSpecGroup* gp : parentGroups){
     276         177 :                 assert(gp->isSpeculationEnable());
     277             :             }
     278             :         }
     279             :         else{
     280           0 :             assert(counterParentResults == 0);
     281             :         }
     282         109 :     }
     283             : 
     284             :     /////////////////////////////////////////////////////////////////////////
     285             : 
     286         179 :     void setParentSpecResult(const bool inSpeculationSucceed){
     287         179 :         assert(isSpeculatif);
     288         179 :         assert((isParentSpeculationResultUndefined() && counterParentResults < int(parentGroups.size()))
     289             :                 || didParentSpeculationFailed());
     290         179 :         counterParentResults += 1;
     291             : 
     292         179 :         if(didParentSpeculationFailed()){
     293             :             // We know already that parents failed
     294             :         }
     295         151 :         else if(inSpeculationSucceed == false){
     296             :             // It is new, now we know parents failed
     297          46 :             parentSpeculationResults = SpecResult::SPECULATION_FAILED;
     298             :             // Inform children
     299          75 :             for(auto* child : subGroups){
     300          29 :                 child->setParentSpecResult(false);
     301             :             }
     302          46 :             assert(mainTask->isEnable() == false);
     303          46 :             assert(specTask->isEnable());
     304          46 :             tryToEnableMainTask();
     305          46 :             specTask->setDisabledIfNotOver();
     306          46 :             DisableAllTasks(selectTasks);
     307             :         }
     308         105 :         else if(counterParentResults == int(parentGroups.size())){
     309             :             // All parents are over, and none of them failed, then it is a success!
     310          63 :             parentSpeculationResults = SpecResult::SPECULATION_SUCCED;
     311          63 :             assert(mainTask->isEnable() == false);
     312          63 :             assert(specTask->isEnable());
     313             :             if constexpr(SpecModel == SpSpeculativeModel::SP_MODEL_3) {
     314          24 :                 if(*numberOfSpeculativeSiblingSpecGroupsCounter == 1) {
     315          18 :                     mainTask->getSpecGroup<SpGeneralSpecGroup<SpecModel>>()->setSpeculationCurrentResult(false);
     316             :                 }
     317             :             }
     318          63 :             if(didSpeculationSucceed()){
     319          18 :                 DisableTasksDelegate(selectTasks);
     320             : 
     321          41 :                 for(auto* child : subGroups){
     322          23 :                     child->setParentSpecResult(true);
     323             :                 }
     324             :                 if constexpr(SpecModel != SpSpeculativeModel::SP_MODEL_3) {
     325          13 :                     if(*numberOfSpeculativeSiblingSpecGroupsCounter == 1) {
     326          13 :                         mainTask->getSpecGroup<SpGeneralSpecGroup<SpecModel>>()->setSpeculationCurrentResult(true);
     327             :                     }
     328             :                 }
     329             :             }
     330          45 :             else if(didSpeculationFailed()){
     331             :                 // Already done EnableAllTasks(selectTasks);
     332           6 :                 for(auto* child : subGroups){
     333           2 :                     child->setParentSpecResult(false);
     334             :                 }
     335             :                 if constexpr(SpecModel != SpSpeculativeModel::SP_MODEL_3) {
     336           2 :                     if(*numberOfSpeculativeSiblingSpecGroupsCounter == 1) {
     337           2 :                         mainTask->getSpecGroup<SpGeneralSpecGroup<SpecModel>>()->setSpeculationCurrentResult(false);
     338             :                     }
     339             :                 }
     340             :             }
     341             :         }
     342         179 :     }
     343             : 
     344         159 :     void setSpeculationCurrentResult(const bool inSpeculationSucceed){
     345         159 :         assert(isSpeculationEnable());
     346         159 :         assert((specTask != nullptr &&  parentGroups.size())
     347             :                || (specTask == nullptr &&  parentGroups.empty()));
     348             :         
     349         159 :         if(inSpeculationSucceed){
     350         103 :             selfSpeculationResults = SpecResult::SPECULATION_SUCCED;
     351             :         }
     352             :         else{
     353          56 :             selfSpeculationResults = SpecResult::SPECULATION_FAILED;
     354             :         }
     355             : 
     356         159 :         if(parentGroups.empty()){
     357         100 :             assert(specTask == nullptr);
     358         100 :             assert(selectTasks.size() == 0);
     359             : 
     360         202 :             for(auto* child : subGroups){
     361         102 :                 child->setParentSpecResult(inSpeculationSucceed);
     362             :             }
     363             :         }
     364             :         else{
     365          59 :             assert(isSpeculatif);
     366          59 :             assert(specTask != nullptr);
     367             : 
     368          59 :             if(didParentSpeculationSucceed()){
     369             :                 
     370             :                 if constexpr(SpecModel != SpSpeculativeModel::SP_MODEL_3) {
     371          16 :                     if(*numberOfSpeculativeSiblingSpecGroupsCounter == 1) {
     372          16 :                         mainTask->getSpecGroup<SpGeneralSpecGroup<SpecModel>>()->setSpeculationCurrentResult(inSpeculationSucceed);
     373             :                     }
     374             :                 }
     375             :                 
     376          50 :                 for(auto* child : subGroups){
     377          21 :                     child->setParentSpecResult(inSpeculationSucceed);
     378             :                 }
     379          29 :                 assert(mainTask->isEnable() == false);
     380          29 :                 if(inSpeculationSucceed){
     381          17 :                     DisableTasksDelegate(selectTasks);
     382             :                 }
     383             :             }
     384          30 :             else if(didParentSpeculationFailed()){
     385             :                 // Check
     386           3 :                 for([[maybe_unused]] auto* child : subGroups){
     387           0 :                     assert(child->didParentSpeculationFailed());
     388             :                 }
     389          27 :             }else if(!inSpeculationSucceed) { // if current spec group failed,
     390           8 :                 for(auto* child : subGroups){ // make all children fail right away 
     391           2 :                     child->setParentSpecResult(false);
     392             :                 }
     393             :             }
     394             :             // If parentResult is undefined and current spec group succeeded, we have to wait
     395             :         }
     396         159 :     }
     397             : 
     398             :     ///////////////////////////////////////////////////////////////////////////////////////////
     399             : 
     400         445 :     bool isSpeculationResultUndefined() const{
     401         445 :         return selfSpeculationResults == SpecResult::UNDEFINED;
     402             :     }
     403             : 
     404         288 :     bool isParentSpeculationResultUndefined() const{
     405         288 :         return parentSpeculationResults == SpecResult::UNDEFINED;
     406             :     }
     407             : 
     408        1305 :     bool didSpeculationFailed() const{
     409        1305 :         return selfSpeculationResults == SpecResult::SPECULATION_FAILED;
     410             :     }
     411             : 
     412        1543 :     bool didParentSpeculationFailed() const{
     413        1543 :         return parentSpeculationResults == SpecResult::SPECULATION_FAILED;
     414             :     }
     415             : 
     416          63 :     bool didSpeculationSucceed() const{
     417          63 :         return selfSpeculationResults == SpecResult::SPECULATION_SUCCED;
     418             :     }
     419             : 
     420         815 :     bool didParentSpeculationSucceed() const{
     421         815 :         return parentSpeculationResults == SpecResult::SPECULATION_SUCCED;
     422             :     }
     423             : 
     424         177 :     bool didAllSpeculationSucceed() const{
     425         252 :         return (parentGroups.empty() || parentSpeculationResults == SpecResult::SPECULATION_SUCCED)
     426         252 :                 && selfSpeculationResults == SpecResult::SPECULATION_SUCCED;
     427             :     }
     428             : 
     429             :     ///////////////////////////////////////////////////////////////////////////////////////////
     430             :     
     431         338 :     SpTaskActivation getActivationStateForCopyTasks() {
     432         338 :         assert(didParentSpeculationFailed() == false);
     433         338 :         assert(didSpeculationFailed() == false);
     434         338 :         if(isSpeculationEnable()){
     435         338 :             return SpTaskActivation::ENABLE;
     436             :         }
     437             :         else {
     438           0 :             return SpTaskActivation::DISABLE;
     439             :         }
     440             :     }
     441             :     
     442         227 :     SpTaskActivation getActivationStateForMainTask() {
     443         227 :         if(!isSpeculatif || isSpeculationDisable() || didParentSpeculationFailed()){
     444         151 :             return SpTaskActivation::ENABLE;
     445             :         }
     446             :         else {
     447          76 :             return SpTaskActivation::DISABLE;
     448             :         }
     449             :     }
     450             :     
     451         109 :     SpTaskActivation getActivationStateForSpeculativeTask() {
     452         109 :         assert(didSpeculationFailed() == false);
     453         109 :         assert(isSpeculatif == true);
     454             :         
     455         109 :         if(isSpeculationEnable() && !didParentSpeculationFailed()){
     456         109 :             return SpTaskActivation::ENABLE;
     457             :         }
     458             :         else {
     459           0 :             return SpTaskActivation::DISABLE;
     460             :         }
     461             :     }
     462             :     
     463         147 :     SpTaskActivation getActivationStateForSelectTask(bool isCarryingSurelyWrittenValuesOver) {
     464         147 :         assert(mainTask);
     465         147 :         assert(specTask);
     466         147 :         assert(isSpeculatif == true);
     467             :         
     468         147 :         if(!isSpeculationEnable() || didParentSpeculationFailed()){
     469           0 :             return SpTaskActivation::DISABLE;
     470         147 :         }else if(isSpeculationEnable() && didParentSpeculationSucceed() && didSpeculationSucceed()){
     471           0 :             if(isCarryingSurelyWrittenValuesOver){
     472           0 :                 return SpTaskActivation::ENABLE;
     473             :             } else {
     474           0 :                 return SpTaskActivation::DISABLE;
     475             :             }
     476             :         }else{
     477         147 :             return SpTaskActivation::ENABLE;
     478             :         }
     479             :     }
     480             :     
     481         282 :     void addCopyTask(SpAbstractTask* inPreTask){
     482         282 :         assert(didParentSpeculationFailed() == false);
     483         282 :         assert(didSpeculationFailed() == false);
     484         282 :         assert(inPreTask->isOver() == false);
     485         282 :         copyTasks.push_back(inPreTask);
     486         282 :     }
     487             :     
     488             :     void addCopyTasks(const small_vector_base<SpAbstractTask*>& incopyTasks){
     489             :         copyTasks.reserve(copyTasks.size() + incopyTasks.size());
     490             :         copyTasks.insert(std::end(copyTasks), std::begin(incopyTasks), std::end(incopyTasks));
     491             :     }
     492             : 
     493         336 :     void setMainTask(SpAbstractTask* inMainTask){
     494         336 :         assert(mainTask == nullptr);
     495         336 :         mainTask = inMainTask;
     496         336 :     }
     497             : 
     498         109 :     void setSpecTask(SpAbstractTask* inSpecTask){
     499         109 :         assert(specTask == nullptr);
     500         109 :         specTask = inSpecTask;
     501         109 :     }
     502             : 
     503             :     void addSelectTasks(const small_vector_base<SpAbstractTask*>& inselectTasks){
     504             :         selectTasks.reserve(selectTasks.size() + inselectTasks.size());
     505             :         selectTasks.insert(std::end(selectTasks), std::begin(inselectTasks), std::end(inselectTasks));
     506             :     }
     507             :     
     508         147 :     void addSelectTask(SpAbstractTask* inSelectTask) {
     509         147 :         selectTasks.push_back(inSelectTask);
     510         147 :     }
     511             :     
     512          46 :     void tryToEnableMainTask() {
     513          46 :         (*numberOfSpeculativeSiblingSpecGroupsCounter)--;
     514          46 :         if(*numberOfSpeculativeSiblingSpecGroupsCounter == 0){
     515          17 :             mainTask->setEnabled(SpTaskActivation::ENABLE);
     516             :         }
     517          46 :     }
     518             : };
     519             : 
     520             : 
     521             : 
     522             : #endif
     523             : 
     524             :