NOMeS: Near-Optimal Metaheuristic Scheduling for MPSoCs

Amin Majd; Masoud Daneshtalab; Juha Plosila; Nima Khalilzad; Golnaz Sahebi; Elena Troubitsyna

doi:10.1109/CADS.2017.8310723

NOMeS: Near-Optimal Metaheuristic Scheduling for MPSoCs

Amin Majd, Masoud Daneshtalab, Juha Plosila, Nima Khalilzad, Golnaz Sahebi, Elena Troubitsyna

Research output: Chapter in Book/Conference proceeding › Conference contribution › Scientific › peer-review

5 Citations (Scopus)

Abstract

The task scheduling problem for MultiprocessorSystem-on-Chips (MPSoC), which plays a vital role in performance, is an NP-hardproblem. Exploring the whole search space in order to find the optimal solutionis not time efficient, thus metaheuristics are mostly used to find anear-optimal solution in a reasonable amount of time. We propose a novel metaheuristicmethod for near-optimal scheduling that can provide performance guarantees formultiple applications implemented on a shared platform. Applications arerepresented as directed acyclic task graphs (DAG) and are executed on an MPSoCplatform with given communication costs. We introduce a novel multi-populationmethod inspired by both genetic and imperialist competitive algorithms. It is specializedfor the scheduling problem with the goal to improve the convergence policy andselection pressure. The potential of the approach is demonstrated byexperiments using a Sobel ﬁlter, a SUSAN ﬁlter, RASTA-PLP and JPEG encoder asreal-world case studies.

Original language	Undefined/Unknown
Title of host publication	2017 19th International Symposium on Computer Architecture and Digital Systems (CADS)
Publisher	IEEE
Pages	70–75
ISBN (Electronic)	978-1-5386-4379-2
ISBN (Print)	978-1-5386-4380-8
DOIs	https://doi.org/10.1109/CADS.2017.8310723
Publication status	Published - 2018
MoE publication type	A4 Article in a conference publication
Event	International Symposium on Computer Architecture and Digital Systems (CADS) - 19th International Symposium on Computer Architecture and Digital Systems (CADS’17) Duration: 21 Dec 2017 → 22 Dec 2017

Conference

Conference	International Symposium on Computer Architecture and Digital Systems (CADS)
Period	21/12/17 → 22/12/17

Access to Document

10.1109/CADS.2017.8310723

https://ieeexplore.ieee.org/document/8310723

Cite this

@inproceedings{d41e773a14ed4bbb94f9077b49c569c8,

title = "NOMeS: Near-Optimal Metaheuristic Scheduling for MPSoCs",

abstract = "The task scheduling problem for MultiprocessorSystem-on-Chips (MPSoC), which plays a vital role in performance, is an NP-hardproblem. Exploring the whole search space in order to find the optimal solutionis not time efficient, thus metaheuristics are mostly used to find anear-optimal solution in a reasonable amount of time. We propose a novel metaheuristicmethod for near-optimal scheduling that can provide performance guarantees formultiple applications implemented on a shared platform. Applications arerepresented as directed acyclic task graphs (DAG) and are executed on an MPSoCplatform with given communication costs. We introduce a novel multi-populationmethod inspired by both genetic and imperialist competitive algorithms. It is specializedfor the scheduling problem with the goal to improve the convergence policy andselection pressure. The potential of the approach is demonstrated byexperiments using a Sobel ﬁlter, a SUSAN ﬁlter, RASTA-PLP and JPEG encoder asreal-world case studies.",

author = "Amin Majd and Masoud Daneshtalab and Juha Plosila and Nima Khalilzad and Golnaz Sahebi and Elena Troubitsyna",

year = "2018",

doi = "10.1109/CADS.2017.8310723",

language = "Odefinierat/ok{\"a}nt",

isbn = "978-1-5386-4380-8",

pages = "70–75",

booktitle = "2017 19th International Symposium on Computer Architecture and Digital Systems (CADS)",

publisher = "IEEE",

note = "International Symposium on Computer Architecture and Digital Systems (CADS) ; Conference date: 21-12-2017 Through 22-12-2017",

}

Majd, A, Daneshtalab, M, Plosila, J, Khalilzad, N, Sahebi, G & Troubitsyna, E 2018, NOMeS: Near-Optimal Metaheuristic Scheduling for MPSoCs. in 2017 19th International Symposium on Computer Architecture and Digital Systems (CADS). IEEE, pp. 70–75, International Symposium on Computer Architecture and Digital Systems (CADS), 21/12/17. https://doi.org/10.1109/CADS.2017.8310723

TY - GEN

T1 - NOMeS: Near-Optimal Metaheuristic Scheduling for MPSoCs

AU - Majd, Amin

AU - Daneshtalab, Masoud

AU - Plosila, Juha

AU - Khalilzad, Nima

AU - Sahebi, Golnaz

AU - Troubitsyna, Elena

PY - 2018

Y1 - 2018

N2 - The task scheduling problem for MultiprocessorSystem-on-Chips (MPSoC), which plays a vital role in performance, is an NP-hardproblem. Exploring the whole search space in order to find the optimal solutionis not time efficient, thus metaheuristics are mostly used to find anear-optimal solution in a reasonable amount of time. We propose a novel metaheuristicmethod for near-optimal scheduling that can provide performance guarantees formultiple applications implemented on a shared platform. Applications arerepresented as directed acyclic task graphs (DAG) and are executed on an MPSoCplatform with given communication costs. We introduce a novel multi-populationmethod inspired by both genetic and imperialist competitive algorithms. It is specializedfor the scheduling problem with the goal to improve the convergence policy andselection pressure. The potential of the approach is demonstrated byexperiments using a Sobel ﬁlter, a SUSAN ﬁlter, RASTA-PLP and JPEG encoder asreal-world case studies.

AB - The task scheduling problem for MultiprocessorSystem-on-Chips (MPSoC), which plays a vital role in performance, is an NP-hardproblem. Exploring the whole search space in order to find the optimal solutionis not time efficient, thus metaheuristics are mostly used to find anear-optimal solution in a reasonable amount of time. We propose a novel metaheuristicmethod for near-optimal scheduling that can provide performance guarantees formultiple applications implemented on a shared platform. Applications arerepresented as directed acyclic task graphs (DAG) and are executed on an MPSoCplatform with given communication costs. We introduce a novel multi-populationmethod inspired by both genetic and imperialist competitive algorithms. It is specializedfor the scheduling problem with the goal to improve the convergence policy andselection pressure. The potential of the approach is demonstrated byexperiments using a Sobel ﬁlter, a SUSAN ﬁlter, RASTA-PLP and JPEG encoder asreal-world case studies.

U2 - 10.1109/CADS.2017.8310723

DO - 10.1109/CADS.2017.8310723

M3 - Konferensbidrag

SN - 978-1-5386-4380-8

SP - 70

EP - 75

BT - 2017 19th International Symposium on Computer Architecture and Digital Systems (CADS)

PB - IEEE

T2 - International Symposium on Computer Architecture and Digital Systems (CADS)

Y2 - 21 December 2017 through 22 December 2017

ER -