Optimizing Scheduling for Heterogeneous Computing Systems using Combinatorial Meta-heuristic Solution

Amin Majd, Golnaz Sahebi, Masoud Daneshtalab, Elena Troubitsyna

    Forskningsoutput: Kapitel i bok/konferenshandlingKonferensbidragVetenskapligPeer review

    2 Citeringar (Scopus)

    Sammanfattning

    Today, based on fast development especially in Network-on-Chip (NoC)-based many-core systems, the task scheduling problem plays a critical role in high-performance computing. It is an NP-hard problem. The complexity increases further when the scheduling problem is applied to heterogeneous platforms. 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 compound method to select the best near-optimal task schedule in the heterogeneous platform in order to minimize the execution time. For this, we combine a new parallel meta-heuristic method with a greedy scheme. We introduce a novel metaheuristic method for near-optimal scheduling that can provide performance guarantees for multiple applications implemented on a shared platform. Applications are modeled as directed acyclic task graphs (DAG) for execution on a heterogeneous NoC-based many-core platform with given communication costs. We introduce an order-based encoding especially for pipelined operation that improves (decreases) execution time by more than 46%. Moreover, we present a novel multi-population method inspired by both genetic and imperialist competitive algorithms specialized for the scheduling problem, improving the convergence policy and selection pressure. The potential of the approach is demonstrated by experiments using a Sobel filter, SUSAN filter, RASTA-PLP, and JPEG encoder as real-world case studies.

    OriginalspråkOdefinierat/okänt
    Titel på värdpublikation2017 IEEE SmartWorld, Ubiquitous Intelligence & Computing, Advanced & Trusted Computed, Scalable Computing & Communications, Cloud & Big Data Computing, Internet of People and Smart City Innovation (SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI)
    FörlagIEEE
    Sidor
    ISBN (elektroniskt)978-1-5386-0435-9
    ISBN (tryckt)978-1-5386-1591-1
    DOI
    StatusPublicerad - 2017
    MoE-publikationstypA4 Artikel i en konferenspublikation
    EvenemangIEEE SmartWorld, Ubiquitous Intelligence & Computing, Advanced & Trusted Computed, Scalable Computing & Communications, Cloud & Big Data Computing, Internet of People and Smart City Innovation (SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI) - The 17th IEEE International Conference on Scalable Computing and Communications (Smart World 2017)
    Varaktighet: 4 aug. 20178 aug. 2017

    Konferens

    KonferensIEEE SmartWorld, Ubiquitous Intelligence & Computing, Advanced & Trusted Computed, Scalable Computing & Communications, Cloud & Big Data Computing, Internet of People and Smart City Innovation (SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI)
    Period04/08/1708/08/17

    Citera det här