TOWARDS PARALLELIZATION OF CONCURRENT SYSTEMS

摘要

A notion of parallelization of concurrent processes is proposed that satisfies some intuitive requirements. Roughly, given a process P, a more parallel version Q of P can be the result of replacing one of the sequential summands S in one of P subterms by a process R, provided that Q is functionally equivalent to P and R is either a parallel term or a summand of S. This defines an equivalence preserving preorder on processes Q is contained in P according to which in Q parallelism is increased or the amount of redundancy is decreased. We show that our notion has some connection with the notion of factorization proposed by Milner and Moller. Finally, we identify some classes of processes for which the most parallel version is unique.%Nous proposons une notion de parallélisation de processus concurrents qui satisfait quelques exigences intuitives. En gros, si P est un processus, une version plus parallèle Q de P peut être obtenue en remplaçant un des sommants séquentiels S dans un sous-terme de P, pourvu que Q soit fonctionnellement équivalent à P et que R soit ou bien un terme parallèle ou bien un somant de S. Ceci définit une équivalence qui conserve le préordre sur les processus Q is contained in P suivant lequel ans Q le paralélisme est augmenté ou bien la quantité de redondance est diminuée. Nous montrons que notre notion est reliée à celle de factorisation proposée par Milner et Moller. Finalement, nous identifions quelques classes de processus pour lesquels la version la plus parallèle est unique.