Modeling Parallel Shared Memory Computations
Simo Juvaste

Keywords: parallel computing, shared memory, modeling, F-PRAM

Abstract

     Interprocessor 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. For shared memory access, the model presents a new
  prefetching primitive. By using the model the programmer can avoid too
  expensive communication, and the parallel computer manufacturer can
  choose the most important features to improve.
     The new model was tested with a fully configurable emulator of an
  abstract parallel computer. Using the emulator we implemented and
  analyzed a set of sample algorithms. These measurements revealed,
  e.g., the effects of insufficient shared memory access capabilities.
  Different algorithms tolerated different levels of scarcities such as
  insufficient bandwidth or high shared memory latency. We also
  estimated the values of the parameters on some existing parallel
  computers.