Yet Another Bridging Model - The Parallel Memory Hierarchy
Larry Carter
The Parallel Memory Hierarchy (PMH) model of computation is a tree
of "modules", where each module is a finite RAM, and communication
of blocks of contiguous data occurs on tree edges. Each module is
parameterized by its memory capacity and number of children. Each
edge is parameterized by the block size and transfer time. Modules
nearer the root have larger memories; those nearer the leaves are
smaller but faster (and more numerous). High performance is achieved
by moving small, compute-intensive subproblems towards the leaves,
and finding indepence among the subproblems that are assigned to
separate children.
It is asserted that:
- Appropriate parameter choices can be made to model a wide variety
of real computers.
- Efficient PMH programs correspond to efficient real programs.
- Future machines will have more levels, more multi-child levels,
(i.e., more parallelism), and more heterogeniety.
- Portable, efficient PMH programs can be written by having each
module break its subproblems into still smaller sub-subproblems
(whose number and size is influenced by the PMH's parameters) that
are passed to the module's children in a pipelined fashion.
- Hierarchical tiling, or formal methods (e.g. skeletons) may
reduce the difficulty of writing PMH programs.