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

TODO: 2015/02/10 #69

Closed jinnaiyuu closed 9 years ago

jinnaiyuu commented 9 years ago

1 . Compare structured zobrist of TSP 2 . summarize Structured Zobrist for 15 puzzle with 12, 16 threads

jinnaiyuu commented 9 years ago

TODO: 3 . Summarize structured zobrist for 24 puzzle with 8, 12, 16 threads 4 . Calculate page faults, cache misses for 15 puzzle 5 . think about new domains?

jinnaiyuu commented 9 years ago

TODO: 6 . generalize structured zobrist hash in theory. 7 . think how to make structured zobrist for typical domains 8 . investigate what it actually mean cache-misses in perf-stat

jinnaiyuu commented 9 years ago

4 . Calculate page faults, cache misses for 15 puzzle Seems A* < HDA* SZ < HDA* for both page faults and cache misses.

However, not sure what those terms are about.

jinnaiyuu commented 9 years ago

8 . investigate what it actually mean cache-misses in perf-stat the cache-misses event represents the number of memory access that could not be served by any of the cache.

jinnaiyuu commented 9 years ago

8 . investigate what it actually mean cache-misses in perf-stat

There are two types of page fault: major fault and minor fault. Seems what we observed is minor fault.

https://en.wikipedia.org/wiki/Page_fault

jinnaiyuu commented 9 years ago

TODO: 9 . Calculate the number of misses and faults for 1, 2, 4, 8, 12, 16, 24 threads

jinnaiyuu commented 9 years ago

1 . Compare structured zobrist of TSP Implemented on Jinnai version. Seems working fine.

9 . Calculate the number of misses and faults for 1, 2, 4, 8, 12, 16, 24 threads There are big variance in cache misses. Now we are running 10 times for each experiment and calculating the average and the standard deviation.

jinnaiyuu commented 9 years ago

9 . Calculate the number of misses and faults for 1, 2, 4, 8, 12, 16, 24 threads

Done.

hdastar 1 1,999,198,579 19,379,480 730.155406223 2 5,162,938,683 23,454,368 1029.851781759 4 9,989,202,076 30,476,655 889.328067885 8 6,147,948,532 13,185,540 566.930228157 12 12,944,426,705 19,156,850 454.356790821 16 18,310,613,940 22,480,225 421.101401477

hdastar with SZ 1 1,591,294,860 15,271,646 729.176127195 2 2,196,408,619 15,160,558 542.836429554 4 3,876,420,813 17,788,759 368.249341266 8 2,551,498,993 7,713,447 247.849373707 12 4,997,681,519 12,135,082 293.249802669 16 8,228,236,836 15,101,682 227.101206860

jinnaiyuu commented 9 years ago

TODO: 10 . Structured zobrist for TSP with clustering Give each n cities a hash key. If the node has visited any of the cities, then XOR the hash key. Even if the node has visited more than one cities of the n cities, give only ony XORing.

jinnaiyuu commented 9 years ago

TODO: Calculate cache misses per seconds.