diff options
| author | Paul E. McKenney <paulmck@linux.vnet.ibm.com> | 2014-01-17 14:18:05 -0800 |
|---|---|---|
| committer | Paul E. McKenney <paulmck@linux.vnet.ibm.com> | 2014-02-18 12:26:52 -0800 |
| commit | 53954671033dc878acbeef1ecf9ac653c7b1a58f (patch) | |
| tree | cf1605094cd114483887cac885d0188fdd72f6f8 /tools | |
| parent | 0ae3f73af5ba8025abcb328913643b291698af35 (diff) | |
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>
Diffstat (limited to 'tools')
| -rw-r--r-- | tools/testing/selftests/rcutorture/bin/kvm.sh | 37 |
1 files changed, 36 insertions, 1 deletions
diff --git a/tools/testing/selftests/rcutorture/bin/kvm.sh b/tools/testing/selftests/rcutorture/bin/kvm.sh index ad3779cefdb8..18649b87ea6c 100644 --- a/tools/testing/selftests/rcutorture/bin/kvm.sh +++ b/tools/testing/selftests/rcutorture/bin/kvm.sh @@ -214,7 +214,42 @@ do 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 \ |