Asynchronous Memory Machine Models with Barrier Synchronization

作者：Nakano Koji^*

来源：IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2014, E97D(3): 431-441.

DOI：10.1587/transinf.E97.D.431

• memory machine models
• parallel algorithms
• contiguous memory access
• asynchronous models
• GPU
• CUDA

The Discrete Memory Machine (DMM) and the Unified Memory Machine (UMM) are theoretical parallel computing models that capture the essence of the shared memory and the global memory of GPUs. It is assumed that warps (or groups of threads) on the DMM and the UMM work synchronously in a round-robin manner. However, warps work asynchronously in real GPUs, in the sense that they are randomly (or arbitrarily) dispatched for execution. The first contribution of this paper is to introduce asynchronous versions of these models in which warps are arbitrarily dispatched. In addition, we assume that threads can execute the %26quot;syncthreads%26quot; instruction for barrier synchronization. Since the barrier synchronization operation may be costly, we should evaluate and minimize the number of barrier synchronization operations executed by parallel algorithms. The second contribution of this paper is to show a parallel algorithm to the sum of n numbers in optimal computing time and few barrier synchronization steps. Our parallel algorithm computes the sum of n numbers in O(n/w + l log n) time units and O(log l/log w + log log w) barrier synchronization steps using wl threads on the asynchronous UMM with width w and latency I. Since the computation of the sum takes at least Omega(n/w + l log n) time units, this algorithm is time optimal. Finally, we show that the prefix-sums of n numbers can also be computed in O(n/w + l log n) time units and O(log l/log w + log log w) barrier synchronization steps using wl threads.

• 出版日期2014-3