충돌 없는 패턴

참고: 이 섹션은 NVIDIA GPU 전용입니다

여기서 다루는 뱅크 충돌 분석과 프로파일링 기법은 NVIDIA GPU에 특화되어 있습니다. 프로파일링 명령은 NVIDIA CUDA 툴킷에 포함된 NSight Compute 도구를 사용합니다.

프로파일링 역량을 바탕으로

Puzzle 30에서 GPU 프로파일링 기초를 배우고, Puzzle 31에서 리소스 최적화를 이해했습니다. 이제 배운 탐정 기술을 새로운 성능 미스터리에 적용할 차례입니다: 공유 메모리 뱅크 충돌.

탐정 도전 과제: 동일한 수학적 연산((input + 10) * 2)을 수행하는 두 GPU 커널이 있습니다. 둘 다 정확히 같은 결과를 냅니다. 같은 양의 공유 메모리를 사용합니다. 점유율도 동일합니다. 그런데 하나는 공유 메모리에 접근하는 방식 때문에 체계적인 성능 저하를 겪습니다.

여러분의 임무: 지금까지 배운 프로파일링 방법론으로 이 숨겨진 성능 함정을 밝혀내고, 실제 GPU 프로그래밍에서 뱅크 충돌이 언제 중요한지 이해하세요.

개요

공유 메모리 뱅크 충돌은 워프 내의 여러 스레드가 동일한 메모리 뱅크의 서로 다른 주소에 동시에 접근할 때 발생합니다. 이 탐정 사건에서는 대조적인 접근 패턴을 가진 두 커널을 살펴봅니다:

comptime SIZE = 8 * 1024  # 8K elements - small enough to focus on shared memory patterns
comptime TPB = 256  # Threads per block - divisible by 32 (warp size)
comptime THREADS_PER_BLOCK = (TPB, 1)
comptime BLOCKS_PER_GRID = (SIZE // TPB, 1)
comptime dtype = DType.float32
comptime layout = Layout.row_major(SIZE)


fn no_conflict_kernel[
    layout: Layout
](
    output: LayoutTensor[dtype, layout, MutAnyOrigin],
    input: LayoutTensor[dtype, layout, ImmutAnyOrigin],
    size: Int,
):
    """Perfect shared memory access - no bank conflicts.

    Each thread accesses a different bank: thread_idx.x maps to bank thread_idx.x % 32.
    This achieves optimal shared memory bandwidth utilization.
    """

    # Shared memory buffer - each thread loads one element
    shared_buf = LayoutTensor[
        dtype,
        Layout.row_major(TPB),
        MutAnyOrigin,
        address_space = AddressSpace.SHARED,
    ].stack_allocation()

    global_i = Int(block_dim.x * block_idx.x + thread_idx.x)
    local_i = thread_idx.x

    # Load from global memory to shared memory - no conflicts
    if global_i < size:
        shared_buf[local_i] = (
            input[global_i] + 10.0
        )  # Add 10 as simple operation

    barrier()  # Synchronize shared memory writes

    # Read back from shared memory and write to output - no conflicts
    if global_i < size:
        output[global_i] = shared_buf[local_i] * 2.0  # Multiply by 2

    barrier()  # Ensure completion

fn two_way_conflict_kernel[
    layout: Layout
](
    output: LayoutTensor[dtype, layout, MutAnyOrigin],
    input: LayoutTensor[dtype, layout, ImmutAnyOrigin],
    size: Int,
):
    """Stride-2 shared memory access - creates 2-way bank conflicts.

    Threads 0,16 → Bank 0, Threads 1,17 → Bank 1, etc.
    Each bank serves 2 threads, doubling access time.
    """

    # Shared memory buffer - stride-2 access pattern creates conflicts
    shared_buf = LayoutTensor[
        dtype,
        Layout.row_major(TPB),
        MutAnyOrigin,
        address_space = AddressSpace.SHARED,
    ].stack_allocation()

    global_i = Int(block_dim.x * block_idx.x + thread_idx.x)
    local_i = thread_idx.x

    # CONFLICT: stride-2 access creates 2-way bank conflicts
    conflict_index = (local_i * 2) % TPB

    # Load with bank conflicts
    if global_i < size:
        shared_buf[conflict_index] = (
            input[global_i] + 10.0
        )  # Same operation as no-conflict

    barrier()  # Synchronize shared memory writes

    # Read back with same conflicts
    if global_i < size:
        output[global_i] = (
            shared_buf[conflict_index] * 2.0
        )  # Same operation as no-conflict

    barrier()  # Ensure completion

전체 파일 보기: problems/p32/p32.mojo

미스터리: 이 커널들은 동일한 결과를 계산하지만 공유 메모리 접근 효율은 극적으로 다릅니다. 체계적인 프로파일링 분석을 통해 그 이유를 밝혀내는 것이 임무입니다.

구성

요구 사항:

• Puzzle 30의 CUDA 툴킷과 NSight Compute가 설치된 NVIDIA GPU
• 이전 섹션에서 다룬 공유 메모리 뱅킹 개념에 대한 이해

커널 설정:

comptime SIZE = 8 * 1024      # 8K elements - focus on shared memory patterns
comptime TPB = 256            # 256 threads per block (8 warps)
comptime BLOCKS_PER_GRID = (SIZE // TPB, 1)  # 32 blocks

핵심 통찰: 전역 메모리 대역폭 제한이 아닌 공유 메모리 효과를 부각하기 위해 문제 크기를 의도적으로 이전 퍼즐보다 작게 설정했습니다.

조사 과정

Step 1: 정확성 검증

pixi shell -e nvidia
mojo problems/p32/p32.mojo --test

두 커널 모두 동일한 결과를 내야 합니다. 이를 통해 뱅크 충돌이 정확성이 아닌 성능에 영향을 미친다는 것을 확인합니다.

Step 2: 성능 기준선 벤치마크

mojo problems/p32/p32.mojo --benchmark

실행 시간을 기록하세요. 워크로드가 전역 메모리 접근에 의해 지배되기 때문에 비슷한 성능이 나올 수 있지만, 뱅크 충돌은 프로파일링 메트릭을 통해 드러납니다.

Step 3: 프로파일링용 빌드

mojo build --debug-level=full problems/p32/p32.mojo -o problems/p32/p32_profiler

Step 4: 뱅크 충돌 프로파일링

NSight Compute를 사용하여 공유 메모리 뱅크 충돌을 정량적으로 측정합니다:

# Profile no-conflict kernel
ncu --metrics=l1tex__data_bank_conflicts_pipe_lsu_mem_shared_op_ld,l1tex__data_bank_conflicts_pipe_lsu_mem_shared_op_st problems/p32/p32_profiler --no-conflict

그리고

# Profile two-way conflict kernel
ncu --metrics=l1tex__data_bank_conflicts_pipe_lsu_mem_shared_op_ld,l1tex__data_bank_conflicts_pipe_lsu_mem_shared_op_st problems/p32/p32_profiler --two-way

기록할 핵심 메트릭:

• l1tex__data_bank_conflicts_pipe_lsu_mem_shared_op_ld.sum - 로드 충돌
• l1tex__data_bank_conflicts_pipe_lsu_mem_shared_op_st.sum - 스토어 충돌

Step 5: 접근 패턴 분석

프로파일링 결과를 바탕으로 수학적 접근 패턴을 분석합니다:

충돌 없는 커널 접근 패턴:

# Thread mapping: thread_idx.x directly maps to shared memory index
shared_buf[thread_idx.x]  # Thread 0→Index 0, Thread 1→Index 1, etc.
# Bank mapping: Index % 32 = Bank ID
# Result: Thread 0→Bank 0, Thread 1→Bank 1, ..., Thread 31→Bank 31

2-way 충돌 커널 접근 패턴:

# Thread mapping with stride-2 modulo operation
shared_buf[(thread_idx.x * 2) % TPB]
# For threads 0-31: Index 0,2,4,6,...,62, then wraps to 64,66,...,126, then 0,2,4..
# Bank mapping examples:
# Thread 0  → Index 0   → Bank 0
# Thread 16 → Index 32  → Bank 0  (conflict!)
# Thread 1  → Index 2   → Bank 2
# Thread 17 → Index 34  → Bank 2  (conflict!)

도전 과제: 뱅크 충돌 미스터리를 풀어보세요

위의 조사 단계를 완료한 후, 다음 분석 질문에 답하세요:

성능 분석 (Step 1-2)

1. 두 커널이 동일한 수학적 결과를 내나요?
2. 커널 간 실행 시간 차이가 있나요?
3. 접근 패턴이 다른데도 성능이 비슷할 수 있는 이유는 무엇인가요?

뱅크 충돌 프로파일링 (Step 4)

1. 충돌 없는 커널은 로드와 스토어에서 몇 건의 뱅크 충돌을 발생시키나요?
2. 2-way 충돌 커널은 로드와 스토어에서 몇 건의 뱅크 충돌을 발생시키나요?
3. 두 커널 간 총 충돌 횟수 차이는 얼마인가요?

접근 패턴 분석 (Step 5)

1. 충돌 없는 커널에서 Thread 0은 어떤 뱅크에 접근하나요? Thread 31은?
2. 2-way 충돌 커널에서 Bank 0에 접근하는 스레드는? Bank 2에 접근하는 스레드는?
3. 충돌 커널에서 같은 뱅크를 놓고 경쟁하는 스레드는 몇 개인가요?

뱅크 충돌 탐정 작업

1. 충돌 없는 커널은 충돌이 0인데, 2-way 충돌 커널에서는 측정 가능한 충돌이 나타나는 이유는 무엇인가요?
2. stride-2 접근 패턴 (thread_idx.x * 2) % TPB는 어떻게 체계적인 충돌을 만들어내나요?
3. 뱅크 충돌이 메모리 바운드 커널보다 연산 집약적 커널에서 더 중요한 이유는 무엇인가요?

실전 시사점

1. 뱅크 충돌이 애플리케이션 성능에 큰 영향을 미칠 것으로 예상되는 경우는 언제인가요?
2. 공유 메모리 알고리즘을 구현하기 전에 뱅크 충돌 패턴을 어떻게 예측할 수 있나요?
3. 행렬 연산과 스텐실 연산에서 뱅크 충돌을 피하는 데 도움이 되는 설계 원칙은 무엇인가요?

솔루션

✅ No-conflict kernel: PASSED
✅ Two-way conflict kernel: PASSED
✅ Both kernels produce identical results

| name             | met (ms)           | iters |
| ---------------- | ------------------ | ----- |
| no_conflict      | 2.1930616745886655 | 547   |
| two_way_conflict | 2.1978922967032966 | 546   |

l1tex__data_bank_conflicts_pipe_lsu_mem_shared_op_ld.sum    0
l1tex__data_bank_conflicts_pipe_lsu_mem_shared_op_st.sum    0

l1tex__data_bank_conflicts_pipe_lsu_mem_shared_op_ld.sum    256
l1tex__data_bank_conflicts_pipe_lsu_mem_shared_op_st.sum    256

shared_buf[thread_idx.x]

Thread 0  → Index 0   → Bank 0 % 32 = 0
Thread 1  → Index 1   → Bank 1 % 32 = 1
Thread 2  → Index 2   → Bank 2 % 32 = 2
...
Thread 31 → Index 31  → Bank 31 % 32 = 31

shared_buf[(thread_idx.x * 2) % TPB]  # TPB = 256

Thread 0  → Index (0*2)%256 = 0   → Bank 0
Thread 1  → Index (1*2)%256 = 2   → Bank 2
Thread 2  → Index (2*2)%256 = 4   → Bank 4
...
Thread 16 → Index (16*2)%256 = 32 → Bank 0  ← Thread 0과 충돌
Thread 17 → Index (17*2)%256 = 34 → Bank 2  ← Thread 1과 충돌
Thread 18 → Index (18*2)%256 = 36 → Bank 4  ← Thread 2와 충돌
...

# Problematic: All threads in warp access same column
for k in range(tile_size):
    acc += a_shared[local_row, k] * b_shared[k, local_col]  # b_shared[k, 0] conflicts

# Problematic: Stride access in boundary handling
shared_buf[thread_idx.x * stride]  # Creates systematic conflicts

# Problematic: Power-of-2 stride patterns
if thread_idx.x < stride:
    shared_buf[thread_idx.x] += shared_buf[thread_idx.x + stride]  # Conflict potential

shared[thread_idx.x]  # Optimal - each thread different bank

constant = shared[0]  # All threads read same address - hardware optimized

shared = LayoutTensor[dtype, Layout.row_major(TPB + 1), MutAnyOrigin, address_space = AddressSpace.SHARED].stack_allocation()  # Shift access patterns