1# Copyright 2026 Huawei Technologies Co., Ltd
2#
3# Licensed under the Apache License, Version 2.0 (the "License");
4# you may not use this file except in compliance with the License.
5# You may obtain a copy of the License at
6#
7# http://www.apache.org/licenses/LICENSE-2.0
8#
9# Unless required by applicable law or agreed to in writing, software
10# distributed under the License is distributed on an "AS IS" BASIS,
11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12# See the License for the specific language governing permissions and
13# limitations under the License.
14# ============================================================================
15# Copyright (c) 2023-2025, Songlin Yang, Yu Zhang
16
17# pylint: disable=missing-public-type-hints,missing-public-docstring,disallowed-name
18# pylint: disable=useless-return,unused-argument,no-else-return,invalid-name
19# pylint: disable=missing-module-docstring,missing-function-docstring
20
21from typing import Optional
22
23import torch
24import triton
25import triton.language as tl
26
27from .utils import prepare_chunk_indices
28
29
30@triton.heuristics({
31 'HAS_SCALE': lambda args: args['scale'] is not None,
32 'IS_VARLEN': lambda args: args['cu_seqlens'] is not None
33})
34@triton.jit(do_not_specialize=['T'])
35def chunk_local_cumsum_scalar_kernel(
36 s,
37 o,
38 scale,
39 cu_seqlens,
40 chunk_indices,
41 T,
42 B: tl.constexpr,
43 H: tl.constexpr,
44 BLOCK_T: tl.constexpr,
45 REVERSE: tl.constexpr,
46 HAS_SCALE: tl.constexpr,
47 IS_VARLEN: tl.constexpr,
48 HEAD_FIRST: tl.constexpr,
49 CHUNK_SIZE: tl.constexpr = 64,
50):
51 i_block, i_b = tl.program_id(0), tl.program_id(1)
52 N_CHUNKS: tl.constexpr = BLOCK_T // CHUNK_SIZE
53
54 if IS_VARLEN:
55 i_s, i_block = tl.load(chunk_indices + i_block * 2).to(tl.int32), tl.load(
56 chunk_indices + i_block * 2 + 1
57 ).to(tl.int32)
58
59 bos, eos = tl.load(cu_seqlens + i_s).to(tl.int32), tl.load(
60 cu_seqlens + i_s + 1
61 ).to(tl.int32)
62 T = eos - bos
63 else:
64 bos, eos = i_b * T, i_b * T + T
65
66 ptr_s = tl.make_block_ptr(
67 s + bos * H, (T, H), (H, 1), (i_block * BLOCK_T, 0), (BLOCK_T, H), (1, 0)
68 )
69 ptr_o = tl.make_block_ptr(
70 o + bos * H, (T, H), (H, 1), (i_block * BLOCK_T, 0), (BLOCK_T, H), (1, 0)
71 )
72 b_s = tl.load(ptr_s, boundary_check=(0,)).to(tl.float32)
73 b_s = tl.reshape(b_s, (N_CHUNKS, CHUNK_SIZE, H))
74 b_s = tl.trans(b_s, (1, 0, 2))
75 b_o = tl.cumsum(b_s, axis=0)
76 if REVERSE:
77 b_z = tl.sum(b_s, axis=0)
78 b_o = -b_o + b_z[None] + b_s
79 if HAS_SCALE:
80 b_o *= scale
81 b_o = tl.trans(b_o, (1, 0, 2))
82 b_o = tl.reshape(b_o, (BLOCK_T, H))
83
84 tl.store(ptr_o, b_o.to(ptr_o.dtype.element_ty), boundary_check=(0,))
85 return
86
87
88def chunk_local_cumsum_scalar(
89 g: torch.Tensor,
90 chunk_size: int,
91 reverse: bool = False,
92 scale: float = None,
93 cu_seqlens: Optional[torch.Tensor] = None,
94 head_first: bool = False,
95 output_dtype: Optional[torch.dtype] = torch.float
96) -> torch.Tensor:
97
98 B, T, H = g.shape
99 if chunk_size != 2 ** (chunk_size.bit_length() - 1):
100 raise ValueError(
101 f"chunk_size must be a power of 2, chunk_size is {chunk_size}"
102 )
103 # We adjust the tiling strategy to prevent overflow in in backward passes and context parallel scenarios
104 # while maximizing UB utilization where possible.
105 # The tiling strategy is as follows:
106 # 1. BT must be greater than or equal to chunk_size.
107 # 2. UB estimation varies directly with H.
108 # 3. BT in reverse mode is smaller than in forward mode.
109 BT = max(chunk_size, triton.next_power_of_2((1 << 11 if reverse else 1 << 12) // H))
110 chunk_indices = prepare_chunk_indices(cu_seqlens, BT) if cu_seqlens is not None else None
111 NT = triton.cdiv(T, BT) if cu_seqlens is None else len(chunk_indices)
112 g_org, g = g, torch.empty_like(g, dtype=output_dtype or g.dtype)
113 grid = (NT, B)
114 chunk_local_cumsum_scalar_kernel[grid](
115 s=g_org,
116 o=g,
117 scale=scale,
118 cu_seqlens=cu_seqlens,
119 chunk_indices=chunk_indices,
120 T=T,
121 B=B,
122 H=H,
123 BLOCK_T=BT,
124 HEAD_FIRST=head_first,
125 REVERSE=reverse,
126 CHUNK_SIZE=chunk_size,
127 )
128 return g
129
130
131def chunk_local_cumsum(
132 g: torch.Tensor,
133 chunk_size: int,
134 reverse: bool = False,
135 scale: float = None,
136 cu_seqlens: Optional[torch.Tensor] = None,
137 head_first: bool = False,
138 output_dtype: Optional[torch.dtype] = torch.float,
139 **kwargs
140) -> torch.Tensor:
141 if cu_seqlens is not None:
142 if g.shape[0] != 1:
143 raise ValueError(
144 "Only batch size 1 is supported when cu_seqlens are provided, "
145 f"current size is {g.shape[0]}"
146 )
147 if len(g.shape) == 3:
148 return chunk_local_cumsum_scalar(
149 g=g,
150 chunk_size=chunk_size,
151 reverse=reverse,
152 scale=scale,
153 cu_seqlens=cu_seqlens,
154 head_first=head_first,
155 output_dtype=output_dtype
156 )
157 else:
158 raise ValueError(
159 f"Unsupported input shape {g.shape}, "
160 f"which should be (B, T, H, D) if `head_first=False` "
161 f"or (B, H, T, D) otherwise"
162 )