MSA: Performance Issue - Githubissues

jinnaiyuu / Hash-Distributed-Astar

Hash Distributed A*

https://sites.google.com/site/yuujinnaishomepage/home/parallel-search

MIT License

3 stars 1 forks source link

MSA: Performance Issue #73

Closed jinnaiyuu closed 9 years ago

jinnaiyuu commented 9 years ago

Seems MSA do not scale so well. Not sure why. We need to identify why it does not scale so well.

open list access: pop() would take more time if there are less nodes in the queue.
communication overhead: MSA generates many more nodes than 15 puzzle. Packing nodes would be optimal for MSA.
cache-misses: As MSA require more things to store, it costs more cache-misses.
memory contention: MSA accesses main memory more often than 15 puzzle. It may cost a contention on main memory.

jinnaiyuu commented 9 years ago

too big closed list? -> more than enough size for closed list. might cause more cache misses and other problems.

jinnaiyuu commented 9 years ago

changed node pushing strategy for MSA. before: pushes every time node generated. after: pushes nodes after a single expansion. -> it reduces the number of try_lock.

jinnaiyuu commented 9 years ago

Test with easier instances: 1 . in pairwise alignment check f = g + h = const. 2 . Check that in 3 sequences 3 . Reread Korf's paper

jinnaiyuu commented 9 years ago

Weighted A* is working now (but slow...)

Anyway, let's evaluate the spdup of HDA* with this new method.

jinnaiyuu commented 9 years ago

It was all because of Turbo Boost!