Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Valid Count Generator

Intra-Slice Reduce 단계는 REDUCE_LABEL로 식별되는 축(예: R)을 해당 축의 Time 및 Packet 인수에 걸쳐 리덕션하며, Slice 인수는 출력에 남겨 둡니다. 이 축은 하드웨어 차원에 맞추기 위해 패딩이 필요한 경우가 많으며, 패딩으로 추가된 위치에는 리덕션에서 제외해야 하는 임의의 데이터가 들어 있습니다.

Valid Count Generator(VCG)가 이 문제를 해결합니다. 사용자는 매핑에서 R을 하위 표현식으로 나누어 Slice, Time, Packet 중 하나 이상에 걸쳐 배치합니다. 그런 다음 컴파일러는 VCG를 구성하여 8요소 플릿마다 그중 실제 데이터인 요소의 개수를 나타내는 valid_size 값을 태그로 붙입니다. Time 또는 Slice의 각 하위 표현식은 시간 필터에 할당된 Sequencer 카운터에 매핑됩니다. Packet에 있는 각 하위 표현식은 packet clipper를 구동합니다.

이 페이지 전체에서 대문자로 시작하는 Slice, Time, Packet은 매핑 차원을 가리키고, 소문자 slice와 time step은 런타임 인스턴스를 가리킵니다.

VCG가 동작하려면 매핑이 R을 특정한 형태로 표현해야 합니다. R은 하드웨어에 정렬된 크기로 패딩되며, 일반적으로 논의할 때는 R # PADDED_SIZE로 표기합니다. 구체적인 예시에서는 실제 패딩 값을 사용합니다(예: R # 16, R # 48). 그러면 각 하위 표현식은 R # PADDED_SIZE / n % m(스트라이드 n, 모듈로 m) 형태를 갖는 R # PADDED_SIZE의 인수가 됩니다. / n과 % m의 의미는 스트라이드와 모듈로를 참조하십시오. 각 하위 표현식은 하나의 하드웨어 차원에 할당됩니다. 가능한 분배 방식 중 하나는 R = 43을 R # 48로 패딩하여 세 차원 모두에 걸쳐 나누는 것입니다:

Slice:  R # 48 / 8       (stride 8, 6 positions)
Time:   R # 48 / 2 % 4   (stride 2, 4 positions)
Packet: R # 48 % 2       (stride 1, 2 positions)

아키텍처

VCG는 각 플릿에 valid_size(s, t) ∈ {0, 1, ..., 8}를 할당합니다. 여기서 s는 Slice ID(모든 Slice 하위 표현식에 걸친 플릿의 위치를 인코딩하는 정수)이고 t는 시간 단계입니다. 플릿의 처음 valid_size개 요소는 실제 데이터이고, 나머지는 패딩입니다.

struct VcgConfig {
    time_filters:   [TimeFilterConfig; 3], // for R's sub-expressions in Time and/or Slice
    packet_clipper: PacketClipperConfig,   // for R's sub-expressions in Packet
}

impl VcgConfig {
    fn valid_size(&self, s: u64, t: u64) -> u32 {
        if self.time_filters.iter().all(|tf| tf.valid(s, t)) {
            self.packet_clipper.valid_size(t)
        } else {
            0
        }
    }
}

모든 타이머가 플릿 (s, t)에 대해 유효를 보고하면 packet clipper가 해당 플릿의 요소 중 몇 개가 실제 데이터인지 결정합니다. 어느 타이머라도 무효를 보고하면 packet clipper의 판단과 관계없이 플릿의 모든 요소가 제외됩니다. 두 구성 요소인 TimeFilterConfig와 PacketClipperConfig는 아래 절에서 설명합니다.

시간 필터

각 Slice s에 대해 시간 필터는 각 시간 단계 t가 유효한 R 데이터를 담고 있는지 판단합니다. 아래 하위 절에서는 가장 단순한 경우부터 시작하여 복잡도를 더해 가며 fn valid()를 단계적으로 구성합니다. R에 Time이나 Slice의 하위 표현식이 없으면 slice_mask = 0과 slice_thres = 1로 설정하여 시간 필터를 비활성화합니다. 그러면 모든 s에 대해 s & 0 = 0 < 1이 성립하여 Less 분기에 해당하므로 fn valid()는 항상 true를 반환합니다. slice_thres = 1로 정하는 것은 관례일 뿐이며, 0은 항상 양수보다 작으므로 어떤 양수 값을 사용해도 됩니다.

struct TimeFilterConfig {
    // How R's index is reconstructed from t.
    sequencer: Sequencer,

    // Slice classification (see `R in Slice and Time`, `R in Time and Slice`).
    slice_mask:  u32,
    slice_thres: u32,
    time_thres:  u32,
    mode:        TimeFilterMode, // SliceMajor | TimeMajor
}

impl TimeFilterConfig {
    /// Returns true if flit (s, t) carries valid R data.
    fn valid(&self, s: u64, t: u64) -> bool {
        let idx = self.sequencer.index(t);
        match ((s & self.slice_mask).cmp(&self.slice_thres), self.mode) {
            (Less,    _)          => true,
            (Greater, SliceMajor) => false,
            _                     => idx < self.time_thres as u64,
        }
    }
}

Time으로서의 R

가장 단순한 경우에는 R이 다른 축 없이 Time 전체를 차지합니다. 각 시간 단계 t는 하나의 R 인덱스에 직접 대응하며, t < R::SIZE일 때 유효합니다.

// The compiler emits roughly:
TimeFilterConfig {
    sequencer:   [R # PADDED_SIZE -> size PADDED_SIZE : stride 1],  // idx = t
    slice_mask:  0,           // no slice partitioning
    slice_thres: 0,           // 0 cmp 0 = Equal -> falls to `idx < time_thres`
    time_thres:  R::SIZE,     // valid when idx < R::SIZE
    mode:        SliceMajor,  // arbitrary; only the Equal arm is hit
}
#![allow(unused)]
fn main() {
#![feature(adt_const_params)]
extern crate furiosa_opt_std;
use furiosa_opt_std::prelude::*;
axes![A = 8, R = 12, X = 128];

fn reduce_time_only<'l, const T: Tu>(
    input: VectorBranchTensor<'l, T, i32, m![1], m![1 # 2], m![X, A / 4], m![R # 16], m![A % 4 # 8], Fresh, { stage::VeOrder::IntraFirst }>,
) -> VectorIntraSliceReduceTensor<'l, T, i32, m![1], m![1 # 2], m![X, A / 4], m![1], m![A % 4], Fresh, { stage::VeOrder::IntraFirst }>
{
    input
        .vector_narrow_trim::<m![A % 4]>()
        //   Slice     = m![X, A / 4]
        //   Time      = m![R # 16]     (steps < R::SIZE valid)
        //   Packet    = m![A % 4]
        //   OutTime   = m![1]          (R eliminated from Time)
        //   OutPacket = m![A % 4]
        .vector_intra_slice_reduce::<R, m![1], m![A % 4]>(
            IntraSliceReduceOpI32::AddSat,
        )
}

let mut device = Device::new(Topology { chips: 1, pes: 8 }).unwrap();

let i: VectorBranchTensor<'_, _, i32, m![1], m![1 # 2], m![X, A / 4], m![R # 16], m![A % 4 # 8], Fresh, { stage::VeOrder::IntraFirst }> = VectorBranchTensor::new(&mut device.main, Tensor::zero(), TagMode::Zero);
let _o = reduce_time_only(i);
}

위 예제에서 Sequencer는 size 16 : stride 1로 R # 16을 한 번 순회하므로, 모든 시간 단계에서 idx = t입니다. time_thres = R::SIZE = 12이므로 처음 12개의 시간 단계(t = 0..11)는 유효하고, 나머지 4개(t = 12..15)는 걸러집니다. 이어서 Intra-Slice Reduce는 Slice마다 실제 R 요소 12개만 정확히 접습니다.

Time의 R

VCG는 R이 다른 축과 공간을 공유하면서 여러 하위 표현식으로 임의의 순서로 나타나는 Time 매핑을 지원합니다. 시간 필터는 Sequencer를 사용해 t를 하위 표현식별 카운터로 분해합니다. R에 할당된 카운터에 대해 value × stride를 합산하면 idx가 되며, 이 값은 해당 시간 단계에서의 R 인덱스를 나타냅니다.

다음 예제는 R = 10을 R # 12로 패딩하여 사용하며, Time에서 A가 R의 두 하위 표현식 사이에 위치합니다.

#![allow(unused)]
fn main() {
#![feature(adt_const_params)]
extern crate furiosa_opt_std;
use furiosa_opt_std::prelude::*;
axes![A = 3, B = 4, R = 10, X = 64];

// R = 10, padded to R # 12, split as (size 3, stride 4) × (size 4, stride 1).
// time filter sums (R # 12 / 4 value) * 4 + (R # 12 % 4 value) * 1 to recover R index regardless of A.
fn reduce_time_reordered<'l, const T: Tu>(
    input: VectorBranchTensor<'l, T, i32, m![1], m![1 # 2], m![X # 256], m![R # 12 / 4, A, R # 12 % 4], m![B # 8], Fresh, { stage::VeOrder::IntraFirst }>,
) -> VectorIntraSliceReduceTensor<'l, T, i32, m![1], m![1 # 2], m![X # 256], m![A], m![B], Fresh, { stage::VeOrder::IntraFirst }>
{
    input
        .vector_narrow_trim::<m![B]>()
        //   Slice     = m![X # 256]
        //   Time      = m![R # 12 / 4, A, R # 12 % 4]
        //   Packet    = m![B]
        //   OutTime   = m![A]    (R eliminated; A survives)
        //   OutPacket = m![B]
        .vector_intra_slice_reduce::<R, m![A], m![B]>(
            IntraSliceReduceOpI32::AddSat,
        )
}

let mut device = Device::new(Topology { chips: 1, pes: 8 }).unwrap();

let i: VectorBranchTensor<'_, _, i32, m![1], m![1 # 2], m![X # 256], m![R # 12 / 4, A, R # 12 % 4], m![B # 8], Fresh, { stage::VeOrder::IntraFirst }> = VectorBranchTensor::new(&mut device.main, Tensor::zero(), TagMode::Zero);
let _o = reduce_time_reordered(i);
}

컴파일러는 이 배치에 대해 시간 필터를 다음과 같이 구성합니다.

TimeFilterConfig {
    sequencer:   [R # 12 / 4 -> size 3 : stride 4,   // assigned to time filter
                  A          -> size 3 : stride 0,   // not assigned (A's OutTime)
                  R # 12 % 4 -> size 4 : stride 1],  // assigned to time filter
    slice_mask:  0,           // no slice partitioning (R is only in Time)
    slice_thres: 0,           // every slice falls to the `idx < time_thres` arm
    time_thres:  R::SIZE,     // 10
    mode:        SliceMajor,  // arbitrary; only the Equal arm is hit
}

A 항목은 스트라이드가 0이므로 idx에 전혀 기여하지 않으며, 따라서 Time에서 A의 위치는 유효성에 아무런 영향을 주지 않습니다. 나머지 두 항목은 R을 (R # 12 / 4 value) × 4 + (R # 12 % 4 value)로 재구성합니다.

예를 들면 다음과 같습니다.

  • t = 13에서 Sequencer 상태는 (R # 12 / 4, A, R # 12 % 4) = (1, 0, 1)이므로 idx = 1 × 4 + 0 + 1 × 1 = 5가 됩니다. idx < 10이므로 유효합니다.
  • t = 27에서 Sequencer 상태는 (2, 0, 3)이므로 idx = 2 × 4 + 0 + 3 × 1 = 11이 됩니다. idx ≥ 10이므로 유효하지 않습니다(패딩된 두 R 위치 중 하나입니다).

Slice와 Time의 R

SliceMajor 모드에서는 Slice와 Time 모두에 여러 R 하위 표현식을 둘 수 있으며, 이때 Slice 하위 표현식이 Time 하위 표현식보다 더 상위(더 큰 스트라이드)입니다. Slice 안에서 하위 표현식은 스트라이드 내림차순(major가 minor보다 먼저)으로 나타나야 합니다. 또한 각 하위 표현식의 비트가 slice_mask의 연속 구간을 차지하도록, 각 하위 표현식의 크기와 스트라이드는 모두 2의 거듭제곱이어야 합니다. Time 안에서는 하위 표현식이 임의의 순서로 나타날 수 있습니다.

#![allow(unused)]
fn main() {
#![feature(adt_const_params)]
extern crate furiosa_opt_std;
use furiosa_opt_std::prelude::*;
axes![R = 11, X = 64];

fn reduce_slice_time_slicemajor<'l, const T: Tu>(
    input: VectorBranchTensor<'l, T, i32, m![1], m![1 # 2], m![R # 16 / 8, X, R # 16 / 4 % 2], m![R # 16 % 2, R # 16 / 2 % 2], m![1 # 8], Fresh, { stage::VeOrder::IntraFirst }>,
) -> VectorIntraSliceReduceTensor<'l, T, i32, m![1], m![1 # 2], m![R # 16 / 8, X, R # 16 / 4 % 2], m![1], m![1 # 4], Fresh, { stage::VeOrder::IntraFirst }>
{
    input
        .vector_narrow_trim::<m![1 # 4]>()
        //   Slice     = m![R # 16 / 8, X, R # 16 / 4 % 2]   (major R sub-exprs, descending R-stride order required)
        //   Time      = m![R # 16 % 2, R # 16 / 2 % 2]      (minor R sub-exprs, any order OK)
        //   Packet    = m![1 # 4]
        //   OutTime   = m![1]          (R eliminated)
        //   OutPacket = m![1 # 4]
        .vector_intra_slice_reduce::<R, m![1], m![1 # 4]>(
            IntraSliceReduceOpI32::Min,
        )
}

let mut device = Device::new(Topology { chips: 1, pes: 8 }).unwrap();

let i: VectorBranchTensor<'_, _, i32, m![1], m![1 # 2], m![R # 16 / 8, X, R # 16 / 4 % 2], m![R # 16 % 2, R # 16 / 2 % 2], m![1 # 8], Fresh, { stage::VeOrder::IntraFirst }> = VectorBranchTensor::new(&mut device.main, Tensor::zero(), TagMode::Zero);
let _o = reduce_slice_time_slicemajor(i);
}

이 예제는 R = 11(R # 16으로 패딩)을 다음 하위 표현식으로 Slice와 Time에 걸쳐 배치합니다.

차원하위 표현식스트라이드
SliceR # 16 / 88
SliceR # 16 / 4 % 24
TimeR # 16 % 21
TimeR # 16 / 2 % 22

이 예제는 4개의 Slice 그룹(Slice에서 오는 R 기여분 0, 4, 8, 12마다 하나씩)으로 나뉘며, Slice마다 4번의 시간 반복을 수행합니다. 레이아웃은 세 가지 영역으로 구성됩니다. 2개의 Slice는 완전히 유효하고, 1개의 Slice는 부분적으로 유효하며, 1개의 Slice는 완전히 유효하지 않습니다.

Slice에서 오는 R 기여분반복에 따른 R 값유효한 시간 단계
00, 2, 1, 34 (모두 < R::SIZE)
44, 6, 5, 74 (모두 < R::SIZE)
88, 10, 9, 113 (R = 11은 유효하지 않음)
1212, 14, 13, 150 (모두 ≥ R::SIZE)

컴파일러는 아래와 같은 시간 필터 설정을 생성합니다.

TimeFilterConfig {
    sequencer:   [R # 16 % 2     -> size 2 : stride 1,
                  R # 16 / 2 % 2 -> size 2 : stride 2],
    slice_mask:  0b1000001,  // bits 0 (R # 16 / 4 % 2) and 6 (R # 16 / 8) carry the R contribution
    slice_thres: 64,         // masked id encoding the boundary R contribution (= 8)
    time_thres:  3,          // = R::SIZE - boundary = 11 - 8
    mode:        SliceMajor,
}

각 필드는 유효성 판정의 한 부분을 인코딩합니다:

  • sequencer는 각 Time 하위 표현식을 해당 R 스트라이드와 함께 기록합니다. 따라서 재구성된 idx는 각 시간 단계 t에서 Time이 R 인덱스에 기여하는 값과 같습니다. 이 예제에서 t가 [0, 4) 범위를 도는 동안 idx는 {0, 1, 2, 3} 중 하나의 값을 가집니다.
  • slice_mask는 Slice id에서 Slice에서 오는 R 기여분을 담는 비트들을 추출합니다. 이 예제에서 비트 0은 R # 16 / 4 % 2를, 비트 6은 R # 16 / 8을 담으므로 slice_mask = 0b1000001입니다.
  • slice_thres는 부분 Slice의 R 기여분을 인코딩하는, slice_mask 내의 비트 패턴입니다. 위 표에서 부분 Slice의 R 기여분은 8이며, 이는 비트 6을 설정하고(R # 16 / 8 = 1) 비트 0을 해제하여(R # 16 / 4 % 2 = 0) 인코딩됩니다. 따라서 slice_thres = 64입니다.
  • time_thres는 R::SIZE에서 부분 Slice의 R 기여분을 뺀 값입니다. 이 예제에서는 time_thres = 11 - 8 = 3입니다.

fn valid는 모든 플릿에 대해 올바른 유효성을 반환합니다. 이를 검증하려면 R 인덱스를 r = r_slice + idx로 분해한 뒤 Slice 비교의 세 가지 경우를 살펴보십시오. 여기서 r_slice는 Slice에서 오는 R 기여분(s & slice_mask로 인코딩됨)이고 idx는 Time에서 오는 기여분입니다.

  • (s & slice_mask) < slice_thres이면 모든 시간 단계가 유효합니다. r_slice가 부분 Slice의 기여분보다 Slice 간격 하나 이상 작으므로, 모든 idx에 대해 r = r_slice + idx < R::SIZE가 성립하기 때문입니다.
  • (s & slice_mask) = slice_thres일 때, 시간 단계는 idx < time_thres인 경우에만 유효합니다. 이것이 부분 Slice이며, time_thres의 정의에 따라 이 Slice의 r_slice = R::SIZE - time_thres입니다. 따라서 r = r_slice + idx < R::SIZE는 정확히 idx < time_thres일 때 성립합니다.
  • (s & slice_mask) > slice_thres일 때는 유효한 시간 단계가 없습니다. r_slice가 부분 Slice의 기여분보다 최소 Slice 간격 하나만큼 크므로 r_slice ≥ R::SIZE이기 때문입니다.

Time과 Slice에 걸친 R

TimeMajor 모드는 SliceMajor의 쌍대(dual)입니다. major/minor 역할이 뒤바뀌므로 Time 하위 표현식이 더 큰 스트라이드를, Slice 하위 표현식이 더 작은 스트라이드를 가집니다. Slice 내부 및 Time 내부의 순서 규칙과 Slice 하위 표현식의 크기/스트라이드가 2의 거듭제곱이어야 한다는 요구 사항은 SliceMajor에서 그대로 이어집니다.

TimeMajor는 이렇게 이어받은 규칙에 제약 조건 하나를 추가합니다. PADDED_SIZE는 slice_span × time_span으로 분해된다는 점을 상기하십시오. 여기서 slice_span과 time_span은 각각 Slice와 Time에 있는 R의 하위 표현식 크기들의 곱입니다. TimeMajor는 PADDED_SIZE - R::SIZE ≤ slice_span을 요구하며, 이는 초과 패딩될 수 있는 R 위치가 최대 slice_span개라는 뜻입니다. 이 제약 조건은 필수적이며, 이를 위반하는 배치는 VCG에서 지원되지 않습니다(Time과 Slice에 걸친 R 참조).

#![allow(unused)]
fn main() {
#![feature(adt_const_params)]
extern crate furiosa_opt_std;
use furiosa_opt_std::prelude::*;
axes![R = 13, X = 64];

fn reduce_time_slice_timemajor<'l, const T: Tu>(
    input: VectorBranchTensor<'l, T, i32, m![1], m![1 # 2], m![R # 16 / 2 % 2, X, R # 16 % 2], m![R # 16 / 4 % 2, R # 16 / 8], m![1 # 8], Fresh, { stage::VeOrder::IntraFirst }>,
) -> VectorIntraSliceReduceTensor<'l, T, i32, m![1], m![1 # 2], m![R # 16 / 2 % 2, X, R # 16 % 2], m![1], m![1 # 4], Fresh, { stage::VeOrder::IntraFirst }>
{
    input
        .vector_narrow_trim::<m![1 # 4]>()
        //   Slice     = m![R # 16 / 2 % 2, X, R # 16 % 2]
        //   Time      = m![R # 16 / 4 % 2, R # 16 / 8]
        //   Packet    = m![1 # 4]
        //   OutTime   = m![1]          (R eliminated)
        //   OutPacket = m![1 # 4]
        .vector_intra_slice_reduce::<R, m![1], m![1 # 4]>(
            IntraSliceReduceOpI32::AddSat,
        )
}

let mut device = Device::new(Topology { chips: 1, pes: 8 }).unwrap();

let i: VectorBranchTensor<'_, _, i32, m![1], m![1 # 2], m![R # 16 / 2 % 2, X, R # 16 % 2], m![R # 16 / 4 % 2, R # 16 / 8], m![1 # 8], Fresh, { stage::VeOrder::IntraFirst }> = VectorBranchTensor::new(&mut device.main, Tensor::zero(), TagMode::Zero);
let _o = reduce_time_slice_timemajor(i);
}

이 예제는 R = 13(R # 16으로 패딩됨)을 다음 하위 표현식으로 Slice와 Time에 걸쳐 배치합니다.

차원하위 표현식스트라이드
TimeR # 16 / 4 % 24
TimeR # 16 / 88
SliceR # 16 / 2 % 22
SliceR # 16 % 21

이 하위 표현식들로부터 slice_span = 4, time_span = 4, 초과 패딩 PADDED_SIZE - R::SIZE = 3을 얻으며, 이는 제약 조건 3 ≤ 4를 만족합니다. Slice로부터의 R 기여분(0, 1, 2 또는 3)으로 구분되는 4개의 Slice는 각각 4번의 시간 반복에 걸쳐 4개의 R 값을 순회합니다. 이 레이아웃에는 두 가지 경우가 있습니다. 1개의 Slice는 완전히 유효하고, 3개는 부분적입니다(각각 반복 하나씩을 잃습니다).

Slice로부터의 R 기여분반복에 걸친 R 값유효한 시간 단계
00, 8, 4, 124개(모두 < R::SIZE)
11, 9, 5, 133개(R = 13은 무효)
22, 10, 6, 143개(R = 14는 무효)
33, 11, 7, 153개(R = 15는 무효)

컴파일러는 아래와 같은 시간 필터 설정을 생성합니다.

TimeFilterConfig {
    sequencer:   [R # 16 / 4 % 2 -> size 2 : stride 1,    // 1 = 4 / slice_span
                  R # 16 / 8     -> size 2 : stride 2],   // 2 = 8 / slice_span
    slice_mask:  0b1000001,  // bits 0 (R # 16 % 2) and 6 (R # 16 / 2 % 2) carry the R contribution
    slice_thres: 1,          // masked id encoding r_slice = 1
    time_thres:  3,          // = time_span - 1 (partial slices drop the over-padded last iteration)
    mode:        TimeMajor,
}

이 설정은 세 필드에서 SliceMajor와 다릅니다(slice_mask는 같은 패턴을 따릅니다):

  • sequencer: 모든 Time 하위 표현식의 스트라이드를 먼저 slice_span으로 나눕니다. 이 예에서는 스트라이드 4와 8이 1과 2가 됩니다.
  • slice_thres: 부분 Slice의 r_slice = slice_span - (PADDED_SIZE - R::SIZE)를 인코딩합니다. 이 예시에서 목표 값은 4 - 3 = 1이며, 비트 0을 설정하고(R # 16 % 2 = 1) 비트 6을 해제하여(R # 16 / 2 % 2 = 0) 인코딩하므로 slice_thres = 1이 됩니다.
  • time_thres: 항상 time_span - 1입니다. 이 예시에서는 time_thres = 3입니다.

fn valid는 모든 플릿에 대해 올바른 유효성을 반환합니다. 이를 검증하려면 R 인덱스를 r = idx * slice_span + r_slice로 분해하고(여기서 r_slice는 s & slice_mask에서 디코딩한 해당 Slice의 R 기여분입니다), Slice 비교의 두 경우를 살펴보십시오.

  • (s & slice_mask) < slice_thres이면 모든 시간 단계가 유효합니다. r_slice < slice_span - (PADDED_SIZE - R::SIZE)이므로 모든 idx에 대해 r ≤ (time_span - 1) * slice_span + r_slice < R::SIZE입니다.
  • (s & slice_mask) ≥ slice_thres이면 시간 단계는 idx < time_thres = time_span - 1일 때에만 유효합니다. 이때 해당 Slice의 r_slice ≥ slice_span - (PADDED_SIZE - R::SIZE)입니다. idx ≤ time_span - 2이면 r ≤ (time_span - 2) * slice_span + (slice_span - 1) < (time_span - 1) * slice_span ≤ R::SIZE입니다. idx = time_span - 1이면 r ≥ (time_span - 1) * slice_span + slice_span - (PADDED_SIZE - R::SIZE) = R::SIZE입니다.

SliceMajor와 달리 TimeMajor에는 “모두 무효“인 경우가 없습니다. 패딩 제약 조건 PADDED_SIZE - R::SIZE ≤ slice_span이 과잉 패딩을 충분히 엄격하게 제한하므로 완전히 무효가 되는 Slice는 없습니다.

Packet Clipper

packet clipper는 각 플릿에 대해 valid_size(t)를 계산합니다. 이 값은 Slice s가 아닌 t에만 의존하므로, 같은 시간 단계에서는 모든 Slice가 같은 개수를 받습니다. Slice와 무관한 이 성질 때문에 VCG가 표현할 수 있는 배치가 제한됩니다. 아래 하위 절에서는 fn valid_size()를 단계별로 구성합니다. R에 Packet의 하위 표현식이 없으면 빈 Sequencer와 함께 axis_size = packet_span = 8로 설정하여 packet clipper를 비활성화합니다. 이렇게 하면 fn valid_size()가 항상 8(전체 플릿)을 반환합니다.

struct PacketClipperConfig {
    sequencer:   Sequencer,
    axis_size:   u32, // R::SIZE
    packet_span: u32, // R positions per flit
}

impl PacketClipperConfig {
    /// Returns the valid element count for the flit at time step t.
    fn valid_size(&self, t: u64) -> u32 {
        let idx = self.sequencer.index(t);
        (self.axis_size - idx).clamp(0, self.packet_span)
    }
}

packet clipper에는 Packet = m![R # PADDED_SIZE % packet_span # 8] 형식이 필요합니다. 다른 축이 R과 함께 Packet을 공유하거나 R이 Packet 안에서 여러 하위 표현식으로 나뉘면, fn valid_size()가 의존하는 연속 접두사 성질이 깨집니다(표현할 수 없는 패턴 참조).

Packet으로서의 R

가장 단순한 경우에는 R이 단일 플릿에 들어가므로(R::SIZE ≤ 8), 시간 단계나 Slice와 관계없이 모든 플릿이 같은 valid_size = R::SIZE를 가집니다.

#![allow(unused)]
fn main() {
#![feature(adt_const_params)]
extern crate furiosa_opt_std;
use furiosa_opt_std::prelude::*;
axes![A = 8, R = 3, X = 64];

fn reduce_packet_only<'l, const T: Tu>(
    input: VectorBranchTensor<'l, T, f32, m![1], m![1 # 2], m![X, A / 2], m![1], m![R # 8], Fresh, { stage::VeOrder::IntraFirst }>,
) -> VectorIntraSliceReduceTensor<'l, T, f32, m![1], m![1 # 2], m![X, A / 2], m![1], m![1 # 4], Fresh, { stage::VeOrder::IntraFirst }>
{
    input
        .vector_narrow_trim::<m![R # 4]>()
        //   Slice     = m![X, A / 2]
        //   Time      = m![1]
        //   Packet    = m![R # 4]
        //   OutTime   = m![1]
        //   OutPacket = m![1 # 4]  (R eliminated from Packet)
        .vector_intra_slice_reduce::<R, m![1], m![1 # 4]>(
            IntraSliceReduceOpF32::Add,
        )
}

let mut device = Device::new(Topology { chips: 1, pes: 8 }).unwrap();

let i: VectorBranchTensor<'_, _, f32, m![1], m![1 # 2], m![X, A / 2], m![1], m![R # 8], Fresh, { stage::VeOrder::IntraFirst }> = VectorBranchTensor::new(&mut device.main, Tensor::zero(), TagMode::Zero);
let _o = reduce_packet_only(i);
}

위 예제는 R = 3(R # 8로 패딩)을 단일 하위 표현식으로 Packet에 모두 배치합니다. 컴파일러는 packet clipper를 다음과 같이 구성합니다:

PacketClipperConfig {
    sequencer:   [],   // empty: a single flit holds all of R
    axis_size:   3,    // R::SIZE
    packet_span: 8,    // R fits in 8 flit positions
}

모든 플릿의 valid_size = clamp(3 - 0, 0, 8) = 3입니다(시간 단계와 Slice에 관계없이 일정).

Time과 Packet에 걸친 R

VCG는 Time과 Packet 양쪽에 하위 표현식이 있는 R을 지원합니다.

#![allow(unused)]
fn main() {
#![feature(adt_const_params)]
extern crate furiosa_opt_std;
use furiosa_opt_std::prelude::*;
axes![A = 8, R = 10, X = 64];

fn reduce_time_packet<'l, const T: Tu>(
    input: VectorBranchTensor<'l, T, f32, m![1], m![1 # 2], m![X, A / 2], m![R # 16 / 4], m![R # 16 % 4 # 8], Fresh, { stage::VeOrder::IntraFirst }>,
) -> VectorIntraSliceReduceTensor<'l, T, f32, m![1], m![1 # 2], m![X, A / 2], m![1], m![1 # 4], Fresh, { stage::VeOrder::IntraFirst }>
{
    input
        .vector_narrow_trim::<m![R # 16 % 4]>()
        //   Slice     = m![X, A / 2]
        //   Time      = m![R # 16 / 4]
        //   Packet    = m![R # 16 % 4 # 8]
        //   OutTime   = m![1]          (R eliminated)
        //   OutPacket = m![1 # 4]
        .vector_intra_slice_reduce::<R, m![1], m![1 # 4]>(
            IntraSliceReduceOpF32::Add,
        )
}

let mut device = Device::new(Topology { chips: 1, pes: 8 }).unwrap();

let i: VectorBranchTensor<'_, _, f32, m![1], m![1 # 2], m![X, A / 2], m![R # 16 / 4], m![R # 16 % 4 # 8], Fresh, { stage::VeOrder::IntraFirst }> = VectorBranchTensor::new(&mut device.main, Tensor::zero(), TagMode::Zero);
let _o = reduce_time_packet(i);
}

위 예제는 R = 10(R # 16으로 패딩)을 Time과 Packet에 걸쳐 배치합니다.

차원하위 표현식스트라이드
TimeR # 16 / 44
PacketR # 16 % 4 # 81

컴파일러는 packet clipper를 다음과 같이 구성합니다:

PacketClipperConfig {
    sequencer:   [R # 16 / 4 -> size 4 : stride 4],
    axis_size:   10,   // R::SIZE
    packet_span: 4,    // 4 R positions per flit (the trailing 4 flit positions are always padding)
}

이 구성에서 Sequencer는 R 인덱스에 대한 Time의 기여분인 idx(t)를 재구성합니다(Time에 있는 R 참조). axis_size = 10개 요소 중 idx(t)개를 Time이 담당하고 나면 axis_size - idx(t)개가 남습니다. packet clipper는 남은 요소를 플릿에 최대한 많이 담되, 그 수는 최대 packet_span = 4개로 제한됩니다. 따라서 fn valid_size(t) = clamp(10 - idx(t), 0, 4)입니다. 뒤쪽 4개의 플릿 위치는 항상 패딩이며, R::SIZE가 packet_span의 배수가 아니면 마지막 플릿은 일부 개수만 담습니다:

  flit 0: idx =  0  →  clamp(10 -  0, 0, 4) = 4  [████    ]
  flit 1: idx =  4  →  clamp(10 -  4, 0, 4) = 4  [████    ]
  flit 2: idx =  8  →  clamp(10 -  8, 0, 4) = 2  [██      ]
  flit 3: idx = 12  →  clamp(10 - 12, 0, 4) = 0  [        ]

종합하기

앞 절에서는 하나 또는 두 차원에 배치된 단일 R 하위 표현식을 다루었습니다. 실제로 Intra-Slice Reduce는 단일 REDUCE_LABEL(R)과 함께 패딩된 리덕션 외 축을 추가로 받으며, VCG는 이 축을 모두 추적합니다. 패딩된 각 축(R이든 다른 축이든)은 시간 필터 슬롯 하나를 차지하고, R의 Packet 부분은 packet clipper를 차지합니다. 이 예제는 축 하나에서 시작해 세 개까지 확장하므로 각 차원의 기여분을 명확히 알 수 있습니다.

원래 형태는 [H, C, W] = [5, 5, 19]입니다. 각 축은 배치 방식에 따라 slice/시간/패킷 부분으로 분할됩니다:

축패딩Slice시간패킷
H# 8H # 8 / 2 (크기 4)H # 8 % 2 (크기 2)-
C# 8C # 8 / 2 (크기 4)C # 8 % 2 (크기 2)-
W# 24-W # 24 / 8 (크기 3)W # 24 % 8 (크기 8)

이후 단계에서는 간결하게 Ho/Co/Wo와 Hi/Ci/Wi를 약칭으로 사용합니다. *o는 표의 행에서 가장 왼쪽 인자(H/C는 slice, W는 시간)이고, *i는 그 바로 오른쪽 인자입니다.

1단계: W=19만 사용(packet clipper만 사용, 시간 필터 없음)

지금은 H와 C를 무시합니다. 시간 필터 0과 1을 비활성화합니다(slice_mask=0, slice_thres=1). 모든 Slice가 3개의 플릿(Wo 크기 3)을 처리하며, packet clipper는 다음과 같은 톱니 모양 패턴을 생성합니다:

valid_size: 8, 8, 3
              ^     ^
            full   19 - 16 = 3 (partial)

시간 필터가 없으므로 모든 Slice는 이와 정확히 같은 패턴을 받습니다:

All slices, all flits:
flit 0: ████████  (valid_size=8)
flit 1: ████████  (valid_size=8)
flit 2: ███       (valid_size=3)

2단계: C=5 추가(packet clipper + 시간 필터 0)

이제 C 축 타이머(시간 필터 0)를 활성화합니다. C=5는 Co(slice, 크기 4) × Ci(시간, 크기 2)로 분할됩니다. C 시간 필터 설정은 slice_mask=0b0011(slice_id에서 Co를 추출), slice_thres=2, time_thres=1, SliceMajor입니다.

이제 각 Slice는 6개의 플릿을 실행합니다: Ci 크기 2 × Wo 크기 3. C 시간 필터는 Slice를 Co 값에 따라 분류합니다:

Co그룹효과
0미만(< 2)6개 플릿 모두 packet clipper의 패턴을 통과합니다
1미만(< 2)동일합니다
2경계(= 2)Ci=0에서는 유효하고, Ci=1에서는 유효하지 않습니다
3초과(> 2)6개 플릿 모두 valid_size = 0입니다

Slice별 결과(6개 플릿 = Ci 크기 2 × Wo 크기 3):

Co=0:  [8,8,3, 8,8,3]   (both Ci steps valid)
Co=1:  [8,8,3, 8,8,3]   (same)
Co=2:  [8,8,3, 0,0,0]   (Ci=0 valid, Ci=1 invalid)
Co=3:  [0,0,0, 0,0,0]   (all invalid)

타이머의 효과에 주목하십시오. 일부 Slice는 전부 0이 되고, 경계 Slice는 후반부를 잃습니다. 하지만 유효한 플릿 안에서는 packet clipper가 만든 [8,8,3] 패턴이 그대로 유지됩니다.

3단계: H=5 추가(packet clipper + 시간 필터 0 + 시간 필터 1)

이제 H 축 타이머(시간 필터 1)를 활성화합니다. H=5는 Ho(slice, 크기 4) × Hi(시간, 크기 2)로 분할됩니다. H 시간 필터 설정은 다음과 같습니다: slice_mask=0b1100(slice_id에서 Ho를 추출), slice_thres=0b1000, time_thres=1, SliceMajor.

slice id는 두 slice 인자를 slice_id = Ho * 4 + Co로 인코딩하므로 Slice는 16개가 됩니다. 이제 각 Slice는 12개의 플릿을 실행합니다: Hi 크기 2 × Ci 크기 2 × Wo 크기 3.

구성 요소축추적 대상설정
packet clipperW=19플릿별 R 개수axis_size=19, packet_span=8, sequencer = [Wo -> size 3 : stride 8]
시간 필터 0C=5Slice별 Co 유효성slice_mask=0b0011, slice_thres=2, time_thres=1, SliceMajor
시간 필터 1H=5Slice별 Ho 유효성slice_mask=0b1100, slice_thres=0b1000, time_thres=1, SliceMajor

H 시간 필터는 C 시간 필터가 Co로 Slice를 분류하는 것과 같은 로직으로 Ho에 따라 Slice를 분류합니다.

Ho그룹효과
0미만열림
1미만열림
2경계Hi=0이면 열림, Hi=1이면 닫힘
3초과닫힘

최종 valid_size는 두 시간 필터가 모두 true를 반환하면 packet clipper의 개수가 되고, 어느 하나라도 false를 반환하면 0이 됩니다.

아래의 전체 히트맵은 16개 Slice(열, Ho별로 묶음) × 12개 플릿(행, (Hi, Ci)별로 묶음)으로 구성됩니다. 오른쪽 주석(H:, C:)은 각 행에서 어떤 타이머가 활성 상태인지 나타냅니다. v = 유효, > = 경계, x = 무효입니다. 먼저 이 주석을 훑어보고 어떤 행 × 열 블록이 전부 0이어야 하는지(타이머 중 하나라도 x), 어떤 블록에 데이터가 있어야 하는지 예측하십시오. 그런 다음 셀을 읽어 [8, 8, 3] 패킷 차원의 톱니 패턴을 확인하십시오.

                     Ho=0       |Ho=1       |Ho=2       |Ho=3
                Co:  0  1  2  3 | 0  1  2  3| 0  1  2  3| 0  1  2  3
     H time filter: v  v  v  v  | v  v  v  v| >  >  >  >| x  x  x  x
     C time filter: v  v  >  x  | v  v  >  x| v  v  >  x| v  v  >  x
--------------------------------------------------------------------------------
 t= 0  Hi=0,Ci=0  W  8  8  8  0 | 8  8  8  0| 8  8  8  0| 0  0  0  0  H:v C:v
 t= 1             |  8  8  8  0 | 8  8  8  0| 8  8  8  0| 0  0  0  0
 t= 2             |  3  3  3  0 | 3  3  3  0| 3  3  3  0| 0  0  0  0
                                |           |           |
 t= 3  Hi=0,Ci=1  W  8  8  0  0 | 8  8  0  0| 8  8  0  0| 0  0  0  0  H:v C:>
 t= 4             |  8  8  0  0 | 8  8  0  0| 8  8  0  0| 0  0  0  0
 t= 5             |  3  3  0  0 | 3  3  0  0| 3  3  0  0| 0  0  0  0
                                |           |           |
 t= 6  Hi=1,Ci=0  W  8  8  8  0 | 8  8  8  0| 0  0  0  0| 0  0  0  0  H:> C:v
 t= 7             |  8  8  8  0 | 8  8  8  0| 0  0  0  0| 0  0  0  0
 t= 8             |  3  3  3  0 | 3  3  3  0| 0  0  0  0| 0  0  0  0
                                |           |           |
 t= 9  Hi=1,Ci=1  W  8  8  0  0 | 8  8  0  0| 0  0  0  0| 0  0  0  0  H:> C:>
 t=10             |  8  8  0  0 | 8  8  0  0| 0  0  0  0| 0  0  0  0
 t=11             |  3  3  0  0 | 3  3  0  0| 0  0  0  0| 0  0  0  0

Legend: `v` = below (all valid), `>` = boundary (partial), `x` = above (all invalid)
  • Ho=3 열(가장 오른쪽 4개): 모두 0입니다(H 시간 필터가 x이며 항상 닫힘).
  • Co=3 열(4번째마다): 모두 0입니다(C 시간 필터가 x).
  • Co=2 열(H:v C:>): C 시간 필터가 경계이므로 Ci=0인 행만 통과합니다. Co=1과 Co=2를 비교해 보십시오.
  • Ho=2 열(H:> C:v): H 시간 필터가 경계이므로 Hi=0인 행만 통과합니다. Ho=1과 Ho=2를 비교해 보십시오.
  • Ho=2 × Co=2(둘 다 >): 두 경계의 교집합인 (Hi=0, Ci=0) 행만 통과합니다.
  • 유효한 셀 안에서는 packet clipper가 만드는 [8, 8, 3] 톱니 패턴이 항상 나타나며, 이는 Slice와 관계없이 동일합니다.

표현할 수 없는 패턴

다음 배치는 VCG로 표현할 수 없습니다. 각 하위 절에서 배치를 보여 주고 그 이유를 설명합니다.

Slice에 있는 R, 순서가 뒤바뀐 경우

Slice에 R의 하위 표현식이 여러 개 있으면, 바깥쪽 하위 표현식은 안쪽 하위 표현식보다 더 큰 스트라이드를 가져야 합니다. 이 순서를 뒤집으면 Slice별 R 인덱스 범위가 단조롭지 않게 되어, 단일 slice_thres로는 이를 포착할 수 없습니다.

#![allow(unused)]
fn main() {
#![feature(adt_const_params)]
extern crate furiosa_opt_std;
use furiosa_opt_std::prelude::*;
axes![R = 13, X = 32];

// NOT supported: inner sub-expression (/ 2 % 4, stride 2) placed outside major (/ 8, stride 8) in Slice.
// Produces non-monotonic slice validity (S6 valid after S5 partial); VCG cannot express this.
fn reduce_wrong_ordering<'l, const T: Tu>(
    input: VectorBranchTensor<'l, T, i32, m![1], m![1 # 2], m![X, R # 16 / 2 % 4, R # 16 / 8], m![R # 16 % 2], m![1 # 8], Fresh, { stage::VeOrder::IntraFirst }>,
) -> VectorIntraSliceReduceTensor<'l, T, i32, m![1], m![1 # 2], m![X, R # 16 / 2 % 4, R # 16 / 8], m![1], m![1 # 4], Fresh, { stage::VeOrder::IntraFirst }>
{
    input
        .vector_narrow_trim::<m![1 # 4]>()
        //   Slice     = m![X, R # 16 / 2 % 4, R # 16 / 8]
        //   Time      = m![R # 16 % 2]
        //   Packet    = m![1 # 8]
        //   OutTime   = m![1]          (R eliminated)
        //   OutPacket = m![1 # 4]
        .vector_intra_slice_reduce::<R, m![1], m![1 # 4]>(
            IntraSliceReduceOpI32::Min,
        )
}

let mut device = Device::new(Topology { chips: 1, pes: 8 }).unwrap();

let i: VectorBranchTensor<'_, _, i32, m![1], m![1 # 2], m![X, R # 16 / 2 % 4, R # 16 / 8], m![R # 16 % 2], m![1 # 8], Fresh, { stage::VeOrder::IntraFirst }> = VectorBranchTensor::new(&mut device.main, Tensor::zero(), TagMode::Zero);
let _o = reduce_wrong_ordering(i);
}

Slice와 Time에 있는 R, 교차 배치된 경우

R의 하위 표현식이 두 Time 인수 사이에 Slice 인수가 끼도록 분산되면, Slice마다 필요한 유효 시간 단계 수가 달라집니다. 단일 slice_thres로는 이러한 Slice별 차이를 표현할 수 없습니다.

#![allow(unused)]
fn main() {
#![feature(adt_const_params)]
extern crate furiosa_opt_std;
use furiosa_opt_std::prelude::*;
axes![R = 13, X = 64];

// NOT supported: Time-Slice-Time interleave.
// Different slices need different valid step counts (e.g., S2: 3/4, S3: 2/4); single threshold cannot express this.
fn reduce_wrong_interleave<'l, const T: Tu>(
    input: VectorBranchTensor<'l, T, i32, m![1], m![1 # 2], m![X, R # 16 / 2 % 4], m![R # 16 / 8, R # 16 % 2], m![1 # 8], Fresh, { stage::VeOrder::IntraFirst }>,
) -> VectorIntraSliceReduceTensor<'l, T, i32, m![1], m![1 # 2], m![X, R # 16 / 2 % 4], m![1], m![1 # 4], Fresh, { stage::VeOrder::IntraFirst }>
{
    input
        .vector_narrow_trim::<m![1 # 4]>()
        //   Slice     = m![X, R # 16 / 2 % 4]
        //   Time      = m![R # 16 / 8, R # 16 % 2]
        //   Packet    = m![1 # 8]
        //   OutTime   = m![1]          (R eliminated)
        //   OutPacket = m![1 # 4]
        .vector_intra_slice_reduce::<R, m![1], m![1 # 4]>(
            IntraSliceReduceOpI32::Min,
        )
}

let mut device = Device::new(Topology { chips: 1, pes: 8 }).unwrap();

let i: VectorBranchTensor<'_, _, i32, m![1], m![1 # 2], m![X, R # 16 / 2 % 4], m![R # 16 / 8, R # 16 % 2], m![1 # 8], Fresh, { stage::VeOrder::IntraFirst }> = VectorBranchTensor::new(&mut device.main, Tensor::zero(), TagMode::Zero);
let _o = reduce_wrong_interleave(i);
}

Slice와 Time에 있는 R, 과도하게 패딩된 경우

TimeMajor 모드는 PADDED_SIZE - R::SIZE ≤ slice_span을 요구합니다. 과도하게 패딩될 수 있는 R 위치는 최대 slice_span개입니다.

아래 예시에서 R = 14, Slice = m![X, R # 20 % 4](slice_span = 4), Time = m![A, R # 20 / 4]이며 A = 3입니다(따라서 R # 20 / 4로부터 time_span = 5이고, Time::SIZE = A × time_span = 15입니다). 제약 조건은 Time::SIZE가 아니라 time_span에 걸립니다: A처럼 Time에 있는 R이 아닌 축은 R의 인덱스를 바꾸지 않고 사이클을 돌므로 제약 조건에 영향을 주지 않습니다. 올바른 패딩은 R # 16이며(16 - 14 = 2 ≤ slice_span = 4이므로), 이 경우 time_span = 4가 됩니다. R # 20을 사용하면 R이 과도하게 패딩되어 time_span = 5가 되고, 실제 데이터가 없는 Time 반복이 하나 더 추가됩니다. slice_thres 미만의 Slice(Slice 기여분 = 0)에서는 R # 20 / 4 = 4일 때 Sequencer가 재구성한 idx가 4 × 4 = 16에 도달하여 R 인덱스가 16 ≥ R::SIZE가 됩니다. 즉, 도달해서는 안 되는 패딩입니다. CPU 엔진은 바로 이 경우를 잡아냅니다. 과도하게 패딩된 레이아웃에 대해 리덕션을 수행하면, 유효하지 않고 도달할 수 없는 R 인덱스로 실행을 계속하는 대신 panic(out x residue must factor the operand)이 발생합니다.

#![allow(unused)]
fn main() {
#![feature(adt_const_params)]
extern crate furiosa_opt_std;
use furiosa_opt_std::prelude::*;
axes![A = 3, R = 14, X = 64];

fn reduce_time_major_wrong<'l, const T: Tu>(
    input: VectorBranchTensor<'l, T, i32, m![1], m![1 # 2], m![X, R # 20 % 4], m![A, R # 20 / 4], m![1 # 8], Fresh, { stage::VeOrder::IntraFirst }>,
) -> VectorIntraSliceReduceTensor<'l, T, i32, m![1], m![1 # 2], m![X, R # 20 % 4], m![A], m![1 # 4], Fresh, { stage::VeOrder::IntraFirst }>
{
    input
        .vector_narrow_trim::<m![1 # 4]>()
        //   Slice     = m![X, R # 20 % 4]
        //   Time      = m![A, R # 20 / 4]   (A is non-R; time_span = 5 from R # 20 / 4)
        //   Packet    = m![1 # 8]
        //   OutTime   = m![A]              (R eliminated; A survives)
        //   OutPacket = m![1 # 4]
        // NOT supported: R # 20 over-pads (20 - 14 = 6 > slice_span = 4).
        // time_span = 5 > 4. Below-group slices include time steps where R # 20 / 4 = 4 (R = 16 padding).
        .vector_intra_slice_reduce::<R, m![A], m![1 # 4]>(
            IntraSliceReduceOpI32::AddSat,
        )
}

let mut device = Device::new(Topology { chips: 1, pes: 8 }).unwrap();

let i: VectorBranchTensor<'_, _, i32, m![1], m![1 # 2], m![X, R # 20 % 4], m![A, R # 20 / 4], m![1 # 8], Fresh, { stage::VeOrder::IntraFirst }> = VectorBranchTensor::new(&mut device.main, Tensor::zero(), TagMode::Zero);
let _o = reduce_time_major_wrong(i);
}

Packet에 있는 R, 복잡한 경우

packet clipper는 Packet = m![R # PADDED_SIZE % packet_span # 8]을 요구합니다. 다른 형태는 fn valid_size()가 의존하는 연속 접두사 속성을 깨뜨립니다.

첫 번째 예제는 R의 상위 부분을 Packet에 배치하므로(R # 24 % 8 대신 R # 24 / 8 형식), 접두부가 R의 다음 연속 구간을 담지 않고 서로 다른 R 스트라이드의 위치를 섞게 됩니다.

#![allow(unused)]
fn main() {
#![feature(adt_const_params)]
extern crate furiosa_opt_std;
use furiosa_opt_std::prelude::*;
axes![A = 8, R = 19, X = 64];

fn reduce_wrong_packet_outer<'l, const T: Tu>(
    input: VectorBranchTensor<'l, T, f32, m![1], m![1 # 2], m![X, A / 2], m![R # 24 % 8], m![R # 24 / 8 # 8], Fresh, { stage::VeOrder::IntraFirst }>,
) -> VectorIntraSliceReduceTensor<'l, T, f32, m![1], m![1 # 2], m![X, A / 2], m![1], m![1 # 4], Fresh, { stage::VeOrder::IntraFirst }>
{
    input
        .vector_narrow_trim::<m![R # 24 / 8 # 4]>()
        //   Slice     = m![X, A / 2]
        //   Time      = m![R # 24 % 8]
        //   Packet    = m![R # 24 / 8 # 8]   (NOT supported: major R in Packet)
        //   OutTime   = m![1]          (R eliminated)
        //   OutPacket = m![1 # 4]
        .vector_intra_slice_reduce::<R, m![1], m![1 # 4]>(
            IntraSliceReduceOpF32::Add,
        )
}

let mut device = Device::new(Topology { chips: 1, pes: 8 }).unwrap();

let i: VectorBranchTensor<'_, _, f32, m![1], m![1 # 2], m![X, A / 2], m![R # 24 % 8], m![R # 24 / 8 # 8], Fresh, { stage::VeOrder::IntraFirst }> = VectorBranchTensor::new(&mut device.main, Tensor::zero(), TagMode::Zero);
let _o = reduce_wrong_packet_outer(i);
}

두 번째 예시는 R이 다른 축 A와 Packet을 공유하므로, 접두사 기반 개수 계산에서 패딩으로 취급하는 위치를 A의 요소가 차지하게 됩니다.

#![allow(unused)]
fn main() {
#![feature(adt_const_params)]
extern crate furiosa_opt_std;
use furiosa_opt_std::prelude::*;
axes![A = 4, R = 19, X = 256];

fn reduce_wrong_mixed_packet<'l, const T: Tu>(
    input: VectorBranchTensor<'l, T, f32, m![1], m![1 # 2], m![X], m![R # 24 / 2], m![R # 24 % 2, A], Fresh, { stage::VeOrder::IntraFirst }>,
) -> VectorIntraSliceReduceTensor<'l, T, f32, m![1], m![1 # 2], m![X], m![1], m![A], Fresh, { stage::VeOrder::IntraFirst }>
{
    input
        .vector_narrow_split::<m![R # 24], m![A]>()
        //   at Vector Init:
        //   Slice     = m![X]
        //   Time      = m![R # 24 / 2]
        //   Packet    = m![R # 24 % 2, A]   (NOT supported: A shares Packet with R)
        //   OutTime   = m![1]          (R eliminated; A silently excluded by prefix valid_size)
        //   OutPacket = m![A]
        .vector_intra_slice_reduce::<R, m![1], m![A]>(
            IntraSliceReduceOpF32::Add,
        )
}

let mut device = Device::new(Topology { chips: 1, pes: 8 }).unwrap();
let i: VectorBranchTensor<'_, _, f32, m![1], m![1 # 2], m![X], m![R # 24 / 2], m![R # 24 % 2, A], Fresh, { stage::VeOrder::IntraFirst }> = VectorBranchTensor::new(&mut device.main, Tensor::zero(), TagMode::Zero);
let _o = reduce_wrong_mixed_packet(i);
}

Slice와 Packet에 있는 R

R이 Slice와 Packet으로 나뉘어 분할됩니다. 이것을 왜 표현할 수 없는지 알아보기 위해, R = 2045(R # 2048로 패딩)를 Slice = m![R # 2048 / 8](256개 Slice)와 Packet = m![R # 2048 % 8](8요소 플릿)로 분할하는 경우를 생각해 봅시다. 유일한 시간 단계인 t = 0에서 fn valid_size는 모든 Slice에 대해 clamp(2045 - 0, 0, 8) = 8을 계산합니다. 하지만 Slice 255의 플릿은 R 인덱스 2040–2047을 담고 있으며, 그중 실제 데이터는 다섯 개뿐입니다:

t = 0, slice = 255일 때:

플릿 위치01234567
R 인덱스20402041204220432044204520462047
유효 여부예예예예예[pad][pad][pad]

Slice 0–254에는 valid_size = 8이 필요한 것이 맞지만, Slice 255에는 valid_size = 5가 필요합니다. fn valid_size(t)는 주어진 t에 대해 하나의 값만 반환할 수 있으므로, 어떤 단일 설정으로도 동작하지 않습니다.

R::SIZE % packet_span = 0인 퇴화 하위 사례(모든 패킷이 가득 차 있거나 비어 있는 경우)는 Slice 단독 사례로 귀결되며 지원됩니다.

#![allow(unused)]
fn main() {
#![feature(adt_const_params)]
extern crate furiosa_opt_std;
use furiosa_opt_std::prelude::*;
axes![R = 2045];

// NOT supported: R = 2045 split across Slice (/ 8, 256 slices) and Packet (% 8).
// Slices 0-254 need valid_size = 8; slice 255 needs valid_size = 5. fn valid_size(t) cannot vary by slice.
fn reduce_wrong_slice_packet<'l, const T: Tu>(
    input: VectorBranchTensor<'l, T, i32, m![1], m![1 # 2], m![R # 2048 / 8], m![1], m![R # 2048 % 8], Fresh, { stage::VeOrder::IntraFirst }>,
) -> VectorIntraSliceReduceTensor<'l, T, i32, m![1], m![1 # 2], m![R # 2048 / 8], m![1], m![1 # 4], Fresh, { stage::VeOrder::IntraFirst }>
{
    input
        .vector_narrow_trim::<m![R # 2048 % 4]>()
        //   Slice     = m![R # 2048 / 8]
        //   Time      = m![1]
        //   Packet    = m![R # 2048 % 8]
        //   OutTime   = m![1]          (R eliminated)
        //   OutPacket = m![1 # 4]
        .vector_intra_slice_reduce::<R, m![1], m![1 # 4]>(
            IntraSliceReduceOpI32::AddSat,
        )
}

let mut device = Device::new(Topology { chips: 1, pes: 8 }).unwrap();
let i: VectorBranchTensor<'_, _, i32, m![1], m![1 # 2], m![R # 2048 / 8], m![1], m![R # 2048 % 8], Fresh, { stage::VeOrder::IntraFirst }> = VectorBranchTensor::new(&mut device.main, Tensor::zero(), TagMode::Zero);
let _o = reduce_wrong_slice_packet(i);
}

제약 조건

구성 요소용량
packet clipper인스턴스 1개
시간 필터인스턴스 3개
시간 필터 / packet clipper별 Sequencer 항목8(Sequencer 참조)

유효성 추적이 필요한 패딩된 축은 각각 시간 필터 하나 또는 packet clipper를 차지합니다. 한 번의 호출에서 최대 4개의 축을 추적할 수 있습니다(packet clipper 1개 + 시간 필터 3개). 패딩되지 않은 축에는 슬롯이 필요하지 않습니다(slice_mask=0, slice_thres=1은 시간 필터를 비활성화하여 항상 true를 반환하게 합니다).

Intra-Slice Reduce는 단일 REDUCE_LABEL만 받으므로, “다중 축“은 여러 리덕션을 동시에 수행한다는 뜻이 아니라 하나의 리덕션 축 R에 패딩된 비리덕션 축이 추가로 더해진다는 뜻입니다.

다운스트림 4-Way 연산

VCG는 좁히기가 일어나기 전에 8-way 플릿마다 valid_size를 생성합니다. 다운스트림 Narrow 단계는 각 8-way 플릿을 4-way 절반 두 개로 나누며, 좁히기를 적용하는 방식에 따라 각 valid_size가 두 절반에 어떻게 나뉘는지가 결정됩니다.

연산입력출력Valid Count 변환
vector_narrow_split8-way 플릿(valid_size = v)4-way 플릿 두 개low: min(v, 4), high: max(v - 4, 0)
vector_narrow_trim8-way 플릿(valid_size = v)4-way 플릿 한 개min(v, 4)
vector_widen_concat4-way 플릿 두 개(v_low, v_high)8-way 플릿v_low + v_high
vector_widen_pad4-way 플릿8-way 플릿변경 없음

vector_narrow_split과 vector_widen_concat은 접두사 속성을 보존합니다. vector_narrow_trim의 경우 매핑이 v <= 4임을 정적으로 보장해야 합니다. 상위 4개 요소가 유효할 수 있다면 이를 잘라낼 때 데이터가 손실됩니다.

원문 © FuriosaAI · Programming Tensor Contraction Processors · Apache License 2.0 · NOTICE
yeokja 한국어 번역 · Anthropic 사의 claude-sonnet-5 모델을 활용하여 번역되었으며 학습을 모두 비허용한 상태로 작업하였습니다 · 이 문서는 원문을 수정한 비공식 번역본이며 Apache License 2.0으로 제공합니다.