this is my first question in SOF.
I have a question about this problem.
I coded a linear (without threads) app, it looks ok, solving speed - normal. Also I coded a multi-thread app, and it is ok, when I use 2 processors and 2 threads, also it is fine when I use 4 processors and 4 threads, but when I try to solve with 6 processors and 6 threads I am not satisfied with solving speed. I attached a source code and my results table. Maybe do you have any ideas how to make it faster?
P.S. algorithm works perfect, it founds the correct answer.
Thank you for time, xsiraul.
Main.java file:
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws InterruptedException {
// TODO Auto-generated method stub
//Scanner scanner = new Scanner(System.in);
//System.out.println("Iveskite N:");
//int n = Integer.parseInt(scanner.nextLine());
int n = Integer.parseInt(args[0]);
int maxThreads = Integer.parseInt(args[1]);
Karalienes.setMaxGSK(maxThreads);
Karalienes queens = new Karalienes(n, 1, new int[n+1]);
long startedTime = System.currentTimeMillis();
queens.start();
queens.join();
System.out.println("Solutions: "+Karalienes.getVariantuSkaiciu());
//queens.print();
System.out.println("Working time: "+(float)(System.currentTimeMillis()-startedTime)/1000
+ " s.");
}
}
Karalienes.java file:
import java.util.Stack;
public class Karalienes extends Thread {
private int n;
private int places[];
private int column;
private static Integer solutions = new Integer(0);
private static Integer startedThreads = 0;
private static int maxThreads;
private Stack<Karalienes> stack;
public Karalienes(int n,int column, int places[]) {
this.n = n;
this.column = column;
this.places = places;
stack = new Stack<Karalienes>();
}
public static void setMaxGSK(int sk) {
this.maxThreads = sk;
}
private boolean arOk(int row, int column) {
boolean ok = true;
int tmpColumn = column-1;
for(; tmpColumn>=1; tmpColumn--) {
if ((places[tmpColumn]-row)==0) {
ok = false;
break;
}
int rowDiff = places[column] - places[tmpColumn];
if (rowDiff < 0)
rowDiff = 0 - rowDiff;
if (rowDiff == column-tmpColumn) {
ok = false;
break;
}
}
return ok;
}
public void deliojam() {
for(int i=1; i<=n ; i++ ) { //dirbam su row
places[column] = i;
if (arOk(i, column)) {
if (column<n) {
int gSk;
synchronized (startedThreads) {
gSk = startedThreads;
}
if (gSk < maxThreads) {
Karalienes kar = new Karalienes(n, column+1, places.clone());
kar.start();
stack.add(kar);
}
else {
column++;
deliojam();
column--;
}
}
if (column==n) {
Karalienes.incVariantuSkaiciu();
}
}
}
while (stack.size()!=0) {
try {
stack.pop().join();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
@Override
public void run() {
// TODO Auto-generated method stub
Karalienes.incGijuSk();
deliojam();
Karalienes.decGijuSk();
}
private static synchronized void incVariantuSkaiciu() {
solutions++;
}
private static synchronized void incGijuSk() {
startedThreads++;
}
private static synchronized void decGijuSk() {
startedThreads--;
}
public static int getVariantuSkaiciu() {
return solutions;
}
}
List of times:
Computer (code with threads)
Proc Threads N Working time (in seconds)
2 2 9 0,022
2 2 10 0,052
2 2 11 0,106
2 2 12 0,299
2 2 13 1,342
2 2 14 7,303
2 2 15 47,486
2 2 16 345,369
2 2 17 2702,898
4 4 9 0,043
4 4 10 0,067
4 4 11 0,135
4 4 12 0,438
4 4 13 1,609
4 4 14 7,146
4 4 15 42,196
4 4 16 293,293
4 4 17 2038,762
6 6 9 0,053
6 6 10 0,09
6 6 11 0,194
6 6 12 0,483
6 6 13 1,99
6 6 14 10,347
6 6 15 62,086
6 6 16 420,496
6 6 17 2915,52
