Mapping stream programs onto multicore platforms by local search and genetic algorithm. (November 2016)

• Record Type: Journal Article
• Authors: Farhad, S.M.; Nayeem, Muhammad Ali; Rahman, Md. Khaledur; Rahman, M. Sohel
• Is Part Of: Computer languages, systems & structures. Volume 46(2016)
• Page Start: 182
• Page End: 205
• Publication Date: 2016-11
• Subjects: Stream programming -- Metaheuristics -- Local search operator -- Compiler optimization -- Parallel programming -- Genetic algorithm -- Hybrid genetic algorithm; Programming languages (Electronic computers) -- Periodicals; Computer networks -- Periodicals; Computer architecture -- Periodicals; Computer systems -- Periodicals; Langage de programmation; Réseau d'ordinateurs; Architecture d'ordinateur; Périodique électronique (Descripteur de forme); Ressource Internet (Descripteur de forme); 005.13
• DOI: 10.1016/j.cl.2016.08.007
• Languages: English
• ISSNs: 1477-8424

Abstract

Abstract: 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.