Thread algebra for poly-threading

Abstract

It is a fact of life that sequential programs are often fragmented. Consequently, fragmented program behaviours are frequently found.We consider this phenomenon in the setting of thread algebra.We extend basic thread algebra with poly-threading, the barest mechanism for sequencing of threads that are taken for program fragment behaviours. This mechanism is the counterpart of program overlaying at the level of program behaviours. We relate the resulting theory to the process theory known as ACP and use it to describe analytic execution architectures suited for fragmented programs. We also consider the case where the steps of fragmented program behaviours are interleaved in the ways of non-distributed and distributed multi-threading.

View-only version of article

Preprint available: arXiv:0803.0378 [cs.LO]