More Related Content
What's hot (20)
Similar to Solving Nonograms In Parallel (20)
Recently uploaded (20)
![ESET Smart Security Crack + Activation Key 2025 [Latest]](https://cdn.slidesharecdn.com/ss_thumbnails/bagc0125seedtechmaizeppt-250402180805-04ae8272-250402193656-b12a103b-thumbnail.jpg?width=560&fit=bounds)
![Virtual DJ Pro Crack 2025 Full Version Download [Latest]](https://cdn.slidesharecdn.com/ss_thumbnails/bagc0125seedtechmaizeppt-250402180805-04ae8272-250402192401-da188303-thumbnail.jpg?width=560&fit=bounds)
Solving Nonograms In Parallel
- 1. Solving Nonograms in parallel Group 7 0456095 ~ҿ 0116339 S 0116097 ꐹ
- 3. ? ߉[ ? }ĿһcꇈD } ? NP-complete ? O(2NxN) ? 1000}Ŀ ? c50%~35% ? Size = 25x25 What is Nonogram
- 5. 2. Related Work / Problem statement
- 6. How to solve Genetic Algorithm For big size problem,depth-first search algorithm is better Linear programming Exact cover Interesting way,but hard to improve Search Algorithm Most paper Heuristics rules Branch and bound Depth-first search
- 7. The Algorithm we choose 1. Line solving dynamic programming һӋ}Ŀеһ 2. Fully probing Ȍ}ĿвͬP ҳһϷһǷIJݽ 3. Backtracking ь depth-first search I-Chen Wu; Der-Johng Sun; Lung-Ping Chen; Kan-Yueh Chen; Ching-Hua Kuo; Hao-Hua Kang; Hung-Hsuan Lin, An Efficient Approach to Solving Nonograms, ~ҿ; Sչ, Nonogram}ٷ̽ӑ
- 8. Online resources Original program: https://github.com/xnum/nng2014 Google-perftools: http://gperftools.googlecode.com/svn/trunk/doc/cpuprofile.html About SIMD: http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32- architectures-software-developer-vol-1-manual.pdf OpenMPI v1.6 documentation: http://www.open-mpi.org/doc/v1.6/ pthread on Linux: http://linux.die.net/man/3/pthread_create
- 9. Environment Hardware ? E5-2620 v2 @ 2.1GHz 2cpus, 12cores, HT disabled ? DDR3 16GB 1600MHz w/ ECC ? 1 node Software ? Ubuntu 14.04.3 LTS ? Gcc 4.8.4 ? OpenMPI 1.6.5 Compiler arguments: mpic++ -Wall -Wextra -std=c++11 - m64 -march=native -msse4.2 -g
- 11. ʽY ?ʽ^gᣬӋSIMDָ̎ ?memset ,memcmp ,xor ,and ,or ?̫Y͑BҪcpu cycleӋ ?SIMD register size (128bits,256bits,512bits)
- 14. ʽY(Eval) old new new2 data1 398s 383s 380s data2 563s 542s 538s data3 417s 401s 398s
- 15. ӛwȡ 1. Ҫmemcpydata16bytes align aligned loadָ 2. struct ( <=128bits) assignment ȡ memcpy
- 16. ӛwȡ(Eval) serial optimized data1 1242s 1131s data2 1403s 1358s data3 1204s 1143s ? Compiler arguments: ? g++ -std=c++11 -msse4.2 - march=native -O3 ? Эh: ? n̹վ
- 17. MPI Ver 1 for( int i = rank*data_size ; i < (rank+1)*data_size ; ++i ) doSolve(); 1 1 2 2 3 3 4 4 5 5 ? εз ? ɹƽ ? Ác֮㷨^
- 18. MPI Ver 2 for( int i = rank ; i < problem_size ; i += size ) doSolve(); 1 2 3 4 5 1 2 3 4 5 ? problemseӋ ? ߀з䲻r
- 19. MPI Ver 3 Dynamic Scheduling Master Do wait for ask problem dispatch to slave Until All problems are solved Slaves Do ask new problem do solve Until no more problems
- 20. MPI Ver 3 (patch) Master Do wait for ask problem dispatch to slave Until All problems are solved Slaves Do ask new problem do solve Until no more problems
- 21. Busy waiting Master call MPI-Recv and its a sync IO function
- 22. Async IO for MPI-Recv int MPI_MyRecv( ... ) { PMPI_Irecv( ... ); do { nanosleep( ... ); PMPI_Request_get_status( ... ); } while (!flag); return (*status).MPI_ERROR; }
- 23. 0 1 2 3 4 5 6 7 8 9 10 1 2 4 8 10 MPI ver 1 TAAI2012 TAAI2013 TAAI2014 Perfect
- 24. 0 1 2 3 4 5 6 7 8 9 10 1 2 4 8 10 MPI ver 2 TAAI2012 TAAI2013 TAAI2014 Perfect
- 25. 0 1 2 3 4 5 6 7 8 9 10 1 2 4 8 10 MPI ver 3 TAAI2012 TAAI2013 TAAI2014 Perfect
- 26. 0 1 2 3 4 5 6 7 8 9 10 1 3 5 9 11 MPI ver 3(patch) N+1 core TAAI2012 TAAI2013 TAAI2014 Perfect
- 27. MPI ver execution time(seconds) on 10 cores serial ver1 ver2 ver3 ver3(p) data1 2089 891 451 413 400 data2 2635 978 811 577 560 data3 2154 741 409 441 415
- 28. WHY When we use 10 cores, speedup only 5.2x
- 29. 0 100 200 300 400 500 600 TAAI2012 TAAI2013 TAAI2014 execution time on 10 core 1 2 3 4 5 6 7 8 9 10
- 30. 0 100 200 300 400 500 600 700 800 900 TAAI2012 TAAI2013 TAAI2014 execution time on 4 core 1 2 3 4
- 31. Min and Max proc. Exec time 4,min 10,min 4,max 10,max data1 538 191 601 400 data2 652 216 816 560 data3 480 164 710 415
- 32. We need threads
- 33. ҂Lԇ ?Custom thread pools ?Tiny master and worker system ?Sync without pthread-cond- pthread-mutex balabala ?pthread-rwlock for data dependency But still fails Execution time ~7000s
- 35. Contributions ~ҿ S ꐹ Proposal 100% 0% 0% Related work 70% 15% 15% Design / coding 70% 15% 15% Evaluation 0% 50% 50% Presentation 100% 0% 0%
- 36. Conclusion Data dependency YԵ͵ĵطܵõܺõ ЧL oQԆ} ʽЧܷܕ׃ Memory Ӌ}⣬ӛwʹú ȡҲǺҪĿc Load Balancing Ĕr£ }eױ¶ ƽһ̶ȵЧ Project Repository https://github.com/xnum/nng2014
- 37. thanks! Any questions? You can find me at @xnum s000032001@gmail.com