context_bound_scheduler.hpp - medfall - A super great game engine

context_bound_scheduler.hpp (4774B)
      1 /*  Relacy Race Detector
      2  *  Copyright (c) 2008-2013, Dmitry S. Vyukov
      3  *  All rights reserved.
      4  *  This software is provided AS-IS with no warranty, either express or implied.
      5  *  This software is distributed under a license and may not be copied,
      6  *  modified or distributed except as expressly authorized under the
      7  *  terms of the license contained in the file LICENSE in this distribution.
      8  */
      9 
     10 #ifndef RL_CONTEXT_BOUND_SCHEDULER_HPP
     11 #define RL_CONTEXT_BOUND_SCHEDULER_HPP
     12 #ifdef _MSC_VER
     13 #   pragma once
     14 #endif
     15 
     16 #include "base.hpp"
     17 #include "full_search_scheduler.hpp"
     18 #include "foreach.hpp"
     19 
     20 
     21 namespace rl
     22 {
     23 
     24 
     25 template<thread_id_t thread_count>
     26 struct context_bound_scheduler_thread_info : tree_search_scheduler_thread_info<thread_count>
     27 {
     28     unsigned sched_count_;
     29     unsigned forced_context_switch_count_;
     30 
     31     void reset(test_params& params)
     32     {
     33         tree_search_scheduler_thread_info<thread_count>::reset(params);
     34         sched_count_ = 0;
     35         forced_context_switch_count_ = 0;
     36     }
     37 };
     38 
     39 
     40 
     41 
     42 template<thread_id_t thread_count>
     43 class context_bound_scheduler
     44     : public tree_search_scheduler<context_bound_scheduler<thread_count>
     45         , context_bound_scheduler_thread_info<thread_count>, thread_count>
     46 {
     47 public:
     48     typedef tree_search_scheduler<context_bound_scheduler<thread_count>
     49         , context_bound_scheduler_thread_info<thread_count>, thread_count> base_t;
     50     typedef typename base_t::thread_info_t thread_info_t;
     51     typedef typename base_t::shared_context_t shared_context_t;
     52 
     53     context_bound_scheduler(test_params& params, shared_context_t& ctx, thread_id_t dynamic_thread_count)
     54         : base_t(params, ctx, dynamic_thread_count)
     55     {
     56     }
     57 
     58     thread_id_t iteration_begin_impl()
     59     {
     60         switches_remain_ = this->params_.context_bound;
     61         return base_t::iteration_begin_impl();
     62     }
     63 
     64     bool can_switch(thread_info_t& t)
     65     {
     66         t.sched_count_ += 1;
     67         return switches_remain_ != 0;
     68     }
     69 
     70     void on_switch(thread_info_t& t)
     71     {
     72         if (t.state_ == thread_state_running)
     73         {
     74             RL_VERIFY(switches_remain_);
     75             switches_remain_ -= 1;
     76         }
     77         else
     78         {
     79             t.forced_context_switch_count_ += 1;
     80         }
     81     }
     82 
     83     double iteration_count_approx()
     84     {
     85         return 1.0;
     86         /*
     87         iteration_t const P = thread_count;
     88         iteration_t const C0 = this->params_.context_bound;
     89         iteration_t total = 1;//factorial(P);// * power(P, P * C0);
     90         for (iteration_t i = 0; i != P - 1; ++i)
     91             total *= power(i + 1, C0 + 1);
     92         //if (C0)
     93         //    total *= power(P - 1, P - 1);
     94         if (val(P) > 1)
     95         {
     96             for (iteration_t i = 0; i != P; ++i)
     97             {
     98                 iteration_t const N = this->threads_[i].sched_count_;
     99                 iteration_t const C = C0 + this->threads_[i].forced_context_switch_count_;
    100                 //total *= (iteration_t)pow((double)(threads_[i].sched_count_ + 2) * (thread_count - 1), (int)(params_.context_bound + threads_[i].forced_context_switch_count_));
    101                 total *= factorial(N, C) / factorial(C);
    102                 //C$ += C + 1;
    103                 //total *= (int)(params_.context_bound + threads_[i].forced_context_switch_count_));
    104             }
    105             //total *= factorial(C$);
    106         }
    107         else
    108         {
    109             total = 1;
    110         }
    111         //iteration_t total = (iteration_t)pow((double)sched_count / thread_count + 1, (int)(params_.context_bound * thread_count + forced_context_switch_mean_ + 0.5));
    112         //total *= thread_count;
    113         //total *= (iteration_t)pow((double)thread_count - 1, thread_count);
    114         for (size_t i = 0; i != this->stree_.size(); ++i)
    115         {
    116             if (this->stree_[i].type_ != sched_type_sched)
    117             {
    118                 total *= this->stree_[i].count_;
    119             }
    120         }
    121         return (double)total;
    122         */
    123     }
    124 
    125 private:
    126     unsigned switches_remain_;
    127 
    128     template<typename T>
    129     static T factorial(T x, T i)
    130     {
    131         if (0 == i)
    132             return 1;
    133         T r = x;
    134         for (--i; i; --i)
    135             r *= x - i;
    136         return r;
    137     }
    138 
    139     template<typename T>
    140     static T factorial(T x)
    141     {
    142         if (0 == x)
    143             return 1;
    144         T r = x;
    145         for (T i = x - 1; i; --i)
    146             r *= i;
    147         return r;
    148     }
    149 
    150     template<typename T>
    151     static T power(T x, T y)
    152     {
    153         if (0 == y)
    154             return 1;
    155         T r = x;
    156         for (T i = y - 1; i; --i)
    157             r *= x;
    158         return r;
    159     }
    160 
    161     RL_NOCOPY(context_bound_scheduler);
    162 };
    163 
    164 
    165 }
    166 
    167 #endif
    168