Daniel de Angelis Cordeiro - The impact of cooperation on new high performance computing platforms

13:30
Jeudi
9
Fév
2012
Organisé par : 

Daniel de Angelis Cordeiro - MOAIS

Intervenant : 

Daniel de Angelis Cordeiro

Équipes : 
Information détaillée : 

- Cette thèse a été réalisée au sein de l’équipe MOAIS du Laboratoire d’Informatique de Grenoble.

- La soutenance aura lieu le jeudi 9 février 2012 à 13h30 dans l’amphithéâtre de la MJK.

- Une version préliminaire du manuscrit, rédigée en anglais, est disponible en ligne.

- Le jury sera composé de :

  • M. Bruno Gaujal, INRIA (Président proposé)
  • M. Jean-Charles Billaut, Université de Tours (Rapporteur)
  • Mme Laetitia Jourdan, Université Lille 1 (Rapporteur)
  • M. Wiesław Kubiak, Memorial University of Newfoundland (Examinateur)
  • M. Philippe Navaux, Univ. Federal do Rio Grande do Sul (Examinateur)
  • Mme Fanny Pascual, Université Pierre et Marie Curie (Examinatrice)
  • M. Denis Trystram, Grenoble INP (Directeur de thèse)
Résumé : 

Computer science is deeply changing methodological aspects of the discovery process in different areas of knowledge. Researchers have at their disposal new capabilities that can create novel research opportunities. Parallel and distributed platforms composed of resources shared between different participants can make these new capabilities accessible to every researcher at every level, delivering computational power that was restricted before to bigger (and wealthy) scientific projects.

This work explores four different facets of the rules that govern how organizations engage in collaboration on modern parallel and distributed platforms. Using classical combinatorial tools, multi-objective scheduling and game-theory, we showed how to compute schedules with good trade-offs between the results got by the participants and the global performance of the platform. By ensuring fair results and guaranteeing performance improvements for the participants, we can create an efficient platform where everyone always feels encouraged to collaborate and to share its resources.

First, we study the collaboration between selfish organizations. We show how the selfish behavior between the participants imposes a lower bound on the global makespan. We present algorithms that cope with the selfishness of the organizations and that achieve good fairness in practice.

The second study is about collaboration between organizations that can tolerate a limited degradation on their performance if this can help ameliorate the global makespan. We improve the existing inapproximation bounds for this problem and present new algorithms whose guarantees are close to the Pareto set.

The third form of collaboration studied is between rational participants that can independently choose the best strategy for their jobs. We present a non-cooperative game-theoretic model for the problem and show how coordination mechanisms allow the creation of approximate pure equilibria with bounded price of anarchy.

Finally, we study collaboration between users sharing a set of common resources. We present a method that enumerates the frontier of best compromise solutions for the users and selects the solution that brings the best value for the global performance function.