Advertisement
If you have a new account but are having problems posting or verifying your account, please email us on hello@boards.ie for help. Thanks :)
Hello all! Please ensure that you are posting a new thread or question in the appropriate forum. The Feedback forum is overwhelmed with questions that are having to be moved elsewhere. If you need help to verify your account contact hello@boards.ie
Hi all! We have been experiencing an issue on site where threads have been missing the latest postings. The platform host Vanilla are working on this issue. A workaround that has been used by some is to navigate back from 1 to 10+ pages to re-sync the thread and this will then show the latest posts. Thanks, Mike.
Hi there,
There is an issue with role permissions that is being worked on at the moment.
If you are having trouble with access or permissions on regional forums please post here to get access: https://www.boards.ie/discussion/2058365403/you-do-not-have-permission-for-that#latest
There is an issue with role permissions that is being worked on at the moment.
If you are having trouble with access or permissions on regional forums please post here to get access: https://www.boards.ie/discussion/2058365403/you-do-not-have-permission-for-that#latest
Knight's tour
-
24-04-2013 1:57pmHi all,
how to implement knight's tour in parallel? this program should be organised around a family of producer/consumer worker threads. However, I am really struggling with that and cannot start with the program. Could someone give me some advises? Thank you very much!0
Comments
-
followme_1987 wrote: »Hi all,
how to implement knight's tour in parallel? this program should be organised around a family of producer/consumer worker threads. However, I am really struggling with that and cannot start with the program. Could someone give me some advises? Thank you very much!
What do you need help with?
The parallel bit, or the knights tour bit?
How much can you do yourself?
What are your current thoughts on the problem?
You have to at least start the problem yourself.
Have you tried implement knights tour but not in parallel? How far have you gotten with that?0 -
What do you need help with?
The parallel bit, or the knights tour bit?
How much can you do yourself?
What are your current thoughts on the problem?
You have to at least start the problem yourself.
Have you tried implement knights tour but not in parallel? How far have you gotten with that?
Yes, I have implemented it in sequential. I want to implement the parallel version based on the sequential one.
My thoughts are to create four workers threads as my laptop is four-cores and these four threads are both consumers and producers. besides i need a work queue containing the path. each iteration takes a path from this queue and generate the new paths and put them in the work queue. Does the idea make sense?
However, my code does not work. the result is ridiculous. I do not know where the problem is.0 -
followme_1987 wrote: »Yes, I have implemented it in sequential. I want to implement the parallel version based on the sequential one.
That sounds like a good start.
Have you tested your sequential version? Does it find tours correctly on small sized boards?
Do you understand it fully, and have a good grasp of the main parts of the problem?followme_1987 wrote: »My thoughts are to create four workers threads as my laptop is four-cores
That sounds like a good start. I would guess that knights tour is heavily CPU bound, due to the nature of the problem, and that as such, one worker per core is a good starting point.followme_1987 wrote: »and these four threads are both consumers and producers.
besides i need a work queue containing the path.
Ok, so you are making 4 separate worker threads, and you are going to use a queue to handle communication between these threads.
That seems standard enough.
You would have to be very careful, because threads share address space, that the one way you are communicating between the threads is by using the queue, in the way you intend. It could cause problems if the threads were all separately trying to modify shared state (shared variables). Are you aware of issues like that, and watching out for them?followme_1987 wrote: »each iteration takes a path from this queue and generate the new paths and put them in the work queue. Does the idea make sense?
How are you going to split up the problem, so that the queue can be used to share the work?
I presume the model you are following here, for getting knights tours, is to recursively search for possible tours, backtracking when you get stuck?
Have you got a good strategy for splitting this sequential algorithm up, so that many workers can work on it in parallel?
Ultimately, you want a way of:
1) taking a partial solution to the problem from the queue (e.g. a partial solution could be represented on the queue by a partial path, i.e. a partial possible tour)
2) then doing a little bit of work towards the solution, and then
3) putting a piece of information (e.g. the updated partial path, or partial possible tour) back onto the queue
You will need to be sure there is some sort of ordering to how the solutions are found, so that various workers done cover the same ground; and so that when something processing partial solutions gets one from the queue, that it knows exactly what work to do next.
Are you figured out a good way of doing that?
Are you convinced of the correctness of your solution?
If so, why don't you say exactly how you are doing that?followme_1987 wrote: »However, my code does not work. the result is ridiculous. I do not know where the problem is.
Do you think the issue is in your conceptualisation of the problem, or do you think you have figured out how to do it, and you have a small bug in your code?
People would need a lot more to go on, in order to help you.
But a good first step would be to describe your solution in more detail -- sometimes even the act of describing it can help you find bugs.0 -
That sounds like a good start.....
class KnightsTourMulThread { static class KnightsTours implements Runnable { private Buffer<Path> workQ; KnightsTours(Buffer<Path> workQ) { this.workQ = workQ; } @Override public void run() { while (true) { Path p = workQ.take(); if (p == null) { return; } Position[] moves = p.pathMoves(); for (Position pos : moves) { if (!p.contains(pos)) { Path newPath = new Path(pos, p); if (newPath.pathComplete()) { if (newPath.pathClosed()) { newPath.putPath(); } return; } else { workQ.put(newPath); } } } } } } public static void main(String[] args) { int numWorkers = Runtime.getRuntime().availableProcessors(); Buffer<Path> workQ = new Buffer<Path>(numWorkers); workQ.put(new Path(new Position(0, 0), null)); Thread[] t = new Thread[numWorkers]; for (int i = 0; i < numWorkers; i++) { t[i] = new Thread(new KnightsTours(workQ)); t[i].start(); } for (int i = 0; i < numWorkers; i++) { try { t[i].join(); } catch (InterruptedException e) { } } } }
the following is a "work queue" classimport java.util.*; // for LinkedList import java.util.concurrent.locks.*; class Buffer<E> { // Unbounded shared buffer with termination detection for systems // of a fixed number of producer/consumers private ReentrantLock monitor = new ReentrantLock(); private Condition notEmpty = monitor.newCondition(); private LinkedList<E> buffer = new LinkedList<E>(); // the buffer private int numLive; // number of live producer/consumers Buffer(int numLive) { this.numLive = numLive; } void put(E x) { monitor.lock(); buffer.add(x); notEmpty.signal(); monitor.unlock(); } E take() { monitor.lock(); while (buffer.size() == 0) { numLive--; if (numLive == 0) { // discover it's finished notEmpty.signalAll(); // waken others to finish monitor.unlock(); return null; } try { notEmpty.await(); } catch (InterruptedException e) { } if (numLive == 0) { // am being told it's finished monitor.unlock(); return null; } else { numLive++; } } E x = buffer.removeFirst(); monitor.unlock(); return x; } }
the following two pieces of code are about the algorithm of knight's tour. I think that should be rightclass Path { // non-empty path of Position's private Position start; // one end position in path (other is (0,0)) private Path next; // path following start node (may be null) private int pathLength; // length of path Path(Position start0, Path next0) { start = start0; next = next0; if (next == null) { pathLength = 1; } else { pathLength = 1 + next.pathLength; } } boolean contains(Position p) { // does p occur in this path? if (start.equals(p)) { return true; } else if (next == null) { return false; } else { return next.contains(p); } } Position[] pathMoves() { // new positions to extend path return start.knightMoves(); } boolean pathComplete() { // does the path cover the entire board? int tourLength = Position.numRows * Position.numCols; return pathLength == tourLength; } boolean pathClosed() { // is the path (assumed complete) closed? return start.equals(Position.end1) || start.equals(Position.end2); } void putPath() { // print path start.putPosition(); if (next != null) { System.out.print(":"); next.putPath(); } } }
class Position { static final int numRows = 3; // number of rows on board static final int numCols = 10; // number of columns on board static final Position end1 = new Position(1, 2); // possible end positions // (start is (0,0) static final Position end2 = new Position(2, 1); // other possible end // position private int row; // row number, o<=i<numRows private int col; // column number, o<=j<numCols Position(int row0, int col0) { row = row0; col = col0; } public boolean equals(Object obj) { // compare with another position if (obj == null) { return false; } Position p = (Position) obj; return (p.row == row && p.col == col); } Position[] knightMoves() { // list of knight's possible moves from here Position[] temp = new Position[8]; int count = 0; // temp[0..count-1] holds results int[] xStep = { 2, 2, -2, -2, 1, 1, -1, -1 }; // potential moves are // (row+yStep[k],col+xStep[k]) // for each index k int[] yStep = { 1, -1, 1, -1, 2, -2, 2, -2 }; for (int k = 0; k < xStep.length; k++) { // check that each potential move stays on board int x = row + yStep[k]; int y = col + xStep[k]; if (0 <= x && x < numCols && 0 <= y && y < numRows) { temp[count] = new Position(x, y); count++; } } Position[] result = new Position[count]; for (int k = 0; k < count; k++) { result[k] = temp[k]; } return result; } void putPosition() { // print position // print position System.out.print("(" + row + "," + col + ")"); } }
0
Advertisement