Changes between Version 5 and Version 6 of CreditNew

Timestamp:

Nov 3, 2009, 11:38:32 AM (14 years ago)

Author:

davea

Comment:

--

CreditNew

@@ -189 +189 @@
 == Host normalization ==
 
-For a given application,
-all hosts should get the same average granted credit per job.
+Assuming that hosts are sent jobs for a given app uniformly,
+then for a given app
+hosts should get the same average granted credit per job.
 To ensure this, for each application A we maintain the average VNPFC*(A),
 and for each host H we maintain VNPFC*(H, A).
-The "claimed credit" for a given job J is then
+The '''claimed credit''' for a given job J is then
 {{{
 VNPFC(J) * (VNPFC*(A)/VNPFC*(H, A))
 }}}
+
+There are some cases where hosts are not sent jobs uniformly:
+ * job-size matching
+ * GPUGrid.net's scheme for sending some (presumably larger)
+   jobs to GPUs with more processors.
+In these cases we must scale
 
 Notes:
@@ -204 +211 @@
    than average.
  * VNPFC* is averaged over jobs, not hosts.
- * This assumes that all hosts are sent the same distribution of jobs.
-   There are two situations where this is not the case:
-   a) job-size matching, and b) GPUGrid.net's scheme for sending
-   some (presumably larger) jobs to GPUs with more processors.
-   This can be dealt with using app units (see below).
 
 == Computing averages ==
@@ -221 +223 @@
    and we can't let this mess up the average.
 
-In addition, we may as well maintain the standard deviation
-of the quantities,
+In addition, we may as well maintain the variance of the quantities,
 although the current system doesn't use it.
 
 So for each quantity we maintain the following object:
 {{{
+#define MIN_SAMPLES     20
+        // after this many samples, use exponentially averaged version
+#define SAMPLE_WEIGHT   0.001
+        // new samples get this weight in exp avg
+#define SAMPLE_LIMIT    10
+        // cap samples at recent_mean*10
+
 struct STATS {
     int nsamples;
-    double sum;
-    double exp_avg;
+    double mean;
+        double sum_var;
+    double recent_mean;
+        double recent_var;
 
     void update(double sample) {
-    }
-
-    double mean() {
+                if (sample < 0) return;
+                if (nsamples > MIN_SAMPLES) {
+                        if (sample > recent_mean*SAMPLE_LIMIT) {
+                                sample = recent_main*SAMPLE_LIMIT;
+                        }
+                }
+                // see http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance
+                nsamples++;
+                double delta = sample - mean;
+                mean += delta/nsamples;
+                sum_var += delta*(sample-mean);
+
+                if (nsamples < MIN_SAMPLES) {
+                        recent_mean = mean;
+                        recent_var = sum_var/nsamples;
+                } else {
+                        // update recent averages
+                        delta = sample - recent_mean;
+                        recent_mean += SAMPLE_WEIGHT*delta;
+                        double d2 = delta*delta - recent_var;
+                        recent_var += SAMPLE_WEIGHT*d2;
+                }
     }
 };