A4 Article in conference proceedings
NOMeS: Near-Optimal Metaheuristic Scheduling for MPSoCs

List of Authors: Amin Majd, Masoud Daneshtalab, Juha Plosila, Nima Khalilzad, Golnaz Sahebi, Elena Troubitsyna
Publication year: 2018
Journal: CSI International Symposium on Computer Architecture and Digital Systems
Book title *: 2017 19th International Symposium on Computer Architecture and Digital Systems (CADS)
Number of pages: 6
ISBN: 978-1-5386-4380-8
eISBN: 978-1-5386-4379-2
ISSN: 2325-9361


The task scheduling problem for Multiprocessor System-on-Chips (MPSoC), which plays a vital role in performance, is an NP-hard problem. Exploring the whole search space in order to find the optimal solution is not time efficient, thus metaheuristics are mostly used to find a near-optimal solution in a reasonable amount of time. We propose a novel metaheuristic method for near-optimal scheduling that can provide performance guarantees for multiple applications implemented on a shared platform. Applications are represented as directed acyclic task graphs (DAG) and are executed on an MPSoC platform with given communication costs. We introduce a novel multi-population method inspired by both genetic and imperialist competitive algorithms. It is specialized for the scheduling problem with the goal to improve the convergence policy and selection pressure. The potential of the approach is demonstrated by experiments using a Sobel filter, a SUSAN filter, RASTA-PLP and JPEG encoder as real-world case studies.

Last updated on 2019-21-08 at 21:55