Savant: Automatic generation of a parallel scheduling heuristic for map-reduce

Article type: Research Article

Authors: Pinel, Frédéric^{a; *} | Dorronsoro, Bernabé^b

Affiliations: [a] University of Luxembourg, Luxembourg, Luxembourg | [b] University of Lille, Lille, France

Correspondence: [*] Corresponding author: Frédéric Pinel, University of Luxembourg, Luxembourg, Luxembourg. E-mail: frederic.pinel@uni.lu

Abstract: This paper investigates the automatic generation of a Map-Reduce program, which implements a heuristic for an NP-complete problem with machine learning. The objective is to automatically design a new concurrent algorithm that finds solutions of comparable quality to the original heuristic. Our approach, called Savant, is inspired from the savant syndrome. Its concurrency model is based on Map-Reduce. The approach is evaluated with the well-known Min-Min heuristic. Experimental results on two problem sizes are promising, the produced algorithm is able to find solutions of comparable quality.

Keywords: Pattern recognition, parallelism and concurrency, conversion from sequential to parallel forms

DOI: 10.3233/HIS-140200

Journal: International Journal of Hybrid Intelligent Systems, vol. 11, no. 4, pp. 287-302, 2014