Modeling Streams-based Variants of Ant Colony Optimisation for Parallel Systems

Wei Cheng; Frank Penczek; Clemens Grelck; Raimund Kirner; Bernd Scheuermann; Alex Shafarenko

Modeling Streams-based Variants of Ant Colony Optimisation for Parallel Systems

Wei Cheng, Frank Penczek, Clemens Grelck, Raimund Kirner, Bernd Scheuermann, Alex Shafarenko

Centre for Computer Science and Informatics Research

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

32 Downloads (Pure)

Abstract

In this paper we present the implementation of a concurrent ant colony optimisation based solver for the combinatorial Single Machine Total Weighted Tardiness Problem (ACO- SMTWTP). We introduce S-Net, a coordination language based on dataflow principles, report on the performance of the implementation and compare it against a sequential and a parallel implementation of the same algorithm in C. As the workload of the optimisation algorithm is highly irregu- lar we consider this application to be an important use-case for runtime measurement directed optimisations of the co- ordination rogram as much as for guiding optimisations of numerical code.

Original language	English
Title of host publication	Proceedings: 2nd HiPEAC Workshop on Feedback-Directed Compiler Optimization for Multi-Core Architectures
Editors	C. Grelck, K. Hammond, S. B. Scholz
Publisher	HiPEAC
Number of pages	8
Publication status	Published - Jan 2012
Event	2nd FD-COMA Workshop at HiPEAC Conference 2013 - Berlin, Germany Duration: 22 Jan 2013 → 22 Jan 2013 http://www.project-advance.eu/2012/07/fd-coma-workshop-2013/

Conference

Conference	2nd FD-COMA Workshop at HiPEAC Conference 2013
Country/Territory	Germany
City	Berlin
Period	22/01/13 → 22/01/13
Internet address	http://www.project-advance.eu/2012/07/fd-coma-workshop-2013/

Access to Document

rr_2012_FDCOMA12_ant_algFinal published version, 463 KB

Cite this

@inproceedings{66fe1d7fdd3d4426a269a7157dd4425a,

title = "Modeling Streams-based Variants of Ant Colony Optimisation for Parallel Systems",

abstract = "In this paper we present the implementation of a concurrent ant colony optimisation based solver for the combinatorial Single Machine Total Weighted Tardiness Problem (ACO- SMTWTP). We introduce S-Net, a coordination language based on dataflow principles, report on the performance of the implementation and compare it against a sequential and a parallel implementation of the same algorithm in C. As the workload of the optimisation algorithm is highly irregu- lar we consider this application to be an important use-case for runtime measurement directed optimisations of the co- ordination rogram as much as for guiding optimisations of numerical code.",

author = "Wei Cheng and Frank Penczek and Clemens Grelck and Raimund Kirner and Bernd Scheuermann and Alex Shafarenko",

note = "Wei Cheng, Frank Penczek, Clemens Grelck, Raimund Kirner, Bernd Scheuermann, Alex Shafarenko, 'Modeling Streams-based Variants of Ant Colony Optimisation for Parallel Systems' in Proceedings: 2nd HiPEAC Workshop on Feedback-Directed Compiler Optimization for Multi-Core Architectures. Berlin, Germany. 22 January 2013; 2nd FD-COMA Workshop at HiPEAC Conference 2013 ; Conference date: 22-01-2013 Through 22-01-2013",

year = "2012",

month = jan,

language = "English",

editor = "C. Grelck and K. Hammond and Scholz, {S. B.}",

booktitle = "Proceedings: 2nd HiPEAC Workshop on Feedback-Directed Compiler Optimization for Multi-Core Architectures",

publisher = "HiPEAC",

url = "http://www.project-advance.eu/2012/07/fd-coma-workshop-2013/",

}

Cheng, W, Penczek, F, Grelck, C, Kirner, R, Scheuermann, B & Shafarenko, A 2012, Modeling Streams-based Variants of Ant Colony Optimisation for Parallel Systems. in C Grelck, K Hammond & SB Scholz (eds), Proceedings: 2nd HiPEAC Workshop on Feedback-Directed Compiler Optimization for Multi-Core Architectures. HiPEAC, 2nd FD-COMA Workshop at HiPEAC Conference 2013 , Berlin, Germany, 22/01/13.

Modeling Streams-based Variants of Ant Colony Optimisation for Parallel Systems. / Cheng, Wei; Penczek, Frank; Grelck, Clemens et al.
Proceedings: 2nd HiPEAC Workshop on Feedback-Directed Compiler Optimization for Multi-Core Architectures. ed. / C. Grelck; K. Hammond; S. B. Scholz. HiPEAC, 2012.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Modeling Streams-based Variants of Ant Colony Optimisation for Parallel Systems

AU - Cheng, Wei

AU - Penczek, Frank

AU - Grelck, Clemens

AU - Kirner, Raimund

AU - Scheuermann, Bernd

AU - Shafarenko, Alex

N1 - Wei Cheng, Frank Penczek, Clemens Grelck, Raimund Kirner, Bernd Scheuermann, Alex Shafarenko, 'Modeling Streams-based Variants of Ant Colony Optimisation for Parallel Systems' in Proceedings: 2nd HiPEAC Workshop on Feedback-Directed Compiler Optimization for Multi-Core Architectures. Berlin, Germany. 22 January 2013

PY - 2012/1

Y1 - 2012/1

N2 - In this paper we present the implementation of a concurrent ant colony optimisation based solver for the combinatorial Single Machine Total Weighted Tardiness Problem (ACO- SMTWTP). We introduce S-Net, a coordination language based on dataflow principles, report on the performance of the implementation and compare it against a sequential and a parallel implementation of the same algorithm in C. As the workload of the optimisation algorithm is highly irregu- lar we consider this application to be an important use-case for runtime measurement directed optimisations of the co- ordination rogram as much as for guiding optimisations of numerical code.

AB - In this paper we present the implementation of a concurrent ant colony optimisation based solver for the combinatorial Single Machine Total Weighted Tardiness Problem (ACO- SMTWTP). We introduce S-Net, a coordination language based on dataflow principles, report on the performance of the implementation and compare it against a sequential and a parallel implementation of the same algorithm in C. As the workload of the optimisation algorithm is highly irregu- lar we consider this application to be an important use-case for runtime measurement directed optimisations of the co- ordination rogram as much as for guiding optimisations of numerical code.

M3 - Conference contribution

BT - Proceedings: 2nd HiPEAC Workshop on Feedback-Directed Compiler Optimization for Multi-Core Architectures

A2 - Grelck, C.

A2 - Hammond, K.

A2 - Scholz, S. B.

PB - HiPEAC

T2 - 2nd FD-COMA Workshop at HiPEAC Conference 2013

Y2 - 22 January 2013 through 22 January 2013

ER -

Modeling Streams-based Variants of Ant Colony Optimisation for Parallel Systems

Abstract

Conference

Access to Document

Fingerprint

Cite this