followme_1987 Registered User
#1

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!

fergalr Registered User
#2

followme_1987 said:
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?

followme_1987 Registered User
#3

fergalr said:
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.

fergalr Registered User
#4

followme_1987 said:
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 said:

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 said:

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 said:

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?

followme_1987 said:

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.

followme_1987 Registered User
#5

Want to share your thoughts?

Login here to discuss!