/**********************************************************************************************/ /* This program is part of the Barcelona OpenMP Tasks Suite */ /* Copyright (C) 2009 Barcelona Supercomputing Center - Centro Nacional de Supercomputacion */ /* Copyright (C) 2009 Universitat Politecnica de Catalunya */ /* */ /* This program is free software; you can redistribute it and/or modify */ /* it under the terms of the GNU General Public License as published by */ /* the Free Software Foundation; either version 2 of the License, or */ /* (at your option) any later version. */ /* */ /* This program 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 for more details. */ /* */ /* You should have received a copy of the GNU General Public License */ /* along with this program; if not, write to the Free Software */ /* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ /**********************************************************************************************/ /* * Original code from the Cilk project (by Keith Randall) * * Copyright (c) 2000 Massachusetts Institute of Technology * Copyright (c) 2000 Matteo Frigo */ package edu.rice.hj.example.comp322.labs.lab9; import java.util.concurrent.atomic.LongAdder; /** * Nqueens was ported from the BOTS nqueens.c benchmark. See below for provenance. *
* This program computes all solutions to the n-queens problem where n is specified in args[0] (default = 12), * and repeats the computation "repeat" times where "repeat" is specifies in args[1] (default = ). * There is a cutoff value specified as an optional third parameter in args[1] (default = 3) * that is used in the async seq clause to specify when a new async should be created. *
* The program uses the count of the total number of solutions as a correctness check and * also prints the execution time for each repetition. * The HjFinishAccumulator class is used to accumulate the total count as an illustration * of how non-blocking operations can be used in conjunction with HJ. *
* Note the use of single "finish" statement in findQueensPar() that awaits termination of all * async's created by the recursive calls to nqueensKernelPar. *
* To study scalability on a multi-core processor, you can execute "Nqueens 13 4 6" by * varying the number of worker threads. * * @author Jun Shirako, Rice University * @author Vivek Sarkar, Rice University */ public class NqueensThreadSolution { // STATIC FIELDS private static final int[] solutions = { 1, 0, 0, 2, 10, /* 5 */ 4, 40, 92, 352, 724, /* 10 */ 2680, 14200, 73712, 365596, }; private static final int MAX_SOLUTIONS = 14; private static int size; // Problem size private static int cutoff_value; // Used to specify cutoff threshold in async seq clause /** *
main.
* * @param args an array of {@link String} objects. */ public static void main(final String[] args) { final int repeat = initialize(args); for (int i = 0; i < repeat; i++) { System.out.println("\nIteration-" + i); runNqueens(); } } private static int initialize(final String[] args) { size = (args.length > 0) ? Integer.parseInt(args[0]) : 13; cutoff_value = (args.length > 2) ? Integer.parseInt(args[2]) : 4; final int repeat = (args.length > 1) ? Integer.parseInt(args[1]) : 6; if (size < 1) { size = 1; System.out.println("Size was modified to 1"); } else if (size > MAX_SOLUTIONS) { size = MAX_SOLUTIONS; System.out.println("Size was modified to " + MAX_SOLUTIONS); } System.out.println("Configuration:"); System.out.printf("%14s = %2d \n", "Input size", size); System.out.printf("%14s = %2d \n", "Cutoff value", cutoff_value); System.out.printf("%14s = %2d \n", "Repeats", repeat); return repeat; } private static void runNqueens() { final NqueensThreadSolution q = new NqueensThreadSolution(); // Timing for parallel run final long startTimeNanos = System.nanoTime(); q.findQueensPar(); final long endTimeNanos = System.nanoTime(); final double execTimeMillis = (endTimeNanos - startTimeNanos) / 1e6; final String modeStr = "Threaded"; System.out.printf(" %10s Time: %9.2f ms. ", modeStr, execTimeMillis); q.verifyQueens(); } private int total_count; void findQueensPar() { final LongAdder ac = new LongAdder(); final LongAdder activeThreadCounter = new LongAdder(); final int[] a = new int[0]; nqueensKernelPar(a, 0, ac, activeThreadCounter); while (activeThreadCounter.intValue() != 0) { // busy-wait loop } total_count = ac.intValue(); } void nqueensKernelPar(final int[] a, final int depth, final LongAdder ac, final LongAdder threadCounter) { if (size == depth) { ac.increment(); return; } /* try each possible position for queen