Massively Parallel Computing and Polynomial GCD's

Note:This thesis studies massively parallel synchronous processing models and algorithms. We survey the basic models, discuss their interrelationships and analyze properties of some feasible network models. A new definition of Gentleman's o-function is given. We present routines that simulate the CUBE ASCEND /DESCEND class algorithms on the CCC (cube-connected cycles) and the PERFECT SHUFFLE machines of any sufficient size. We give the exact (non-asymptotic) computation times and prove the correctness of the algorithms. This extends the previous results of Stone (1971) and Preparata-Vuillemin (1979). Borodin-von zur Gathen-Hopcroft (1984) laid out a program to obtain a "theory package for parallel algebraic manipulation". […]Cette thèse discute d'algorithmes et de modèles de traitement synchrones massifs. Nous présentons les modèles de base et nous discutons de leur réciprocité; de plus, nous analysons les propriétés de quelques modèles plausibles de réseaux. Une nouvelle définition de la fonction-u de Gentleman est présentée. Nous discutons égallement de procédures qui simulent les algorithmes CUBE ASCEND /DESCEND auprès du CCC (cycles cube-connecte') et des machines PERFECT SHUFFLE de n'importe quelle taille. Nous donnons les temps de calculs exacts (non-asymptotiques) et nous prouvons !'exactitude des algorithmes. Ceci ajoute au résultats précédents de Stone (1971) at de Preparate-Vuillemin (1979). Borodin-von zur Gathen-Hopcroft (1984) précisa un programme afin d'obtenir un "groupement de théories pour la manipulation algébraique parallèle". […