Chapter 4: The Map pattern
This introduction defines the Map pattern, illustrates its independent per-element work, and relates it to GPU execution.
After this chapter you will be able to
- Independent element-wise mapping. Explain what makes an operation a Map and how its independent elements relate to threads.
- Map input and output arrangements. Describe how a Map can use multiple inputs and either update an array in place or write a separate output.
- Independent Element Transformations. Explain how independent array operations can be performed concurrently as a map, using doubling as an example.
- Pure Map Independence Test. Apply the two-step test to distinguish a pure map from an output-dependent operation or a gather, including cases with multiple inputs.
- Map in familiar tools. Recognize the Map pattern in familiar array, row, and collection operations.
- Pattern versus execution parallelism. Distinguish the Map pattern from whether its implementation actually runs operations in parallel.
- Pure functions and isolation. Explain how side-effect-free element work and separate outputs prevent interference between Map threads.
- Thread to element mapping. Explain how Map assigns output elements to threads and handles launches that include extra threads. Describe why kernels use a global index even though the single-block example reduces it to threadIdx.x.
- Single program multiple data. Describe how the same kernel runs across threads on different elements, using the five-thread doubling trace as an example.
- Two-input vector addition. Explain how vector addition maps two input vectors to an element-wise sum, and apply it to a small example.
- Vector Addition Parallel Checklist. Apply the Parallel Checklist to vector addition, identifying its inputs, output, and independent per-thread work.
- Vector addition Map structure. Explain the three-step Map kernel structure and how vector addition assigns work to threads.
- Scalar vector multiplication. Describe how to compute scalar vector multiplication from a vector and a scalar, and illustrate it with the section’s example.
- Independent scalar vector outputs. Explain why scalar-vector multiplication fits the Map pattern despite sharing a scalar among threads.
- Scalar and array arguments. Distinguish how the scalar k and arrays A and B are represented in the kernel signature.
- Per-thread scalar multiplication. Explain how threads apply the same scalar to different array elements in scalar vector multiplication.
- Scalar and array parameters. Distinguish passing a shared scalar by value from passing per-element array data through a device pointer. Apply the distinction to a constant added to every element.
- Vector ReLU mapping. Explain how ReLU transforms each element of an input vector into its corresponding output element.
- Vector ReLU parallel independence. Explain why the vector ReLU work can be done independently by threads.
- ReLU ternary operation. Explain how the ReLU expression uses a C ternary operator to select each output value, and relate it to an equivalent if/else.
- PyTorch element wise maps. Describe how the chapter's map computations appear in PyTorch and distinguish the expressed operation from the kernel actually launched.
- Silent data access mistakes. Describe the two data-access mistakes and their possible consequence: reading an element another thread is writing and overwriting a kernel's own input can quietly produce wrong answers.
- Neighbor Read Race Condition. Explain how an in-place neighbor read can race with another thread’s write and what results may appear.
- Separate Input and Output. Describe how reading from A and writing to B prevents the neighbor read from colliding with a write.
- Map and Neighbor Dependencies. Distinguish a dependency on another thread’s result from reading a neighbor in an unchanged input array.
- In-place input overwrite. Explain why writing vector-addition results into an input can cause later errors, and describe the safer alternative.
- Pure Map independence checklist. Describe the inputs, output, and per-index dependencies in the section's pure Map checklist, and explain why the threads can work independently.
What it builds on
- Squaring an array (chapter 2) · The earlier array-squaring example supplies a familiar Map.
- Your first multi-block kernel (chapter 3) · Provides the earlier multi-block doubling kernel.
- How the hardware runs your threads: warps and SMs (chapter 2) · Introduces how GPU hardware runs threads using warps and SMs.
- Sequential vs. parallel thinking (chapter 1) · The distinction between sequential and parallel thinking.
- A family of parallel approaches (chapter 1) · The family of parallel approaches that includes SIMD, OpenMP, and MapReduce.
- Each thread has its own job (chapter 2) · Each thread has its own job.
- Bounds check (chapter 2) · A bounds check prevents threads outside the array from doing element work.
- The global index formula (chapter 3) · The global index combines block and thread coordinates.
Section by section
Introduction
This introduction defines the Map pattern, illustrates its independent per-element work, and relates it to GPU execution.
- Independent element-wise mapping: Explain what makes an operation a Map and how its independent elements relate to threads.
Why it matters: Recognizing independent, same-index work helps you identify problems suited to Map. - Map input and output arrangements: Describe how a Map can use multiple inputs and either update an array in place or write a separate output.
Why it matters: These variations let you recognize Map even when its data layout differs from a single-array example. - GPU threads and cores: Explain how GPUs run Map work across cores and why raw CUDA core counts should not be compared directly with CPU core counts.
Why it matters: This explains why independent Map work fits GPUs and helps avoid misleading core-count comparisons.
Key terms: map pattern, independently, one thread per output element, vector addition, input array, output array, index, CUDA core, CPU core, streaming multiprocessor
4.1 What makes a problem “mappable”?
This section explains why independent element-wise work can run in parallel and how to distinguish a pure map from related patterns.
- Independent Element Transformations: Explain how independent array operations can be performed concurrently as a map, using doubling as an example.
Why it matters: Independence is what lets you replace a sequential loop with concurrent work. - Pure Map Independence Test: Apply the two-step test to distinguish a pure map from an output-dependent operation or a gather, including cases with multiple inputs.
Why it matters: The test separates safe parallelism from the stricter definition of a pure map.
Key terms: map, embarrassingly parallel, thread, transformation, pure map, independence test, gather, stencil, same-index rule
4.2 Where you’ve seen Map before
This section connects Map to familiar programming tools and explains how independent, side-effect-free element operations can run in different execution environments.
- Map in familiar tools: Recognize the Map pattern in familiar array, row, and collection operations.
Why it matters: Recognizing the pattern across languages helps you identify work that can be mapped. - Pattern versus execution parallelism: Distinguish the Map pattern from whether its implementation actually runs operations in parallel.
Why it matters: A Map operation exposes independent work but does not guarantee parallel execution. - CPU and cluster mappings: Describe how the same independent Map work can be distributed within a CPU or across a cluster.
Why it matters: Map is useful beyond GPUs because independent work can be distributed at several scales. - Pure functions and isolation: Explain how side-effect-free element work and separate outputs prevent interference between Map threads.
Why it matters: Isolating each thread's work is what lets many copies run without interfering.
Key terms: map, element, row, map pattern, sequential, parallel, CUDA, SIMD, AVX, OpenMP
4.3 One thread, one element
This section explains how Map assigns one output element to each GPU thread using a global index and the single program, multiple data model.
- Thread to element mapping: Explain how Map assigns output elements to threads and handles launches that include extra threads. Describe why kernels use a global index even though the single-block example reduces it to threadIdx.x.
Why it matters: This mapping lets a Map kernel cover an array without assigning work to threads beyond its bounds. - Single program multiple data: Describe how the same kernel runs across threads on different elements, using the five-thread doubling trace as an example.
Why it matters: SPMD explains how one kernel definition can apply the same operation to many data elements.
Key terms: Map pattern, global index, blockIdx.x, blockDim.x, threadIdx.x, bounds check, __global__, kernel, single program, multiple data, SPMD
4.4 Map in action: vector addition
This section introduces vector addition as a two-input map that sums corresponding elements of two vectors.
- Two-input vector addition: Explain how vector addition maps two input vectors to an element-wise sum, and apply it to a small example.
Why it matters: This example extends the map idea from one input to two corresponding inputs.
Key terms: two-input map, vector addition, element-wise sum
4.5 Thinking in parallel
This section applies the Parallel Checklist to vector addition before writing a kernel.
- Vector Addition Parallel Checklist: Apply the Parallel Checklist to vector addition, identifying its inputs, output, and independent per-thread work.
Why it matters: This checklist helps you identify independent work before translating a problem into parallel code.
Key terms: Parallel Checklist, map pattern, vector addition
4.6 Breaking it down, line by line
This section breaks down a vector-addition Map kernel and its launch, synchronization, error handling, and indexing pitfalls.
- Vector addition Map structure: Explain the three-step Map kernel structure and how vector addition assigns work to threads.
Why it matters: This structure is the reusable foundation for the chapter’s Map kernels. - Rounded-up kernel launch: Describe how the vector-addition launch chooses the block count and why it rounds up.
Why it matters: Rounding up prevents the launch from leaving elements unprocessed. - Blocking copy synchronization: Explain why the program does not need an explicit cudaDeviceSynchronize() between the kernel launch and the copy.
Why it matters: The result must be ready before the program uses the copied data. - CUDA API error returns: Describe how CUDA API error returns can be checked without cluttering every call site.
Why it matters: Checking API results helps catch errors while a helper keeps the code readable. - Multi-block indexing bug: Explain what goes wrong when a multi-block kernel uses threadIdx.x alone as its array index.
Why it matters: Correct indexing is necessary for multiple blocks to cover distinct elements.
Key terms: Map kernel, global-index formula, bounds check, idx, numBlocks, threadsPerBlock, ceiling division, cudaMemcpy, cudaDeviceSynchronize(), blocking
4.7 Map in action: scalar vector multiplication
This section defines scalar vector multiplication as multiplying each vector element by the same scalar.
- Scalar vector multiplication: Describe how to compute scalar vector multiplication from a vector and a scalar, and illustrate it with the section’s example.
Why it matters: This gives you the elementwise operation used in the scalar multiplication example.
Key terms: scalar vector multiplication, vector, scalar
4.8 Thinking in parallel
This section explains why scalar-vector multiplication is a Map and how its shared scalar differs from the array arguments.
- Independent scalar vector outputs: Explain why scalar-vector multiplication fits the Map pattern despite sharing a scalar among threads.
Why it matters: A shared input does not prevent a calculation from being a Map when threads only read it and outputs are independent. - Scalar and array arguments: Distinguish how the scalar k and arrays A and B are represented in the kernel signature.
Why it matters: The kernel signature expresses the difference between shared arrays and a single common multiplier.
Key terms: Map, scalar, read-only, int*, int k, passed by value, GPU memory
4.9 Breaking it down, line by line
This section explains how scalar vector multiplication assigns one element to each thread and passes shared scalar and per-element array data to the kernel.
- Per-thread scalar multiplication: Explain how threads apply the same scalar to different array elements in scalar vector multiplication.
Why it matters: This shows how one shared operation becomes independent work across array elements. - Scalar and array parameters: Distinguish passing a shared scalar by value from passing per-element array data through a device pointer. Apply the distinction to a constant added to every element.
Why it matters: Choosing the appropriate parameter form avoids unnecessary device allocation and copying. - Scalar multiplication host setup: Describe how the scalar multiplication main function differs from the vector addition setup in its inputs and device array allocations.
Why it matters: The different inputs determine how many device arrays the host program needs.
Key terms: scalar, thread, A[idx], parameter, value, pointer, cudaMemcpy, host memory, device, main()
4.10 Map in action: vector ReLU
This section introduces vector ReLU as a per-element Map operation used in neural networks.
- Vector ReLU mapping: Explain how ReLU transforms each element of an input vector into its corresponding output element.
Why it matters: ReLU shows that Map applies to per-element operations beyond addition and multiplication. - Neural network activation role: Describe ReLU's role as an activation function in neural networks.
Why it matters: This connects the per-element operation to a practical neural network use.
Key terms: Map, ReLU, Rectified Linear Unit, B[i] = max(0, A[i]), activation function, training, inference
4.11 Thinking in parallel
This section applies the parallel checklist to vector ReLU, emphasizing independent elementwise work.
- Vector ReLU parallel independence: Explain why the vector ReLU work can be done independently by threads.
Why it matters: Recognizing independent elementwise work helps you identify when the Map pattern fits.
Key terms: input array, output, A[idx], thread
4.12 Breaking it down, line by line
This section explains the ReLU map kernel, its floating-point host setup and edge cases, and connects element-wise CUDA maps to an absolute-value exercise and PyTorch operations.
- ReLU ternary operation: Explain how the ReLU expression uses a C ternary operator to select each output value, and relate it to an equivalent if/else.
Why it matters: This is the per-element operation that makes the kernel a ReLU map. - Floating point host setup: Describe the float-related and input-array changes in the ReLU host code compared with vector addition.
Why it matters: Changing the data type affects the host setup without changing the map's overall kernel structure. - NaN handling in ReLU: Explain how the shown ReLU ternary and fmaxf handle NaN and what is needed to preserve NaNs.
Why it matters: This choice can hide a NaN that would otherwise reveal corrupted upstream data. - Absolute value map exercise: Apply the conditional map pattern to compute integer absolute values under the exercise's stated assumption.
Why it matters: This exercise checks whether you can adapt the same per-element conditional to a different operation. - PyTorch element wise maps: Describe how the chapter's map computations appear in PyTorch and distinguish the expressed operation from the kernel actually launched.
Why it matters: The CUDA examples help you recognize the same computations in higher-level tensor code without assuming an exact implementation.
Key terms: ReLU, ternary operator, if/else, float, double, f suffix, scanf, sizeof(float), fmaxf, NaN
4.13 Common mistakes
This section identifies two data-access mistakes that can quietly produce incorrect kernel results.
- Silent data access mistakes: Describe the two data-access mistakes and their possible consequence: reading an element another thread is writing and overwriting a kernel's own input can quietly produce wrong answers.
Why it matters: Incorrect data access can produce a wrong result even when the kernel appears to run successfully.
Key terms: thread, kernel, input
4.14 Mistake 1: Accessing another thread’s element
This section explains why reading another thread’s changing element causes a race and how separate input and output arrays avoid it.
- Neighbor Read Race Condition: Explain how an in-place neighbor read can race with another thread’s write and what results may appear.
Why it matters: A race can produce wrong answers without crashing, making it difficult to spot in testing. - Separate Input and Output: Describe how reading from A and writing to B prevents the neighbor read from colliding with a write.
Why it matters: Keeping the input unchanged removes the read-write collision in this example. - Map and Neighbor Dependencies: Distinguish a dependency on another thread’s result from reading a neighbor in an unchanged input array.
Why it matters: This distinction helps you recognize when a problem is not an independent map. - Neighbor Index Boundary: Explain the boundary error at index zero and the guard used in the corrected example.
Why it matters: Avoiding the race does not by itself make an out-of-bounds neighbor access safe.
Key terms: race condition, in-place update, input array, map, reduction, scan, stencil, idx > 0, boundary check
4.15 Mistake 2: Accidentally overwriting your input
This section explains how to avoid destroying Map inputs, use const for read-only arrays, and check whether outputs can be computed independently.
- In-place input overwrite: Explain why writing vector-addition results into an input can cause later errors, and describe the safer alternative.
Why it matters: Preserving inputs prevents subtle errors in code that uses them later. - Const input parameters: Explain how declaring a read-only input as const helps prevent accidental writes and what the section says about performance.
Why it matters: A read-only declaration lets the compiler catch accidental input writes. - Pure Map independence checklist: Describe the inputs, output, and per-index dependencies in the section's pure Map checklist, and explain why the threads can work independently.
Why it matters: The dependency check tells you why the work can be assigned independently to threads. - Broad and pure Map: Distinguish the broad Map examples from a pure Map using their input-reading behavior and output independence.
Why it matters: Independent outputs can still be parallel even when their input reads are not restricted to the same index.
Key terms: in-place, pure map, race, separate output array, const, read-only parameters, compile-time error, Map, same-index inputs, independently
4.16 Summary
Where this is used later
- What a stencil is: a window around every element (chapter 9) · The distinction introduces a fixed-neighborhood read as a stencil rather than a pure map.
- Mistake 2: In-place stencil (the sneaky one) (chapter 9) · Recognizes the read-write hazard in an in-place stencil.
- The shared-variable trap: many threads, one counter (chapter 5) · Threads can race when one reads an element another is writing.
- Mistake 1: Reading and writing the same array (chapter 6) · The danger of reading another thread’s element while it is being overwritten.
- Why naive parallelism fails (chapter 5) · Builds on recognizing that dependencies call for an approach other than a simple map.
- Understanding the Scan pattern (chapter 6) · Introduces a pattern suited to dependencies rather than independent map operations.
Concepts explained in this chapter
- mapThe map pattern applies an operation independently to each element of a collection.
- vector additionVector addition combines two vectors by adding their corresponding components.
- one thread per elementOne thread per element is a data-mapping approach that assigns one parallel thread to each element of an input collection.
- cudaMemcpycudaMemcpy is a CUDA runtime API function that copies data between host and device memory or between device memory regions.
- threadA thread is a sequence of instructions that performs a unit of computation.
- race conditionA race condition is a concurrency error in which unsynchronized reads and writes let one thread overwrite a value before another thread reads it.
- data dependencyA data dependency occurs when one computation requires a value produced or modified by another computation.
- bounds checkingA bounds check is a conditional test that verifies an index lies within a data structure's valid range before access or computation.
- global indexA global index identifies a thread's corresponding element across all blocks in a CUDA grid.
- out-of-bounds array accessAn out-of-bounds access is an attempt to read or write outside the valid range of a data structure or memory allocation.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.
