Scheduling on Two Types of Resources: A Survey

被引：12

作者：

Beaumont, Olivier ^{[1
]}

Canon, Louis-Claude ^{[2
]}

Eyraud-Dubois, Lionel ^{[1
]}

Lucarelli, Giorgio ^{[3
]}

Marchal, Loris ^{[4
]}

Mommessin, Clement ^{[5
]}

Simon, Bertrand ^{[6
]}

Trystram, Denis ^{[5
]}

机构：

[1] INRIA Bordeaux, 200 Ave Vieille Tour, F-33405 Bordeaux, France

[2] Univ Bourgogne Franche Comte, FEMTO ST, 15B Ave, F-25000 Besancon, France

[3] Univ Lorraine, LCOMS, 3 Rue Augustin Fresnel, F-57073 Metz, France

[4] Univ Lyon, CNRS, LIP, 46 Allee Italie, F-69007 Lyon, France

[5] Univ Grenoble Alpes, CNRS, INRIA, Grenoble INP,LIG, 700 Ave Cent, F-38401 St Martin Dheres, France

[6] Univ Bremen, Bibliothekstr 1, D-28359 Bremen, Germany

来源：

ACM COMPUTING SURVEYS | 2020年 / 53卷 / 03期

关键词：

Scheduling; makespan minimization; resource allocation; heterogeneity; performance evaluation; online scheduling; APPROXIMATION ALGORITHMS; TASKS;

D O I：

10.1145/3387110

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The evolution in the design of modern parallel platforms leads to revisit the scheduling jobs on distributed heterogeneous resources. The goal of this survey is to present the main existing algorithms, to classify them based on their underlying principles, and to propose unified implementations to enable their fair comparison, in terms of running time and quality of schedules, on a large set of common benchmarks that we made available for the community. Beyond this comparison, our goal is also to understand the main difficulties that heterogeneity conveys and the shared principles that guide the design of efficient algorithms.

引用

页数：36

共 51 条

[1] Approximation algorithm for scheduling applications on hybrid multi-core machines with communications delays [J].

Aba, Massinissa Ait ;

Zaourar, Lilia ;

Munier-Kordon, Alix .

2018 IEEE INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS (IPDPSW 2018), 2018, :36-45

[2]

Agullo Emmanuel, 2016, CONCURR COMPUT PRACT, V28, P9

[3] Generic Algorithms for Scheduling Applications on Hybrid Multi-core Machines [J].

Amaris, Marcos ;

Lucarelli, Giorgio ;

Mommessin, Clement ;

Trystram, Denis .

EURO-PAR 2017: PARALLEL PROCESSING, 2017, 10417 :220-231

[4]

Amaris Marcos, 2019, CONCURR COMPUT PRACT, V31, P15

[5]

[Anonymous], 1979, Computers and intractability

[6]

[Anonymous], 1997, ACM Sigact News

[7] StarPU: a unified platform for task scheduling on heterogeneous multicore architectures [J].

Augonnet, Cedric ;

Thibault, Samuel ;

Namyst, Raymond ;

Wacrenier, Pierre-Andre .

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE, 2011, 23 (02) :187-198

[8] Optimal Long Code Test with One Free Bit [J].

Bansal, Nikhil ;

Khot, Subhash .

2009 50TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE: FOCS 2009, PROCEEDINGS, 2009, :453-462

[9]

Beaumont Olivier, 2017, P IEEE INT PAR DISTR

[10]

Beaumont Olivier, 2018, CONCURR COMPUT PRACT, V30, P17

← 1 2 3 4 5 6 →