Changes between Version 5 and Version 6 of CreditNew

Show
Ignore:
Author:
davea (IP: 128.32.18.181)
Timestamp:
11/03/09 11:38:32 (3 weeks ago)
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • CreditNew

    v5 v6  
    189189== Host normalization == 
    190190 
    191 For a given application, 
    192 all hosts should get the same average granted credit per job. 
     191Assuming that hosts are sent jobs for a given app uniformly, 
     192then for a given app 
     193hosts should get the same average granted credit per job. 
    193194To ensure this, for each application A we maintain the average VNPFC*(A), 
    194195and for each host H we maintain VNPFC*(H, A). 
    195 The "claimed credit" for a given job J is then 
     196The '''claimed credit''' for a given job J is then 
    196197{{{ 
    197198VNPFC(J) * (VNPFC*(A)/VNPFC*(H, A)) 
    198199}}} 
     200 
     201There are some cases where hosts are not sent jobs uniformly: 
     202 * job-size matching 
     203 * GPUGrid.net's scheme for sending some (presumably larger) 
     204   jobs to GPUs with more processors. 
     205In these cases we must scale 
    199206 
    200207Notes: 
    204211   than average. 
    205212 * VNPFC* is averaged over jobs, not hosts. 
    206  * This assumes that all hosts are sent the same distribution of jobs. 
    207    There are two situations where this is not the case: 
    208    a) job-size matching, and b) GPUGrid.net's scheme for sending 
    209    some (presumably larger) jobs to GPUs with more processors. 
    210    This can be dealt with using app units (see below). 
    211213 
    212214== Computing averages == 
    221223   and we can't let this mess up the average. 
    222224 
    223 In addition, we may as well maintain the standard deviation 
    224 of the quantities, 
     225In addition, we may as well maintain the variance of the quantities, 
    225226although the current system doesn't use it. 
    226227 
    227228So for each quantity we maintain the following object: 
    228229{{{ 
     230#define MIN_SAMPLES     20 
     231        // after this many samples, use exponentially averaged version 
     232#define SAMPLE_WEIGHT   0.001 
     233        // new samples get this weight in exp avg 
     234#define SAMPLE_LIMIT    10 
     235        // cap samples at recent_mean*10 
     236 
    229237struct STATS { 
    230238    int nsamples; 
    231     double sum; 
    232     double exp_avg; 
     239    double mean; 
     240        double sum_var; 
     241    double recent_mean; 
     242        double recent_var; 
    233243 
    234244    void update(double sample) { 
    235     } 
    236  
    237     double mean() { 
     245                if (sample < 0) return; 
     246                if (nsamples > MIN_SAMPLES) { 
     247                        if (sample > recent_mean*SAMPLE_LIMIT) { 
     248                                sample = recent_main*SAMPLE_LIMIT; 
     249                        } 
     250                } 
     251                // see http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance 
     252                nsamples++; 
     253                double delta = sample - mean; 
     254                mean += delta/nsamples; 
     255                sum_var += delta*(sample-mean); 
     256 
     257                if (nsamples < MIN_SAMPLES) { 
     258                        recent_mean = mean; 
     259                        recent_var = sum_var/nsamples; 
     260                } else { 
     261                        // update recent averages 
     262                        delta = sample - recent_mean; 
     263                        recent_mean += SAMPLE_WEIGHT*delta; 
     264                        double d2 = delta*delta - recent_var; 
     265                        recent_var += SAMPLE_WEIGHT*d2; 
     266                } 
    238267    } 
    239268}; 

If this page is incomplete or incorrect, please edit it or add it to the wiki to-do list. To do this, you must be logged in; click Login or Register above.