Short modules for introducing parallel concepts

One of the current big challenges in CS education is how to incorporate parallel programming to prepare our graduates for a world in which essentially all computers have multiple cores. The recent model Computer Science Curricula 2013 (CS2013) is spurring many into action, but there are still many questions about what to teach and how to add parallelism to already-full courses. This tutorial presents three modules the presenter and others have used in actual classes as brief introductions to parallel concepts as part of an "early and often"' approach to incorporating parallelism throughout the curriculum. Each module is built around a different parallel language that highlights a different aspect of parallel programming. Despite this, each requires only a couple of days of class time and fits within a standard course. All of them include associated assignments and/or laboratory exercises for students. • The first module uses OpenMP to quickly prototype different approaches to parallelizing a simple fractal generation program. It demonstrates the ideas of speedup, race conditions, load balancing, and parallel overhead. The presenter has used it in an operating systems course, connected to the presentation of threads and concurrency normally included in that course. An added appeal of this unit is that OpenMP is a standard feature in common C compilers and no special hardware is needed; the demonstration and practical aspects of the module work fine on dual- and quad-core systems. • The second module uses CUDA to demonstrate SIMD (Single Instruction, Multiple Data) computing and heterogeneous parallelism. CUDA is NVIDIA's architecture and programming language for general-purpose computing on graphics processing units (GP-GPU programming). CUDA is an appealing option for parallel computing because graphics processors have large numbers of cores (several hundred on mid-range cards) and the language is C plus a couple of added constructs. Thus, it is easy to get started and high speedups can be achieved, making CUDA quite appealing to students. The module, presented in the context of a computer organization course, uses several factors that complicate writing high-performance CUDA programs to demonstrate the role of architectural features in program performance. First of all, typical CUDA programs involve explicitly transferring data between the host machine and graphics card. (Newer versions can do this automatically, but high performance still requires an awareness of the data transfer.) Secondly, the high core count is achieved by making each graphics core simpler than a CPU core and organizing them into groups that operate in lockstep, requiring a SIMD programming style. Finally, CUDA cards have several different kinds of memory, each with different performance characteristics. Students are not able to fully optimize performance of CUDA after a short module, but these architectural features make it easy to demonstrate important concepts like memory management, SIMD, and system heterogeneity. This module does require a CUDA-enabled graphics card. These are not standard on typical lab machines, but can easily be purchased separately. Even fairly high end cards are a couple of hundred dollars and more affordable options are also available. The software required is free and works easily on Windows, Macs, and Linux. The module could easily be ported to OpenCL, a non-proprietary alternative. • The final module uses Chapel, a parallel programming language designed for high-performance computing (HPC). One of its original design goals was ease of use, which we exploit to quickly introduce the language in the context of an algorithms course. The module only covers a subset of the language, but includes the keywords to launch parallel tasks to demonstrate parallelism in divide and conquer algorithms. Also included is the idea of reductions, a fundamental parallel algorithmic technique. Standard reductions (like summing values) are built into Chapel, but the programmer can also define customized reductions using a framework that fits into the discussion of dynamic programming. The Chapel compiler is available for free. It is easily installed on Linux and Mac OS; installation on Windows requires using Cygwin. The presenter has always used it on multicore systems, but cluster installation is also possible. Each of these modules will be presented, including a discussion of the context and possible variations. After the tutorial, the presenter will make his slides, as well as lecture notes and assignments available for others to use.