Polynomial Scheduling Algorithm for Parallel Applications on Hybrid Platforms

Autor:	Alix Munier, Massinissa Ait Aba, Lilia Zaourar
Rok vydání:	2020
Předmět:	Job shop scheduling Computer science Approximation algorithm Parallel computing Directed acyclic graph Computer Science::Operating Systems Performance guarantee Execution time Scheduling (computing)
Zdroj:	Lecture Notes in Computer Science ISBN: 9783030532611 ISCO
DOI:	10.1007/978-3-030-53262-8_12
Popis:	This work addresses the problem of scheduling parallel applications into hybrid platforms composed of two different types of resources. We focus on finding a generic approach to schedule applications represented by directed acyclic graphs that minimises makespan with performance guarantee. A three-phase algorithm is proposed; the first two phases consist in solving linear formulations to find the type of processor assigned to execute each task. In the third phase, we compute the start execution time of each task to generate a feasible schedule. Finally, we test our algorithm on a large number of instances. These tests demonstrate that the proposed algorithm achieves a close-to-optimal performance.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::fe65e1d5fa75bb67211ad186747bd88e https://doi.org/10.1007/978-3-030-53262-8_12 Zobrazit plný text záznamu