Mapping stream programs onto multicore platforms by local search and genetic algorithm

This paper presents a number of novel metaheuristic approaches that can efficiently map stream graphs on multicores. A stream graph consists of a set of actors performing different functions communicating through edges. Orchestrating stream graphs on multicores can be formulated as an Integer Linear...

Full description

Saved in:
Bibliographic Details
Published in:Computer languages, systems & structures systems & structures, 2016-11, Vol.46, p.182-205
Main Authors: Farhad, S.M., Nayeem, Muhammad Ali, Rahman, Md. Khaledur, Rahman, M. Sohel
Format: Article
Language:English
Subjects:
Algorithms
Compiler optimization
Genetic algorithm
Genetic algorithms
Graphs
Heuristic methods
Hybrid genetic algorithm
Local search operator
Mathematical models
Metaheuristics
Optimization
Parallel programming
Searching
Stream programming
Streams
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents a number of novel metaheuristic approaches that can efficiently map stream graphs on multicores. A stream graph consists of a set of actors performing different functions communicating through edges. Orchestrating stream graphs on multicores can be formulated as an Integer Linear Programming (ILP) problem but ILP solver takes exponential time to provide an optimal solution. We propose metaheuristic algorithms to achieve near optimal solutions within a reasonable amount of time. We employ six different variants of the Hill-Climbing (HC) algorithm employing different tweak operators that produce excellent result extremely quickly. We also propose six different variants of Genetic Algorithm (GA) to examine how effective these variants can be in escaping the local optima. We finally combine HC and GA techniques (which is also known as ‘memetic algorithm’) to produce hybrid techniques that outperform the individual performance of HC and GA techniques. We compare our results with the results generated by the CPLEX optimization tool. Our best technique has achieved a geometric mean speedup of 7.42× across a range of StreamIt benchmarks on an eight-core processor.
ISSN:1477-8424
1873-6866
DOI:10.1016/j.cl.2016.08.007