Virtual Memory for Data-Parallel Computing
Thomas H. Cormen
Massachussetts Institute of Technology, 1992
Throughout the history of electronic computing, no matter how big and
fast the top machines have been, there have always been applications
that needed them to be bigger and faster. We see this phenomenon
today in parallel computing.
Almost thirty years ago, computer architects devised virtual memory to
solve this problem for sequential machines, but data-parallel machines
don't have it yet. This thesis explores several issues that arise in
the design and implementation of virtual-memory systems for
data-parallel computing, with the following contributions:
- A system, VM-DP, for data-parallel computing with virtual
- Theoretical results for classes of bit-defined permutations (BPC
and BMMC permutations in particular) on parallel disk systems.
- Practical methods for performing permutations. This thesis
presents how VM-DP performs general permutations and lists several
special permutations that can be performed faster: monotonic routes,
mesh and torus permutations, BPC and BMMC permutations, and general
matrix transpose. Moreover, each of these special permutations can be
detected efficiently at run time.
- A study of how the layout of vectors on disk affects
- A comparison of alternative demand paging strategies in VM-DP.