On the Optimization of HDA* for Multicore Machines : performance analysis
Material type:
ArticleDescription: 1 archivo (578,7 kB)Subject(s): Summary: Combinatorial optimization problems are interesting due to their complexity and applications, particularly in robotics. This paper deals with a parallel algorithm suitable for shared memory architectures, based on the HDA* algorithm (Hash Distributed A*), which allows finding solutions to combinatorial optimization problems. The implementation was carried out using the shared memory programming tools provided by the Pthreads library, the Jemalloc memory allocator and taking the N2-1 Puzzle as study case. The experimental work focuses on analyzing the speedup and efficiency achieved by the parallel algorithm when running on a computer with multi-core processors, for different instances of the problem and varying the amount of threads/cores used. Finally, the scalability obtained with increasing workload and number of threads/cores used is analyzed.
| Item type | Home library | Collection | Call number | URL | Status | Date due | Barcode | |
|---|---|---|---|---|---|---|---|---|
Capítulo de libro
|
Biblioteca de la Facultad de Informática | Biblioteca digital | A0822 (Browse shelf(Opens below)) | Link to resource | No corresponde |
Browsing Biblioteca de la Facultad de Informática shelves, Collection: Biblioteca digital Close shelf browser (Hides shelf browser)
Formato de archivo PDF. -- Este documento es producción intelectual de la Facultad de Informática - UNLP (Colección BIPA/Biblioteca)
Combinatorial optimization problems are interesting due to their complexity and applications, particularly in robotics. This paper deals with a parallel algorithm suitable for shared memory architectures, based on the HDA* algorithm (Hash Distributed A*), which allows finding solutions to combinatorial optimization problems. The implementation was carried out using the shared memory programming tools provided by the Pthreads library, the Jemalloc memory allocator and taking the N2-1 Puzzle as study case. The experimental work focuses on analyzing the speedup and efficiency achieved by the parallel algorithm when running on a computer with multi-core processors, for different instances of the problem and varying the amount of threads/cores used. Finally, the scalability obtained with increasing workload and number of threads/cores used is analyzed.
PDPTA ཊ - The 2014 International Conference on Parallel and Distributed Processing Techniques and Applications (2014 : Las Vegas, Estados Unidos)