A Parallel and Concurrent Implementation of Lin-Kernighan Heuristic (LKH-2) for Solving Traveling Salesman Problem for Multi-Core Processors using SPC3 Programming Model
With the arrival of multi-cores, every processor has now built-in parallel computational power and that can be fully utilized only if the program in execution is written accordingly. This study is a part of an on-going research for designing of a new parallel programming model for multi-core processors. In this paper we have presented a combined parallel and concurrent implementation of Lin-Kernighan Heuristic (LKH-2) for Solving Travelling Salesman Problem (TSP) using a newly developed parallel programming model, SPC3 PM, for general purpose multi-core processors. This implementation is found to be very simple, highly efficient, scalable and less time consuming in compare to the existing LKH-2 serial implementations in multi-core processing environment. We have tested our parallel implementation of LKH-2 with medium and large size TSP instances of TSBLIB. And for all these tests our proposed approach has shown much improved performance and scalability.
%0 Journal Article
%1 IJACSA.2011.020706
%A Muhammad Ali Ismail Dr. Shahid H. Mirza, Dr. Talat Altaf
%D 2011
%J International Journal of Advanced Computer Science and Applications(IJACSA)
%K Heuristics; Multi-core Parallel models.,TSP; parallel processors programming
%N 7
%T A Parallel and Concurrent Implementation of Lin-Kernighan Heuristic (LKH-2) for Solving Traveling Salesman Problem for Multi-Core Processors using SPC3 Programming Model
%U http://ijacsa.thesai.org/
%V 2
%X With the arrival of multi-cores, every processor has now built-in parallel computational power and that can be fully utilized only if the program in execution is written accordingly. This study is a part of an on-going research for designing of a new parallel programming model for multi-core processors. In this paper we have presented a combined parallel and concurrent implementation of Lin-Kernighan Heuristic (LKH-2) for Solving Travelling Salesman Problem (TSP) using a newly developed parallel programming model, SPC3 PM, for general purpose multi-core processors. This implementation is found to be very simple, highly efficient, scalable and less time consuming in compare to the existing LKH-2 serial implementations in multi-core processing environment. We have tested our parallel implementation of LKH-2 with medium and large size TSP instances of TSBLIB. And for all these tests our proposed approach has shown much improved performance and scalability.
@article{IJACSA.2011.020706,
abstract = {With the arrival of multi-cores, every processor has now built-in parallel computational power and that can be fully utilized only if the program in execution is written accordingly. This study is a part of an on-going research for designing of a new parallel programming model for multi-core processors. In this paper we have presented a combined parallel and concurrent implementation of Lin-Kernighan Heuristic (LKH-2) for Solving Travelling Salesman Problem (TSP) using a newly developed parallel programming model, SPC3 PM, for general purpose multi-core processors. This implementation is found to be very simple, highly efficient, scalable and less time consuming in compare to the existing LKH-2 serial implementations in multi-core processing environment. We have tested our parallel implementation of LKH-2 with medium and large size TSP instances of TSBLIB. And for all these tests our proposed approach has shown much improved performance and scalability.
},
added-at = {2014-02-21T08:00:08.000+0100},
author = {{Muhammad Ali Ismail Dr. Shahid H. Mirza}, Dr. Talat Altaf},
biburl = {https://www.bibsonomy.org/bibtex/27fffe5f17beb362b9b85704395422e3a/thesaiorg},
interhash = {8ff0c3ebb7a3c7c4c49cb4ab7cdfdc11},
intrahash = {7fffe5f17beb362b9b85704395422e3a},
journal = {International Journal of Advanced Computer Science and Applications(IJACSA)},
keywords = {Heuristics; Multi-core Parallel models.,TSP; parallel processors programming},
number = 7,
timestamp = {2014-02-21T08:00:08.000+0100},
title = {{A Parallel and Concurrent Implementation of Lin-Kernighan Heuristic (LKH-2) for Solving Traveling Salesman Problem for Multi-Core Processors using SPC3 Programming Model}},
url = {http://ijacsa.thesai.org/},
volume = 2,
year = 2011
}