{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T14:18:14Z","timestamp":1778077094779,"version":"3.51.4"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,4,29]],"date-time":"2021-04-29T00:00:00Z","timestamp":1619654400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,29]],"date-time":"2021-04-29T00:00:00Z","timestamp":1619654400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004869","name":"Westf\u00e4lische Wilhelms-Universit\u00e4t M\u00fcnster","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004869","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Parallel Prog"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Parallel implementations of swarm intelligence algorithms such as the ant colony optimization (ACO) have been widely used to shorten the execution time when solving complex optimization problems. When aiming for a GPU environment, developing efficient parallel versions of such algorithms using CUDA can be a difficult and error-prone task even for experienced programmers. To overcome this issue, the parallel programming model of<jats:italic>Algorithmic Skeletons<\/jats:italic>simplifies parallel programs by abstracting from low-level features. This is realized by defining common programming patterns (e.g. map, fold and zip) that later on will be converted to efficient parallel code. In this paper, we show how algorithmic skeletons formulated in the domain specific language<jats:italic>Musket<\/jats:italic>can cope with the development of a parallel implementation of ACO and how that compares to a low-level implementation. Our experimental results show that<jats:italic>Musket<\/jats:italic>suits the development of ACO. Besides making it easier for the programmer to deal with the parallelization aspects,<jats:italic>Musket<\/jats:italic>generates high performance code with similar execution times when compared to low-level implementations.<\/jats:p>","DOI":"10.1007\/s10766-021-00714-1","type":"journal-article","created":{"date-parts":[[2021,4,29]],"date-time":"2021-04-29T13:03:14Z","timestamp":1619701394000},"page":"776-801","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["High-Level Parallel Ant Colony Optimization with Algorithmic Skeletons"],"prefix":"10.1007","volume":"49","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7010-7482","authenticated-orcid":false,"given":"Breno A.","family":"de Melo Menezes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nina","family":"Herrmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Herbert","family":"Kuchen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fernando","family":"Buarque de Lima Neto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,4,29]]},"reference":[{"key":"714_CR1","doi-asserted-by":"crossref","unstructured":"Talbi, E-G.: Metaheuristics. Wiley, Hoboken, NJ (2009)","DOI":"10.1002\/9780470496916"},{"key":"714_CR2","doi-asserted-by":"crossref","unstructured":"Kallioras, N.A., Kepaptsoglou, K., Lagaros, N.D.: Transit stop inspection and maintenance scheduling: A GPU accelerated metaheuristics approach. Transp. Res. Part C Emerg. Technol., 55, 246\u2013260 (2015)","DOI":"10.1016\/j.trc.2015.02.013"},{"key":"714_CR3","unstructured":"Dorigo, M.: Optimization, Learning and Natural Algorithms[in Italian]. PhD thesis, Dipartimentodi Elettronica, Politecnico di Milano, Milan (1992)"},{"key":"714_CR4","unstructured":"Cole, M.I.: Algorithmic Skeletons: Structured Management of Parallel Computation. Pitman London (1989)"},{"key":"714_CR5","first-page":"1534","volume":"F147772","author":"C Rieger","year":"2019","unstructured":"Rieger, C., Wrede, F., Kuchen, H.: Musket: a domain-specific language for high-level parallel programming with algorithmic skeletons. Proc. ACM Symp. Appl. Comput. Part F147772, 1534\u20131543 (2019)","journal-title":"Proc. ACM Symp. Appl. Comput. Part"},{"key":"714_CR6","doi-asserted-by":"crossref","unstructured":"Wrede, F., Rieger, C., Kuchen, H.: Generation of high-performance code based on a domain-specific language for algorithmic skeletons. J. Supercomput. 0123456789 (2019)","DOI":"10.1007\/s11227-019-02825-6"},{"issue":"4","key":"714_CR7","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1109\/MCI.2006.329691","volume":"1","author":"M Dorigo","year":"2006","unstructured":"Dorigo, M., Birattari, M., Stutzle, T.: Ant colony optimization. IEEE Comput. Intell. Mag. 1(4), 28\u201339 (2006)","journal-title":"IEEE Comput. Intell. Mag."},{"key":"714_CR8","unstructured":"Dorigo, M., Caro, G.D.: Ant colony optimization: a new meta-heuristic (1999)"},{"issue":"7","key":"714_CR9","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1057\/palgrave.jors.2601771","volume":"55","author":"J Levine","year":"2004","unstructured":"Levine, J., Ducatelle, F.: Ant colony optimization and local search for bin packing and cutting stock problems. J. Oper. Res. Soc. 55(7), 705\u2013716 (2004)","journal-title":"J. Oper. Res. Soc."},{"key":"714_CR10","unstructured":"Lee, S.Y., Bau, Y.-T.: An ant colony optimization approach for solving the Multidimensional Knapsack Problem. In: 2012 International Conference on Computer & Information Science (ICCIS), pp. 441\u2013446. IEEE (2012)"},{"issue":"4","key":"714_CR11","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1080\/17445760.2013.842568","volume":"29","author":"A Uchida","year":"2014","unstructured":"Uchida, A., Ito, Y., Nakano, K.: Accelerating ant colony optimisation for the travelling salesman problem on the GPU. Int. J. Parallel Emergent Distrib. Syst. 29(4), 401\u2013420 (2014)","journal-title":"Int. J. Parallel Emergent Distrib. Syst."},{"issue":"1","key":"714_CR12","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.jpdc.2012.01.002","volume":"73","author":"JM Cecilia","year":"2013","unstructured":"Cecilia, J.M., Garc\u00eda, J.M., Nisbet, A., Amos, M., Ujald\u00f3n, M.: Enhancing data parallelism for ant colony optimization on GPUs. J. Parallel Distrib. Comput. 73(1), 42\u201351 (2013)","journal-title":"J. Parallel Distrib. Comput."},{"key":"714_CR13","doi-asserted-by":"crossref","unstructured":"Menezes, B.A., Kuchen, H., Neto, H.A.A., de Lima Neto, F.B.: Parallelization strategies for GPU-based ant colony optimization solving the traveling salesman problem. In: 2019 IEEE Congress on Evolutionary Computation, CEC 2019 - Proceedings, pp. 3094\u20133101 (2019)","DOI":"10.1109\/CEC.2019.8790073"},{"key":"714_CR14","unstructured":"Menezes, B.A.D.M., Pessoa, L.F.D.A., Kuchen, H., Neto, F.B.D.L.: Parallelization strategies for GPU- ased ant colony optimization applied to TSP. Adv. Parallel Comput., 36, 321\u2013330 (2020)"},{"key":"714_CR15","doi-asserted-by":"crossref","unstructured":"Aldinucci, M., Danelutto, M., Kilpatrick, P., Torquati, M.: Fastflow: high-level and efficient streaming on multi-core. Programming Multi-Core and Many-Core Computing Systems, Parallel and Distributed Computing (2017)","DOI":"10.1002\/9781119332015.ch13"},{"issue":"7","key":"714_CR16","doi-asserted-by":"publisher","first-page":"5038","DOI":"10.1007\/s11227-019-02824-7","volume":"76","author":"T \u00d6hberg","year":"2020","unstructured":"\u00d6hberg, T., Ernstsson, A., Kessler, C.: Hybrid cpu-gpu execution support in the skeleton programming framework skepu. J. Supercomput. 76(7), 5038\u20135056 (2020)","journal-title":"J. Supercomput."},{"issue":"2","key":"714_CR17","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1504\/IJHPCN.2012.046370","volume":"7","author":"S Ernsting","year":"2012","unstructured":"Ernsting, S., Kuchen, H.: Algorithmic skeletons for multi-core, multi-gpu systems and clusters. Int. J. High Perform. Comput. Networking 7(2), 129\u2013138 (2012)","journal-title":"Int. J. High Perform. Comput. Networking"},{"issue":"2","key":"714_CR18","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/s10766-016-0416-7","volume":"45","author":"S Ernsting","year":"2017","unstructured":"Ernsting, S., Kuchen, H.: Data parallel algorithmic skeletons with accelerator support. Int. J. Parallel Prog. 45(2), 283\u2013299 (2017)","journal-title":"Int. J. Parallel Prog."},{"key":"714_CR19","doi-asserted-by":"crossref","unstructured":"Benoit, A., Cole, M., Gilmore, S., Hillston, J.: Flexible skeletal programming with eskel. In: European Conference on Parallel Processing, pp. 761\u2013770. Springer, Berlin (2005)","DOI":"10.1007\/11549468_83"},{"key":"714_CR20","unstructured":"Menezes, B.A.D.M., Herrmann, N.: Musket repository. https:\/\/github.com\/wwu-pi\/musket_dsl (2020)"},{"key":"714_CR21","unstructured":"The Eclipse Foundation. Xtext documentation. https:\/\/eclipse.org\/Xtext\/documentation\/ (2020)"},{"key":"714_CR22","unstructured":"Riguzzi, F.: A survey of software metrics. Technical report (1996)"},{"key":"714_CR23","unstructured":"Menezes, B.A.D.M., Herrmann, N.: Ant colony optimization project. https:\/\/github.com\/brenoamm\/ant-colony-optimization-project (2021). Accessed 24 March 2021"},{"key":"714_CR24","unstructured":"University of\u00a0Waterloo. National traveling salesman problems. http:\/\/www.math.uwaterloo.ca\/tsp\/world\/countries.html. Accessed 14 March 2018"},{"key":"714_CR25","unstructured":"Heidelberg University. Discrete and combinatorial optimization. https:\/\/www.iwr.uni-heidelberg.de\/groups\/comopt\/software\/TSPLIB95\/XML-TSPLIB\/instances\/. Accessed 14 March 2018"},{"key":"714_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2016.04.030","volume":"255","author":"M Delorme","year":"2016","unstructured":"Delorme, M., Iori, M., Martello, S.: Bin packing and cutting stock problems: mathematical models and exact algorithms. Eur. J. Oper. Res. 255, 1\u201320 (2016)","journal-title":"Eur. J. Oper. Res."},{"key":"714_CR27","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/BF00226291","volume":"2","author":"E Falkenauer","year":"1996","unstructured":"Falkenauer, E.: A hybrid grouping genetic algorithm for bin packing. J. Heuristics 2, 5\u201330 (1996)","journal-title":"J. Heuristics"},{"key":"714_CR28","doi-asserted-by":"crossref","unstructured":"Beasley, J.E.: OR-Library: distributing test problems by electronic mail. J. Oper. Res. Soc. pp. 1069\u20131072 (1990)","DOI":"10.1057\/jors.1990.166"}],"container-title":["International Journal of Parallel Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-021-00714-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10766-021-00714-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-021-00714-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,25]],"date-time":"2022-12-25T22:03:31Z","timestamp":1672005811000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10766-021-00714-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,29]]},"references-count":28,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["714"],"URL":"https:\/\/doi.org\/10.1007\/s10766-021-00714-1","relation":{},"ISSN":["0885-7458","1573-7640"],"issn-type":[{"value":"0885-7458","type":"print"},{"value":"1573-7640","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,29]]},"assertion":[{"value":"13 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 April 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}