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

Amin Majd, Golnaz Sahebi, Masoud Daneshtalab, Elena Troubitsyna

Research output: Chapter in Book/Conference proceedingConference contributionScientificpeer-review

Abstract

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.

Original languageUndefined/Unknown
Title of host publication2017 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)
PublisherIEEE
Pages
ISBN (Electronic)978-1-5386-0435-9
ISBN (Print)978-1-5386-1591-1
DOIs
Publication statusPublished - 2017
MoE publication typeA4 Article in a conference publication
EventIEEE 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)
Duration: 4 Aug 20178 Aug 2017

Conference

ConferenceIEEE 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

Cite this