Modeling Parallel Shared Memory Computations

190 pages ISSN 1238-6944, ISBN 951-708-693-8 Keywords: parallel computing, shared memory, modeling, F-PRAM nterprocessor communication is the most difficult part of parallel computation on current parallel computers. Programmers find it difficult to correctly and reliably distribute and maintain the data of a parallel program. Most efficiency problems are due to excessive or inefficient communication. Parallel computer manufacturers find it difficult and expensive to build interprocessor communication networks that would keep up with fast processors. In this thesis we shall present a new model of parallel computing, the F-PRAM model. The model characterizes parallel computers with a set of parameters, most of which model the limitations of the shared memory access of the processors, i.e., the communication. For the programmer, the new model offers a convenient abstraction of shared memory, but charges duely the machine-dependent costs of the use of the shared memory. Fo