Travail à effectuer: Articles proposés:
  1. M. A. Bender and M. O. Rabin. "Online Scheduling of Parallel Programs on Heterogeneous Systems with Applications to Cilk." Theory of Computing Systems Special Issue on SPAA '00, 35: 289-304, 2002. Online publication. Comment ordonnancer de manière distribuée sur des machines hétérogènes uniformes ?
  2. Scheduling Threads for Low Space Requirement and Good Locality http://www-2.cs.cmu.edu/~girija/publications.html ( local ) Question: quel compromis entre temps et consommation mémoire est atteint par l'ordonnancement DFDeques ?
  3. M. A. Bender, Z. Duan, J. Iacono, and J. Wu. "A Locality-Preserving Cache-Oblivious Dynamic Dictionary." Journal of Algorithms, 3(2):115-136, 2004. Online publication. Hottest article, 2004. Comment les algorithmes "cache-oblivious" permettent-ils de garantir la localité ?
  4. OpenMP for Networks of SMPs http://citeseer.nj.nec.com/hu99openmp.html ( local ) Question: comment implanter la mémoire partagée d'OpenMP sur une architecture distribuée ?
  5. M. A. Bender, J. T. Fineman, S. Gilbert, and B. C. Kuszmaul. "Concurrent Cache-Oblivious Search Trees." Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 228-237, 2005. 
  6. M. A. Bender, M. Farach-Colton, S. He, B. C. Kuszmaul, and C. E. Leiserson. "Adversarial Contention Resolution for Simple Channels." Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 325-332, 2005.
  7. "Scheduling parallel machines on-line" Comment peut-on ordonnancer (statiquement, i.e. off-line) des machines de vitesse proportionnelles ?
  8. "LogP: Towards a realistic model of parallel computation" \\ Exhiber (en prouvant) un algorithme de diffusion optimale sur LogP pour de petits messages.
  9. "The implementation of the Cilk-5 multithreaded language" Comment est compilée l'instruction sync du langage Cilk ? Justifier.
  10. "Hood: a user level threads library for multiprogrammes multiprocessors"\\ Décrire l'implantation du work-stealing proposée; détailler la gestion de la liste des tâches.
  11. "Parallel evaluation of arithmetic circuits ?" Sous quelles conditions et comment l'algorithme proposé peut être utilisé pour paralléliser automatiquement un programme ?
  12. "Breaking the barriers : two models for MPI programming" Comment peut-on programmer un algorithme de type BSP avec MPI ? Quelles performances peut-on attendre ?
  13. "Towards an architecture independent analysis of parallel algorithms" \\ Donner un ordonnancement ($T_1, T_\infty, C_1, C_\infty$) pour le graphe de tâche pyramide.
  14. "Thread scheduling for multiprogrammed multiprocessors"\\ Décrire l'implantation de la gestion de la liste des tâches.
  15. "Efficient PRAM simulation on a dsistributed architecture"\\ Quel est l'utilité du hachage universel pour simuler une mémoire globale sur une architecture distribuée ?
  16. "Guaranteing Good Memory Bounds for Parallel Programs" Quel est la mémoire requise pour un système TAM ?
  17. "Using duplication for scheduling unitary tasks on $m$ processors with unit communication delays". Expliciter un algorithme d'ordonnancement permettant d'atteindre un temps optimal avec une infinité de processeurs. Illustrer par un exemple.
  18. "A survey of Cache coherehnce schemes for multiprocessors" Classifier les mécanismes pour assurer la cohérence des caches au niveau matériel et logiciel.
  19. "Athapascan-1: On line building data flow graph in a parallel language" Comment implanter un ordonnancement ETF dans le système Athapascan ?
  20. "Linda implementation revisited" Quelle implantation de la mémoire globale est proposée ici ? A quel type d'ordonnancement se rapporte-t-elle ?
  21. "Strategies for dynamic load balancing on highly parallel computers" Comment implanter, à partir des conclusions de cet article, un algorithme d'ordonnacement glouton ?
  22. "Provably efficient scheduling for languages with fine grain parallelism" Comment décrire les besoins mémoire d'un algorithme ? A quelle(s) condition(s) fondamentale(s) est-il possible d'implanter l'algorithme d'ordonnacement proposé ?
  23. "The implementation of the Cilk-5 multithreaded language" Comment est compilée l'instruction sync du langage Cilk ? Justifier.
  24. "Parallelism in Random access Machines" Comment est définie une PRAM dans cet article fondateur ? Quel est le rapport avec une machine de Turing ?
  25. "An on-line scheduling heuristic with better worst case ratio than Graham's list scheduling". Quel est le pire cas pour un ordonnacement glouton de liste ?
  26. "A framework for analyzing locality and portability issues in parallel computing" Comment peut-on définir la complexité de communication ? Quelle est l'intérêt d'une telle définition ?
  27. "Parrallelism always help" Etant donné un programme séquentiel de temps T, quel est le temps parallèle obtenu par l'émulation proposée sur un nombre infini de processeurs ? et sur p processeurs ?
  28. "A complexity theory of efficient parallel algorithms" L'algorithme de préfixe vu en cours est-il efficace ? Et les algorithmes de résliution de systèmes triangulaires ?
  29. "Are wait-free algorithms fast ?" Qu'estce qu'un algorithme "wait-free" ?
  30. "New bounds for parallel prefix circuits" Existe-t-il un algorithme de calcul des préfixes s'exécutant en temps T_seq / p sur p processeurs ? Justifier votre reponse.
  31. "Theory and Practice in parallel Job Scheduling", G. Feitelson, L. Rudolph , U. Schwiegelshohn, C. Kenneth
    Question: La caractérisation des tâches peut-elle amener une politique efficace pour l'exploitation d'un calculateur parallèle ?