--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/concurrent/forkjoin/NQueensCS.java Mon Nov 02 17:25:38 2009 -0800
@@ -0,0 +1,174 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ */
+
+/*
+ * This file is available under and governed by the GNU General Public
+ * License version 2 only, as published by the Free Software Foundation.
+ * However, the following notice accompanied the original version of this
+ * file:
+ *
+ * Written by Doug Lea with assistance from members of JCP JSR-166
+ * Expert Group and released to the public domain, as explained at
+ * http://creativecommons.org/licenses/publicdomain
+ */
+
+/*
+ * @test
+ * @bug 6865571
+ * @summary Solve NQueens using fork/join
+ * @run main NQueensCS maxBoardSize=11 reps=1
+ * @run main NQueensCS maxBoardSize=11 reps=1 procs=8
+ */
+
+import java.util.Arrays;
+import java.util.concurrent.ForkJoinPool;
+import java.util.concurrent.RecursiveAction;
+
+public class NQueensCS extends RecursiveAction {
+
+ static long lastStealCount;
+ static int boardSize;
+
+ static final int[] expectedSolutions = new int[] {
+ 0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200,
+ 73712, 365596, 2279184, 14772512, 95815104, 666090624
+ }; // see http://www.durangobill.com/N_Queens.html
+
+ static String keywordValue(String[] args, String keyword) {
+ for (String arg : args)
+ if (arg.startsWith(keyword))
+ return arg.substring(keyword.length() + 1);
+ return null;
+ }
+
+ static int intArg(String[] args, String keyword, int defaultValue) {
+ String val = keywordValue(args, keyword);
+ return (val == null) ? defaultValue : Integer.parseInt(val);
+ }
+
+ /** for time conversion */
+ static final long NPS = (1000L * 1000L * 1000L);
+
+ /**
+ * Usage: NQueensCS [minBoardSize=N] [maxBoardSize=N] [procs=N] [reps=N]
+ */
+ public static void main(String[] args) throws Exception {
+ // Board sizes too small: hard to measure well.
+ // Board sizes too large: take too long to run.
+ final int minBoardSize = intArg(args, "minBoardSize", 8);
+ final int maxBoardSize = intArg(args, "maxBoardSize", 15);
+
+ final int procs = intArg(args, "procs", 0);
+
+ for (int reps = intArg(args, "reps", 10); reps > 0; reps--) {
+ ForkJoinPool g = (procs == 0) ?
+ new ForkJoinPool() :
+ new ForkJoinPool(procs);
+ lastStealCount = g.getStealCount();
+ for (int i = minBoardSize; i <= maxBoardSize; i++)
+ test(g, i);
+ System.out.println(g);
+ g.shutdown();
+ }
+ }
+
+ static void test(ForkJoinPool g, int i) throws Exception {
+ boardSize = i;
+ int ps = g.getParallelism();
+ long start = System.nanoTime();
+ NQueensCS task = new NQueensCS(new int[0]);
+ g.invoke(task);
+ int solutions = task.solutions;
+ long time = System.nanoTime() - start;
+ double secs = (double) time / NPS;
+ if (solutions != expectedSolutions[i])
+ throw new Error();
+ System.out.printf("NQueensCS %3d", i);
+ System.out.printf(" Time: %7.3f", secs);
+ long sc = g.getStealCount();
+ long ns = sc - lastStealCount;
+ lastStealCount = sc;
+ System.out.printf(" Steals/t: %5d", ns/ps);
+ System.out.println();
+ }
+
+ // Boards are represented as arrays where each cell
+ // holds the column number of the queen in that row
+
+ final int[] sofar;
+ NQueensCS nextSubtask; // to link subtasks
+ int solutions;
+ NQueensCS(int[] a) {
+ this.sofar = a;
+ }
+
+ public final void compute() {
+ NQueensCS subtasks;
+ int bs = boardSize;
+ if (sofar.length >= bs)
+ solutions = 1;
+ else if ((subtasks = explore(sofar, bs)) != null)
+ solutions = processSubtasks(subtasks);
+ }
+
+ private static NQueensCS explore(int[] array, int bs) {
+ int row = array.length;
+ NQueensCS s = null; // subtask list
+ outer:
+ for (int q = 0; q < bs; ++q) {
+ for (int i = 0; i < row; i++) {
+ int p = array[i];
+ if (q == p || q == p - (row - i) || q == p + (row - i))
+ continue outer; // attacked
+ }
+ NQueensCS first = s; // lag forks to ensure 1 kept
+ if (first != null)
+ first.fork();
+ int[] next = Arrays.copyOf(array, row+1);
+ next[row] = q;
+ NQueensCS subtask = new NQueensCS(next);
+ subtask.nextSubtask = first;
+ s = subtask;
+ }
+ return s;
+ }
+
+ private static int processSubtasks(NQueensCS s) {
+ // Always run first the task held instead of forked
+ s.compute();
+ int ns = s.solutions;
+ s = s.nextSubtask;
+ // Then the unstolen ones
+ while (s != null && s.tryUnfork()) {
+ s.compute();
+ ns += s.solutions;
+ s = s.nextSubtask;
+ }
+ // Then wait for the stolen ones
+ while (s != null) {
+ s.join();
+ ns += s.solutions;
+ s = s.nextSubtask;
+ }
+ return ns;
+ }
+}