A Review of CUDA, MapReduce, and Pthreads Parallel Computing Models <s> BACKGROUND AND RELATED WORK <s> MapReduce is a programming model and an associated implementation for processing and generating large data sets. Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with the same intermediate key. Many real world tasks are expressible in this model, as shown in the paper. ::: ::: Programs written in this functional style are automatically parallelized and executed on a large cluster of commodity machines. The run-time system takes care of the details of partitioning the input data, scheduling the program's execution across a set of machines, handling machine failures, and managing the required inter-machine communication. This allows programmers without any experience with parallel and distributed systems to easily utilize the resources of a large distributed system. ::: ::: Our implementation of MapReduce runs on a large cluster of commodity machines and is highly scalable: a typical MapReduce computation processes many terabytes of data on thousands of machines. Programmers find the system easy to use: hundreds of MapReduce programs have been implemented and upwards of one thousand MapReduce jobs are executed on Google's clusters every day. <s> BIB001 </s> A Review of CUDA, MapReduce, and Pthreads Parallel Computing Models <s> BACKGROUND AND RELATED WORK <s> The development of microprocessors design has been shifting to multi-core architectures. Therefore, it is expected that parallelism will play a significant role in future generations of applications. Throughout the years, there has been a myriad number of parallel programming models proposed. In choosing a parallel programming model, not only the performance aspect is important, but also qualitative the aspect of how well parallelism is abstracted to developers. A model with a well abstraction of parallelism leads to a higher application-development productivity. In this paper, we propose seven criteria to qualitatively evaluate parallel programming models. Our focus is on how parallelism is abstracted and presented to application developers. As a case study, we use these criteria to investigate six well-known parallel programming models in the HPC community. <s> BIB002 </s> A Review of CUDA, MapReduce, and Pthreads Parallel Computing Models <s> BACKGROUND AND RELATED WORK <s> In today's widely used parallel programming models, subtle programming errors can lead to unintended nondeterministic behavior and hard to catch bugs. In contrast, we argue for a parallel programming model that is deterministic by default: deterministic behavior is guaranteed unless the programmer explicitly uses nondeterministic constructs. This goal is particularly challenging for modern object-oriented languages with expressive use of reference aliasing and updates to shared mutable state. We propose a broad research agenda in support of this goal, and we describe some of our own work to further that agenda. <s> BIB003 </s> A Review of CUDA, MapReduce, and Pthreads Parallel Computing Models <s> BACKGROUND AND RELATED WORK <s> Dynamic runtimes can simplify parallel programming by automatically managing concurrency and locality without further burdening the programmer. Nevertheless, implementing such runtime systems for large-scale, shared-memory systems can be challenging. This work optimizes Phoenix, a MapReduce runtime for shared-memory multi-cores and multiprocessors, on a quad-chip, 32-core, 256-thread UltraSPARC T2+ system with NUMA characteristics. We show how a multi-layered approach that comprises optimizations on the algorithm, implementation, and OS interaction leads to significant speedup improvements with 256 threads (average of 2.5× higher speedup, maximum of 19×). We also identify the roadblocks that limit the scalability of parallel runtimes on shared-memory systems, which are inherently tied to the OS scalability on large-scale systems. <s> BIB004 </s> A Review of CUDA, MapReduce, and Pthreads Parallel Computing Models <s> BACKGROUND AND RELATED WORK <s> The trend towards processors with more and more parallel cores is increasing the need for software that can take advantage of parallelism. The most widespread method for writing parallel software is to use explicit threads. Writing correct multithreaded programs, however, has proven to be quite challenging in practice. The key difficulty is nondeterminism. The threads of a parallel application may be interleaved nondeterministically during execution. In a buggy program, nondeterministic scheduling can lead to nondeterministic results—where some interleavings produce the correct result while others do not. We propose an assertion framework for specifying that regions of a parallel program behave deterministically despite nondeterministic thread interleaving. Our framework allows programmers to write assertions involving pairs of program states arisingfrom different parallel schedules. We describe an implementation of our deterministic assertions as a library for Java, and evaluate the utility of our specifications on a number of parallel Java benchmarks. We found specifying deterministic behavior to be quite simple using our assertions. Further, in experiments with our assertions, we were able to identify two races as true parallelism errors that lead to incorrect non-deterministic behavior. These races were distinguished from a number of benign races in the benchmarks. <s> BIB005 </s> A Review of CUDA, MapReduce, and Pthreads Parallel Computing Models <s> BACKGROUND AND RELATED WORK <s> Many-core processors target improved computational performance by making available various forms of architectural parallelism, including but not limited to multiple cores and vector instructions. However, approaches to parallel programming based on targeting these low-level parallel mechanisms directly leads to overly complex, non-portable, and often unscalable and unreliable code. ::: ::: A more structured approach to designing and implementing parallel algorithms is useful to reduce the complexity of developing software for such processors, and is particularly relevant for many-core processors with a large amount of parallelism and multiple parallelism mechanisms. In particular, efficient and reliable parallel programs can be designed around the composition of deterministic algorithmic skeletons, or patterns. While improving the productivity of experts, specific patterns and fused combinations of patterns can also guide relatively inexperienced users to developing efficient algorithm implementations that have good scalability. ::: ::: The approach to parallelism described in this document includes both collective "data-parallel" patterns such as map and reduce as well as structured "task-parallel" patterns such as pipelining and superscalar task graphs. The structured pattern based approach, like data-parallel models, addresses issues of both data access and parallel task distribution in a common framework. Optimization of data access is important for both many-core processors with shared memory systems and accelerators with their own memories not directly attached to the host processor. ::: ::: A catalog of useful structured serial and parallel patterns will be presented. Serial patterns are presented because structured parallel programming can be considered an extension of structured control flow in serial programming. We will emphasize deterministic patterns in order to support the development of systems that automatically avoid unsafe race conditions and deadlock. <s> BIB006 </s> A Review of CUDA, MapReduce, and Pthreads Parallel Computing Models <s> BACKGROUND AND RELATED WORK <s> Modern General Purpose Graphics Processing Units (GPGPUs) provide high degrees of parallelism in computation and memory access, making them suitable for data parallel applications such as those using the elastic MapReduce model. Yet designing a MapReduce framework for GPUs faces significant challenges brought by their multi-level memory hierarchy. Due to the absence of atomic operations in the earlier generations of GPUs, existing GPU MapReduce frameworks have problems in handling input/output data with varied or unpredictable sizes. Also, existing frameworks utilize mostly a single level of memory, \emph{i.e.}, the relatively spacious yet slow global memory. In this work, we attempt to explore the potential benefit of enabling a GPU MapReduce framework to use multiple levels of the GPU memory hierarchy. We propose a novel GPU data staging scheme for MapReduce workloads, tailored toward the GPU memory hierarchy. Centering around the efficient utilization of the fast but very small shared memory, we designed and implemented a GPU MapReduce framework, whose key techniques include (1) shared memory staging area management, (2) thread-role partitioning, and (3) intra-block thread synchronization. We carried out evaluation with five popular MapReduce workloads and studied their performance under different GPU memory usage choices. Our results reveal that exploiting GPU shared memory is highly promising for the Map phase (with an average 2.85x speedup over using global memory only), while in the Reduce phase the benefit of using shared memory is much less pronounced, due to the high input-to-output ratio. In addition, when compared to Mars, an existing GPU MapReduce framework, our system is shown to bring a significant speedup in Map/Reduce phases. <s> BIB007 </s> A Review of CUDA, MapReduce, and Pthreads Parallel Computing Models <s> BACKGROUND AND RELATED WORK <s> We design and implement Mars, a MapReduce runtime system accelerated with graphics processing units (GPUs). MapReduce is a simple and flexible parallel programming paradigm originally proposed by Google, for the ease of large-scale data processing on thousands of CPUs. Compared with CPUs, GPUs have an order of magnitude higher computation power and memory bandwidth. However, GPUs are designed as special-purpose coprocessors and their programming interfaces are less familiar than those on the CPUs to MapReduce programmers. To harness GPUs' power for MapReduce, we developed Mars to run on NVIDIA GPUs, AMD GPUs as well as multicore CPUs. Furthermore, we integrated Mars into Hadoop, an open-source CPU-based MapReduce system. Mars hides the programming complexity of GPUs behind the simple and familiar MapReduce interface, and automatically manages task partitioning, data distribution, and parallelization on the processors. We have implemented six representative applications on Mars and evaluated their performance on PCs equipped with GPUs as well as multicore CPUs. The experimental results show that, the GPU-CPU coprocessing of Mars on an NVIDIA GTX280 GPU and an Intel quad-core CPU outperformed Phoenix, the state-of-the-art MapReduce on the multicore CPU with a speedup of up to 72 times and 24 times on average, depending on the applications. Additionally, integrating Mars into Hadoop enabled GPU acceleration for a network of PCs. <s> BIB008 </s> A Review of CUDA, MapReduce, and Pthreads Parallel Computing Models <s> BACKGROUND AND RELATED WORK <s> We present GPMR, our stand-alone MapReduce library that leverages the power of GPU clusters for large-scale computing. To better utilize the GPU, we modify MapReduce by combining large amounts of map and reduce items into chunks and using partial reductions and accumulation. We use persistent map and reduce tasks and stress aspects of GPMR with a set of standard MapReduce benchmarks. We run these benchmarks on a GPU cluster and achieve desirable speedup and efficiency for all benchmarks. We compare our implementation to the current-best GPU-MapReduce library (runs only on a solo GPU) and a highly-optimized multi-core MapReduce to show the power of GPMR. We demonstrate how typical MapReduce tasks are easily modified to fit into GPMR and leverage a GPU cluster. We highlight how total and relative amounts of communication affect GPMR. We conclude with an exposition on the types of MapReduce tasks well-suited to GPMR, and why some tasks need more modifications than others to work well with GPMR. <s> BIB009 </s> A Review of CUDA, MapReduce, and Pthreads Parallel Computing Models <s> BACKGROUND AND RELATED WORK <s> This paper describes our rewrite of Phoenix, a MapReduce framework for shared-memory CMPs and SMPs. Despite successfully demonstrating the applicability of a MapReduce-style pipeline to shared-memory machines, Phoenix has a number of limitations; its uniform intermediate storage of key-value pairs, inefficient combiner implementation, and poor task overhead amortization fail to efficiently support a wide range of MapReduce applications, encouraging users to manually circumvent the framework. We describe an alternative implementation, Phoenix++, that provides a modular, flexible pipeline that can be easily adapted by the user to the characteristics of a particular workload. Compared to Phoenix, this new approach achieves a 4.7-fold performance improvement and increased scalability, while allowing users to write simple, strict MapReduce code. <s> BIB010 </s> A Review of CUDA, MapReduce, and Pthreads Parallel Computing Models <s> BACKGROUND AND RELATED WORK <s> While high-efficiency machines are increasingly embracing heterogeneous architectures and massive multithreading, contemporary mainstream programming languages reflect a mental model in which processing elements are homogeneous, concurrency is limited, and memory is a flat undifferentiated pool of storage. Moreover, the current state of the art in programming heterogeneous machines tends towards using separate programming models, such as OpenMP and CUDA, for different portions of the machine. Both of these factors make programming emerging heterogeneous machines unnecessarily difficult. We describe the design of the Phalanx programming model, which seeks to provide a unified programming model for heterogeneous machines. It provides constructs for bulk parallelism, synchronization, and data placement which operate across the entire machine. Our prototype implementation is able to launch and coordinate work on both CPU and GPU processors within a single node, and by leveraging the GASNet runtime, is able to run across all the nodes of a distributed-memory machine. <s> BIB011 </s> A Review of CUDA, MapReduce, and Pthreads Parallel Computing Models <s> BACKGROUND AND RELATED WORK <s> Current deterministic systems generally incur large overhead due to the difficulty of detecting and eliminating data races. This paper presents RaceFree, a novel multi-threading runtime that adopts a relaxed deterministic model to provide a data-race-free environment for parallel programs. This model cuts off unnecessary shared-memory communication by isolating threads in separated memories, which eliminates direct data races. Meanwhile, we leverage the happen-before relation defined by applications themselves as one-way communication pipes to perform necessary thread communication. Shared-memory communication is transparently converted to message-passing style communication by our Memory Modification Propagation (MMP) mechanism, which propagates local memory modifications to other threads through the happen-before relation pipes. The overhead of RaceFree is 67.2% according to our tests on parallel benchmarks. <s> BIB012
As HPC systems increasingly becomes a necessity in mainstream computing, a number of researchers have done work on documenting various features in parallel computing models. Although a number of features in parallel programming models are discussed in literature, CUDA, MapReduce, and Pthreads models, utilize multi-threading and, as such, a look at abstraction and determinism in multithreading, is given consideration in this paper. In their survey on the parallel programming models, Kasim, March, Zhang, and See (2008), described how parallelism is abstracted and presented to programmers, by investigating six parallel programming models used by the HPC community, namely, Pthreads, OpenMP, CUDA, MPI, UPC, and Fortress BIB002 . Furthermore, Kasim et al, proposed a set of criteria to evaluate how parallelism is abstracted and presented to programmers, namely, (i) system architecture, (ii) programming methodologies, (iii) worker management, (iv) workload partitioning scheme, (v) task-to-worker mapping, (vi) synchronization, and (vii) communication model BIB002 . On the feature of determinism in parallel programming, Bocchino, Adve, Adve, and Snir (2009), noted that with most parallel programming models, subtle coding errors could lead to inadvertent non-deterministic actions and bugs that are hard to find and debug BIB003 . Therefore, Bocchino et al, argued for a parallel programming model that was deterministic by default unless the programmer unambiguously decided to use non-deterministic constructs BIB003 . Non-determinism is a condition in multi-threading parallel processing, in which erratic and unpredictable behavior, bugs, and errors occur among threads due to their random interleaving and implicit communication when accessing shared memory, thus making it more problematic to program in parallel model than the sequential von Neumann model  BIB005 . Additionally, on the feature of determinism in parallel programming languages, BIB006 argued that a more structured approach in the design and implementation of parallel algorithms was needed in order to reduce the complexity in developing software BIB006 . Moreover, BIB006 suggested the utilization of deterministic algorithmic skeletons and patterns in the design of parallel programs BIB006 . McCool (2010) generally proposed that any system that maintains a specification and composition of a high-quality pattern can be used as a template to steer developers in designing more dependable deterministic parallel programs BIB006 . However, Yang, Cui, Wu, Tang, and Hu (2013) contended that determinism in parallel programming was difficult to achieve since threads are nondeterministic by default and therefore making parallel programs reliable with stable multi-threading was more practical  . On the other hand, Garland, Kudlur, and Zheng (2012), observed that while heterogeneous architectures and massive multithreading concepts have been accepted in the larger HPC community, modern programming models suffer from a defect of limited concurrency, undifferentiated flat memory storage, and a homogenous processing of elements BIB011 . Garland et al, then, proposed a unified programming model for heterogeneous machines that provides constructs for massive parallelism, synchronization, and data assignment, executed on the whole machine BIB011 . Dean and Ghemawat BIB001 presented a run-time parallel, distributed, scalable programming model, which encompassed a map and reduce function in order to map and reduce key-value pairs BIB001 . Though there were many parallel, distributed, scalable programming models that currently existed, there was no model in existence whose goal through development was to create a programming model that was easy to use. The innate ability of MapReduce to do its parallel and distributed computation across large commodity clusters at run-time allowed developers to express simple computations while hiding the messy details of communication, parallelization, fault tolerance, and load balancing BIB001 . On fully utilizing the GPU and MapReduce model, BIB007 , explored the prospective value of allowing for a GPU MapReduce structure that uses multiple levels of the GPU memory hierarchy BIB007 . To achieve this goal, Ji and Ma (2011) proposed a resourceful deployment using small shared but fast memory, which included, a shared memory staging area management, thread-role partitioning, and intra-block thread synchronization BIB007 . Furthermore, Fang, He, Luo, and Govindaraju (2011) proposed the Mars model, which combines GPU and MapReduce features to attain: (i) ease of programming GPUs, (ii) portability such that the system can be applied on different technologies such as NVIDIA CUDA, or Pthreads, and (iii) effective use of high performance using GPUs BIB008 . To achieve these goals, the Mars model hides the programming complexity of GPUs by: (i) use of a simple and conversant MapReduce interface, (ii) routinely managing subdividing tasks, (iii) managing the dissemination of data, and (iv) dealing with process parallelization BIB008 . On the other hand, for efficient utilization of resources, BIB009 , proposed GPMR, a stand-alone MapReduce library that takes advantage of the power of GPU clusters for extensive computing by merging bulky quantities of map and reduce items into slices and using fractional reductions and accruals to complete computations BIB009 . Although the Pthreads model has been around for some time  , application of the MapReduce model using Pthreads is accomplished via the Phoenix model -a programming paradigm that is built on Pthreads for MapReduce implementation BIB004 . Of recent, the Phoenix++ MapReduce model, a variation of Phoenix model, was created based on the C++ programming prototype BIB010 . Yet still, on the issue of determinism in Pthreads, Liu, Curtsinger, and Berger (2011), observed that enforcing determinism in threads was still problematic and they proposed the DTHREADS multi-threading model, built on C/C++ to replace the Pthreads library and alleviate the nondeterminism problem  . DTHREADS model imposes determinism by separating multi-thread programs into several processes; using private and copy-on-write maps to shared memory, employing standard virtual memory protection to keep track of writes, and then deterministically ordering updates on each thread, and as such, eliminating false sharing  . However, the issue of multi-thread non-determinism in parallel programming models still persists, and continues to be problematic due to the data race issue, a condition brought about by unneeded shared memory communication between threads BIB012 . To address this problem Lu, Zhou, Wang, Zhang, and Li (2013), proposed RaceFree, a relaxed deterministic model that offers a data race free multi-threading setting whereby determinism in parallel programs is only affected by synchronization race BIB012 .