Puzzle 31: 점유율 최적화

이 퍼즐이 중요한 이유

Puzzle 30의 연장선: GPU 프로파일링 도구를 배우고, 메모리 접근 패턴이 어떻게 극적인 성능 차이를 만들어내는지 발견했습니다. 이제 다음 단계로 나아갈 준비가 되었습니다: 리소스 최적화.

학습 여정:

• Puzzle 30에서는 NSight 프로파일링(nsys와 ncu)을 통해 성능 문제를 진단하는 법을 배웠습니다
• Puzzle 31에서는 리소스 관리를 통해 성능을 예측하고 제어하는 법을 배웁니다
• 둘을 합치면 GPU 최적화를 위한 완전한 도구 세트를 갖추게 됩니다

발견하게 될 것: GPU 성능은 단순히 알고리즘 효율의 문제가 아닙니다 - 코드가 한정된 하드웨어 리소스를 어떻게 활용하느냐가 핵심입니다. 모든 GPU는 유한한 레지스터, 공유 메모리, 실행 유닛을 갖고 있습니다. 점유율(occupancy) - SM당 활성 워프 수 대비 최대 가능 워프 수의 비율 - 을 이해하는 것은 다음과 같은 이유로 중요합니다:

• 지연 시간 은닉: 메모리 대기 시간 동안 GPU가 유휴 상태에 빠지지 않도록 유지
• 리소스 할당: 레지스터, 공유 메모리, 스레드 블록 간의 균형 조절
• 성능 예측: 병목이 발생하기 전에 미리 파악
• 최적화 전략: 점유율에 집중해야 할 때와 다른 요소에 집중해야 할 때 판단

GPU를 넘어서 적용되는 원리: 여기서 배우는 원리는 리소스를 여러 실행 유닛이 공유하는 모든 병렬 컴퓨팅 시스템에 적용됩니다 - 하이퍼스레딩을 사용하는 CPU부터 분산 컴퓨팅 클러스터까지.

개요

GPU 점유율은 SM당 활성 워프 수 대비 최대 가능 워프 수의 비율입니다. GPU가 워프 전환을 통해 메모리 지연 시간을 얼마나 효과적으로 숨길 수 있는지를 결정합니다.

SAXPY는 Single-precision Alpha times X plus Y의 약자입니다. 이 퍼즐에서는 수학적으로 동일하지만 리소스 사용이 다른 세 가지 SAXPY 커널(y[i] = alpha * x[i] + y[i])을 탐구합니다:

comptime SIZE = 32 * 1024 * 1024  # 32M elements - larger workload to show occupancy effects
comptime THREADS_PER_BLOCK = (1024, 1)
comptime BLOCKS_PER_GRID = (SIZE // 1024, 1)
comptime dtype = DType.float32
comptime layout = Layout.row_major(SIZE)
comptime ALPHA = Float32(2.5)  # SAXPY coefficient


fn minimal_kernel[
    layout: Layout
](
    y: LayoutTensor[dtype, layout, MutAnyOrigin],
    x: LayoutTensor[dtype, layout, ImmutAnyOrigin],
    alpha: Float32,
    size: Int,
):
    """Minimal SAXPY kernel - simple and register-light for high occupancy."""
    i = Int(block_dim.x * block_idx.x + thread_idx.x)
    if i < size:
        # Direct computation: y[i] = alpha * x[i] + y[i]
        # Uses minimal registers (~8), no shared memory
        y[i] = alpha * x[i] + y[i]

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

fn sophisticated_kernel[
    layout: Layout
](
    y: LayoutTensor[dtype, layout, MutAnyOrigin],
    x: LayoutTensor[dtype, layout, ImmutAnyOrigin],
    alpha: Float32,
    size: Int,
):
    """Sophisticated SAXPY kernel - over-engineered with excessive resource usage.
    """
    # Maximum shared memory allocation (close to 48KB limit)
    shared_cache = LayoutTensor[
        dtype,
        Layout.row_major(1024 * 12),
        MutAnyOrigin,
        address_space = AddressSpace.SHARED,
    ].stack_allocation()  # 48KB

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

    if i < size:
        # REAL computational work that can't be optimized away - affects final result
        base_x = x[i]
        base_y = y[i]

        # Simulate "precision enhancement" - multiple small adjustments that add up
        # Each computation affects the final result so compiler can't eliminate them
        # But artificially increases register pressure
        precision_x1 = base_x * 1.0001
        precision_x2 = precision_x1 * 0.9999
        precision_x3 = precision_x2 * 1.000001
        precision_x4 = precision_x3 * 0.999999

        precision_y1 = base_y * 1.000005
        precision_y2 = precision_y1 * 0.999995
        precision_y3 = precision_y2 * 1.0000001
        precision_y4 = precision_y3 * 0.9999999

        # Multiple alpha computations for "stability" - should equal alpha
        alpha1 = alpha * 1.00001 * 0.99999
        alpha2 = alpha1 * 1.000001 * 0.999999
        alpha3 = alpha2 * 1.0000001 * 0.9999999
        alpha4 = alpha3 * 1.00000001 * 0.99999999

        # Complex polynomial "optimization" - creates register pressure
        x_power2 = precision_x4 * precision_x4
        x_power3 = x_power2 * precision_x4
        x_power4 = x_power3 * precision_x4
        x_power5 = x_power4 * precision_x4
        x_power6 = x_power5 * precision_x4
        x_power7 = x_power6 * precision_x4
        x_power8 = x_power7 * precision_x4

        # "Advanced" mathematical series that contributes tiny amount to result
        series_term1 = x_power2 * 0.0000001  # x^2/10M
        series_term2 = x_power4 * 0.00000001  # x^4/100M
        series_term3 = x_power6 * 0.000000001  # x^6/1B
        series_term4 = x_power8 * 0.0000000001  # x^8/10B
        series_correction = (
            series_term1 - series_term2 + series_term3 - series_term4
        )

        # Over-engineered shared memory usage with multiple caching strategies
        if local_i < 1024:
            shared_cache[local_i] = precision_x4
            shared_cache[local_i + 1024] = precision_y4
            shared_cache[local_i + 2048] = alpha4
            shared_cache[local_i + 3072] = series_correction
        barrier()

        # Load from shared memory for "optimization"
        cached_x = shared_cache[local_i] if local_i < 1024 else precision_x4
        cached_y = (
            shared_cache[local_i + 1024] if local_i < 1024 else precision_y4
        )
        cached_alpha = (
            shared_cache[local_i + 2048] if local_i < 1024 else alpha4
        )
        cached_correction = (
            shared_cache[local_i + 3072] if local_i
            < 1024 else series_correction
        )

        # Final "high precision" computation - all work contributes to result
        high_precision_result = (
            cached_alpha * cached_x + cached_y + cached_correction
        )

        # Over-engineered result with massive resource usage but mathematically ~= alpha*x + y
        y[i] = high_precision_result

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

fn balanced_kernel[
    layout: Layout
](
    y: LayoutTensor[dtype, layout, MutAnyOrigin],
    x: LayoutTensor[dtype, layout, ImmutAnyOrigin],
    alpha: Float32,
    size: Int,
):
    """Balanced SAXPY kernel - efficient optimization with moderate resources.
    """
    # Reasonable shared memory usage for effective caching (16KB)
    shared_cache = LayoutTensor[
        dtype,
        Layout.row_major(1024 * 4),
        MutAnyOrigin,
        address_space = AddressSpace.SHARED,
    ].stack_allocation()  # 16KB total

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

    if i < size:
        # Moderate computational work that contributes to result
        base_x = x[i]
        base_y = y[i]

        # Light precision enhancement - less than sophisticated kernel
        enhanced_x = base_x * 1.00001 * 0.99999
        enhanced_y = base_y * 1.00001 * 0.99999
        stable_alpha = alpha * 1.000001 * 0.999999

        # Moderate computational optimization
        x_squared = enhanced_x * enhanced_x
        optimization_hint = x_squared * 0.000001

        # Efficient shared memory caching - only what we actually need
        if local_i < 1024:
            shared_cache[local_i] = enhanced_x
            shared_cache[local_i + 1024] = enhanced_y
        barrier()

        # Use cached values efficiently
        cached_x = shared_cache[local_i] if local_i < 1024 else enhanced_x
        cached_y = (
            shared_cache[local_i + 1024] if local_i < 1024 else enhanced_y
        )

        # Balanced computation - moderate work, good efficiency
        result = stable_alpha * cached_x + cached_y + optimization_hint

        # Balanced result with moderate resource usage (~15 registers, 16KB shared)
        y[i] = result

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

도전 과제

프로파일링 도구를 사용하여 세 커널을 조사하고, 점유율 최적화에 대한 분석 질문에 답하세요. 커널들은 동일한 결과를 계산하지만 리소스 사용이 극적으로 다릅니다 - 성능과 점유율이 왜 직관에 어긋나는 방식으로 동작하는지 발견하는 것이 여러분의 임무입니다!

이 퍼즐에 표시된 구체적인 수치 결과는 NVIDIA A10G (Ampere 8.6) 하드웨어를 기준으로 합니다. 결과는 GPU 제조사와 아키텍처(NVIDIA: Pascal/Turing/Ampere/Ada/Hopper, AMD: RDNA/GCN, Apple: M1/M2/M3/M4/M5)에 따라 달라지지만, 기본 개념, 방법론, 통찰은 모든 최신 GPU에 보편적으로 적용됩니다. pixi run gpu-specs를 실행하여 하드웨어별 수치를 확인하세요.

구성

요구 사항:

• CUDA 툴킷이 설치된 NVIDIA GPU
• Puzzle 30의 NSight Compute

⚠️ GPU 호환성 참고: 기본 설정은 공격적인 값을 사용하므로 구형이나 저사양 GPU에서는 실패할 수 있습니다:

comptime SIZE = 32 * 1024 * 1024  # 32M 요소 (배열당 ~256MB 메모리)
comptime THREADS_PER_BLOCK = (1024, 1)  # 블록당 1024 스레드
comptime BLOCKS_PER_GRID = (SIZE // 1024, 1)  # 32768 블록

실행 실패 시 problems/p31/p31.mojo에서 다음 값을 줄이세요:

• 구형 GPU (Compute Capability < 3.0): THREADS_PER_BLOCK = (512, 1), SIZE = 16 * 1024 * 1024 사용
• 메모리 제한 GPU (< 2GB): SIZE = 8 * 1024 * 1024 또는 SIZE = 4 * 1024 * 1024 사용
• 그리드 차원 제한: BLOCKS_PER_GRID는 SIZE에 맞춰 자동 조정됩니다

점유율 공식:

이론적 점유율 = min(
    SM당 레지스터 수 / (스레드당 레지스터 수 × 블록당 스레드 수),
    SM당 공유 메모리 / 블록당 공유 메모리,
    SM당 최대 블록 수
) × 블록당 스레드 수 / SM당 최대 스레드 수

조사 과정

Step 1: 커널 테스트

pixi shell -e nvidia
mojo problems/p31/p31.mojo --all

세 커널 모두 동일한 결과를 내야 합니다. 미스터리: 왜 성능은 다를까요?

Step 2: 성능 벤치마크

mojo problems/p31/p31.mojo --benchmark

세 커널 모두 동일한 결과를 내야 합니다. 미스터리: 왜 성능은 다를까요?

Step 3: 프로파일링용 빌드

mojo build --debug-level=full problems/p31/p31.mojo -o problems/p31/p31_profiler

Step 4: 리소스 사용량 프로파일링

# 각 커널의 리소스 사용량 프로파일링
ncu --set=@occupancy --section=LaunchStats problems/p31/p31_profiler --minimal
ncu --set=@occupancy --section=LaunchStats problems/p31/p31_profiler --sophisticated
ncu --set=@occupancy --section=LaunchStats problems/p31/p31_profiler --balanced

점유율 분석을 위해 리소스 사용량을 기록하세요.

Step 5: 이론적 점유율 계산

먼저 GPU 아키텍처와 세부 스펙을 확인합니다:

pixi run gpu-specs

참고: gpu-specs는 GPU 제조사(NVIDIA/AMD/Apple)를 자동 감지하고 하드웨어에서 파생된 모든 아키텍처 세부 정보를 표시합니다 - 별도의 참조표가 필요 없습니다!

주요 아키텍처 스펙 (참고용):

📚 공식 문서:

• NVIDIA CUDA Compute Capability Table
• CUDA Programming Guide - Compute Capabilities
• Hopper Architecture In-Depth
• Ampere Architecture Whitepaper

⚠️ 참고: 이 값들은 이론적 최대치입니다. 실제 점유율은 하드웨어 스케줄링 제약, 드라이버 오버헤드 등의 요인으로 더 낮을 수 있습니다.

GPU 스펙과 점유율 공식을 사용하여:

• 블록당 스레드 수: 1024 (커널 설정값)

점유율 공식과 하드웨어 스펙을 사용하여 각 커널의 이론적 점유율을 예측하세요.

Step 6: 실제 점유율 측정

# 각 커널의 실제 점유율 측정
ncu --metrics=smsp__warps_active.avg.pct_of_peak_sustained_active problems/p31/p31_profiler --minimal
ncu --metrics=smsp__warps_active.avg.pct_of_peak_sustained_active problems/p31/p31_profiler --sophisticated
ncu --metrics=smsp__warps_active.avg.pct_of_peak_sustained_active problems/p31/p31_profiler --balanced

이론적 계산과 실제 측정된 점유율을 비교하세요 - 미스터리가 드러나는 순간입니다!

핵심 통찰

💡 점유율 임계값: 대기 시간을 숨기기에 충분한 점유율(~25-50%)을 확보하면, 그 이상의 점유율은 수확 체감 효과를 보입니다.

💡 메모리 바운드 vs 연산 바운드: SAXPY는 메모리 바운드입니다. 메모리 바운드 커널에서는 메모리 대역폭이 점유율보다 더 중요한 경우가 많습니다.

💡 리소스 효율: 최신 GPU는 적당한 수준의 레지스터 압박(스레드당 20-40개)을 점유율의 극적인 감소 없이 처리할 수 있습니다.

도전 과제: 다음 질문에 답하세요

위의 조사 단계를 완료한 후, 다음 분석 질문에 답하여 점유율 미스터리를 풀어보세요:

성능 분석 (Step 2):

1. 어떤 커널이 가장 빠르고, 어떤 커널이 가장 느린가요? 실행 시간 차이를 기록하세요.

리소스 프로파일링 (Step 4):

2. 각 커널의 스레드당 레지스터 수, 블록당 공유 메모리, SM당 워프 수를 기록하세요.

이론적 계산 (Step 5):

3. GPU 스펙과 점유율 공식을 사용하여 각 커널의 이론적 점유율을 계산하세요. 어떤 커널이 가장 높고/낮아야 하나요?

측정된 점유율 (Step 6):

4. 측정된 점유율 값이 계산 결과와 어떻게 비교되나요?

점유율 미스터리:

5. 리소스 사용이 극적으로 다른데도 세 커널 모두 비슷한 점유율(~64-66%, GPU 아키텍처에 따라 다를 수 있음)를 달성하는 이유는 무엇인가요?
6. 리소스 사용이 극적으로 차이나는데(19 vs 40 레지스터, 0KB vs 49KB 공유 메모리) 성능이 거의 동일한(<2% 차이) 이유는 무엇인가요?
7. 이론적 점유율 계산과 실제 GPU 동작 사이의 관계에 대해 무엇을 알 수 있나요?
8. 이 SAXPY 워크로드의 실제 성능 병목이 점유율이 아니라면 무엇인가요?

솔루션

레지스터 제한 = 65,536 / (19 × 1,024) = 3.36 블록/SM
공유 메모리 제한 = 164KB / 0KB = ∞ 블록/SM
하드웨어 블록 제한 = 32 블록/SM

스레드 제한 = 1,536 / 1,024 = 1 블록/SM (내림)
실제 블록 = min(3, ∞, 1) = 1 블록/SM
이론적 점유율 = (1 × 1,024) / 1,536 = 66.7%

레지스터 제한 = 65,536 / (25 × 1,024) = 2.56 블록/SM
공유 메모리 제한 = 164KB / 16.4KB = 10 블록/SM
하드웨어 블록 제한 = 32 블록/SM

스레드 제한 = 1,536 / 1,024 = 1 블록/SM (내림)
실제 블록 = min(2, 10, 1) = 1 블록/SM
이론적 점유율 = (1 × 1,024) / 1,536 = 66.7%

레지스터 제한 = 65,536 / (40 × 1,024) = 1.64 블록/SM
공유 메모리 제한 = 164KB / 49.2KB = 3.33 블록/SM
하드웨어 블록 제한 = 32 블록/SM

스레드 제한 = 1,536 / 1,024 = 1 블록/SM (내림)
실제 블록 = min(1, 3, 1) = 1 블록/SM
이론적 점유율 = (1 × 1,024) / 1,536 = 66.7%

단일 커널 패스 분석:
- 입력 배열: 32M × 4바이트 × 2 배열 = 256MB 읽기
- 출력 배열: 32M × 4바이트 × 1 배열 = 128MB 쓰기
- 커널당 총량: 384MB 메모리 트래픽

최대 대역폭 (A10G): 600 GB/s
단일 패스 시간: 384MB / 600 GB/s ≈ 0.64ms 이론적 최소치
벤치마크 시간: ~328ms (여러 반복 + 오버헤드 포함)

# GPU 스펙 확인
pixi run gpu-specs

# 리소스 소비량 측정
ncu --set=@occupancy --section=LaunchStats your_kernel

# 달성된 점유율 측정
ncu --metrics=smsp__warps_active.avg.pct_of_peak_sustained_active your_kernel

# 항상 실제 성능 측정으로 검증
ncu --set=@roofline --section=MemoryWorkloadAnalysis your_kernel

점유율 분석 → 최적화 전략:

높은 점유율 (>70%) + 좋은 성능:
→ 점유율은 충분, 다른 병목에 집중

낮은 점유율 (<30%) + 나쁜 성능:
→ 리소스 최적화를 통해 점유율 향상 필요

적당한 점유율 (50-70%) + 나쁜 성능:
→ 메모리 대역폭, 캐시, 연산 병목 조사 필요

낮은 점유율 (<30%) + 좋은 성능:
→ 워크로드가 높은 점유율을 필요로 하지 않음 (메모리 바운드)