Serialization of concurrent software specifications and the effects of processor autonomy on parallel program execution

This dissertation has two parts, one addressing issues in the area of computer-aided software development and the other concerning parallel computer architecture. The first part develops a methodology for serializing a concurrent software specification to achieve efficient execution on a single processor. A concurrent specification provides a natural, architecture-independent expression of the desired behavior of a concurrent system. Automation of the serialization process allows serial code to be produced quickly and without error. Serialization begins by translating the specification into labeled transition systems. These systems are combined into a single labeled transition system represented by a superstate graph. This graph is pruned according to rules that reduce its potentially enormous size while preserving correct system behavior. Improved pruning algorithms and heuristic techniques for simplifying the system representation make the resulting serialization more compact. The second part of this work presents a new taxonomy for computer architecture and uses it to define the concept of processor autonomy, the potential of one processing element in a parallel computer to act differently from other processors during execution. Processor autonomy is possible when multiple data value, data address, instruction value, or instruction address streams are available. Parallel program execution can be significantly aided by processor autonomy, allowing various mappings and dynamic reassignment of processors to streams to avoid serialization of execution. Parallel program performance is evaluated for several sorting algorithms using one form of data address autonomy, indirect addressing, and one form of instruction value autonomy, branch selection