Yves Robert

Professor, Ecole Normale Supérieure de Lyon

Research: Graal project and CS lab. LIP

Fellow of the IEEE

Senior Member, Institut Universitaire de France

Head, CS Teaching Department


Contact:

Laboratoire de l'Informatique du Parallélisme
UMR CNRS -- ENS Lyon -- INRIA -- UCB Lyon 5668
Ecole Normale Supérieure de Lyon
46, allée d'Italie
69364 Lyon Cedex 07 , France
Phone: (+33) 4 72 72 85 86
Fax: (+33) 4 72 72 88 06
E-mail: Yves.Robert@ens-lyon.fr or Yves.Robert@inria.fr




SLIDES for IPDPS 2006 (pdf file) Static scheduling for large-scale heterogeneous platforms
April 2006

HiPC 2006 13th IEEE International Conference on High Performance Computing, December 18-21, 2006, Bangalore, India

Research activities

Latest work

Recent slides

Publications

Research Reports

Link to related people

Teaching material

Photo




Research activities

I am mainly interested in algorithm design and scheduling techniques for large-scale distributed platforms. Here are some recent work topics:

  • Algorithms for heterogeneous platforms.
  • Master-slave tasking for heterogeneous platforms.
  • Linear algebra kernels on heterogeneous clusters and ... on the computational grid.
  • Divisible load scheduling.
  • Steady-state scheduling.
  • ...


    Latest work

    Here are the most recent reports:
  • Anne Benoit, Veronika Rehn and Yves Robert, "Impact of QoS on Replica Placement in Tree Networks", Report LIP RR-2006-48, December 2006. RR-2006-48

  • Anne Benoit, and Yves Robert, "Mapping pipeline skeletons onto heterogeneous platforms", Report LIP RR-2006-40, November 2006. Updated version, RR-2007-05, January 2007. RR-2007-05

  • Jean-François Pineau, Yves Robert and Frédéric Vivien, "Revisiting matrix product on master-worker platforms", Report LIP RR-2006-39, November 2006. RR-2006-39

  • Anne Benoit, Veronika Rehn and Yves Robert, "Strategies for replica placement in tree networks", Report LIP RR-2006-30, October 2006. RR-2006-30

  • Matthieu Gallet, Yves Robert and Frédéric Vivien, "Scheduling communication requests traversing a switch: complexity and algorithms", Report LIP RR-2006-25, June 2006. RR-2006-25

  • Loris Marchal, Veronika Rehn, Yves Robert and Frédéric Vivien, "Scheduling and data redistribution strategies on star platforms", Report LIP RR-2006-23, June 2006. RR-2006-23

  • Olivier Beaumont, Loris Marchal, Veronika Rehn and Yves Robert, "FIFO scheduling of divisible loads with return messages under the one-port model", Report LIP RR-2005-52, October 2005. RR-2005-52

  • Jean-François Pineau, Yves Robert and Frédéric Vivien "The impact of heterogeneity on master-slave on-line scheduling", Report LIP RR-2005-51, October 2005. RR-2005-51

  • Olivier Beaumont, Larry Carter, Jeanne Ferrante, Arnaud Legrand, Loris Marchal and Yves Robert, "Scheduling multiple bags of tasks on heterogeneous master-worker platforms: centralized versus distributed solutions", Report LIP RR-2005-45, September 2005. RR-2005-45

  • Loris Marchal, Yves Robert, Pascale Vicat-Blanc Primet and Jingdi Zeng, "Scheduling network requests with transmission window", Report LIP RR-2005-32, July 2005. RR-2005-32

  • Jean-François Pineau, Yves Robert and Frédéric Vivien "Off-line and on-line scheduling on heterogeneous master-slave platforms", Report LIP RR-2005-31, July 2005. RR-2005-31

  • Olivier Beaumont, Loris Marchal and Yves Robert, "Scheduling divisible loads with return messages on heterogeneous master-worker platforms", Report LIP RR-2005-21, May 2005. RR-2005-21

  • Loris Marchal, Yves Robert, Pascale Vicat-Blanc Primet and Jingdi Zeng, "Optimizing network resource sharing in grids", Report LIP RR-2005-10, March 2005. RR-2005-10

  • Olivier Beaumont, Loris Marchal and Yves Robert, "Broadcast trees for heterogeneous platforms", Report LIP RR-2004-46, November 2004. RR-2004-46

  • Hélène Renard, Yves Robert and Frédéric Vivien, " Data redistribution algorithms for heterogeneous processor rings", Report LIP RR-2004-28, May 2004. RR-2004-28

  • Olivier Beaumont, Arnaud Legrand, Loris Marchal and Yves Robert, "Independent and Divisible Task Scheduling on Heterogeneous Star-shaped Platforms with Limited Memory", Report LIP RR-2004-22, April 2004. RR-2004-22

  • Loris Marchal, Yang Yang, Henri Casanova and Yves Robert, "A realistic network/application model for scheduling divisible loads on large-scale platforms", Report LIP RR-2004-21, April 2004. RR-2004-21

  • Olivier Beaumont, Arnaud Legrand, Loris Marchal and Yves Robert, "Assessing the impact and limits of steady-state scheduling for mixed task and data parallelism on heterogeneous platforms", Report LIP RR-2004-20, April 2004. RR-2004-20

  • Olivier Beaumont, Arnaud Legrand, Loris Marchal and Yves Robert, "Complexity results and heuristics for pipelined multicast operations on heterogeneous platforms", Report LIP RR-2004-07, February 2004. RR-2004-07


  • Recent slides

  • SLIDES (pdf file) Strategies for Replica Placement in Tree Networks
    ICL Lunch Talk, Knoxville, October 2006

  • SLIDES (pdf file) Static Scheduling for Large-Scale Heterogeneous Platforms: Myth or Reality?
    Invited talk at IPDPS Rhodes, April 2006

  • SLIDES (pdf file) Scheduling algorithms for heterogeneous platforms
    Tutorial given at HiPC Goa, December 2005

  • SLIDES (pdf file) Broadcast trees for heterogeneous platforms
    December 2004

  • SLIDES (pdf file) Steady-state scheduling for heterogeneous platforms
    April 2004


  • Publications

    Books, edited proceedings and special issues

    Journals

  • List of journal publications, pdf file Journals (.pdf)

  • List of journal publications, source file (.bib) Journals (.bib)

    Conferences

  • List of conference publications, pdf file Conferences (.pdf)

  • List of conference publications, source file (.bib) Conferences (.bib)


    LIP Research Reports

    1993

  • Alain Darte and Yves Robert, "Mapping Uniform Loop Nests onto Distributed Memory Architectures". RR93-03

  • Alain Darte and Yves Robert, "A Graph-Theoretic Approach to the Alignment Problem". RR93-20

  • Pierre Boulet, Alain Darte, Tanguy Risset and Yves Robert, "(Pen)-ultimate Tiling?". RR93-36

    1994

  • Vincent Bouchitte, Pierre Boulet, Alain Darte and Yves Robert, "Evaluating Array Expressions on Massively Parallel Machines with Communication/Computation Overlap". RR94-10

  • Michele Dion, Jean-Laurent Philippe and Yves Robert, "Parallelizing compilers: what can be achieved?". RR94-11

  • Michele Dion, Tanguy Risset and Yves Robert, Resource-constrained Scheduling of Partitioned Algorithms on Processor Array". RR94-19

  • Michele Dion and Yves Robert, Mapping Affine Loop Nests: New Results". RR94-30

    1995

  • Alain Darte, Michele Dion and Yves Robert, "A Characterization of One-to-One Modular Mappings". RR95-09

  • Pierre-Yves Calland, Anne Mignotte, Olivier Peyran, Yves Robert and Frederic Vivien, Retiming DAGs". RR95-18

  • Michele Dion, Cyril Randriamaro and Yves Robert, "How to optimize residual communications ?". RR95-27

  • Pierre-Yves Calland, Alain Darte and Yves Robert, "A New Guaranteed Heuristic for the Software Pipelining Problem". RR95-42

    1996

  • Pierre-Yves Calland, Alain Darte, Yves Robert and Frederic Vivien, "On the Removal of Anti and Output Dependences". RR96-04

  • Pierre-Yves Calland, Alain Darte, Yves Robert and Frederic Vivien, "Plugging Anti and Output Dependence Removal Techniques into Loop Parallelization Algorithms". RR96-13

    1997

  • Pierre-Yves Calland , Jack Dongarra and Yves Robert , "Tiling with limited resources". RR97-15

  • Frederic Desprez, Jack Dongarra, Fabrice Rastello and Yves Robert, "Determining the Idle Time of a Tiling". RR97-35

    1998

  • Pierre Boulet, Jack Dongarra, Yves Robert and Frederic Vivien, "Tiling for Heterogeneous Computing Platforms". RR98-08

  • Christophe Barberet, Lionel Brunie, Frederic Desprez, Gilles Lebourgeois, Yves Robert, Stephane Ubeda and Karine Van Heumen, "Technology Transfer within the ProHPC TTN at ENS Lyon". RR98-09

  • Fabrice Rastello and Yves Robert, "Loop Partitioning versus Tiling for Cache-based Multiprocessors". RR98-13

  • Frederic Desprez, Stephane Domas, Jack Dongarra, Antoine Petitet, Cyril Randriamaro and Yves Robert, "More on Scheduling Block-Cyclic Array Redistribution". RR98-17

  • Vincent Boudet, Fabrice Rastello and Yves Robert, "Alignment and distribution is NOT (always) NP-hard". RR98-30

  • Pierre Boulet, Jack Dongarra, Fabrice Rastello, Yves Robert and Frederic Vivien, "Algorithmic Issues on Heterogeneous Computing Platforms". RR98-49

    1999

  • Vincent Boudet, Fabrice Rastello and Yves Robert, "A Proposal for a Heterogeneous Cluster ScaLAPACK (Dense Linear Solvers)". RR99-17

  • Vincent Boudet, Fabrice Rastello and Yves Robert, "Algorithmic Issues for (Distributed) Heterogeneous Computing Platforms". RR99-19

  • Vincent Boudet, Antoine Petitet, Fabrice Rastello and Yves Robert, "Data Allocation Strategies for Dense Linear Algebra Kernels on Heterogeneous Two-dimensional Grids". RR99-31

  • Jean-Francois Mehaut and Yves Robert, "Algorithms and Tools for (Distributed) Heterogeneous Computing: A Prospective Report". RR99-36

    2000

  • Olivier Beaumont, Vincent Boudet, Fabrice Rastello and Yves Robert, "Matrix-Matrix Multiplication on Heterogeneous Platforms", Report LIP RR-2000-02, January 2000. RR-2000-02

  • Olivier Beaumont, Vincent Boudet, Fabrice Rastello and Yves Robert, "Partitioning a Square into Rectangles: NP-Completeness and Approximation Algorithms", Report LIP RR-2000-10, February 2000. RR-2000-10

  • Olivier Beaumont, Vincent Boudet, Arnaud Legrand, Fabrice Rastello and Yves Robert, "Heterogeneity Considered Harmful to Algorithm Designers", Report LIP RR-2000-24, June 2000. RR-2000-24

  • Olivier Beaumont, Arnaud Legrand, Fabrice Rastello and Yves Robert, "Static LU decomposition on heterogeneous platforms", Report LIP RR-2000-45, December 2000. RR-2000-44

  • Olivier Beaumont, Arnaud Legrand, Fabrice Rastello and Yves Robert, "Dense linear algebra kernels on heterogeneous platforms: redistribution issues", Report LIP RR-2000-45, December 2000. RR-2000-45

    2001

  • Olivier Beaumont, Arnaud Legrand, and Yves Robert, "The master-slave paradigm with heterogeneous processors", Report LIP RR-2001-13, March 2001. RR-2001-13

  • Olivier Beaumont, Arnaud Legrand, and Yves Robert, "Data allocation strategies for dense linear algebra on tow-dimensional grids with heterogeneous communication links", Report LIP RR-2001-14, April 2001. RR-2001-14

  • Olivier Beaumont, Vincent Boudet and Yves Robert, "The Iso-Level Scheduling Heuristic for Heterogeneous Processors", Report LIP RR-2001-22, May 2001. RR-2001-22

  • Olivier Beaumont, Larry Carter, Jeanne Ferrante, Arnaud Legrand and Yves Robert, "Bandwidth-centric allocation of independent tasks on heterogeneous platforms", Report LIP RR-2001-25, June 2001. RR-2001-25

  • Olivier Beaumont, Vincent Boudet and Yves Robert, "A Realistic model and an efficient heuristic\\ for scheduling with heterogeneous processors", Report LIP RR-2001-37, September 2001. RR-2001-37

    2002

  • Olivier Beaumont, Arnaud Legrand and Yves Robert, "A polynomial-time algorithm for allocating independent tasks on heterogeneous fork-graphs", Report LIP RR-2002-07, February 2002. RR-2002-07

  • Cyril Banino, Olivier Beaumont, Arnaud Legrand and Yves Robert, "Scheduling strategies for master-slave tasking on heterogeneous processor grids", Report LIP RR-2002-12, March 2002. RR-2002-12

  • Olivier Beaumont, Arnaud Legrand and Yves Robert, "Scheduling strategies for mixed data and task parallelism on heterogeneous processor grids", Report LIP RR-2002-20, May 2002. RR-2002-20

  • Olivier Beaumont, Arnaud Legrand and Yves Robert, "Static scheduling strategies for heterogeneous systems", Report LIP RR-2002-29, July 2002. RR-2002-29

  • Olivier Beaumont, Arnaud Legrand and Yves Robert, "Optimal algorithms for scheduling divisible workloads on heterogeneous systems", Report LIP RR-2002-36, October 2002. RR-2002-36

    2003

  • Hélène Renard, Yves Robert and Frédéric Vivien, "Static load-balancing techniques for iterative computations on heterogeneous clusters", Report LIP RR-2003-12, February 2003. RR-2003-12

  • Arnaud Legrand, Hélène Renard, Yves Robert and Frédéric Vivien, "Load-balancing iterative computations in heterogeneous clusters with shared communication links", Report LIP RR-2003-23, April 2003. RR-2003-23

  • Arnaud Giersch, Yves Robert and Frédéric Vivien, "Scheduling tasks sharing files on heterogeneous clusters", Report LIP RR-2003-28, May 2003. RR-2003-28

  • Arnaud Legrand, Loris Marchal and Yves Robert, "Optimizing the steady-state throughput of scatter and reduce operations on heterogeneous platforms", Report LIP RR-2003-33, June 2003. RR-2003-33

  • Olivier Beaumont, Arnaud Legrand, Loris Marchal and Yves Robert, "Optimizing the steady-state throughput of broadcasts on heterogeneous platforms", Report LIP RR-2003-34, June 2003. RR-2003-34

  • Olivier Beaumont, Henri Casanova, Arnaud Legrand, Yves Robert, and Yang Yang "Scheduling divisible loads on star and tree networks: results and open problems", Report LIP RR-2003-41, September 2003. RR-2003-41

  • Arnaud Giersch, Yves Robert, and Frédéric Vivien "Scheduling tasks sharing files from distributed repositories", Report LIP RR-2003-49, October 2003. RR-2003-49

    2004

  • Arnaud Giersch, Yves Robert, and Frédéric Vivien "Scheduling tasks sharing files from distributed repositories", Report LIP RR-2004-04, February 2004. RR-2004-04

  • Olivier Beaumont, Arnaud Legrand, Loris Marchal and Yves Robert, " Complexity results and heuristics for pipelined multicast operations on heterogeneous platforms", Report LIP RR-2004-07, February 2004. RR-2004-07

  • Olivier Beaumont, Arnaud Legrand, Loris Marchal and Yves Robert, "Assessing the impact and limits of steady-state scheduling for mixed task and data parallelism on heterogeneous platforms", Report LIP RR-2004-20, April 2004. RR-2004-20

  • Loris Marchal, Yang Yang, Henri Casanova and Yves Robert, "A realistic network/application model for scheduling divisible loads on large-scale platforms", Report LIP RR-2004-21, April 2004. RR-2004-21

  • Olivier Beaumont, Arnaud Legrand, Loris Marchal and Yves Robert, "Independent and Divisible Task Scheduling on Heterogeneous Star-shaped Platforms with Limited Memory", Report LIP RR-2004-22, April 2004. RR-2004-22

  • Hélène Renard, Yves Robert and Frédéric Vivien, " Data redistribution algorithms for heterogeneous processor rings", Report LIP RR-2004-28, May 2004. RR-2004-28

  • Olivier Beaumont, Loris Marchal and Yves Robert, "Broadcast trees for heterogeneous platforms", Report LIP RR-2004-46, November 2004. RR-2004-46

    2005

  • Loris Marchal, Yves Robert, Pascale Vicat-Blanc Primet and Jingdi Zeng, "Optimizing network resource sharing in grids", Report LIP RR-2005-10, March 2005. RR-2005-10

  • Olivier Beaumont, Loris Marchal and Yves Robert, "Scheduling divisible loads with return messages on heterogeneous master-worker platforms", Report LIP RR-2005-21, May 2005. RR-2005-21

  • Jean-François Pineau, Yves Robert and Frédéric Vivien "Off-line and on-line scheduling on heterogeneous master-slave platforms", Report LIP RR-2005-31, July 2005. RR-2005-31

  • Loris Marchal, Yves Robert, Pascale Vicat-Blanc Primet and Jingdi Zeng, "Scheduling network requests with transmission window", Report LIP RR-2005-32, July 2005. RR-2005-32

  • Olivier Beaumont, Larry Carter, Jeanne Ferrante, Arnaud Legrand, Loris Marchal and Yves Robert, "Scheduling multiple bags of tasks on heterogeneous master-worker platforms: centralized versus distributed solutions", Report LIP RR-2005-45, September 2005. RR-2005-45

  • Jean-François Pineau, Yves Robert and Frédéric Vivien "The impact of heterogeneity on master-slave on-line scheduling", Report LIP RR-2005-51, October 2005. RR-2005-51

  • Olivier Beaumont, Loris Marchal, Veronika Rehn and Yves Robert, "FIFO scheduling of divisible loads with return messages under the one-port model", Report LIP RR-2005-52, October 2005. RR-2005-52

    2006

  • Loris Marchal, Veronika Rehn, Yves Robert and Frédéric Vivien, "Scheduling and data redistribution strategies on star platforms", Report LIP RR-2006-23, June 2006. RR-2006-23

  • Matthieu Gallet, Yves Robert and Frédéric Vivien, "Scheduling communication requests traversing a switch: complexity and algorithms", Report LIP RR-2006-25, June 2006. RR-2006-25

  • Anne Benoit, Veronika Rehn and Yves Robert, "Strategies for replica placement in tree networks", Report LIP RR-2006-30, October 2006. RR-2006-30

  • Jean-François Pineau, Yves Robert and Frédéric Vivien, "Revisiting matrix product on master-worker platforms", Report LIP RR-2006-39, November 2006. RR-2006-39

  • Anne Benoit, and Yves Robert, "Mapping pipeline skeletons onto heterogeneous platforms", Report LIP RR-2006-40, November 2006. RR-2006-40

  • ...


  • Link to related people

    Link to my Ph.D. Students

  • Matthieu Gallet (co-supervising with Frédéric Vivien )
  • Jean-François Pineau (co-supervising with Frédéric Vivien )
  • Veronika Rehn (co-supervising with Anne Benoit )
  • Link to goners (some former Ph.D. Students)

  • Vincent Boudet
  • Pierre Boulet
  • Pierre-Yves Calland
  • Henri-Pierre Charles
  • Arnaud Legrand
  • Loris Marchal
  • Serge Miguet
  • Cyril Randriamaro
  • Hélène Renard
  • Tanguy Risset
  • Link to other researchers in LIP

  • Anne Benoit
  • Alain Darte
  • Eddy Caron
  • Frédéric Desprez
  • Fabrice Rastello
  • Frédéric Vivien

  • Teaching material



    Epreuve orale d'informatique aux concours des ENS


    Nous avons rassemblé quelques documents qui ont servi de base de travail pour faire passer l'épreuve orale d'Informatique commune aux trois ENS Cachan, Lyon, et Ulm en 1999.
    Cliquer ici pour le fichier postcript compressé (avec gzip).

    Epreuve d'informatique, écrit du concours 2005 des ENS


    Voici le sujet et le corrigé de cette épreuve:
    Cliquer ici pour le fichier .pdf.

    Cours Parallélisme


    Le contenu du polycopié "Algorithmes et Architectures Parallèles" n'est plus disponible en ligne:
    il a donné lieu au livre "Algorithmique Parallèle: Cours et exercices corrigés", par Arnaud Legrand et Yves Robert, Dunod 2003.
    Des compléments en ligne pour cet excellent ouvrage sont accessibles sur cette page



    Transparents (cours et TD)

    Machines P-RAM et réseaux de tri (fichier postcript)
    TD 1(fichier postcript)
    Algorithmique sur anneau de processeurs (fichier postcript)
    TD 2 (fichier postcript)
    Communications, routage et algorithmique (fichier postcript)
    Algorithmique hétérogène (fichier postcript)
    Les 6 documents précédents, avec 2 transparents par page (fichier postcript)
    Parallélisation automatique (fichier postcript)
    TD 4 et 5 (fichier postcript)
    Pipeline logiciel (fichier postcript)

    Cours Algorithmique MIM1/L3

    Corrigé du DM1 sur les partitions et tableaux de Young, par Bastien Boussau
    Fichier postcript

    Polycopié du cours et des TD d'algorithmique, avec leur corrigé (attention, fichier de 3 mégaoctets)
    Fichier postcript


    Quelques lectures pour le cours

    Chaines additives, pour les curieux

    Chaines additives, pour les curieux

    *** Making change, article à lire ***

    Making change, pour les curieux

    Coloriage de graphes et intervalles, pour les curieux

    Documents divers


    Exposé "Petit L3IF deviendra grand chercheur" (introduction aux métiers de chercheur et d'enseignant chercheur)

    Fichier pdf

    Dernier rapport d'activité du LIP (2005)

    Fichier postcript