search

jinnaiyuu / Hash-Distributed-Astar

Hash Distributed A*
https://sites.google.com/site/yuujinnaishomepage/home/parallel-search
MIT License
3 stars 1 forks source link

Idea: Load Balance is necessary but not enough #43

Closed jinnaiyuu closed 9 years ago

jinnaiyuu commented 9 years ago

HDA* with stupid hash actually has a great value regarding load balancing (like 1.05). In order to check the distribution you have to pay attention to the quality of the works, not only the amount of the work. What often happen with bad hash is that some threads work sufficient but the others just do no contribution to the search (but they expand nodes in a same pace!).

For this reason we need a new method to evaluate the real balancing in threads.

jinnaiyuu commented 9 years ago

What about counting the expanded nodes which are also expanded in serial A* search? That means that the node expansion is a necessary work. Also discard duplicated nodes with higher f value. Then we can evaluate the realistic load balancing.

jinnaiyuu commented 9 years ago

We can propose a new idea and then compare the old one and the new one.