• Chapter: Algorithms and scheduling techniques for clusters and grids. Anne Benoit, Loris Marchal, Yves Robert, and Frédéric Vivien. In Advances in Parallel Computing, vol.18: High Speed and Large Scale Scientific Computing, 2009. IOS Press. ISBN 978-1-60750-073-5.
  
  
• Introduction to Scheduling, Yves Robert and Frédéric Vivien, editors, 2009. Chapman and Hall/CRC Press. ISBN 9781420072730.
  
  
• Chapter: Divisible load scheduling. Matthieu Gallet, Yves Robert, and Frédéric Vivien. In Introduction to Scheduling, 2009. Chapman and Hall/CRC Press. ISBN 9781420072730.
  
  
• Chapter: Algorithmic Issues in Grid Computing. Yves Robert and Frédéric Vivien. In Algorithms and Theory of Computation Handbook, 2009, second edition. Chapman and Hall/CRC Press. ISBN 9781584888185.
  
  
• Scheduling and Automatic Parallelization by Alain Darte, Yves Robert, and Frédéric Vivien, Birkhäuser Boston, 2000. ISBN 0-8176-4149-1.
  
  
• Chapter: Loop Parallelization Algorithms by Alain Darte, Yves Robert, and Frédéric Vivien, in volume 1808 of LNCS on Compiler Optimizations for Scalable Parallel Systems: Languages, Compilation Techniques, and Run Time Systems, Dharma P. Agrawal and Santosh Pande editors, pages 141-172. Springer Verlag, 2001.
  PDF
  

• Static worksharing strategies for heterogeneous computers with unrecoverable interruptions. Anne Benoit, Yves Robert, Arnold Rosenberg, and Frédéric Vivien. In Parallel Computing, 2010, to appear.
  PDF.
  
  
• Energy-aware scheduling of bag-of-tasks applications on master-worker platforms. Jean-Francois Pineau, Yves Robert, and Frédéric Vivien. In Concurrency and Computation: Practice and Experience, 2010, to appear.
  PDF.
  
  
• Scheduling concurrent bag-of-tasks applications on heterogeneous platforms. Anne Benoit, Loris Marchal, Jean-François Pineau, Yves Robert, and Frédéric Vivien. In IEEE Transactions on Computers, vol 59(2), pages 202-217, 2010.
  PDF and web supplementary material(PDF).
  
  
• Minimizing the stretch when scheduling flows of divisible requests. Arnaud Legrand, Alan Su, and Frédéric Vivien. In Journal of Scheduling, vol 11(5), pages 381-404, 2008.
  PDF.
  Abstract and corresponding research report.
  
  
• Comments on "Design and performance evaluation of load distribution strategies for multiple loads on heterogeneous linear daisy chain networks". Matthieu Gallet, Yves Robert, and Frédéric Vivien. In Journal of parallel and distributed computing, 68(7): 1021-1031, 2008.
  PDF.
  Abstract and corresponding research report.
  
  
• The impact of heterogeneity on master-slave scheduling. Jean-François Pineau, Yves Robert, and Frédéric Vivien. In Parallel computing, 2008, 34(3): 158-176.
  PDF.
  Abstract and corresponding research report.
  
  
• Revisiting Matrix Product on Master-Worker Platforms. Jack Dongarra, Jean-François Pineau, Yves Robert, Zhiao Shi, and Frédéric Vivien. In International Journal of Foundations of Computer Science 19(6):1317-1336, 2008.
  PDF.
  Abstract and corresponding research report.
  
  
• A step towards unifying schedule and storage optimization. William Thies, Frédéric Vivien, and Saman Amarasinghe. In ACM Transactions on Programming Languages and Systems (TOPLAS), 29(6), 2007 (article 34, 45 p.).
  PDF.
  
  
• Scheduling algorithms for data redistribution and load-balancing on master-slave platforms. Loris Marchal, Veronika Rehn, Yves Robert, and Frédéric Vivien. In Parallel Processing Letters, 17(1):61-77, 2007.
  PDF.
  Abstract and corresponding research report.
  
  
• Automatic Middleware Deployment Planning on Clusters. Pushpinder-Kaur Chouhan, Holly Dail, Eddy Caron, and Frédéric Vivien. In International Journal of High Performance Computing Applications, 20(4):517-530, November 2006.
  PDF.
  Abstract and corresponding research report.
  
  
• Data redistribution algorithms for homogeneous and heterogeneous processor rings. Hélène Renard, Yves Robert, and Frédéric Vivien. In International Journal of High Performance Computing Applications, 20:31-43, 2006.
  PDF.
  Abstract and corresponding research report.
  
  
• Scheduling tasks sharing files on heterogeneous master-slave platforms. Arnaud Giersch, Yves Robert, and Frédéric Vivien. In Journal of Systems Architecture, 52(2): 88-104, 2006.
  PDF.
  Abstract and corresponding research report.
  
  
• Load-Balancing Scatter Operations for Grid Computing. Stéphane Genaud, Arnaud Giersch, and Frédéric Vivien. In Parallel computing 30(8): 923-946, 2004.
  The article on the journal web site.
  Gziped PostScript or PDF.
  Abstract and corresponding research report.
  
  
• Minimal enclosing parallelepiped in 3D. Frédéric Vivien and Nicolas Wicker. Computational Geometry: Theory and Applications 29(3): 177-190, 2004.
  The article on the journal web site.
  PDF
  Abstract and corresponding research report.
  Library implementing the algorithm.
  
  
• Mapping and Load-Balancing Iterative Computations. Arnaud Legrand, Hélène Renard, Yves Robert, and Frédéric Vivien. IEEE Transactions on Parallel and Distributed Systems15 (6):546-558, June 2004.
  The article on the journal web site.
  PDF
  Corresponding research report.
  
  
• On the optimality of Feautrier's scheduling algorithm. Frédéric Vivien. Concurrency and Computation:Practice and Experience, 15(11-12): 1047-1068, September 2003 (special issue on Euro-Par 2002). © 2003 John Wiley & Sons Ltd.
  The article on the journal web site.
  Compressed PostScript or PDF
  Abstract and corresponding research report.
  
  
• Constructing and exploiting linear schedules with prescribed parallelism. Alain Darte, Robert Schreiber, B. Ramakrishna Rau, and Frédéric Vivien. ACM Transactions on Design Automation of Electronic Systems, 7(1):159-172, January 2002.
  PDF
  Abstract and corresponding research report: A constructive solution to the juggling problem in systolic array synthesis.
  
  
• Algorithmic issues on heterogeneous computing platforms. Pierre Boulet, Jack Dongarra, Fabrice Rastello, Yves Robert, and Frédéric Vivien. Parallel Processing Letters, 9(2):197-213, June 1999.
  Compressed PostScript or PDF
  Abstract and corresponding research report: Algorithmic Issues on Heterogeneous Computing Platforms.
  
  
• Static tiling for heterogeneous computing platforms. Pierre Boulet, Jack Dongarra, Yves Robert, and Frédéric Vivien. Parallel Computing, 25(5):547-568, May 1999.
  Compressed PostScript or PDF
  Abstract and corresponding research report: Tiling for heterogeneous computing platforms.
  
  
• Retiming DAG's. Pierre-Yves Calland, Anne Mignotte, Olivier Peyran, Yves Robert, and Frédéric Vivien. IEEE Transactions on Computer-Aided Design of integrated circuits and systems, 17(12):1319-1325, December 1998.
  PDF
  Abstract and corresponding research report: Retiming DAGs.
  
  
• On the Removal of Anti- and Output-Dependences. Pierre-Yves Calland, Alain Darte, Yves Robert, and Frédéric Vivien. International Journal of Parallel Programming, 26(3):285-312, June 1998.
  PDF
  Abstract and corresponding research report: On the removal of anti and output dependences.
  
  
• Loop parallelization algorithms: From parallelism extraction to code generation. Pierre Boulet, Alain Darte, Georges-André Silber, and Frédéric Vivien. Parallel Computing, 24(3-4):421-444, May 1998, special issue on "Languages and Compilers for Parallel Computers".
  Compressed PostScript or PDF
  Abstract and corresponding research report: Loop parallelization algorithms: from parallelism extraction to code generation.
  
  
• Optimal Fine and Medium Grain Parallelism Detection in Polyhedral Reduced Dependence Graphs. Alain Darte and Frédéric Vivien. International Journal of Parallel Programming, 25(6):447-496, December 1997.
  Compressed PostScript or PDF
  Abstract and corresponding research report: Optimal fine and medium grain parallelism detection in polyhedral reduced dependence graphs
  
  
• Combining Retiming and Scheduling Techniques for Loop Parallelization and Loop Tiling. Alain Darte, Georges-André Silber, and Frédéric Vivien. Parallel Processing Letters, 7(4):379-392, December 1997.
  Compressed PostScript
  Abstract and corresponding research report: Combining retiming and scheduling techniques for loop parallelization and loop tiling.
  
  
• Parallelizing Nested Loops with Approximation of Distance Vectors: A Survey. Alain Darte and Frédéric Vivien. Parallel Processing Letters, 7(2):133-144, June 1997.
  Compressed PostScript
  Abstract and corresponding research report: A comparison of nested loops parallelization algorithms.
  
  
• On the optimality of Allen and Kennedy's algorithm for parallelism extraction in nested loops. Alain Darte and Frédéric Vivien. Journal of Parallel Algorithms and Applications, Special issue on "Optimizing Compilers for Parallel Languages", 12:83-112, 1997.
  Compressed PostScript
  Abstract and corresponding research report: On the optimality of Allen and Kennedy's algorithm for parallelism extraction in nested loops.
  
  
• Plugging anti and output dependence removal techniques into loop parallelization algorithms. Pierre-Yves Calland, Alain Darte, Yves Robert, and Frédéric Vivien. Parallel Computing, 23(1-2):251-266, April 1997. Special issue on "Environment and tools for parallel scientific computing".
  Compressed PostScript or PDF
  Abstract and corresponding research report: Plugging anti and output dependence removal techniques into loop parallelization algorithms.
  
  
• Revisiting the decomposition of Karp, Miller and Winograd. Alain Darte and Frédéric Vivien. Parallel Processing Letters, 5(4), 551-562, December 1995.
  Compressed PostScript
  Abstract and corresponding research report: Automatic parallelization based on multi-dimensional scheduling.

• Dynamic Fractional Resource Scheduling for HPC Workloads. Mark Stillwell, Frédéric Vivien, and Henri Casanova. In Proceedings of the 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS 2010), Atlanta (GA), USA, April 19-23, 2010. IEEE Computer Society Press.
  Submitted version (PDF).
  
  
• Static Worksharing Strategies for Heterogeneous Computers with Unrecoverable Failures Anne Benoit, Yves Robert, Arnold Rosenberg, and Frédéric Vivien. In Proceedings of HeteroPar 2009, volume ???? of LNCS, pages ???-???, Delft, The Netherlands, August 25, 2009.
  PDF.
  Abstract and corresponding research report.
  
  
• Energy-aware scheduling of flow applications on master-worker platforms. Jean-Francois Pineau, Yves Robert, and Frédéric Vivien. In Proceedings of Euro-Par 2009, volume 5704 of LNCS, pages 281-292, Delft, The Netherlands, August 25-28, 2009.
  PDF.
  Abstract and corresponding research report.
  
  
• Resource-aware allocation strategies for divisible loads on large-scale systems. Anne Benoit, Loris Marchal, Jean-Francois Pineau, Yves Robert, and Frédéric Vivien. In Proceedings of the 18th International Heterogeneity in Computing Workshop (HCW 2009) , Roma, Italy, May 25, 2009. IEEE Computer Society Press.
  PDF.
  
  
• Resource allocation using virtual clusters. Mark Stillwell, David Schanzenbach, Frédéric Vivien, and Henri Casanova. In Proceedings of the 9th IEEE International Symposium on Cluster Computing and the Grid (CCGrid 09), Shangai, China, May 18-21, 2009. IEEE Computer Society Press.
  PDF.
  Abstract and corresponding research report.
  
  
• Efficient scheduling of task graph collections on heterogeneous resources. Matthieu Gallet, Loris Marchal, and Frédéric Vivien. In Proceedings of the 23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS 2009), Roma, Italy, May 25-29, 2009. IEEE Computer Society Press.
  PDF.
  Abstract and corresponding research report.
  
  
• Static strategies for worksharing with unrecoverable interruptions. Anne Benoit, Yves Robert, Arnold L. Rosenberg, and Frédéric Vivien. In Proceedings of the 23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS 2009), Roma, Italy, May 25-29, 2009. IEEE Computer Society Press.
  PDF.
  Abstract and corresponding research report.
  
  
• Parallel large scale inference of protein domain families. Daniel Kahn, Clément Rezvoy, and Frédéric Vivien. In Proceedings of the 14th IEEE International Conference on Parallel and Distributed Systems (ICPADS'08), pages 72-79, Melbourne, Victoria, Australia, December 8-10, 2008. IEEE Computer Society Press.
  PDF.
  Abstract and corresponding research report.
  
  
• Allocating Series of Workflows on Computing Grids. Matthieu Gallet, Loris Marchal, and Frédéric Vivien. In Proceedings of the 14th IEEE International Conference on Parallel and Distributed Systems (ICPADS'08), pages 48-55, Melbourne, Victoria, Australia, December 8-10, 2008. IEEE Computer Society Press.
  PDF.
  Abstract and corresponding research report.
  
  
• Offline and online master-worker scheduling of concurrent bags-of-tasks on heterogeneous platforms. Anne Benoit, Loris Marchal, Jean-François Pineau, Yves Robert, and Frédéric Vivien. In Proceedings of 10th Workshop on Advances on Parallel and Distributed Processing Symposium (APDCM 2008), Miami, FL, USA, April 14, 2008. Workshop held in conjunction with IPDPS 2008. IEEE Computer Society Press.
  PDF.
  Abstract and corresponding research report.
  
  
• Matrix product on heterogeneous master-worker platforms. Jack Dongarra, Jean-François Pineau, Yves Robert, and Frédéric Vivien. In Proceedings of 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming (PPoPP), Salt Lake City, UT, USA, February 20-23, 2008.
  PDF.
  Abstract and corresponding research report.
  
  
• Scheduling multiple divisible loads on a linear processor network. Matthieu Gallet, Yves Robert, and Frédéric Vivien. In Proceedings of ICPADS'2007, the 13th International Conference on Parallel and Distributed Systems, Taiwan, December 2007.
  PDF.
  Abstract and corresponding research report.
  
  
• A First Step Towards Automatically Building Network Representations. Lionel Eyraud-Dubois, Arnaud Legrand, Martin Quinson, and Frédéric Vivien. In Proceedings of Euro-Par 2007 Parallel Processing, volume 4641 of LNCS, pages 160-169, Rennes, France, August 2007.
  PDF.
  Abstract and corresponding research report.
  
  
• Revisiting Matrix Product on Master-Worker Platforms. Jack Dongarra, Jean-François Pineau, Yves Robert, Zhiao Shi, and Frédéric Vivien. In Proceedings of the 9th Workshop on Advances in Parallel and Distributed Computational Models (APDCM), Long Beach, CA, USA, March 26, 2007. Workshop held in conjunction with IPDPS 2007. IEEE Computer Society Press.
  PDF.
  Abstract and corresponding research report.
  
  
• Scheduling and data redistribution strategies on star platforms. Loris Marchal, Veronika Rehn, Yves Robert, and Frédéric Vivien. In Proceedings of PDP'2007, 15th Euromicro Workshop on Parallel, Distributed and Network-based Processing, Naples, Italy, February 7-9, 2007. IEEE Computer Society Press.
  PDF.
  Abstract and corresponding research report.
  
  
• Scheduling communication requests traversing a switch: complexity and algorithms. Matthieu Gallet, Yves Robert, and Frédéric Vivien. In Proceedings of PDP'2007, 15th Euromicro Workshop on Parallel, Distributed and Network-based Processing, Naples, Italy, February 7-9, 2007. IEEE Computer Society Press.
  PDF.
  Abstract and corresponding research report.
  
  
• Minimizing the stretch when scheduling flows of biological requests. Arnaud Legrand, Alan Su, and Frédéric Vivien. In Proceedings of SPAA 2006, Cambridge, MA, USA July 30 - August 2, 2006.
  PDF.
  Abstract and corresponding research report.
  
  
• How should you structure your hierarchical scheduler ? Pushpinder Kaur Chouhan, Holly Dail, Eddy Caron, and Frédéric Vivien. In Proceedings of the 15th IEEE International Symposium on High Performance Distributed Computing (HPDC-15), Paris, France, pages 339-340 (Poster), June 19-23, 2006.
  PDF.
  Abstract and corresponding research report.
  
  
• The impact of heterogeneity on master-slave on-line scheduling. Jean-François Pineau, Yves Robert, and Frédéric Vivien. Proceedings of HCW 2006, Rhodes, Greece, April 25, 2006.
  PDF.
  Abstract and corresponding research report.
  
  
• Off-line and on-line scheduling on heterogeneous master-slave platforms. Jean-François Pineau, Yves Robert, and Frédéric Vivien. Proceedings of the 14th Euromicro Conference on Parallel, Distributed and Network based Processing, pages 439-446, Montbéliard-Sochaux, France, February 15-17, 2006.
  PDF.
  Abstract and corresponding research report.
  
  
• Off-line scheduling of divisible requests on an heterogeneous collection of databanks. Arnaud Legrand, Alan Su, and Frédéric Vivien. Proceedings of HCW 2005, Denver, Colorado, USA, April 4, 2005.
  PDF.
  Abstract and corresponding research report.
  
  
• Data redistribution algorithms for homogeneous and heterogeneous processor rings. Hélène Renard, Yves Robert, and Frédéric Vivien. Proceedings of HiPC 2004, volume 3296 of LNCS, pages 123-132, Bangalore, India, Dec. 19-22, 2004.
  Gziped PostScript or PDF.
  Abstract and corresponding research report.
  
  
• Scheduling tasks sharing files from distributed repositories. Arnaud Giersch, Yves Robert, and Frédéric Vivien. Proceedings of Euro-Par 2004, volume 3149 of LNCS, pages 246-253, Pisa, Italy, Aug. 31 - Sep. 3, 2004.
  Gziped PostScript or PDF.
  Abstract and corresponding research report.
  
  
• Scheduling tasks sharing files on heterogeneous master-slave platforms. Arnaud Giersch, Yves Robert, and Frédéric Vivien. In Proceedings of the 12-th Euromicro Conference on Parallel, Distributed and Network based Processing, A Coruña, Spain, February, 11-13, 2004, pages 364-371, IEEE Press.
  Gziped PostScript or PDF.
  Abstract and corresponding research report.
  
  
• Scheduling tasks sharing files on heterogeneous clusters. Arnaud Giersch, Yves Robert, and Frédéric Vivien. Poster in Proceedings of 10th European PVM/MPI User's Group Meeting, volume 2840 of LNCS, pages 657-660, Venice, Italy, Sep 29 - Oct 2, 2003.
  PDF.
  Abstract and corresponding research report.
  
  
• Mapping and load-balancing iterative computations on heterogeneous clusters. Arnaud Legrand, Hélène Renard, Yves Robert, and Frédéric Vivien. In Proceedings of 10th European PVM/MPI User's Group Meeting, volume 2840 of LNCS, pages 586-594, Venice, Italy, Sep 29 - Oct 2, 2003.
  PDF.
  No corresponding research report.
  
  
• Load-balancing iterative computations on heterogeneous clusters with shared communication links. Arnaud Legrand, Hélène Renard, Yves Robert, and Frédéric Vivien. Presented at the International Workshop on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks (HeteroPar'03) whose proceedings are published in conjunction with those of the Fifth International Conference on Parallel Processing and Applied Mathematics (PPAM 2003) volume 3019 of LNCS, pages 930-937, Czestochowa, Poland, September 7-10, 2003.
  Gziped PostScript or PDF.
  Abstract and corresponding research report.
  
  
• Static load-balancing techniques for iterative computations on heterogeneous clusters. Hélène Renard, Yves Robert, and Frédéric Vivien. Distinguished paper in volume 2790 of the LNCS, pages 148-159, Klagenfurt, Austria, August 26-29, 2003.
  PDF.
  Abstract and corresponding research report.
  
  
• Load-Balancing Scatter Operations for Grid Computing. Stéphane Genaud, Arnaud Giersch, and Frédéric Vivien. In Proceedings of the 12th Heterogeneous Computing Workshop (HCW 2003), Nice, France, April 22, 2003.
  Gziped PostScript or PDF.
  Abstract and corresponding research report.
  
  
• On the Optimality of Feautrier's Scheduling Algorithm. Frédéric Vivien. In Proceedings of Euro-Par 2002, volume 2400 of LNCS, pages 299-308, Paderborn, Germany, August 2002.
  Gziped PostScript or PDF © Springer-Verlag.
  Presentation slides: PDF.
  Abstract and corresponding research report (including the proofs).
  
  
• Incrementalized Pointer and Escape Analysis. Frédéric Vivien and Martin Rinard. ACM SIGPLAN'01 Conference on Programming Language Design and Implementation (PLDI), SNOWBIRD, UTAH, June 2001.
  Gziped PostScript or PDF.
  Presentation: PDF or Power Point.
  Abstract and corresponding research report.
  
  
• A Unified Framework for Schedule and Storage Optimization. William Thies, Frédéric Vivien, Jeffrey Sheldon, and Saman Amarasinghe. ACM SIGPLAN'01 Conference on Programming Language Design and Implementation (PLDI), SNOWBIRD, UTAH, June 2001.
  Gziped PostScript or PDF.
  Presentation: PDF or Power Point.
  Abstract and corresponding research report.
  
  
• Scheduling the Computations of a Loop Nest with Respect to a Given Mapping. Alain Darte, Claude Diderich, Marc Gengler, and Frédéric Vivien. In Proceedings of Euro-Par 2000, volume 1900 of LNCS, pages 405-414, Munich, Germany, September 2000.
  Gziped PostScript or PDF
  Abstract and corresponding research report.
  
  
• A Constructive Solution to the Juggling Problem in Processor Array Synthesis. Alain Darte, Robert Schreiber, B. Ramakrishna Rau, and Frédéric Vivien. International Parallel and Distributed Processing Symposium, IPDPS 2000, IEEE Press, May 2000.
  Compressed PostScript or PDF
  Abstract and corresponding research report: A constructive solution to the juggling problem in processor array synthesis.
  
  
• Retiming DAGs. Pierre-Yves Calland, Anne Mignotte, Olivier Peyran, Yves Robert, and Frédéric Vivien. In 1997 ACM/IEEE International Workshop on Timing Issues in the Specification and Synthesis of Digital Systems (TAU 97), pages 123-128, Austin, TX, USA, December 1997.
  Abstract and corresponding research report: Retiming DAGs.
  
  
• Optimal Fine and Medium Grain Parallelism Detection in Polyhedral Reduced Dependence Graphs. Alain Darte and Frédéric Vivien. Parallel Architectures and Compilation Techniques 1996 (PACT'96), IEEE Computer Society Press.
  PDF
  Abstract and corresponding research report: Optimal fine and medium grain parallelism detection in polyhedral reduced dependence graphs.
  
  
• On the Optimality of Allen and Kennedy's Algorithm for Parallelism Extraction in Nested Loops. Alain Darte and Frédéric Vivien. In Proceedings of Euro-Par 96, LNCS (1123), Springer Verlag, pages 379-388, Lyon, France, August 1996.
  PDF
  Abstract and corresponding research report: On the optimality of Allen and Kennedy's algorithm for parallelism extraction in nested loops.
  
  
• On the removal of anti and output dependences.. Pierre-Yves Calland, Alain Darte, Yves Robert, and Frédéric Vivien. Application Specific Systems, Architectures and Processors, J. Fortes, C. Mongenet, K. Parhi and V. Taylor editors, pages 353-364, Chicago, IL, USA, August 1996. IEEE Computer Society Press.
  PDF
  Abstract and corresponding research report: On the removal of anti and output dependences.
  
  
• A classification of nested loops parallelization algorithms. Alain Darte and Frédéric Vivien. INRIA-IEEE Symposium on Emerging Technologies and Factory Automation, IEEE Computer Society Press, , pages 217--224, Paris, France, October 1995. IEEE Computer Society Press.
  PDF
  Abstract and corresponding research report: A comparison of nested loops parallelization algorithms.
  
  
• Revisiting the decomposition of Karp, Miller and Winograd. Alain Darte and Frédéric Vivien. In P. Cappello, C. Mongenet, G.-R. Perrin, P. Quinton et Y. Robert, éditeurs, Application Specific Array Processors, pages 13-25, Strasbourg, France, July 1995. IEEE Computer Society Press.
  PDF
  Abstract and corresponding research report: Automatic parallelization based on multi-dimensional scheduling.

• Checkpointing strategies for parallel jobs
  
  
• Energy-aware scheduling of flow applications on master-worker platforms
  
  
• Resource Allocation using Virtual Clusters
  
  
• Static Strategies for Worksharing with Unrecoverable Interruptions
  
  
• Allocating Series of Workflows on Computing Grids
  
  
• Offline and online scheduling of concurrent bags-of-tasks on heterogeneous platforms
  
  
• Scheduling multiple divisible loads on a linear processor network
  
  
• A First Step Towards Automatically Building Network Representations
  
  
• Comments on ``Design and performance evaluation of load distribution strategies for multiple loads on heterogeneous linear daisy chain networks''
  
  
• Revisiting Matrix Product on Master-Worker Platforms
  
  
• Scheduling communication requests traversing a switch: complexity and algorithms
  
  
• Scheduling and data redistribution strategies on star platforms
  
  
• Minimizing the stretch when scheduling flows of divisible requests
  
  
• The impact of heterogeneity on master-slave on-line scheduling
  
  
• Automatic Middleware Deployment Planning on Clusters
  
  
• Minimizing the stretch when scheduling flows of biological requests
  
  
• Off-line and on-line scheduling on heterogeneous master-slave platforms
  
  
• Off-line scheduling of divisible requests on an heterogeneous collection of databanks
  
  
• Data redistribution algorithms for homogeneous and heterogeneous processor rings
  
  
• Scheduling tasks sharing files from distributed repositories (revised version)
  
  
• Scheduling tasks sharing files from distributed repositories
  
  
• Scheduling tasks sharing files on heterogeneous clusters
  
  
• Load-balancing iterative computations on heterogeneous clusters with shared communication links
  
  
• Load-Balancing Scatter Operations for Grid Computing
  
  
• Static load-balancing techniques for iterative computations on heterogeneous clusters
  
  
• Minimal enclosing parallelepiped in 3D
  
  
• On the Optimality of Feautrier's Scheduling Algorithm
  
  
• A Unified Framework for Schedule and Storage Optimization
  
  
• Incrementalized Pointer and Escape Analysis
  
  
• Scheduling the Computations of a Loop Nest with Respect to a Given Mapping
  
  
• A constructive solution to the juggling problem in systolic array synthesis
  
  
• Algorithmic Issues on Heterogeneous Computing Platforms
  
  
• Tiling for heterogeneous computing platforms
  
  
• Loop parallelization algorithms: from parallelism extraction to code generation
  
  
• Combining retiming and scheduling techniques for loop parallelization and loop tiling
  
  
• Plugging anti and output dependence removal techniques into loop parallelization algorithms
  
  
• Optimal fine and medium grain parallelism detection in polyhedral reduced dependence graphs
  
  
• On the optimality of Allen and Kennedy's algorithm for parallelism extraction in nested loops
  
  
• On the removal of anti and output dependences
  
  
• Retiming DAGs
  
  
• A comparison of nested loops parallelization algorithms
  
  
• Automatic parallelization based on multi-dimensional scheduling
  
  
• Ordonnancement multidimensionnel pour les équations récurrentes uniformes et affines (rapport de DEA : master thesis, in French)

• By: Marin Bougeret, Henri Casanova, Mikael Rabie, Yves Robert, and Frédéric Vivien
• Number: INRIA 7520
• Date: January 2011
• Abstract:

  This work provides a rigorous analysis of checkpointing strategies for sequential and parallel jobs. The objective is to minimize the expected job execution time in an environment that is subject to processor failures. For sequential jobs, we give the optimal solution if failure inter-arrival times are exponentially distributed. To the best of our knowledge, our result in the Exponential case is the first published rigorous proof that periodic checkpointing is optimal. In the general case (i.e., non-exponentially distributed), we give a dynamic programming algorithm that computes an accurate solution. For parallel jobs, we also provide the optimal solution in the Exponential case, which is given for various models of job parallelism and of checkpointing overhead. In the general case, we develop a dynamic programming algorithm to maximize the amount of work completed before the next failure, which provides a good heuristic solution for minimizing the expected execution time. To assess our work, we perform an extensive set of simulation experiments considering both Exponential and Weibull laws, as several studies have shown that Weibull distributions are the most appropriate to model the distribution of failures. These experiments corroborate all our theoretical results. Furthermore, they show that our dynamic programming algorithm far outperforms existing solutions when failure inter-arrival times follow a Weibull distribution.

• Keywords: Fault-tolerance, checkpointing, sequential job, parallel job, Weibull
• Get it: INRIA version : PDF.

• By: Jean-François Pineau, Yves Robert, and Frédéric Vivien
• Number: LIP 2008-36 / INRIA 6706
• Date: October 2008
• Abstract:

  In this report, we consider the problem of scheduling an application composed of independent tasks on a fully heterogeneous master-worker platform with communication costs. We introduce a bi-criteria approach aiming at maximizing the throughput of the application while minimizing the energy consumed by participating resources. Assuming arbitrary super-linear power consumption laws, we investigate different models for energy consumption, with and without start-up overheads. Building upon closed-form expressions for the uniprocessor case, we are able to derive optimal or asymptotically optimal solutions for both models.

• Keywords: Scheduling, energy, master-worker platforms, communication
• Get it: LIP version : PDF, INRIA version : Compressed PostScript or PDF.

• By: Henri Casanova, David Schanzenbach, Mark Stillwell, and Frédéric Vivien
• Number: LIP 2008-33 / INRIA 6692
• Date: October 2008
• Abstract:

  In this report we demonstrate the potential utility of resource allocation management systems that use virtual machine technology for sharing parallel computing resources among competing jobs. We formalize the resource allocation problem with a number of underlying assumptions, determine its complexity, propose several heuristic algorithms to find near-optimal solutions, and evaluate these algorithms in simulation. We find that among our algorithms one is very efficient and also leads to the best resource allocations. We then describe how our approach can be made more general by removing several of the underlying assumptions.

• Keywords: Virtualization, virtual cluster, scheduling, resource management, fairness
• Get it: LIP version : PDF, INRIA version : PDF.

• By:Anne Benoit, Yves Robert, Arnold L. Rosenberg, and Frédéric Vivien.
• Number: LIP 2008-29
• Date: October 2008
• Abstract:

  One has a large workload that is divisible ---its constituent work's granularity can be adjusted arbitrarily---and one has access to p remote computers that can assist in computing the workload. The problem is that the remote computers are subject to interruptions of known likelihood that kill all work in progress. One wishes to orchestrate sharing the workload with the remote computers in a way that maximizes the expected amount of work completed. Strategies for achieving this goal, by balancing the desire to checkpoint often, in order to decrease the amount of vulnerable work at any point, vs.~the desire to avoid the context-switching required to checkpoint, are studied. Strategies are devised that provably maximize the expected amount of work when there is only one remote computer (the case p=1). Results are presented that suggest the intractability of such maximization for higher values of p, which motivates the development of heuristic approaches. Heuristics are developed that replicate work on several remote computers, in the hope of thereby decreasing the impact of work-killing interruptions.

• Keywords:Fault-tolerance, scheduling, divisible loads, probabilities.
• Get it: LIP version : PDF.

• By:Matthieu Gallet, Loris Marchal, and Frédéric Vivien.
• Number: INRIA 6603
• Date: July 2008
• Abstract:

  In this report, we focus on scheduling jobs on computing Grids. In our model, a Grid job is made of a large collection of input data sets, which must all be processed by the same task graph or workflow, thus resulting in a series of workflow problem. We are looking for an efficient solution with regard to throughput and latency, while avoiding solutions requiring complex control. We thus only consider single-allocation strategies. We present an algorithm based on mixed linear programming to find an optimal allocation, and this for different routing policies depending on how much latitude we have on communications. Then, using simulations, we compare our allocations to reference heuristics. Our results show that our algorithm almost always finds an allocation with good throughput and low latency, and that it outperforms the reference heuristics, especially under communication-intensive scenarios.

• Keywords:
• Get it: INRIA version : PDF.

• By:Anne Benoit, Loris Marchal, Jean-François Pineau, Yves Robert, and Frédéric Vivien.
• Number: LIP 2007-48 / INRIA 6401
• Date: December 2007
• Abstract:

  Scheduling problems are already difficult on traditional parallel machines. They become extremely challenging on heterogeneous clusters, even when embarrassingly parallel applications are considered. In this paper we deal with the problem of scheduling multiple applications, made of collections of independent and identical tasks, on a heterogeneous master-worker platform. The applications are submitted online, which means that there is no a priori (static) knowledge of the workload distribution at the beginning of the execution. The objective is to minimize the maximum stretch, i.e. the maximum ratio between the actual time an application has spent in the system and the time this application would have spent if executed alone. On the theoretical side, we design an optimal algorithm for the offline version of the problem (when all release dates and application characteristics are known beforehand). We also introduce several heuristics for the general case of online applications. On the practical side, we have conducted extensive simulations and MPI experiments, showing that we are able to deal with very large problem instances in a few seconds. Also, the solution that we compute totally outperforms classical heuristics from the literature, thereby fully assessing the usefulness of our approach.

• Keywords:Heterogeneous master-worker platform, online scheduling, multiple applications.
• Get it: LIP version : PDF, INRIA version : Compressed PostScript or PDF.

• By:Matthieu Gallet, Yves Robert, and Frédéric Vivien.
• Number: LIP 2007-29 / INRIA 6235
• Date: June 2007
• Abstract:

  Min, Veeravalli, and Barlas have recently proposed strategies to minimize the overall execution time of one or several divisible loads on a heterogeneous linear network, using one or more installments. We show on a very simple example that their approach does not always produce a solution and that, when it does, the solution is often suboptimal. We also show how to find an optimal schedule for any instance, once the number of installments per load is given. Then, we formally state that any optimal schedule has an infinite number of installments under a linear cost model as the one assumed in the original papers. Therefore, such a cost model cannot be used to design practical multi-installment strategies. Finally, through extensive simulations we confirmed that the best solution is always produced by the linear programming approach, while solutions of the original papers can be far away from the optimal.

• Keywords: Scheduling, heterogeneous processors, divisible loads, single-installment, multiple-installments.
• Get it: LIP version : Compressed PostScript or PDF, INRIA version : Compressed PostScript or PDF.

• By:Lionel Eyraud-Dubois, Arnaud Legrand, Martin Quinson, and Frédéric Vivien.
• Number: LIP 2007-08 / INRIA 6133
• Date: February 2007
• Abstract:

  To fully harness Grids, users or middlewares must have some knowledge on the topology of the platform interconnection network. As such knowledge is usually not available, one must uses tools which automatically build a topological network model through some measurements. In this article, we define a methodology to assess the quality of these network model building tools, and we apply this methodology to representatives of the main classes of model builders and to two new algorithms. We show that none of the main existing techniques build models that enable to accurately predict the running time of simple application kernels for actual platforms. However some of the new algorithms we propose give excellent results in a wide range of situations.

• Keywords:Network model, topology reconstruction, Grids.
• Get it: LIP version : Compressed PostScript or PDF, INRIA version : Compressed PostScript or PDF.

• By:Matthieu Gallet, Yves Robert, and Frédéric Vivien.
• Number: LIP 2007-07 / INRIA 6123
• Date:February 2007
• Abstract:

  Min, Veeravalli, and Barlas proposed strategies to minimize the overall execution time of one or several divisible loads on a heterogeneous linear network, using one or more installments. We show on a very simple example that the proposed approach does not always produce a solution and that, when it does, the solution is often suboptimal. We also show how to find an optimal scheduling for any instance, once the number of installments per load is given. Finally, we formally prove that under a linear cost model, as in the original paper, an optimal schedule has an infinite number of installments. Such a cost model can therefore not be used to design practical multi-installment strategies.

• Keywords:Scheduling, heterogeneous processors, divisible loads, single-installment, multiple-installments.
• Get it: LIP version : Compressed PostScript or PDF, INRIA version : Compressed PostScript or PDF.

• By: Jack Dongarra, Jean-François Pineau, Yves Robert, Zhiao Shi, and Frédéric Vivien.
• Number: LIP 2006-39 / INRIA 6053
• Date: November 2006
• Abstract:

  This paper is aimed at designing efficient parallel matrix-product algorithms for heterogeneous master-worker platforms. While matrix-product is well-understood for homogeneous 2D-arrays of processors (e.g., Cannon algorithm and ScaLAPACK outer product algorithm), there are three key hypotheses that render our work original and innovative:
  

  • Centralized data. We assume that all matrix files originate from, and must be returned to, the master. The master distributes both data and computations to the workers (while in ScaLAPACK, input and output matrices are initially distributed among participating resources). Typically, our approach is useful in the context of speeding up MATLAB or SCILAB clients running on a server (which acts as the master and initial repository of files).
  • Heterogeneous star-shaped platforms. We target fully heterogeneous platforms, where computational resources have different computing powers. Also, the workers are connected to the master by links of different capacities. This framework is realistic when deploying the application from the server, which is responsible for enrolling authorized resources.
  • Limited memory. Because we investigate the parallelization of large problems, we cannot assume that full matrix panels can be stored in the worker memories and re-used for subsequent updates (as in ScaLAPACK). The amount of memory available in each worker is expressed as a given number of buffers, where a buffer can store a square block of matrix elements. The size q of these square blocks is chosen so as to harness the power of Level 3 BLAS routines: q=80 or 100 on most platforms.

  We have devised efficient algorithms for resource selection (deciding which workers to enroll) and communication ordering (both for input and result messages), and we report a set of numerical experiments on various platforms at École Normale Supérieure de Lyon and the University of Tennessee. However, we point out that in this first version of the report, experiments are limited to homogeneous platforms

• Keywords:Matrix product, LU decomposition, Master-worker platform, Heterogeneous platforms, Scheduling.
• Get it: LIP version : Compressed PostScript or PDF, INRIA version : Compressed PostScript or PDF.

• By: Matthieu Gallet, Yves Robert, and Frédéric Vivien
• Number: LIP 2006-25
• Date: June 2006
• Abstract:

  In this paper, we study the problem of scheduling file transfers through a switch. This problem is at the heart of a model often used for large grid computations, where the switch represents the core of the network interconnecting the various clusters that compose the grid. We establish several complexity results, and we introduce and analyze various algorithms, from both a theoretical and a practical perspective.

• Keywords:Grid computing, networks, scheduling file transfers, switch, complexity.
• Get it: LIP version : PDF.

• By: Loris Marchal, Veronika Rehn, Yves Robert, and Frédéric Vivien
• Number: LIP 2006-23 / INRIA 6005
• Date: June 2006
• Abstract:

  In this work we are interested in the problem of scheduling and redistributing data on master-slave platforms. We consider the case were the workers possess initial loads, some of which having to be redistributed in order to balance their completion times. We examine two different scenarios. The first model assumes that the data consists of independent and identical tasks. We prove the NP-completeness in the strong sense for the general case, and we present two optimal algorithms for special platform types. Furthermore we propose three heuristics for the general case. Simulations consolidate the theoretical results. The second data model is based on Divisible Load Theory. This problem can be solved in polynomial time by a combination of linear programming and simple analytical manipulations.

• Keywords:Master-slave platform, scheduling, data redistribution, one-port model, independent tasks, divisible load theory.
• Get it: LIP version : Compressed PostScript or PDF, INRIA version : Compressed PostScript or PDF.

• By: Arnaud Legrand , Alan Su , Frédéric Vivien
• Number: LIP 2006-19 / INRIA 6002
• Date: October 2006
• Abstract:

  In this paper, we consider the problem of scheduling distributed biological sequence comparison applications. This problem lies in the divisible load framework with negligible communication costs. Thus far, very few results have been proposed in this model. We discuss and select relevant metrics for this framework: namely max-stretch and sum-stretch. We explain the relationship between our model and the preemptive uni-processor case, and we show how to extend algorithms that have been proposed in the literature for the uni-processor model to the divisible multi-processor problem domain. We recall known results on closely related problems, we show how to minimize the max-stretch on unrelated machines either in the divisible load model or with preemption, we derive new lower bounds on the competitive ratio of any on-line algorithm, we present new competitiveness results for existing algorithms, and we develop several new on-line heuristics. We also address the Pareto optimization of max-stretch. Then, we extensively study the performance of these algorithms and heuristics in realistic scenarios. Our study shows that all previously proposed guaranteed heuristics for max-stretch for the uni-processor model prove to be inefficient in practice. In contrast, we show our on-line algorithms based on linear programming to be near-optimal solutions for max-stretch. Our study also clearly suggests heuristics that are efficient for both metrics, although a combined optimization is in theory not possible in the general case.

• Keywords:Bioinformatics, heterogeneous computing, scheduling, divisible load, linear programming, stretch.
• Get it: LIP version : Compressed PostScript or PDF, INRIA version : Compressed PostScript or PDF.

• By: Jean-François Pineau, Yves Robert, Frédéric Vivien
• Number: LIP 2005-51 / INRIA 5732
• Date: October 2005
• Abstract:

  In this paper, we assess the impact of heterogeneity for scheduling independent tasks on master-slave platforms. We assume a realistic one-port model where the master can communicate with a single slave at any time-step. We target on-line scheduling problems, and we focus on simpler instances where all tasks have the same size. While such problems can be solved in polynomial time on homogeneous platforms, we show that there does not exist any optimal deterministic algorithm for heterogeneous platforms. Whether the source of heterogeneity comes from computation speeds, or from communication bandwidths, or from both, we establish lower bounds on the competitive ratio of any deterministic algorithm. We provide such bounds for the most important objective functions: the minimization of the makespan (or total execution time), the minimization of the maximum response time (difference between completion time and release time), and the minimization of the sum of all response times. Altogether, we obtain nine theorems which nicely assess the impact of heterogeneity on on-line scheduling. These theoretical contributions are complemented on the practical side by the implementation of several heuristics on a small but fully heterogeneous MPI platform. Our (preliminary) results show the superiority of those heuristics which fully take into account the relative capacity of the communication links.

• Keywords: Scheduling, Master-slave platforms, Heterogeneous computing, On-line, Release dates.
• Get it: LIP version : Compressed PostScript or PDF, INRIA version : Compressed PostScript or PDF.

• By:Pushpinder Kaur Chouhan, Holly Dail, Eddy Caron, Frédéric Vivien
• Number: LIP 2005-50 / INRIA ????
• Date: October 2005
• Abstract:

  The use of many distributed, heterogeneous resources as a large collective resource offers great potential and has become an increasingly popular idea. A key issue for these Grid platforms is middleware scalability and how middleware services can best be mapped to the resource platform structure. Optimizing deployment is a difficult problem with no existing general solutions. In this paper we address a simpler sub-problem: how to carry out an adapted deployment on a cluster with hundreds of nodes? Efficient use of clusters alone or as part of the Grid is an important issue. In this paper we present an approach for automatically determining an optimal deployment for hierarchically distributed middleware services on clusters where the goal is to optimize steady-state request throughput. We prove that a complete spanning d-ary tree provides an optimal deployment and we present an algorithm to construct this optimal tree. We use a distributed Problem Solving Environment called DIET to test our approach. We define a performance model for each component of DIET and validate these models in a real-world cluster environment. Additional experiments demonstrate that our approach selects a deployment that performs better than other reasonable deployments.

• Keywords:Deployment, Cluster, Cluster computing, Network Enabled Server, Steady-state scheduling.
• Get it: LIP version : Compressed PostScript or PDF, INRIA version : Compressed PostScript or PDF.

• By: Arnaud Legrand, Alan Su, Frédéric Vivien
• Number: LIP 2005-48 / INRIA 5724
• Date: October 2005
• Abstract:

  In this paper, we consider the problem of scheduling comparisons of motifs against biological databanks. This problem lies in the divisible load framework with negligible communication costs. Thus far, very few results have been proposed in this model. We first explain the relationship between this model and the preemptive uni-processor one. After having selected a few relevant metrics (max-stretch and sum-stretch), we show how to extend algorithms that have been proposed in the literature for the uni-processor model to our setting. Then we extensively study the performance of these algorithms in realistic scenarios. Our study clearly suggest an efficient heuristic for each of the two metrics, though a combined optimization is in theory not possible in the general case.

• Keywords:Bioinformatics, heterogeneous computing, scheduling, divisible load, linear programming, stretch.
• Get it: LIP version : Compressed PostScript or PDF, INRIA version : Compressed PostScript or PDF.

• By: Jean-François Pineau, Yves Robert, Frédéric Vivien
• Number: LIP 2005-31 / INRIA 5634
• Date: July 2005
• Abstract:

  In this work, we deal with the problem of scheduling independent tasks on heterogeneous master-slave platforms. We target both off-line and on-line problems, with several objective functions (makespan, maximum response time, total completion time). On the theoretical side, our results are two-fold: (i) For off-line scheduling, we prove several optimality results for problems with release dates; (ii) For on-line scheduling, we establish lower bounds on the competitive ratio of any deterministic algorithm. On the practical side, we have implemented several heuristics, some classical and some new ones derived in this paper. We studied experimentally these heuristics on a small but fully heterogeneous MPI platform. Our results show the superiority of those heuristics which fully take into account the relative capacity of the communication links.

• Keywords: Scheduling, Master-slave platforms, Heterogeneous computing, On-line, Release dates.
• Get it: LIP version : Compressed PostScript or PDF, INRIA version : Compressed PostScript or PDF.

• By: Arnaud Legrand, Alan Su, Frédéric Vivien
• Number: LIP 2004-51 / INRIA 5386
• Date: November 2004
• Abstract:

  In this paper, we consider the problem of scheduling comparisons of motifs against biological databanks. We show that this problem lies in the divisible load framework. In this framework, we propose a polynomial-time algorithm to solve the maximum weighted flow off-line scheduling problem on unrelated machines. We also show how to solve the maximum weighted flow off-line scheduling problem with preemption on unrelated machines.

• Keywords: Bioinformatics, heterogeneous computing, scheduling, divisible load, linear programming, stretch, max weighted flow
• Get it: LIP version : Compressed PostScript or PDF, INRIA version : Compressed PostScript or PDF.

• By:Hélène Renard, Yves Robert, and Frédéric Vivien.
• Number: LIP 2004-28 / INRIA 5207
• Date: May 2004
• Abstract:

  We consider the problem of redistributing data on homogeneous and heterogeneous ring of processors. The problem arises in several applications, each time after that a load-balancing mechanism is invoked (but we do not discuss the load-balancing mechanism itself). We provide algorithms that aim at optimizing the data redistribution, both for uni-directional and bi-directional rings, and we give complete proofs of correctness. One major contribution of the paper is that we are able to prove the optimality of the proposed algorithms in all cases except that of a bi-directional heterogeneous ring, for which the problem remains open.

• Keywords: Heterogeneous Rings, Data Redistribution Algorithms, Load-Balancing.
• Get it: LIP version : Compressed PostScript or PDF, INRIA version : Compressed PostScript or PDF.

• By: Arnaud Giersch, Yves Robert, and Frédéric Vivien
• Number: LIP 2004-04 / INRIA 5124
• Date: February 2004
• Abstract:This paper is devoted to scheduling a large collection of independent tasks onto a large distributed heterogeneous platform, which is composed of a set of servers. Each server is a processor cluster equipped with a file repository. The tasks to be scheduled depend upon (input) files which initially reside on the server repositories. A given file may well be shared by several tasks. For each task, the problem is to decide which server will execute it, and to transfer the required files (those which the task depends upon) to that server repository. The objective is to find a task allocation, and to schedule the induced communications, so as to minimize the total execution time. The contribution of this paper is twofold. On the theoretical side, we establish complexity results that assess the difficulty of the problem. On the practical side, we design several new heuristics, including an extension of the \texttt{min-min} heuristic to the decentralized framework, and several lower cost heuristics, which we compare through extensive simulations.
  This report is a revised version of the LIP research report no. 2003-49 / INRIA research report no. 4976, which it replaces.

• Keywords: Scheduling, heterogeneous clusters, grid, independent tasks, file-sharing, heuristics.
• Get it: LIP version : Compressed PostScript or PDF, INRIA version : Compressed PostScript or PDF.

• By: Arnaud Giersch, Yves Robert, and Frédéric Vivien
• Number: LIP 2003-49 / INRIA 4976
• Date: October 2003
• Abstract: This paper is devoted to scheduling a large collection of independent tasks onto a large distributed heterogeneous platform, which is composed of a set of servers. Each server is a processor cluster equipped with a file repository. The tasks to be scheduled depend upon (input) files which initially reside on the server repositories. A given file may well be shared by several tasks. For each task, the problem is to decide on which server to execute it, and to transfer the required files (those which the task depends upon) to that server repository. The objective is to find a task allocation, and to schedule the induced communications, so as to minimize the total execution time. The contribution of this paper is twofold. On the theoretical side, we establish complexity results that assess the difficulty of the problem. On the practical side, we design several new heuristics, including an extension of the \texttt{min-min} heuristic to the decentralized framework, and several lower cost heuristics, which we compare through extensive simulations.

• Keywords: Scheduling, heterogeneous clusters, grid, independent tasks, file-sharing, heuristics.
• Get it: LIP version : Compressed PostScript or PDF, INRIA version : Compressed PostScript or PDF.

• By: Arnaud Giersch, Yves Robert, and Frédéric Vivien
• Number: LIP 2003-28 / INRIA 4819
• Date: May 2003
• Abstract: This paper is devoted to scheduling a large collection of independent tasks onto heterogeneous clusters. The tasks depend upon (input) files which initially reside on a master processor. A given file may well be shared by several tasks. The role of the master is to distribute the files to the processors, so that they can execute the tasks. The objective for the master is to select which file to send to which slave, and in which order, so as to minimize the total execution time. The contribution of this paper is twofold. On the theoretical side, we establish complexity results that assess the difficulty of the problem. On the practical side, we design several new heuristics, which are shown to perform as efficiently as the best heuristics of Casanova et al. although their cost is an order of magnitude lower.

• Keywords: Scheduling, heterogeneous clusters, grid, independent tasks, file-sharing, heuristics.
• Get it: LIP version : Compressed PostScript or PDF, INRIA version : Compressed PostScript or PDF.

• By: Arnaud Legrand, Hélène Renard, Yves Robert, and Frédéric Vivien
• Number: LIP 2003-23 / INRIA 4800
• Date: April 2003
• Abstract:

  This paper is devoted to mapping iterative algorithms onto heterogeneous clusters. The application data is partitioned over the processors, which are arranged along a virtual ring. At each iteration, independent calculations are carried out in parallel, and some communications take place between consecutive processors in the ring. The question is to determine how to slice the application data into chunks, and to assign these chunks to the processors, so that the total execution time is minimized. One major difficulty is to embed a processor ring into a network that typically is not fully connected, so that some communication links have to be shared by several processor pairs. We establish a complexity result that assesses the difficulty of this problem, and we design a practical heuristic that provides efficient mapping, routing, and data distribution schemes.

• Keywords: Heterogeneous clusters, load-balancing, shared communication links, complexity.
• Get it: LIP version : Compressed PostScript or PDF, INRIA version : Compressed PostScript or PDF.

• By: Stéphane Genaud, Arnaud Giersch, and Frédéric Vivien
• Number: LIP 2003-17 / INRIA 4770
• Date: March 2003
• Abstract:

  We present solutions to statically load-balance scatter operations in parallel codes run on grids. Our load-balancing strategy is based on the modification of the data distributions used in scatter operations. We study the replacement of scatter operations with parameterized scatters, allowing custom distributions of data. The paper presents: 1) a general algorithm which finds an optimal distribution of data across processors; 2) a quicker guaranteed heuristic relying on hypotheses on communications and computations; 3) a policy on the ordering of the processors. Experimental results with an MPI scientific code illustrate the benefits obtained from our load-balancing.

• Keywords: Parallel programming, grid computing, heterogeneous computing, load-balancing, scatter operation.
• Get it: LIP version : Compressed PostScript or PDF, INRIA version : Compressed PostScript or PDF.

• By: Hélène Renard, Yves Robert, and Frédéric Vivien
• Number: LIP 2003-12 / INRIA 4745
• Date: February 2003
• Abstract:

  This paper is devoted to static load balancing techniques for mapping iterative algorithms onto heterogeneous clusters. The application data is partitioned over the processors. At each iteration, independent calculations are carried out in parallel, and some communications take place. The question is to determine how to slice the application data into chunks, and to assign these chunks to the processors, so that the total execution time is minimized. We establish a complexity result that assesses the difficulty of this problem, and we design practical heuristics that provide efficient distribution schemes.

• Keywords: Heterogeneous Clusters, Static Load-balancing Techniques, Communication, Complexity.
• Get it: LIP version : Compressed PostScript or PDF, INRIA version : Compressed PostScript or PDF.

• By: Frédéric Vivien and Nicolas Wicker
• Number: LIP 2002-49 / INRIA 4685
• Date: December 2002
• Abstract:

  We investigate the problem of finding a minimal volume parallelepiped enclosing a given set of n three-dimensional points. We give two mathematical properties of these parallelepipeds, from which we derive two algorithms of theoretical complexity O(n^6). Experiments show that in practice our quickest algorithm runs in O(n^2) (at least for n <= 100000). We also present our application in structural biology.

• Keywords: Algorithmic geometry, parallelepiped, bioinformatic.
• Get it: LIP version : Compressed PostScript or PDF, INRIA version : Compressed PostScript or PDF.
• Software: Library implementing the algorithm.
  

• By: Frédéric Vivien
• Number: ICPS 2002-04
• Date: May 2002
• Abstract:

  Feautrier's scheduling algorithm is the most powerful existing algorithm for parallelism detection and extraction. But it has always been known to be suboptimal. However, the question whether it may miss some parallelism because of its design was still open. We show that this is not the case. Therefore, to find more parallelism than this algorithm does, one needs to get rid of some of the hypotheses underlying its framework.

• Keywords: Automatic Parallelization, Nested Loops, Scheduling, Optimality.
• Get it: Compressed PostScript or PDF

• By: William Thies, Frédéric Vivien, Jeffrey Sheldon, and Saman Amarasinghe
• Number: ICPS 2001-03
• Date: April 2001
• Abstract:

  We present a unified mathematical framework for analyzing the tradeoffs between parallelism and storage allocation within a parallelizing compiler. Using this framework, we show how to find a good storage mapping for a given schedule, a good schedule for a given storage mapping, and a good storage mapping that is valid for all legal schedules. We consider storage mappings that collapse one dimension of a multi-dimensional array, and programs that are in a single assignment form with a one-dimensional schedule. Our technique combines affine scheduling techniques with occupancy vector analysis and incorporates general affine dependences across statements and loop nests. We formulate the constraints imposed by the data dependences and storage mappings as a set of linear inequalities, and apply numerical programming techniques to efficiently solve for the shortest occupancy vector. We consider our method to be a first step towards automating a procedure that finds the optimal tradeoff between parallelism and storage space.

• Keywords: Automatic Parallelization, Nested Loops, Scheduling, Occupancy Vector, Memory optimization.
• Format: Compressed PostScript
• Get it

• By: Frédéric Vivien and Martin Rinard
• Number: ICPS 2001-02
• Date: April 2001
• Abstract:

  We present a new pointer and escape analysis. Instead of analyzing the whole program, the algorithm incrementally analyzes only those parts of the program that may deliver useful results. An analysis policy monitors the analysis results to direct the incremental investment of analysis resources to those parts of the program that offer the highest expected optimization return.

  Our experimental results show that almost all of the objects are allocated at a small number of allocation sites and that an incremental analysis of a small region of the program surrounding each site can deliver almost all of the benefit of a whole-program analysis. Our analysis policy is usually able to deliver this benefit at a fraction of the whole-program analysis cost.

• Keywords: Program Analysis, Incremental Analysis, Java.
• Format: Compressed PostScript
• Get it

• By: Alain Darte, Claude Diderich, Marc Gengler, and Frédéric Vivien
• Number: ICPS 2000-04
• Date: May 2000
• Abstract:

  When parallelizing loop nests for distributed memory parallel computers, we have to specify when the different computations are carried out (computation scheduling), where they are carried out (computation mapping), and where the data are stored (data mapping). We show that even the ``best'' scheduling and mapping functions can lead to a sequential execution when combined, if they are independently chosen. We characterize when combined scheduling and mapping functions actually lead to a parallel execution. We present an algorithm which computes a scheduling compatible with a given computation mapping, if such a schedule exists.

• Keywords: Automatic Parallelization, Multi-dimensional Schedule, Loop Nest, Computation Mapping, Polyhedral Reduced Dependence Graph.
• Format: Compressed PostScript
• Get it

• By: Alain Darte, Robert Schreiber, B. Ramakrishna Rau, and Frédéric Vivien
• Number: RR1999-15
• Date: February 1999
• Abstract:

  We describe a new, practical, constructive method for solving the well-known conflict-free scheduling problem for the locally sequential, globally parallel (LSGP) case of systolic array synthesis. Earlier attempts to solve this problem provided a solution with an important practical disadvantage, which we discuss. Here, we provide a closed form solution that enables the enumeration of all valid schedules. The second part of the paper discusses another practical issue: reducing the cost of hardware whose function is to control the flow of data, enable or disable functional units, and generate memory addresses. We present a new technique for controlling the complexity of these housekeeping functions in a systolic array. Both of these techniques have been incorporated into a software system for the automatic synthesis of hardware accelerators developed by HP Labs.

• Keywords: Hardware Accelerators, Systolic Arrays, Automatic Synthesis, LSGP Partitioning.
• Format: Compressed PostScript
• Get it

• By: Pierre Boulet, Fabrice Rastello, Yves Robert, and Frédéric Vivien
• Number: RR98-49
• Date: October 1998
• Abstract:

  This paper discusses some algorithmic issues when computing with a heterogeneous network of workstations (the typical poor man's parallel computer). Dealing with processors of different speeds requires to use more involved strategies than block-cyclic data distributions. Dynamic data distribution is a first possibility but may prove impractical and not scalable due to communication and control overhead. Static data distributions tuned to balance execution times constitute another possibility but may prove inefficient due to variations in the processor speeds (e.g. because of different workloads during the computation). We introduce a static distribution strategy that can be refined on the fly, and we show that it is well-suited to parallelizing scientific computing applications such as finite-difference stencils or LU decomposition.

• Keywords: Tiling, Heterogeneous Computing Platforms, Load Balancing, Distributed Memory, Different-Speed Processors, Communication-Computation Overlap, Mapping, LU decomposition, Relaxation.
• Format: Compressed PostScript
• Get it

• By: Pierre Boulet, Jack Dongarra, Yves Robert, and Frédéric Vivien
• Number: RR98-08
• Date: January 1998
• Abstract:

  In the framework of fully permutable loops, tiling has been extensively studied as a source-to-source program transformation. However, little work has been devoted to the mapping and scheduling of the tiles on physical processors. Moreover, targeting heterogeneous computing platforms has, to the best of our knowledge, never been considered. In this paper we extend tiling techniques to the context of limited computational resources with different-speed processors. In particular, we present efficient scheduling and mapping strategies that are asymptotically optimal. The practical usefulness of these strategies is fully demonstrated by MPI experiments on a heterogeneous network of workstations.

• Keywords: Tiling, Communication-Computation Overlap, Mapping, Limited Resources, Different-Speed Processors, Heterogeneous Networks.
• Format: Compressed PostScript
• Get it

• By: Pierre Boulet, Alain Darte, Georges-André Silber, and Frédéric Vivien
• Number: RR97-17
• Date: June 1997
• Abstract:

  In this paper, we survey loop parallelization algorithms, analyzing the dependence representations they use, the loop transformations they generate, the code generation schemes they require, and their ability to incorporate various optimizing criteria such as maximal parallelism detection, detection of permutable loops, minimization of synchronizations, easiness of code generation, etc. We complete the discussion by presenting new results related to code generation and loop fusion for a particular class of multi-dimensional schedules, called shifted linear schedules. We demonstrate that algorithms based on such schedules, while generally considered as too complex, can indeed lead to simple codes.

• Keywords: Automatic Parallelization, Nested Loops, Parallelization Algorithms, Loop Fusion, Synchronizations, Code Generation.
• Format: Compressed PostScript
• Get it

• By: Alain Darte, Georges-Andre Silber, and Frédéric Vivien
• Number: RR96-34
• Date: November 1996
• Abstract:

  Tiling is a technique used for exploiting medium-grain parallelism in nested loops. It relies on a first step that detects sets of permutable nested loops. All algorithms developed so far consider the statements of the loop body as a single block, in other words, they are not able to take advantage of the structure of dependences between different statements. In this report, we overcome this limitation by showing how the structure of the reduced dependence graph can be taken into account for detecting more permutable loops. Our method combines graph retiming techniques and graph scheduling techniques. It can be viewed as an extension of Wolf and Lam's algorithm to the case of loops with multiple statements. Loop independent dependences play a particular role in our study, and we show how the way we handle them can be useful for fine-grain loop parallelization as well.

• Keywords: Automatic parallelization, nested loops, permutable loops, tiling, medium grain.
• Citation: Presented in workshop at SPDP'96.
• Format: Compressed PostScript
• Get it

• By: Pierre-Yves Calland, Alain Darte, Yves Robert, and Frédéric Vivien
• Number: RR96-13
• Date: June 1996
• Abstract:

  In this paper we shortly survey some loop transformation techniques which break anti or output dependences, or artificial cycles involving such ``false'' dependences. These false dependences are removed through the introduction of temporary buffer arrays. Next we show how to plug these techniques into loop parallelization algorithms (such as Allen and Kennedy's algorithm). The goal is to extract as many parallel loops as the intrinsic degree of parallelism of the nest authorizes, while avoiding a full memory expansion. We try to reduce the number of temporary arrays that we introduce, as well as their dimension.

• Keywords: Array Renaming, Array expansion, Node Splitting, Anti Dependences, Output Dependences, dependence Graph, Parallelization Algorithm, Allen-Kennedy, Heuristics
• Citation: Submitted.
• Format: Compressed PostScript
• Get it

• By: Alain Darte and Frédéric Vivien
• Number: RR96-06
• Date: April, 1996
• Abstract:

  This paper presents an optimal algorithm for detecting fine or medium grain parallelism in nested loops whose dependences are described by an approximation of distance vectors by polyhedra. In particular, it is optimal for direction vectors: this result generalizes, to the case of several statements, Wolf and Lam's algorithm which is optimal for a single statement. Our algorithm relies on a dependence uniformization process and on parallelization techniques related to system of uniform recurrence equations.

• Keywords: Automatic Parallelization, Multi-dimensional Schedule, Loop Nest, System Of Uniform Recurrence Equations, Dependence Analysis, Polyhedral Reduced Dependence Graph.
• Citation: Appeared in the proceedings of PACT'96.
• Format: Compressed PostScript
• Get it

• By: Alain Darte and Frédéric Vivien
• Number: RR96-05
• Date: February 1996
• Abstract:

  We explore the link between dependence abstractions and maximal parallelism extraction in nested loops. Our goal is to find, for each dependence abstraction, the minimal transformations needed for maximal parallelism extraction. The result of this paper is that Allen and Kennedy's algorithm is optimal when dependences are approximated by dependence levels. This means that even the most sophisticated algorithm cannot detect more parallelism than found by Allen and Kennedy's algorithm, as long as dependence level is the only information available. In other words, loop distribution is sufficient for detecting maximal parallelism in dependence graphs with levels.

• Keywords: Nested Loops, Automatic Parallelization, Dependence Analysis, Allen and Kennedy's Algorithm.
• Citation: Appeared in the proceedings of Europar'96, Lyon, France.
• Format: Compressed PostScript
• Get it

• By: Pierre-Yves Calland, Alain Darte, Yves Robert, and Frédéric Vivien
• Number: RR96-04
• Date: February 1996
• Abstract:

  In this paper we build upon results of Padua and Wolfe, who introduce two graph transformations to eliminate anti and output dependences. We first give a unified framework for such transformations. Then, given a loop nest, we aim at determining which statements should be transformed so as to break artificial cycles involving anti or output dependences. The problem of finding the mininum number of statements to be transformed is shown to be NP-complete in the strong sense, and we propose two efficient heuristics.

• Keywords: Node Splitting, Anti Dependences, Output Dependences, Dependence Graph, NP-completeness, Heuristics.
• Citation: Appear in the proceedings of ASAP'96, Chicago.
• Format: Compressed PostScript
• Get it

• By: Pierre-Yves Calland, Anne Mignotte, Olivier Peyran, Yves Robert and Frédéric Vivien
• Number: RR95-18
• Date: September 1995
• Abstract:

  The increasing complexity of digital circuitry makes global design optimization no longer possible: a designer will only consider the critical parts of his circuit. This paper discusses timing optimization problems when these critical parts can be represented by Direct Acyclic Graphs (DAGs). We deal with different (though related) clock period problems, under various external constraints. The main algorithm concerns the determination of the optimal clock period of a given circuit. We propose an efficient solution, based on the retiming technique, which improves current results in the literature. We give three different formulations depending on which combinational gates delay model is used: same delay for every gate, different delays or non-uniform delays.

• Keywords: Direct Acyclic Graph, Clock Period, Optimization, Retiming, Delay Model, Registers.
• Citation: Submitted for publication.
• Format: Compressed PostScript
• Get it

• By: Alain Darte and Frédéric Vivien
• Number: RR95-11
• Date: May 24, 1995
• Abstract:

  In this paper, we compare three nested loops parallelization algorithms (Allen and Kennedy's algorithm, Wolf and Lam's algorithm and Darte and Vivien's algorithm) that use different representations of distance vectors as input. We identify the concepts that make them similar or different. We study the optimality of each with respect to the dependence analysis it uses. We propose well-chosen examples that illustrate the power and limitations of the three algorithms. This study permits to identify which algorithm is the most suitable for a given representation of dependences.

• Keywords: Automatic Parallelization, Dependence Analysis, Linear Programming.
• Citation: Appeared in INRIA-IEEE Symposium on Emerging Technologies and Factory Automation, IEEE Computer Society Press, 1995.
• Format: Compressed PostScript
• Get it

• By: Alain Darte and Frédéric Vivien
• Number: RR94-24
• Date: September 21, 1994
• Abstract:

  In the scope of uniform recurrence equations, we study an algorithm first proposed by Karp, Miller and Winograd for detecting cycles of null weight in cyclic graphs. We show how this algorithm can be used for generating multi-dimensional schedules that express all the potential parallelism contained in a computable system of uniform recurrence equations. We then apply this technique to imperative programs based on loop nests and whose dependences are described in the framework (Z, +, -, *), the most popular way of describing dependences. We are able to show that our technique is an optimal parallelization technique in the sense that no more parallelism can be detected than provided by our new algorithm.

• Keywords: Automatic Parallelization, Multi-dimensional Scheduling, Loop Nest, Systems Of Recurrence Equations, Dependence Analysis.
• Citation: Appeared in Parallel Processing Letters 5(4):551-562, December 1995.
• Format: Compressed PostScript
• Get it

• By: Frédéric Vivien
• Date: June, 1994
• Abstract:

  Dans ce rapport nous présentons un algorithme de construction d'un ordonnancement multidimensionnel pour les systèmes d'équations récurrentes uniformes. Cet algorithme est optimal en ordre de grandeur: il extrait tout le parallélisme existant du système traité. Cet algorithme est étendu au cas des systèmes d'équations récurrentes affines dont les dépendances sont décrites dans l'algèbre (Z, +, -, *). Une généralisation de cet algorithme au cas des nids de boucles non-parfait conclut l'exposé.

• Keywords: Nids de boucles, parallélisation automatique, ordonnancement multi-dimensionnel, analyse de dépendance, systèmes d'équations récurrentes.
• Format: Compressed PostScript
• Get it

Détection de parallélisme dans les boucles imbriquées.

• Date: December 1997
• Résumé :

  Nombre d'utilisateurs de l'informatique aimeraient pouvoir exécuter sur des ordinateurs parallèles leurs programmes « séquentiels » (écrits pour être exécutés sur des ordinateurs classiques). Il est donc devenu nécessaire de savoir « paralléliser » les programmes séquentiels en programmes exécutables sur machines parallèles. Cette parallélisation doit être automatique puisqu'elle s'adresse le plus souvent à de simples utilisateurs. Avant d'initier toute transformation du programme originel, il faut détecter et quantifier le parallélisme qu'il contient implicitement, ce qui requiert la connaissance des dépendances existant entre les différents calculs. Ultérieurement, il sera nécessaire de réordonner les calculs en explicitant le parallélisme découvert. Cette thèse a pour objet la détection automatique du parallélisme implicite et la recherche d'ordonnancements l'explicitant pour des structures de programmes particulières : les ensembles de boucles imbriquées. Nos travaux ont eu principalement pour but la compréhension des techniques existantes de détection de parallélisme, de leur points forts et de leurs limitations. D'un côté, nous avons étudié les principaux algorithmes préexistant à ces travaux. De l'autre, nous sommes partis du modèle théorique fourni par les systèmes d'équations récurrentes uniformes pour proposer un algorithme optimal de parallélisation des graphes de dépendance réduits polyédriques, représentation approchée des dépendances qui généralise les deux modes classiques d'approximation. Nous avons comparé ce nouvel algorithme aux algorithmes classiques et obtenu une classification des principaux algorithmes. Le problème de la détection du parallélisme et de son expression n'étant qu'une des multiples composantes de la parallélisation automatique, nous nous sommes intéressés aux interactions entre les problèmes de placement et d'ordonnancement, et entre les problèmes de détection de parallélisme et d'élimination de « fausses » dépendances.

• Abstract:

  Many computer users would like to be able to run on parallel computers their ``sequential'' programs (written to be run on classical computers). Thus, it became necessary to know how to transform, to ``parallelize'', the sequential programs into programs that can be run on parallel computers. This parallelization must be automatic as it is needed by plain users. Before applying any transformation to the original program, one must detect and quantify the parallelism it implicitly contains, which requires to know the program dependences. Later on, it will be necessary to reorder the computations to explicit the parallelism found. The aim of this thesis is to detect the implicit parallelism, and to search for schedules that explicit it, for particular program structures: set of nested loops. Our main goal was to understand the existing technics for parallelism detection, and to find their strong and weak points. On one hand, we have studied the main existing algorithms. On the other hand, we started from the theoretical model furnished by the systems of uniform recurrence equations and we proposed an optimal algorithm to parallelize the polyhedral reduced dependence graphs, a representation of dependences which generalizes the two classical approximation modes. We compared this new algorithm with the classical ones and we obtained a classification of the main algorithms. The problem of parallelism detection and exhibition is one of the many phases of an automatic parallelizer. Therefore, we have looked at the interactions between the problems of mapping and scheduling, and at the interactions between the problems of parallelism detection and of ``false'' dependences removal.

• Keywords: Automatic Parallelization, Nested Loops, Dependences, Scheduling, Mapping.
• Size: 164p
• Format: Compressed PostScript
• Remark: Only available in French.
• Get it
• Get it