Synchronous Cooperation for Explicit Multi-Threading

Abstract. We develop an algebraic theory of threads, synchronous co-operation of threads and interaction of threads with Maurer machines, and investigate program parallelization using the resulting theory. Pro-gram parallelization underlies techniques for speeding up instruction pro-cessing on a computer that make use of the abilities of the computer to process instructions simultaneously in cases where the state changes in-volved do no in uence each other. One of our ndings is that a strong induction principle is needed when proving theorems about sucient conditions for the correctness of program parallelizations. The induction principle introduced has brought us to construct a projective limit model for the theory developed