linux-kernel - [PATCH tip/core/rcu 11/55] rcutorture: Do better bin packing

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <1392675179-11560-11-git-send-email-paulmck@linux.vnet.ibm.com>
Date:	Mon, 17 Feb 2014 14:12:15 -0800
From:	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
To:	linux-kernel@...r.kernel.org
Cc:	mingo@...nel.org, laijs@...fujitsu.com, dipankar@...ibm.com,
	akpm@...ux-foundation.org, mathieu.desnoyers@...icios.com,
	josh@...htriplett.org, niv@...ibm.com, tglx@...utronix.de,
	peterz@...radead.org, rostedt@...dmis.org, dhowells@...hat.com,
	edumazet@...gle.com, darren@...art.com, fweisbec@...il.com,
	oleg@...hat.com, sbw@....edu,
	"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>
Subject: [PATCH tip/core/rcu 11/55] rcutorture: Do better bin packing

From: "Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>

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@...ux.vnet.ibm.com>
---
 tools/testing/selftests/rcutorture/bin/kvm.sh | 37 ++++++++++++++++++++++++++-
 1 file changed, 36 insertions(+), 1 deletion(-)

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 \
-- 
1.8.1.5

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/