zbMATH — the first resource for mathematics

Reasoning about parallel architectures. (English) Zbl 0759.68009
Hemel Hempstead, Herts.: Simon & Schuster. XX, 234 p. (1992).
Reasoning about parallel architectures means primerily reasoning about the order in which computer instructions have to be executed.
The first chapter introduces a simple example which reveals the failure of a computer to obey the rules governing its behaviour. The history of computer architecture, presented in chapter 2, is one of increasingly sophisticated understanding of the factors that make computer distinguishable or indistinguishable. The advent of (shared memory) multiprocessors and caches enforces a revision of the original rules of behaviour. Reasoning about the issues of distinguishability and indistinguishability requires now more complex methods using sets, factorials and chromatic graphs and the formal definition of a model of a shared memory multiprocessor (chapter 3, 4). The most important rule of behaviour is the rule of computation, which describes how answers are calculated (chapter 5). The many variations on the order rules are described in chapter 6 and the atomicity rules in chapter 7, followed by synchronization rules and intrastatement rules in chapters 8, 9. Chapter 10 states some general results about rules.
The major work of the book occurs in chapters 12, 13. Frey’s theorem demonstrates a simple condition under which read operations can be performed out of order on a multiprocessor without the fact being detected (chapter 11). The WISIWA theorem shows that write operations will appear to occur instantaneously if all processors see all changes in the values of operands occurring in the same order. The performance improvement achievable through the use of this theorem is demonstrated in a ring-structured system and in a more detailed model of a multiprocessor. Finally, some conjectures on further relaxing the rules are offered.
The book can be of value to researchers working in the area of computer architecture; it relies on a formalism based on “behaviour rules”.

68M07 Mathematical problems of computer architecture
68-02 Research exposition (monographs, survey articles) pertaining to computer science