rcutorture: Do better bin packing
Running the standard set of rcutorture tests on 24 CPUs results in
the following sub-optimal schedule:
----start batch----
TREE07 16
----start batch----
TREE08 16
SRCU-P 8
----start batch----
TREE01 8
TREE02 8
TREE03 8
----start batch----
TREE04 8
TREE05 8
TREE06 8
----start batch----
SRCU-N 4
TINY01 1
TINY02 1
TREE09 1
If one of the eight-CPU runs were to be moved into the first batch,
the test suite would complete in four batches rather than five.
This commit therefore uses a greedy algorithm to re-order the test
entries so that the sequential batching will produce an optimal schedule
in this case:
----start batch----
TREE07 16
SRCU-P 8
----start batch----
TREE08 16
TREE01 8
----start batch----
TREE02 8
TREE03 8
TREE04 8
----start batch----
TREE05 8
TREE06 8
SRCU-N 4
TINY01 1
TINY02 1
TREE09 1
Please note that this is still not an optimal bin-packing algorithm,
however, it does produce optimal solutions for most common scenarios.
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Reviewed-by: Josh Triplett <josh@joshtriplett.org>
diff --git a/tools/testing/selftests/rcutorture/bin/kvm.sh b/tools/testing/selftests/rcutorture/bin/kvm.sh
index ad3779c..18649b8 100644
--- a/tools/testing/selftests/rcutorture/bin/kvm.sh
+++ b/tools/testing/selftests/rcutorture/bin/kvm.sh
@@ -214,7 +214,42 @@
done
sort -k2nr $T/cfgcpu > $T/cfgcpu.sort
-awk < $T/cfgcpu.sort \
+awk < $T/cfgcpu.sort > $T/cfgcpu.pack -v ncpus=$cpus '
+BEGIN {
+ njobs = 0;
+}
+
+{
+ cf[njobs] = $1;
+ cpus[njobs] = $2;
+ njobs++;
+}
+
+END {
+ alldone = 0;
+ batch = 0;
+ nc = -1;
+ while (nc != ncpus) {
+ batch++;
+ nc = ncpus;
+ for (i = 0; i < njobs; i++) {
+ if (done[i])
+ continue;
+ if (nc >= cpus[i] || nc == ncpus) {
+ done[i] = batch;
+ nc -= cpus[i];
+ if (nc <= 0)
+ break;
+ }
+ }
+ }
+ for (b = 1; b <= batch; b++)
+ for (i = 0; i < njobs; i++)
+ if (done[i] == b)
+ print cf[i], cpus[i];
+}'
+
+awk < $T/cfgcpu.pack \
-v CONFIGDIR="$CONFIGFRAG/$kversion/" \
-v KVM="$KVM" \
-v ncpus=$cpus \