Boards.ie uses cookies. By continuing to browse this site you are agreeing to our use of cookies. Click here to find out more x
Post Reply  
 
Thread Tools Search this Thread
24-04-2013, 13:57   #1
followme_1987
Registered User
 
Join Date: Nov 2011
Posts: 6
Knight's tour

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!
followme_1987 is offline  
Advertisement
24-04-2013, 22:51   #2
fergalr
Registered User
 
Join Date: Mar 2005
Location: Dublin
Posts: 1,836
Quote:
Originally Posted by followme_1987 View Post
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?
fergalr is offline  
24-04-2013, 23:50   #3
followme_1987
Registered User
 
Join Date: Nov 2011
Posts: 6
Quote:
Originally Posted by fergalr View Post
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.
followme_1987 is offline  
25-04-2013, 00:22   #4
fergalr
Registered User
 
Join Date: Mar 2005
Location: Dublin
Posts: 1,836
Quote:
Originally Posted by followme_1987 View Post
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?

Quote:
Originally Posted by followme_1987 View Post
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.

Quote:
Originally Posted by followme_1987 View Post
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?


Quote:
Originally Posted by followme_1987 View Post
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?
Well, I can certainly think of a way of solving the problem that sounds a bit like that. But I'm not sure exactly what you are doing.

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?

Quote:
Originally Posted by followme_1987 View Post
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.

Last edited by fergalr; 25-04-2013 at 00:24.
fergalr is offline  
25-04-2013, 00:38   #5
followme_1987
Registered User
 
Join Date: Nov 2011
Posts: 6
Quote:
Originally Posted by fergalr View Post
That sounds like a good start.....
I would like to post my code and that is clearer than what i said. Thank you for your attending to this matter !!! it is a 3 X 10 board in my program.
Code:
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" class
Code:
import 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 right
Code:
class 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();
		}
	}

}
Code:
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 + ")");
	}
}
followme_1987 is offline  
Post Reply

Quick Reply
Message:
Remove Text Formatting
Bold
Italic
Underline

Insert Image
Wrap [QUOTE] tags around selected text
 
Decrease Size
Increase Size
Please sign up or log in to join the discussion

Thread Tools Search this Thread
Search this Thread:

Advanced Search



Share Tweet