Sequential Memory Access on the Unified Memory Machine with Application to the Dynamic Programming

The Unified Memory Machine (UMM) is a theoretical parallel computing model that captures the essence of the global memory access of GPUs. Although it is a good theoretical model for GPU computing, the performance analysis of parallel algorithms on it is sometimes complicated. The main contribution of this paper is to provide a useful gadget, the sequential memory access, that makes the computing time evaluation easy, and to show its application to the dynamic programming. The sequential memory access has two parameters: length n and fragmentation f. We first show that the sequential memory access of length n with fragmentation f can be done in O(n/w + nl/p+l+f) time units using p threads on the UMM with width w and latency l. We next show that the dynamic programming to solve the optimal polygon triangulation problem can be implemented in the UMM using the sequential memory access. The resulting implementation for a convex n-gon runs in O(n³/w + n³l/p + nl) time units using p threads on the UMM with width w and latency l. We also prove that any implementation of the dynamic programming needs Omega(n³/w + n³l/p + nl) time units. Thus, our implementation is time optimal.