warp.shuffle_xor() 버터플라이 통신

워프 레벨 버터플라이 통신에서는 shuffle_xor()을 사용하여 워프 내에 정교한 트리 기반 통신 패턴을 구성할 수 있습니다. 이 강력한 기본 요소를 통해 공유 메모리나 명시적 동기화 없이 효율적인 병렬 리덕션, 정렬 네트워크, 고급 조정 알고리즘을 구현할 수 있습니다.

핵심 통찰: shuffle_xor() 연산은 SIMT 실행을 활용하여 XOR 기반 통신 트리를 생성하며, 워프 크기에 대해 \(O(\log n)\) 복잡도로 확장되는 효율적인 버터플라이 네트워크와 병렬 알고리즘을 가능하게 합니다.

버터플라이 네트워크란? 버터플라이 네트워크는 스레드들이 인덱스의 XOR 패턴에 따라 데이터를 교환하는 통신 토폴로지입니다. 이름은 시각적으로 그렸을 때 나비 날개처럼 보이는 연결 패턴에서 유래했습니다. 이 네트워크는 \(O(\log n)\) 통신 복잡도를 가능하게 하기 때문에 FFT, bitonic 정렬, 병렬 리덕션 같은 병렬 알고리즘의 기반이 됩니다.

핵심 개념

이 퍼즐에서 배울 내용:

• shuffle_xor()을 활용한 XOR 기반 통신 패턴
• 병렬 알고리즘을 위한 버터플라이 네트워크 토폴로지
• \(O(\log n)\) 복잡도의 트리 기반 병렬 리덕션
• 고급 조정을 위한 조건부 버터플라이 연산
• 복잡한 공유 메모리를 대체하는 하드웨어 최적화 병렬 기본 요소

shuffle_xor 연산은 각 레인이 XOR 패턴에 따라 다른 레인과 데이터를 교환할 수 있게 합니다: \[\Large \text{shuffle_xor}(\text{value}, \text{mask}) = \text{value_from_lane}(\text{lane_id} \oplus \text{mask})\]

이를 통해 복잡한 병렬 알고리즘이 우아한 버터플라이 통신 패턴으로 변환되어, 명시적 조정 없이 효율적인 트리 리덕션과 정렬 네트워크가 가능합니다.

1. 기본 버터플라이 페어 교환

구성

• 벡터 크기: SIZE = WARP_SIZE (GPU에 따라 32 또는 64)
• 그리드 구성: (1, 1) 그리드당 블록 수
• 블록 구성: (WARP_SIZE, 1) 블록당 스레드 수
• 데이터 타입: DType.float32
• 레이아웃: row_major[SIZE]() (1D row-major)

shuffle_xor 개념

기존 페어 교환 방식은 복잡한 인덱싱과 조정이 필요합니다:

# 기존 방식 - 복잡하고 동기화가 필요
shared_memory[lane] = input[global_i]
barrier()
if lane % 2 == 0:
    partner = lane + 1
else:
    partner = lane - 1
if partner < WARP_SIZE:
    swapped_val = shared_memory[partner]

기존 방식의 문제점:

• 메모리 오버헤드: 공유 메모리 할당이 필요
• 동기화: 명시적 배리어가 필요
• 복잡한 로직: 수동 파트너 계산과 경계 검사
• 낮은 확장성: 하드웨어 통신을 활용하지 못함

shuffle_xor()을 사용하면 페어 교환이 우아해집니다:

# 버터플라이 XOR 방식 - 간단하고 하드웨어 최적화
current_val = input[global_i]
swapped_val = shuffle_xor(current_val, 1)  # 1과 XOR하면 페어가 생성됨
output[global_i] = swapped_val

shuffle_xor의 장점:

• 메모리 오버헤드 제로: 레지스터 간 직접 통신
• 동기화 불필요: SIMT 실행이 정확성을 보장
• 하드웨어 최적화: 모든 레인에 대해 단일 명령으로 처리
• 버터플라이 기반: 복잡한 병렬 알고리즘의 빌딩 블록

완성할 코드

shuffle_xor()을 사용하여 인접 페어 간 값을 교환하는 페어 교환을 구현합니다.

수학적 연산: XOR 패턴으로 인접 페어를 만들어 값을 교환합니다: \[\Large \text{output}[i] = \text{input}[i \oplus 1]\]

입력 데이터 [0, 1, 2, 3, 4, 5, 6, 7, ...]을 페어 [1, 0, 3, 2, 5, 4, 7, 6, ...]으로 변환하며, 각 페어 (i, i+1)이 XOR 통신으로 값을 교환합니다.

def butterfly_pair_swap[
    size: Int
](
    output: TileTensor[mut=True, dtype, LayoutType, MutAnyOrigin],
    input: TileTensor[mut=False, dtype, LayoutType, ImmutAnyOrigin],
):
    """
    Basic butterfly pair swap: Exchange values between adjacent pairs using XOR pattern.
    Each thread exchanges its value with its XOR-1 neighbor, creating pairs: (0,1), (2,3), (4,5), etc.
    Uses shuffle_xor(val, 1) to swap values within each pair.
    This is the foundation of butterfly network communication patterns.
    """
    var global_i = block_dim.x * block_idx.x + thread_idx.x

    # FILL ME IN (4 lines)

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

버터플라이 페어 교환 테스트:

pixi run p26 --pair-swap

pixi run -e amd p26 --pair-swap

pixi run -e apple p26 --pair-swap

uv run poe p26 --pair-swap

풀었을 때의 예상 출력:

WARP_SIZE:  32
SIZE:  32
output: [1.0, 0.0, 3.0, 2.0, 5.0, 4.0, 7.0, 6.0, 9.0, 8.0, 11.0, 10.0, 13.0, 12.0, 15.0, 14.0, 17.0, 16.0, 19.0, 18.0, 21.0, 20.0, 23.0, 22.0, 25.0, 24.0, 27.0, 26.0, 29.0, 28.0, 31.0, 30.0]
expected: [1.0, 0.0, 3.0, 2.0, 5.0, 4.0, 7.0, 6.0, 9.0, 8.0, 11.0, 10.0, 13.0, 12.0, 15.0, 14.0, 17.0, 16.0, 19.0, 18.0, 21.0, 20.0, 23.0, 22.0, 25.0, 24.0, 27.0, 26.0, 29.0, 28.0, 31.0, 30.0]
✅ Butterfly pair swap test passed!

솔루션

def butterfly_pair_swap[
    size: Int
](
    output: TileTensor[mut=True, dtype, LayoutType, MutAnyOrigin],
    input: TileTensor[mut=False, dtype, LayoutType, ImmutAnyOrigin],
):
    """
    Basic butterfly pair swap: Exchange values between adjacent pairs using XOR pattern.
    Each thread exchanges its value with its XOR-1 neighbor, creating pairs: (0,1), (2,3), (4,5), etc.
    Uses shuffle_xor(val, 1) to swap values within each pair.
    This is the foundation of butterfly network communication patterns.
    """
    var global_i = block_dim.x * block_idx.x + thread_idx.x

    if global_i < size:
        var current_val = input[global_i]

        # Exchange with XOR-1 neighbor using butterfly pattern
        # Lane 0 exchanges with lane 1, lane 2 with lane 3, etc.
        var swapped_val = shuffle_xor(current_val, 1)

        # For demonstration, we'll store the swapped value
        # In real applications, this might be used for sorting, reduction, etc.
        output[global_i] = swapped_val

if global_i < size:
    current_val = input[global_i]              # 각 레인이 자신의 요소를 읽음
    swapped_val = shuffle_xor(current_val, 1)  # XOR로 페어 교환 생성

    # 교환된 값을 저장
    output[global_i] = swapped_val

사이클 1: 모든 레인이 동시에 값을 로드
  Lane 0: current_val = input[0] = 0
  Lane 1: current_val = input[1] = 1
  Lane 2: current_val = input[2] = 2
  Lane 3: current_val = input[3] = 3
  ...
  Lane 31: current_val = input[31] = 31

사이클 2: shuffle_xor(current_val, 1)이 모든 레인에서 실행
  Lane 0: Lane 1에서 수신 (0⊕1=1) → swapped_val = 1
  Lane 1: Lane 0에서 수신 (1⊕1=0) → swapped_val = 0
  Lane 2: Lane 3에서 수신 (2⊕1=3) → swapped_val = 3
  Lane 3: Lane 2에서 수신 (3⊕1=2) → swapped_val = 2
  ...
  Lane 30: Lane 31에서 수신 (30⊕1=31) → swapped_val = 31
  Lane 31: Lane 30에서 수신 (31⊕1=30) → swapped_val = 30

사이클 3: 결과 저장
  Lane 0: output[0] = 1
  Lane 1: output[1] = 0
  Lane 2: output[2] = 3
  Lane 3: output[3] = 2
  ...

2. 버터플라이 병렬 최댓값

구성

• 벡터 크기: SIZE = WARP_SIZE (GPU에 따라 32 또는 64)
• 그리드 구성: (1, 1) 그리드당 블록 수
• 블록 구성: (WARP_SIZE, 1) 블록당 스레드 수

완성할 코드

감소하는 offset으로 버터플라이 shuffle_xor을 사용하여 병렬 최댓값 리덕션을 구현합니다.

수학적 연산: 트리 리덕션을 통해 모든 워프 레인에서 최댓값을 계산합니다: \[\Large \text{max_result} = \max_{i=0}^{\small\text{WARP_SIZE}-1} \text{input}[i]\]

버터플라이 리덕션 패턴: XOR 오프셋을 WARP_SIZE/2에서 1까지 절반씩 줄여가며, 통신 범위가 단계마다 반으로 좁아지는 이진 트리를 구성합니다:

• 1단계: WARP_SIZE/2 거리의 레인과 비교 (워프 전체를 포괄)
• 2단계: WARP_SIZE/4 거리의 레인과 비교 (범위를 절반으로 좁힘)
• 3단계: WARP_SIZE/8 거리의 레인과 비교
• 4단계: offset = 1이 될 때까지 계속 절반으로 줄임

\(\log_2(\text{WARP_SIZE})\) 단계를 거치면 모든 레인이 전역 최댓값을 갖게 됩니다. 이 방식은 모든 WARP_SIZE (32, 64 등)에서 동작합니다.

def butterfly_parallel_max[
    size: Int
](
    output: TileTensor[mut=True, dtype, LayoutType, MutAnyOrigin],
    input: TileTensor[mut=False, dtype, LayoutType, ImmutAnyOrigin],
):
    """
    Parallel maximum reduction using butterfly pattern.
    Uses shuffle_xor with decreasing offsets (16, 8, 4, 2, 1) to perform tree-based reduction.
    Each step reduces the active range by half until all threads have the maximum value.
    This implements an efficient O(log n) parallel reduction algorithm.
    """
    var global_i = block_dim.x * block_idx.x + thread_idx.x

    # FILL ME IN (roughly 7 lines)

초기 상태: Lane 0=3, Lane 1=1, Lane 2=7, Lane 3=2

1단계 (offset=2): 0 ↔ 2, 1 ↔ 3
  Lane 0: max(3, 7) = 7
  Lane 1: max(1, 2) = 2
  Lane 2: max(7, 3) = 7
  Lane 3: max(2, 1) = 2

2단계 (offset=1): 0 ↔ 1, 2 ↔ 3
  Lane 0: max(7, 2) = 7
  Lane 1: max(2, 7) = 7
  Lane 2: max(7, 2) = 7
  Lane 3: max(2, 7) = 7

결과: 모든 레인이 전역 최댓값 = 7을 가짐

버터플라이 병렬 최댓값 테스트:

pixi run p26 --parallel-max

pixi run -e amd p26 --parallel-max

uv run poe p26 --parallel-max

풀었을 때의 예상 출력:

WARP_SIZE:  32
SIZE:  32
output: [1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0]
expected: [1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0]
✅ Butterfly parallel max test passed!

솔루션

def butterfly_parallel_max[
    size: Int
](
    output: TileTensor[mut=True, dtype, LayoutType, MutAnyOrigin],
    input: TileTensor[mut=False, dtype, LayoutType, ImmutAnyOrigin],
):
    """
    Parallel maximum reduction using butterfly pattern.
    Uses shuffle_xor with decreasing offsets (16, 8, 4, 2, 1) to perform tree-based reduction.
    Each step reduces the active range by half until all threads have the maximum value.
    This implements an efficient O(log n) parallel reduction algorithm.
    """
    var global_i = block_dim.x * block_idx.x + thread_idx.x

    if global_i < size:
        var max_val = input[global_i]

        # Butterfly reduction tree: dynamic for any WARP_SIZE (32, 64, etc.)
        # Start with half the warp size and reduce by half each step
        var offset = WARP_SIZE // 2
        while offset > 0:
            max_val = max(max_val, shuffle_xor(max_val, UInt32(offset)))
            offset //= 2

        # All threads now have the maximum value across the entire warp
        output[global_i] = max_val

if global_i < size:
    max_val = input[global_i]  # 로컬 값으로 시작

    # 버터플라이 리덕션 트리: 모든 WARP_SIZE에 동적으로 대응
    offset = WARP_SIZE // 2
    while offset > 0:
        max_val = max(max_val, shuffle_xor(max_val, UInt32(offset)))
        offset //= 2

    output[global_i] = max_val  # 모든 레인이 전역 최댓값을 가짐

초기 상태:
  Lane 0: max_val = 0,    Lane 1: max_val = 2
  Lane 2: max_val = 4,    Lane 3: max_val = 6
  Lane 4: max_val = 8,    Lane 5: max_val = 10
  Lane 6: max_val = 12,   Lane 7: max_val = 1000

1단계: shuffle_xor(max_val, 4) - 절반 교환
  Lane 0↔4: max(0,8)=8,     Lane 1↔5: max(2,10)=10
  Lane 2↔6: max(4,12)=12,   Lane 3↔7: max(6,1000)=1000
  Lane 4↔0: max(8,0)=8,     Lane 5↔1: max(10,2)=10
  Lane 6↔2: max(12,4)=12,   Lane 7↔3: max(1000,6)=1000

2단계: shuffle_xor(max_val, 2) - 1/4 교환
  Lane 0↔2: max(8,12)=12,   Lane 1↔3: max(10,1000)=1000
  Lane 2↔0: max(12,8)=12,   Lane 3↔1: max(1000,10)=1000
  Lane 4↔6: max(8,12)=12,   Lane 5↔7: max(10,1000)=1000
  Lane 6↔4: max(12,8)=12,   Lane 7↔5: max(1000,10)=1000

3단계: shuffle_xor(max_val, 1) - 페어 교환
  Lane 0↔1: max(12,1000)=1000,  Lane 1↔0: max(1000,12)=1000
  Lane 2↔3: max(12,1000)=1000,  Lane 3↔2: max(1000,12)=1000
  Lane 4↔5: max(12,1000)=1000,  Lane 5↔4: max(1000,12)=1000
  Lane 6↔7: max(12,1000)=1000,  Lane 7↔6: max(1000,12)=1000

최종 결과: 모든 레인의 max_val = 1000

3. 버터플라이 조건부 최댓값

구성

• 벡터 크기: SIZE_2 = 64 (멀티 블록 시나리오)
• 그리드 구성: BLOCKS_PER_GRID_2 = (2, 1) 그리드당 블록 수
• 블록 구성: THREADS_PER_BLOCK_2 = (WARP_SIZE, 1) 블록당 스레드 수

완성할 코드

짝수 레인은 최댓값을, 홀수 레인은 최솟값을 저장하는 조건부 버터플라이 리덕션을 구현합니다.

수학적 연산: 최댓값과 최솟값 모두에 대해 버터플라이 리덕션을 수행한 후, 레인 홀짝에 따라 조건부로 출력합니다: \[\Large \text{output}[i] = \begin{cases} \max_{j=0}^{\text{WARP_SIZE}-1} \text{input}[j] & \text{if} i \bmod 2 = 0 \\ \min_{j=0}^{\text{WARP_SIZE}-1} \text{input}[j] & \text{if } i \bmod 2 = 1 \end{cases}\]

이중 리덕션 패턴: 버터플라이 트리를 통해 최댓값과 최솟값을 동시에 추적한 후, 레인 ID 홀짝에 따라 조건부로 출력합니다. 이는 버터플라이 패턴이 복잡한 다중 값 리덕션으로 어떻게 확장되는지를 보여줍니다.

def butterfly_conditional_max[
    size: Int
](
    output: TileTensor[mut=True, dtype, Layout2Type, MutAnyOrigin],
    input: TileTensor[mut=False, dtype, Layout2Type, ImmutAnyOrigin],
):
    """
    Conditional butterfly maximum: Perform butterfly max reduction, but only store result
    in even-numbered lanes. Odd-numbered lanes store the minimum value seen.
    Demonstrates conditional logic combined with butterfly communication patterns.
    """
    var global_i = block_dim.x * block_idx.x + thread_idx.x
    var lane = lane_id()

    if global_i < size:
        var current_val = input[global_i]
        var min_val = current_val

        # FILL ME IN (roughly 11 lines)

버터플라이 조건부 최댓값 테스트:

pixi run p26 --conditional-max

pixi run -e amd p26 --conditional-max

uv run poe p26 --conditional-max

풀었을 때의 예상 출력:

WARP_SIZE:  32
SIZE_2:  64
output: [9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0]
expected: [9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 9.0, 0.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0, 63.0, 32.0]
✅ Butterfly conditional max test passed!

솔루션

def butterfly_conditional_max[
    size: Int
](
    output: TileTensor[mut=True, dtype, Layout2Type, MutAnyOrigin],
    input: TileTensor[mut=False, dtype, Layout2Type, ImmutAnyOrigin],
):
    """
    Conditional butterfly maximum: Perform butterfly max reduction, but only store result
    in even-numbered lanes. Odd-numbered lanes store the minimum value seen.
    Demonstrates conditional logic combined with butterfly communication patterns.
    """
    var global_i = block_dim.x * block_idx.x + thread_idx.x
    var lane = lane_id()

    if global_i < size:
        var current_val = input[global_i]
        var min_val = current_val

        # Butterfly reduction for both maximum and minimum: dynamic for any WARP_SIZE
        var offset = WARP_SIZE // 2
        while offset > 0:
            var neighbor_val = shuffle_xor(current_val, UInt32(offset))
            current_val = max(current_val, neighbor_val)

            var min_neighbor_val = shuffle_xor(min_val, UInt32(offset))
            min_val = min(min_val, min_neighbor_val)

            offset //= 2

        # Conditional output: max for even lanes, min for odd lanes
        if lane % 2 == 0:
            output[global_i] = current_val  # Maximum
        else:
            output[global_i] = min_val  # Minimum

if global_i < size:
    current_val = input[global_i]
    min_val = current_val  # 최솟값을 별도로 추적

    # max와 min 동시 버터플라이 리덕션 (log_2(WARP_SIZE) 단계)
    offset = WARP_SIZE // 2
    while offset > 0:
        neighbor_val = shuffle_xor(current_val, UInt32(offset))
        current_val = max(current_val, neighbor_val)    # Max 리덕션

        min_neighbor_val = shuffle_xor(min_val, UInt32(offset))
        min_val = min(min_val, min_neighbor_val)        # Min 리덕션

        offset //= 2

    # 레인 홀짝에 따른 조건부 출력
    if lane % 2 == 0:
        output[global_i] = current_val  # 짝수 레인: 최댓값
    else:
        output[global_i] = min_val      # 홀수 레인: 최솟값

초기 상태:
  Lane 0: current_val=3, min_val=3
  Lane 1: current_val=1, min_val=1
  Lane 2: current_val=7, min_val=7
  Lane 3: current_val=2, min_val=2

1단계: shuffle_xor(current_val, 2)와 shuffle_xor(min_val, 2) - 절반 교환
  Lane 0↔2: max_neighbor=7, min_neighbor=7 → current_val=max(3,7)=7, min_val=min(3,7)=3
  Lane 1↔3: max_neighbor=2, min_neighbor=2 → current_val=max(1,2)=2, min_val=min(1,2)=1
  Lane 2↔0: max_neighbor=3, min_neighbor=3 → current_val=max(7,3)=7, min_val=min(7,3)=3
  Lane 3↔1: max_neighbor=1, min_neighbor=1 → current_val=max(2,1)=2, min_val=min(2,1)=1

2단계: shuffle_xor(current_val, 1)와 shuffle_xor(min_val, 1) - 페어 교환
  Lane 0↔1: max_neighbor=2, min_neighbor=1 → current_val=max(7,2)=7, min_val=min(3,1)=1
  Lane 1↔0: max_neighbor=7, min_neighbor=3 → current_val=max(2,7)=7, min_val=min(1,3)=1
  Lane 2↔3: max_neighbor=2, min_neighbor=1 → current_val=max(7,2)=7, min_val=min(3,1)=1
  Lane 3↔2: max_neighbor=7, min_neighbor=3 → current_val=max(2,7)=7, min_val=min(1,3)=1

최종 결과: 모든 레인이 current_val=7 (전역 max)과 min_val=1 (전역 min)을 가짐

offset = WARP_SIZE // 2
while offset > 0:
    neighbor_val = shuffle_xor(current_val, UInt32(offset))
    current_val = max(current_val, neighbor_val)

    min_neighbor_val = shuffle_xor(min_val, UInt32(offset))
    min_val = min(min_val, min_neighbor_val)

    offset //= 2

요약

shuffle_xor() 기본 요소는 효율적인 병렬 알고리즘의 기반이 되는 강력한 버터플라이 통신 패턴을 가능하게 합니다. 세 가지 문제를 통해 다음을 배웠습니다:

핵심 버터플라이 패턴

1. 페어 교환 (shuffle_xor(value, 1)):

   • 완벽한 인접 페어 생성: (0,1), (2,3), (4,5), …
   • 메모리 오버헤드 제로의 \(O(1)\) 복잡도
   • 정렬 네트워크와 데이터 재배치의 기반

2. 트리 리덕션 (동적 offset: WARP_SIZE/2 → 1):

   • 로그 병렬 리덕션: 순차의 \(O(n)\) 대비 \(O(\log n)\)
   • 모든 결합 연산에 적용 가능 (max, min, sum 등)
   • 모든 워프 레인에 걸쳐 최적의 부하 분산

3. 조건부 다중 리덕션 (이중 추적 + 레인 홀짝):

   • 여러 리덕션을 동시에 병렬 수행
   • 스레드 특성에 따른 조건부 출력
   • 명시적 동기화 없는 고급 조정

핵심 알고리즘 통찰

XOR 통신 특성:

• shuffle_xor(value, mask)가 대칭적이고 겹치지 않는 페어를 생성
• 각 마스크가 고유한 통신 토폴로지를 생성
• 이진 XOR 패턴에서 버터플라이 네트워크가 자연스럽게 도출

동적 알고리즘 설계:

offset = WARP_SIZE // 2
while offset > 0:
    neighbor_val = shuffle_xor(current_val, UInt32(offset))
    current_val = operation(current_val, neighbor_val)
    offset //= 2

성능 이점:

• 하드웨어 최적화: 레지스터 간 직접 통신
• 동기화 불필요: SIMT 실행이 정확성을 보장
• 확장 가능한 복잡도: 모든 WARP_SIZE (32, 64 등)에서 \(O(\log n)\)
• 메모리 효율성: 공유 메모리 불필요

실용적 활용

이 버터플라이 패턴들의 기반이 되는 분야:

• 병렬 리덕션: 합계, max, min, 논리 연산
• 누적 합/스캔 연산: 누적 합, 병렬 정렬
• FFT 알고리즘: 신호 처리와 합성곱
• Bitonic 정렬: 병렬 정렬 네트워크
• 그래프 알고리즘: 트리 순회와 연결성

shuffle_xor() 기본 요소는 복잡한 병렬 조정을 우아하고 하드웨어 최적화된 통신 패턴으로 변환하며, 다양한 GPU 아키텍처에서 효율적으로 확장됩니다.