Parallel efficient algorithms and their programming. Fundation of ATHAPASCAN-1.

2Ce rapport contient les deux premiers chapitres du tutoriel “Parallel Computer Algebra ” donné au colloque annuel de calcul formel ISSAC (Juillet 97, Hawaii) par Jean-Louis Roch et Gilles Vil-lard. Il décrit les bases pour la construction, l’analyse et la programmation d’algorithmes parallèles sur des architectures distribuées. Utilisant les techniques a ̀ la base de l’algorithmique parallèle syn-chrone PRAM, il montre comment elles peuvent être appliquées a ̀ la construction d’algorithmes parallèles qui conduisent a ̀ des programmes performants sur des architectures distribuées asyn-chrones. Deux points sont alors critiques: la prise en compte des surcoûts de communication et d’ordonnancement. Le premier chapitre présente les techniques permettant la construction d’algorithmes efficaces. Différents critères doivent être minimisés: le nombre d’opérations qui doit rester proche du nom-bre optimal d’opérations sur une machine séquentielle, le temps parallèle minimal (i.e. sur un nombre infini de processeurs) pour permettre que le temps d’exécution diminue lorsque le nom-bre de processeurs augmente (on parle d’extensibilité), le volume de communications pour limiter leur surcoût sur une architecture distribuée. Pris séparément, ces différents critéres conduisent à des algorithmes fondamentalement différents. Un algorithme efficace doit alors réaliser un bo